Preface The MathZone Companion Website To the Student 1 The Foundations: Logic and Proofs 1.1 Propositional Logic 1.2 Propositional Equivalences 1.3 Predicates and Quantifiers 1.4 Nested Quantifiers 1.5 Rules of Inference 1.6 Introduction to Proofs 1.7 Proof Methods and Strategy End-of-Chapter Material 2 Basic Structures: Sets, Functions, Sequences and Sums 2.

1 Sets 2.2 Set Operations 2.3 Functions 2.4 Sequences and Summations End-of-Chapter Material 3 The Fundamentals: Algorithms, the Integers, and Matrices 3.1 Algorithms 3.2 The Growth of Functions 3.3 Complexity of Algorithms 3.4 The Integers and Division 3.

5 Primes and Greatest Common Divisors 3.6 Integers and Algorithms 3.7 Applications of Number Theory 3.8 Matrices End-of-Chapter Material 4 Induction and Recursion 4.1 Mathematical Induction 4.2 Strong Induction and Well-Ordering 4.3 Recursive Definitions and Structural Induction 4.4 Recursive Algorithms 4.

5 Program Correctness End-of-Chapter Material 5 Counting 5.1 The Basics of Counting 5.2 The Pigeonhole Principle 5.3 Permutations and Combinations 5.4 Binomial Coefficients 5.5 Generalized Permutations and Combinations 5.6 Generating Permutations and Combinations End-of-Chapter Material 6 Discrete Probability 6.1 An Introduction to Discrete Probability 6.

2 Probability Theory 6.3 Bayes' Theorem 6.4 Expected Value and Variance End-of-Chapter Material 7 Advanced Counting Techniques 7.1 Recurrence Relations 7.2 Solving Linear Recurrence Relations 7.3 Divide-and-Conquer Algorithms and Recurrence elations 7.4 Generating Functions 7.5 Inclusion-Exclusion 7.

6 Applications of Inclusion-Exclusion End-of-Chapter Material 8 Relations 8.1 Relations and Their Properties 8.2n-ary Relations and Their Applications 8.3 Representing Relations 8.4 Closures of Relations 8.5 Equivalence Relations 8.6 Partial Orderings End-of-Chapter Material 9 Graphs 9.1 Graphs and Graph Models 9.

2 Graph Terminology and Special Types of Graphs 9.3 Representing Graphs and Graph Isomorphism 9.4 Connectivity 9.5 Euler and Hamilton Paths 9.6 Shortest-Path Problems 9.7 Planar Graphs 9.8 Graph Coloring End-of-Chapter Material 10 Trees 10.1 Introduction to Trees 10.

2 Applications of Trees 10.3 Tree Traversal 10.4 Spanning Trees 10.5 Minimum Spanning Trees End-of-Chapter Material 11 Boolean Algebra 11.1 Boolean Functions 11.2 Representing Boolean Functions 11.3 Logic Gates 11.4 Minimization of Circuits End-of-Chapter Material 12 Modeling Computation 12.

1 Languages and Grammars 12.2 Finite-State Machines with Output 12.3 Finite-State Machines with No Output 12.4 Language Recognition 12.5 Turing Machines End-of-Chapter Material Appendixes A.1 Axioms for the Real Numbers and the Positive Integers A.2 Exponential and Logarithmic Functions A.3 Pseudocode Suggested Readings Answers to Odd-Numbered Exercises Photo Credits Index of Biographies Index.