1 The Foundations: Logic and Proofs....................................1
1.1 Propositional Logic............................................................1
1.2 Applications of Propositional Logic.............................................17
1.3 Propositional Equivalences....................................................26
1.4 Predicates and Quantifiers.....................................................40
1.5 Nested Quantifiers............................................................60
1.6 Rules of Inference.............................................................73
1.7 Introduction to Proofs.........................................................84
1.8 Proof Methods and Strategy....................................................96
End-of-Chapter Material.....................................................115
2 Basic Structures: Sets, Functions, Sequences, Sums, and atrices....................................121
2.1 Sets........................................................................121
2.2 Set Operations...............................................................133
2.3 Functions...................................................................147
2.4 Sequences and Summations...................................................165
2.5 Cardinality of Sets...........................................................179
2.6 Matrices....................................................................188
End-of-Chapter Material.....................................................195
3 Algorithms.........................................................201
3.1 Algorithms..................................................................201
3.2 The Growth of Functions.....................................................216
3.3 Complexity of Algorithms....................................................231
End-of-Chapter Materia.....................................................244
4 Number Theory and Cryptography..................................251
4.1 Divisibility and Modular Arithmetic...........................................251
4.2 Integer Representations and Algorithms........................................260
4.3 Primes and Greatest Common Divisors........................................271
4.4 Solving Congruences.........................................................290
4.5 Applications of Congruences.................................................303
4.6 Cryptography...............................................................310
End-of-Chapter Materia.....................................................324
5 Induction and Recursion............................................331
5.1 Mathematical Induction......................................................331
5.2 Strong Induction and Well-Ordering...........................................354
5.3 Recursive Definitions and Structural Induction..................................365
5.4 Recursive Algorithms........................................................381
5.5 Program Correctness.........................................................393
End-of-Chapter Materia.....................................................398
6 Counting...........................................................405
6.1 The Basics of Counting.......................................................405
6.2 The Pigeonhole Principle.....................................................420
6.3 Permutations and Combinations...............................................428
6.4 Binomial Coeficients and Identities...........................................437
6.5 Generalized Permutations and Combinations...................................445
6.6 Generating Permutations and Combinations....................................457
End-of-Chapter Materia.....................................................461
7 Discrete Probability.................................................469
7.1 An Introduction to Discrete Probability........................................469
7.2 Probability Theory...........................................................477
7.3 Bayes’Theorem.............................................................494
7.4 Expected Valueand Variance.................................................503
End-of-Chapter Materia.....................................................520
8 Advanced Counting Techniques.....................................527
8.1 Applications of Recurrence Relations..........................................527
8.2 Solving Linear Recurrence Relations..........................................540
8.3 Divide-and-Conquer Algorithms and Recurrence Relations......................553
8.4 Generating Functions........................................................563
8.5 Inclusion–Exclusion.........................................................579
8.6 Applications of Inclusion–Exclusion...........................................585
End-of-Chapter Materia.....................................................592
9 Relations...........................................................599
9.1 Relations and Their Properties................................................599
9.2 n-ary Relations and Their Applications.........................................611
9.3 Representing Relations.......................................................621
9.4 Closures of Relations.........................................................628
9.5 Equivalence Relations........................................................638
9.6 Partial Orderings............................................................650
End-of-Chapter Materia.....................................................665
10 Graphs.............................................................673
10.1 Graphs and Graph Models....................................................673
10.2 Graph Terminology and Special Types of Graphs...............................685
10.3 Representing Graphs and Graph Isomorphism..................................703
10.4 Connectivity................................................................714
10.5 Euler and Hamilton Paths.....................................................728
10.6 Shortest-Path Problems.......................................................743
10.7 Planar Graphs...............................................................753
10.8 Graph Coloring..............................................................762
End-of-Chapter Materia.....................................................771
11 Trees...............................................................781
11.1 Introduction to Trees.........................................................781
11.2 Applications of Trees........................................................793
11.3 Tree Traversal...............................................................808
11.4 Spanning Trees..............................................................821
11.5 Minimum Spanning Trees....................................................835
End-of-Chapter Materia.....................................................841
12 Boolean Algebra....................................................847
12.1 Boolean Functions...........................................................847
12.2 Representing Boolean Functions..............................................855
12.3 Logic Gates.................................................................858
12.4 Minimization of Circuits.....................................................864
End-of-Chapter Materia.....................................................879
13 Modeling Computation .............................................885
13.1 Languages and Grammars....................................................885
13.2 Finite-State Machines with Output.............................................897
13.3 Finite-State Machines with NoOutput.........................................904
13.4 Language Recognition.......................................................917
13.5 Turing Machines.............................................................927
End-of-Chapter Materia.....................................................938
Appendices.........................................................A-1
1 Axioms for the Real Numbers and the Positive Integers..........................A-1
2 Exponential and Logarithmic Functions........................................A-7
3 Pseudocode................................................................A-11
Suggested ReadingsB-1
Answers to Odd-Numbered Exercises S-1
Index of BiographiesI-1
IndexI-2