The Adapter's Words
Preface
Online Resources
To the Student
About the Author
List of Symbols
1 The Foundations: Logic and Proofs1
1.1 Propositional Logic1
1.2 Applications of Propositional Logic15
1.3 Propositional Equivalences22
1.4 Predicates and Quantifiers34
1.5 Nested Quantifiers51
1.6 Rules of Inference62
1.7 Introduction to Proofs72
1.8 Proof Methods and Strategy84
End-of-ChapterMaterial (Online)
2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices101
2.1 Sets101
2.2 Set Operations111
2.3 Functions124
2.4 Sequences and Summations140
2.5 Cardinality of Sets153
2.6 Matrices161
End-of-ChapterMaterial (Online)
3 Counting169
3.1 The Basics of Counting169
3.2 The Pigeonhole Principle182
3.3 Permutations and Combinations189
3.4 Binomial Coefficients and Identities197
3.5 Generalized Permutations and Combinations204
3.6 Generating Permutations and Combinations215
End-of-ChapterMaterial (Online)
4 Advanced Counting Techniques221
4.1 Applications of Recurrence Relations221
4.2 Solving Linear Recurrence Relations232
4.3 Divide-and-Conquer Algorithms and Recurrence Relations244
4.4 Generating Functions253
4.5 Inclusion朎xclusion268
4.6 Applications of Inclusion朎xclusion273
End-of-ChapterMaterial (Online)
5 Relations281
5.1 Relations and Their Properties281
5.2 n-ary Relations and Their Applications292
5.3 Representing Relations302
5.4 Closures of Relations308
5.5 Equivalence Relations317
5.6 Partial Orderings327
End-of-ChapterMaterial (Online)
6 Graphs343
6.1 Graphs and Graph Models343
6.2 Graph Terminology and Special Types of Graphs354
6.3 Representing Graphs and Graph Isomorphism371
6.4 Connectivity380
6.5 Euler and Hamilton Paths393
6.6 Shortest-Path Problems405
6.7 Planar Graphs415
6.8 Graph Coloring423
End-of-ChapterMaterial (Online)
7 Trees431
7.1 Introduction to Trees431
7.2 Applications of Trees442
7.3 Tree Traversal456
7.4 Spanning Trees468
7.5 Minimum Spanning Trees481
End-of-ChapterMaterial (Online)
8 Boolean Algebra487
8.1 Boolean Functions487
8.2 Representing Boolean Functions494
8.3 Logic Gates497
8.4 Minimization of Circuits503
End-of-ChapterMaterial (Online)
Suggested Readings (Online)
Answers to Odd-Numbered Exercises (Online)
