Discrete Mathematics and Its ApplicationsPDF电子书下载

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