1 The Foundations：Logic and Proofs 1
1.1 Propositional Logic 1
1.2 Applications of Propositional Logic 13
1.3 Propositional Equivalences 20
1.4 Predicates and Quantifiers 32
1.5 Nested Quantifiers 49
1.6 Rules of Inference 59
1.7 Introduction to Proofs 70
1.8 Proof Methods and Strategy 80
End-of-Chapter Material 96
2 Basic Structures：Sets，Functions，Sequences， Sums，and Matrices 101
2.1 Sets 101
2.2 Set Operations 111
2.3 Functions 121
2.4 Sequences and Summations 137
2.5 Cardinality of Sets 149
2.6 Matrices 156
End-of-Chapter Material 163
3 Counting 169
3.1 The Basics of Counting 169
3.2 The Pigeonhole Principle 181
3.3 Permutations and Combinations 188
3.4 Binomial Coefficients and Identities 195
3.5 Generalized Permutations and Combinations 202
3.6 Generating Permutations and Combinations 212
End-of-Chapter Material 216
4 Advanced Counting Techniques 223
4.1 Applications of Recurrence Relations 223
4.2 Solving Linear Recurrence Relations 233
4.3 Divide-and-Conquer Algorithms and Recurrence Relations 245
4.4 Generating Functions 254
4.5 Inclusion-Exclusion 268
4.6 Applications of Inclusion-Exclusion 273
End-of-Chapter Material 279
5 Relations 287
5.1 Relations and Their Properties 287
5.2 n-ary Relations and Their Applications 296
5.3 Representing Relations 303
5.4 Closures of Relations 309
5.5 Equivalence Relations 318
5.6 Partial Orderings 327
End-of-Chapter Material 340
6 Graphs 347
6.1 Graphs and Graph Models 347
6.2 Graph Terminology and Special Types of Graphs 356
6.3 Representing Graphs and Graph Isomorphism 372
6.4 Connectivity 380
6.5 Euler and Hamilton Paths 393
6.6 Shortest-Path Problems 404
6.7 Planar Graphs 414
6.8 Graph Coloring 421
End-of-Chapter Material 429
7 Trees 439
7.1 Introduction to Trees 439
7.2 Applications of Trees 450
7.3 Tree Traversal 463
7.4 Spanning Trees 475
7.5 Minimum Spanning Trees 486
End-of-Chapter Material 491
8 Boolean Algebra 497
8.1 Boolean Functions 497
8.2 Representing Boolean Functions 504
8.3 Logic Gates 507
8.4 Minimization of Circuits 513
End-of-Chapter Material 525
Suggested Readings 531