《Discrete Mathematics and Its Applications》

1The Foundations： Logic， Sets， and Functions1

1.1Logic2

1.2 Propositional Equivalences11

1.3 Predicates and Quantifiers17

1.4 Sets25

1.5 Set Operations33

1.6 Functions45

1.7 Sequences and Summations57

1.8The Growth of Functions63

Key Terms and Results72

Supplementary Exercises74

Computer Projects76

2The Fundamentals： Algorithms， The Integers， and Matrices77

2.1Algorithms78

2.2 Complexity of Algorithms84

2.3 The Integers and Division91

2.4 Integers and Algorithms102

2.5Matrices112

Key Terms and Results124

Supplementary Exercises126

Computer Projects127

3Mathematical Reasoning129

3.1Methods of Proof130

3.2 Mathematical Induction141

3.3 Recursive Definitions156

3.4 Recursive Algorithms166

3.5Program Correctness175

Key Terms and Results178

Supplementary Exercises179

Computer Projects182

4Counting184

4.1The Basics of Counting185

4.2 The Pigeonhole Principle194

4.3 Permutations and Combinations200

4.4 Discrete Probability209

4.5 Generalized Permutations and Combinations215

4.6Generating Permutations and Combinations223

Key Terms and Results228

Supplementary Exercises229

Computer Projects232

5Advanced Counting Techniques233

5.1Recurrence Relations234

5.2 Solving Recurrence Relations242

5.3 Divide-and-Conquer Relations250

5.4 Inclusion-Exclusion256

5.5Applications of Inclusion-Exclusion264

Key Terms and Results273

Supplementary Exercises274

Computer Projects277

6Relations278

6.1Relations and Their Properties279

6.2 n-ary Relations and Their Applications289

6.3 Representing Relations297

6.4 Closures of Relations305

6.5 Equivalence Relations317

6.6Partial Orderings326

Key Terms and Results341

Supplementary Exercises344

Computer Projects347

7Graphs348

7.1Introduction to Graphs349

7.2 Graph Terminology357

7.3 Representing Graphs367

7.4 Connectivity378

7.5 Euler and Hamilton Paths387

7.6 Shortest Path Problems401

7.7 Planar Graphs411

7.8Graph Coloring421

Key Terms and Results431

Supplementary Exercises433

Computer Projects438

8Trees439

8.1Introduction to Trees440

8.2 Applications of Trees454

8.3 Tree Traversal460

8.4 Trees and Sorting477

8.5 Spanning Trees486

8.6Minimal Spanning Trees499

Key Terms and Results506

Supplementary Exercises508

Computer Projects512

9Boolean Algebra513

9.1Boolean Functions514

9.2 Representing Boolean Functions520

9.3 Logic Gates525

9.4Minimization of Circuits532

Key Terms and Results546

Supplementary Exercises547

Computer Projects550

10Modeling Computation551

10.1Languages and Grammars552

10.2 Finite-State Machines with Output563

10.3 Finite-State Machines with No Output573

10.4Language Recognition582

Key Terms and Results594

Supplementary Exercises595

Computer Projects598