Chapter 1 The Logic of Compound Statements
  1.1 Logical Form and Logical Equivalence
   Statements; Compound Statements; Truth Values; Evaluating the Truth of More General Compound Statements; Logical Equivalence; Tautologies and Contradictions; Summary of Logical Equivalences
  1.2 Conditional Statements
  1.3 Valid and Invalid Arguments
   Modus Ponens and Modus Tollens; Additional Valid Argument Forms: Rules of Inference; Fallacies; Contradictions and Valid Arguments; Summary of Rules of Inference
  1.4 Application: Digital Logic Circuits
  1.5 Application: Number Systems and Circuits for Addition
 Chapter 2 The Logic of Quantified Statements
  2.1 Introduction to Predicates and Quantified Statements
   The Universal Quantifier. ●; The Existential Quantifier. ●; Formal Versus Informal Language; Universal Conditional Statements; Equivalent Forms of the Universal and Existential Statements; Implicit Quantification; Tarski's World
  2.2 Introduction to Predicates and Quantified Statements
   Negations of Quantified Statements; Negations of Universal Conditional Statements; The Relation among ●,● , a, and v; Vacuous Truth of Universal Statements; Variants of Universal Conditional Statements; Necessary and Sufficient Conditions, Only If
  2.3 Statements Containing Multiple Quantifiers
   Translating from Informal to Formal Language; Ambiguous Language; Negations of Multiply-Quantified Statements; Order of Quantifiers; Formal Logical Notation; Prolog
  2.4 Arguments with Quantified Statements
 Chapter 3 Elementary Number Theory and Methods of Proof
  3.1 Direct Proof and Counterexample Ⅰ: Introduction
  3.2 Direct Proof and Counterexample Ⅱ: Rational Numbers
   More on Generalizing from the Generic Particular, Proving Properties of Rational Numbers; Deriving New Mathematics from Old
  3.3 Direct Proof and Counterexample Ⅲ: Divisibility
   Proving Properties of Divisibility; Counterexamples and Divisibility; The Unique Factorization Theorem
  3.4 Direct Proof and Counterexample Ⅳ: Division into Cases and the Quotient-Remainder Theorem
   Discussion of the Quotient-Remainder Theorem and Examples; div and mod; Alternative Representations of Integers and Applications to Number Theory
  3.5 Direct Proof and Counterexample Ⅴ: Floor and Ceiling
   Definition and Basic Properties; The Floor of n /2
  3.6 Indirect Argument: Contradiction and Contraposition
   Proof by Contradiction; Argument by Contraposition; Relation between Proof by Contradiction and Proof by Contraposition; Proof as a Problem-Solving Tool
  3.7 Two Classical Theorems
   The Irrationality of ●2; The Infinitude of the Set of Prime Numbers; When to Use Indirect Proof; Open Questions in Number Theory
  3.8 Application: Algorithms
   An Algorithmic Language; A Notation for Algorithms; Trace Tables; The Division Algorithm; The Euclidean Algorithm
 Chapter 4 Sequences and Mathematical Induction
  4.1 Sequences
  4.2 Mathematical Induction Ⅰ
   Principle of Mathematical Induction; Sum of the First n Integers; Sum of a Geometric Sequence
  4.3 Mathematical Induction Ⅱ
   Comparison of Mathematical Induction and Inductive Reasoning; Proving Divisibility Properties; Proving Inequalities
  4.4 Strong Mathematical Induction and the Well-Ordering Principle
   The Principle of Strong Mathematical Induction; Binary Representation of Integers; The Well-Ordering Principle for the Integers
  4.5 Application: Correctness of Algorithms
   Assertions; Loop Invariants; Correctness of the Division Algorithm; Correctness of the Euclidean Algorithm
 Chapter 5 Set Theory
  5.1 Basic Definitions of Set Theory
   Subsets; Set Equality; Operations on Sets; Venn Diagrams; The Empty Set; Partitions of Sets; Power Sets; Cartesian Products; An Algorithm to Check Whether One Set Is a Subset of Another (Optional)
  5.2 Properties of Sets
   Set Identities; Proving Set Identities; Proving That a Set Is the Empty Set
  5.3 Disproofs, Algebraic Proofs, and Boolean Algebras
   Disproving an Alleged Set Property; Problem-Solving Strategy; The Number of Subsets of a Set; "Algebraic" Proofs of Set Identities; Boolean Algebras
  5.4 Russell's Paradox and the Halting Problem
   Description of Russell's Paradox; The Halting Problem
 Chapter 6 Counting and Probability
  6.1 Introduction
   Definition of Sample Space and Event; Probability in the Equally Likely Case; Counting the Elements of Lists, Sublists, and One-Dimensional Arrays
  6.2 Possibility Trees and the Multiplication Rule
   Possibility Trees; The Multiplication Rule; When the Multiplication Rule Is Difficult or Impossible to Apply; Permutations; Permutations of Selected Elements
  6.3 Counting Elements of Disjoint Sets: The Addition Rule
   The Addition Rule; The Difference Rule; The Inclusion/Exclusion Rule
  6.4 Counting Subsets of a Set: Combinations
   r-Combinations; Ordered and Unordered Selections; Relation between Permutations and Combinations; Permutation of a Set with Repeated Elements; Some Advice about Counting
  6.5 r-Combinations with Repetition Allowed
   Multisets and How to Count Them; Which Formula to Use?
  6.6 The Algebra of Combinations
   Combinatorial Formulas; Pascal's Triangle; Algebraic and Combinatorial Proofs of Pascal's Formula
  6.7 The Binomial Theorem
   Statement of the Theorem; Algebraic and Combinatorial Proofs; Applications
  6.8 Probability Axioms and Expected Value
   Probability Axioms; Deriving Additional Probability Formulas; Expected Value
  6.9 Conditional Probability, Bayes' Formula, and Independent Events
   Conditional Probability; Bayes' Theorem; Independent Events
 Chapter 7 Functions
  7.1 Functions Defined on General Sets
   Definition of Function; Arrow Diagrams; Function Machines; Examples of Functions; Boolean Functions; Checking Whether a Function Is Well Defined
  7.2 One-to-One and Onto, Inverse Functions
   One-to-One Functions: One-to-One Functions on Infinite Sets; Application: Hash Functions: Onto Functions; Onto Functions on Infinite Sets; Properties of Exponential and Logarithmic Functions: One-to-One Correspondences: Inverse Functions
  7.3 Application: The Pigeonhole Principle
   Statement and Discussion of the Principle; Applications; Decimal Expansions of Fractions; Generalized Pigeonhole Principle: Proof of the Pigeonhole Principle
  7.4 Composition of Functions
   Definition and Examples; Composition of One-to-One Functions; Composition of Onto Functions
  7.5 Cardinality with Applications to Computability
   Definition of Cardinal Equivalence; Countable Sets; The Search for Larger Infinities: The Cantor Diagonalization Process; Application: Cardinality and Computability
 Chapter 8 Recursion
  8.1 Recursively Defined Sequences
   Definition of Recurrence Relation; Examples of Recursively Defined Sequences; The Number of Partitions of a Set Into r Subsets
  8.2 Solving Recurrence Relations by Iteration
   The Method of Iteration; Using Formulas to Simplify Solutions Obtained by Iteration: Checking the Correctness of a Formula by Mathematical Induction: Discovering That an Explicit Formula Is Incorrect
  8.3 Second-Order Linear Homogenous Recurrence Relations with Constant Coefficients
   Derivation of Technique for Solving These Relations; The Distinct-Roots Case; The Single-Root Case
  8.4 General Recursive Definitions
   Recursively Defined Sets; Proving Properties about Recursively Defined Sets: Recursive Definitions of Sum, Product, Union, and Intersection: Recursive Functions
 Chapter 9 The Efficiency of Algorithms
  9.1 Real-Valued Functions of a Real Variable and Their Graphs
   Graph of a Function; Power Functions; The Floor Function: Graphing Functions Defined on Sets of Integers: Graph of a Multiple of a Function; Increasing and Decreasing Functions
  9.2 O, Ω, and ● Notations
   Definition and General Properties of O-, Ω-, and ●-Notations; Orders of Power Functions; Orders of Polynomial Functions; Orders of Functions of Integer Variables; Extension to Functions Composed of Rational Power Functions
  9.3 Application: Efficiency of Algorithms I
   Time Efficiency of an Algorithm; Computing Orders of Simple Algorithms; The Sequential Search Algorithm; The Insertion Sort Algorithm
  9.4 Exponential and Logarithmic Functions: Graphs and Orders
   Graphs of Exponential and Logarithmic Functions; Application: Number of Bits Needed to Represent an Integer in Binary Notation; Application: Using Logarithms to Solve Recurrence Relations; Exponential and Logarithmic Orders
  9.5 Application: Efficiency of Algorithms II
   Divide-and-Conquer Algorithms; The Efficiency of the Binary Search Algorithm; Merge Sort; Tractable and Intractable Problems; A Final Remark on Algorithm Efficiency
 Chapter 10 Relations
  10.1 Relations on Sets
   Definition of Binary Relation; Arrow Diagram of a Relation; Relations and Functions; The Inverse of a Relation; Directed Graph of a Relation; N-ary Relations and Relational Databases
  10.2 Reflexivity, Symmetry, and Transitivity
   Reflexive, Symmetric, and Transitive Properties; The Transitive Closure of a Relation; Properties of Relations on Infinite Sets
  10.3 Equivalence Relations
   The Relation Induced by a Partition; Definition of an Equivalence Relation: Equivalence Classes of an Equivalence Relation
  10.4 Modular Arithmetic with Applications to Cryptography
   Properties of Congruence Modulo n; Modular Arithmetic: Finding an Inverse Modulo n; Euclid's Lemma; Fermat's Little Theorem and the Chinese Remainder Theorem; Why Does the RSA Cipher Work?
  10.5 Partial Order Relations
   Antisymmetry; Partial Order Relations; Lexicographic Order; Hasse Diagrams: Partially and Totally Ordered Sets; Topological Sorting; An Application; PERT and CPM
 Chapter 11 Graphs and Trees
  11.1 Graphs: An Introduction
   Basic Terminology and Examples: Special Graphs; The Concept of Degree
  11.2 Paths and Circuits
   Definitions; Euler Circuits: Hamiltonian Circuits
  11.3 Matrix Representations of Graphs
   Matrices: Matrices and Directed Graphs; Matrices and (Undirected) Graphs; Matrices and Connected Components: Matrix Multiplication; Counting Walks of Length N
  11.4 Isomorphisms of Graphs
   Definition of Graph Isomorphism and Examples; Isomorphic Invariants; Graph Isomorphism for Simple Graphs
  11.5 Trees
   Definition and Examples of Trees; Characterizing Trees; Rooted Trees; Binary Trees
  11.6 Spanning Trees
   Definition of a Spanning Tree; Minimum Spanning Trees; Kruskal's Algorithm; Prim's Algorithm
 Chapter 12 Regular Expressions and Finite-State Automata
  12.1 Formal Languages and Regular Expressions
   Definitions and Examples of Formal Languages and Regular Expressions; Practical Uses of Regular Expressions
  12.2 Finite-State Automata
  12.3 Simplifying Finite-State Automata
   *-Equivalence of States; k -Equivalence of States; Finding the *-Equivalence Classes: The Quotient Automaton: Constructing the Quotient Automaton: Equivalent Automata
 Appendix A Properties of the Real Numbers
 Appendix B Solutions and Hints to Selected Exercises