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
