Logical Methods: The Art of Thinking Abstractly and Mathematically

Description

Many believe mathematics is only about calculations, formulas, numbers, and strange letters. But mathematics is much more than just crunching numbers or manipulating symbols. Mathematics is about discovering patterns, uncovering hidden structures, finding counterexamples, and thinking logically. Mathematics is a way of thinking. It is an activity that is both highly creative and challenging. This book offers an introduction to mathematical reasoning for beginning university or college students, providing a solid foundation for further study in mathematics, computer science, and related disciplines. Written in a manner that directly conveys the sense of excitement and discovery at the heart of doing science, its 25 short and visually appealing chapters cover the basics of set theory, logic, proof methods, combinatorics, graph theory, and much more. In the book you will, among other things, find answers to: What is a proof? What is a counterexample? What does it mean to say that something follows logically from a set of premises? What does it mean to abstract over something? How can knowledge and information be represented and used in calculations? What is the connection between Morse code and Fibonacci numbers? Why could it take billions of years to solve Hanoi's Tower? Logical Methods is especially appropriate for students encountering such concepts for the very first time. Designed to ease the transition to a university or college level study of mathematics or computer science, it also provides an accessible and fascinating gateway to logical thinking for students of all disciplines. Contents Preface Chapter 0 The Art of Thinking Abstractly and Mathematically Abstraction Reasoning About Truth Assumptions Language Definitions Proofs Problem Solving and Pólya’s Heuristics (1) Understand the Problem (2) Make a Plan (3) Execute the Plan (4) Look Over and Check Chapter 1 Basic Set Theory First Steps What Is a Set? Building Sets Operations on Sets Visualizing Sets Comparing Sets Tuples and Products Multisets Exercises Chapter 2 Propositional Logic What Follows from What? What Is a Proposition? Atomic and Composite Propositions Atomic and Composite Formulas Necessary and Sufficient Conditions Parentheses, Precedence Rules, and Practical Abbreviations Exercises Chapter 3 Semantics for Propositional Logic Interpretation of Formulas Valuations and Truth Tables Properties of Implication Logical Equivalence A Study in What Is Equivalent Exercises Chapter 4 Concepts in Propositional Logic Logical Consequence Valid Arguments Satisfiability and Falsifiability Tautology/Validity and Contradiction Symbols for Truth Values Connections Between Concepts Independence of Formulas Deciding Whether a Formula Is Valid or Satisfiable Exercises Chapter 5 Proofs, Conjectures, and Counterexamples Proofs Conjectures Thinking from Assumptions Direct Proofs Existence Proofs Proofs by Cases Proofs of Universal Statements Counterexamples Contrapositive Proofs Proofs by Contradiction Constructive Versus Nonconstructive Proofs Proofs of Falsity Exercises Chapter 6 Relations Abstraction over Relations Some Special Relations The Universe of Relations Reflexivity, Symmetry, and Transitivity Antisymmetry and Irreflexivity Orders, Partial and Total Examples Exercises Chapter 7 Functions What Is a Function? Injective, Surjective, and Bijective Functions Functions with Multiple Arguments The Universe of Functions Composition of Functions Operations Functions as Objects Partial Functions Exercises Chapter 8 A Little More Set Theory Set Theory Set Complement and the Universal Set Computing with Venn Diagrams Venn Diagrams for Multiple Sets Power Sets Infinity Cardinality Countability Uncountability Exercises Chapter 9 Closures and Inductively Defined Sets Defining Sets Step by Step Closures of Sets Closures of Binary Relations Inductively Defined Sets Sets of Numbers Propositional Formulas Lists and Binary Trees Programming Languages Alphabets, Characters, Strings, and Formal Languages Bit Strings Two Interesting Constructions Exercises Chapter 10 Recursively Defined Functions A Powerful Tool The Triangular Numbers Induction and Recursion Form, Content, and Placeholders Replacing Equals by Equals Recursively Defined Functions Number Sets Bit Strings Propositional Formulas Lists Binary Trees Formal Languages Recursion and Programming Exercises Chapter 11 Mathematical Induction A Mathematical Experiment Mathematical Induction Back to the Experiment A Geometric Proof of the Same Claim What Really Goes On in an Induction Proof? Trominoes Properties of Recursively Defined Functions The Tower of Hanoi More Summing of Numbers Reasoning and Strong Induction Exercises Chapter 12 Structural Induction Structural Induction Structural Induction on Bit Strings Structural Induction on Propositional Formulas Structural Induction on Lists Structural Induction on Binary Trees Exercises Chapter 13 First-Order Languages Languages with Greater Expressibility First-Order Languages and Signatures First-Order Terms Prefix, Infix, and Postfix Notation First-Order Formulas Precedence Rules Exercises Chapter 14 Representation of Quantified Statements Representation of Predicates Syntactic Properties of Free Variables The Art of Expressing Yourself with a First-Order Language Choice of First-Order Language Repeating Patterns in Representations Repetition of First-Order Languages Expressibility and Complexity Exercises Chapter 15 Interpretation in Models Semantics for First-Order Logic Definition of Model Interpretation of Terms Interpretation of Atomic Formulas Substitutions Interpretation of Composite Formulas Satisfiability and Validity of First-Order Formulas First-Order Languages and Equality A Little Repetition Exercises Chapter 16 Reasoning About Models Logical Equivalence and Logical Consequence The Interaction Between Quantifiers and Connectives First-Order Logic and Modeling Theories and Axiomatizations Some Technical Special Cases Prenex Normal Form and More Equivalences Final Comments Exercises Chapter 17 Abstraction with Equivalences and Partitions Abstracting with Equivalence Relations Equivalence Classes Partitions The Connection Between Equivalence Classes and Partitions Exercises Chapter 18 Combinatorics The Art of Counting The Inclusion–Exclusion Principle The Multiplication Principle Permutations Ordered Selection Combinations Repetitions and Overcounting Exercises Chapter 19 A Little More Combinatorics Pólya’s Example and Pascal’s Triangle Binomial Coefficients Systematization of Counting Problems Exercises Chapter 20 A Bit of Abstract Algebra Abstract Algebra Inverse Relations and Functions Some Properties of Operations Some Elements with Special Properties Groups Exercises Chapter 21 Graph Theory Graphs Are Everywhere What Is a Graph? Graphs as Representations Definitions and Concepts About Graphs Properties of Graphs Two Graph-Theoretic Results Isomorphisms Exercises Chapter 22 Walks in Graphs The Bridges of Königsberg Paths and Circuits Eulerian Trails and Circuits Hamiltonian Paths and Cycles Final Comments Exercises Chapter 23 Formal Languages and Grammars Formal Language Theory Operations on Languages Regular Languages Regular Expressions Interpretation of Regular Expressions Deterministic Automata Automata and Regular Languages Nondeterministic Automata Formal Grammars Exercises Chapter 24 Natural Deduction Logical Calculi: From Semantics to Syntax Inference Rules of Natural Deduction Closing of Assumptions Derivations and Proofs Negation and RAA The Rules for Disjunction Soundness, Completeness, and Consistency Exercises The Road Ahead The Classics Introductory Books on Mathematical Thinking Introductory Books on Logic Introductory Books on Discrete Mathematics Popular Science, Recreational Mathematics, and Other Books Index Symbols