1The Foundations： Logic， Sets， and Functions 1
1.1 Logic 2
1.2 Propositional Equivalences 11
1.3 Predicates and Quantifiers 17
1.4 Sets 25
1.5 Set Operations 33
1.6 Functions 45
1.7 Sequences and Summations 57
1.8 The Growth of Functions 63
Key Terms and Results 72
Supplementary Exercises 74
Computer Projects 76
2The Fundamentals： Algorithms， The Integers， and Matrices 77
2.1 Algorithms 78
2.2 Complexity of Algorithms 84
2.3 The Integers and Division 91
2.4 Integers and Algorithms 102
2.5 Matrices 112
Key Terms and Results 124
Supplementary Exercises 126
Computer Projects 127
3Mathematical Reasoning 129
3.1 Methods of Proof 130
3.2 Mathematical Induction 141
3.3 Recursive Definitions 156
3.4 Recursive Algorithms 166
3.5 Program Correctness 175
Key Terms and Results 178
Supplementary Exercises 179
Computer Projects 182
4Counting 184
4.1 The Basics of Counting 185
4.2 The Pigeonhole Principle 194
4.3 Permutations and Combinations 200
4.4 Discrete Probability 209
4.5 Generalized Permutations and Combinations 215
4.6 Generating Permutations and Combinations 223
Key Terms and Results 228
Supplementary Exercises 229
Computer Projects 232
5Advanced Counting Techniques 233
5.1 Recurrence Relations 234
5.2 Solving Recurrence Relations 242
5.3 Divide-and-Conquer Relations 250
5.4 Inclusion-Exclusion 256
5.5 Applications of Inclusion-Exclusion 264
Key Terms and Results 273
Supplementary Exercises 274
Computer Projects 277
6Relations 278
6.1 Relations and Their Properties 279
6.2 n-ary Relations and Their Applications 289
6.3 Representing Relations 297
6.4 Closures of Relations 305
6.5 Equivalence Relations 317
6.6 Partial Orderings 326
Key Terms and Results 341
Supplementary Exercises 344
Computer Projects 347
7Graphs 348
7.1 Introduction to Graphs 349
7.2 Graph Terminology 357
7.3 Representing Graphs 367
7.4 Connectivity 378
7.5 Euler and Hamilton Paths 387
7.6 Shortest Path Problems 401
7.7 Planar Graphs 411
7.8 Graph Coloring 421
Key Terms and Results 431
Supplementary Exercises 433
Computer Projects 438
8Trees 439
8.1 Introduction to Trees 440
8.2 Applications of Trees 454
8.3 Tree Traversal 460
8.4 Trees and Sorting 477
8.5 Spanning Trees 486
8.6 Minimal Spanning Trees 499
Key Terms and Results 506
Supplementary Exercises 508
Computer Projects 512
9Boolean Algebra 513
9.1 Boolean Functions 514
9.2 Representing Boolean Functions 520
9.3 Logic Gates 525
9.4 Minimization of Circuits 532
Key Terms and Results 546
Supplementary Exercises 547
Computer Projects 550
10Modeling Computation 551
10.1 Languages and Grammars 552
10.2 Finite-State Machines with Output 563
10.3 Finite-State Machines with No Output 573
10.4 Language Recognition 582
Key Terms and Results 594
Supplementary Exercises 595
Computer Projects 598