Logical Methods: The Art of Thinking Abstractly and Mathematically

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