1 The Foundations : Logic,Sets,and Functions 1
Index of Biographies 1
Suggested Readings 1
A.1 Exponential and Logarithmic Functions 1
Appendixes 1
LIST OF SYMBOLS 1
1．1 Logic 1
Index 3
A.2 Pseudocode 5
1．2Propositional Equivalences 14
1．3 Predicates and Quantifiers 21
1．4 Sets 38
1．5 Set Operations 46
1．6 Functions 56
1．7Sequences and Summations 69
1．8 The Growth of Functions 80
Key Terms and Results 92
Review Questions 94
Supplementary Exercises 95
Writing Projects 97
Computer Projects 97
Computations and Explorations 97
2 The Fundamentals : Algorithms,the Integers,and Matrices 99
2．1 Algorithms 99
2．2 Complexity of Algorithms 105
2．3 The Integers and Division 112
2．4 Integers and Algorithms 127
2．5 Applications of Number Theory 137
2.6 Matrices 150
Key Terms and Results 161
Review Questions 162
Supplementary Exercises 163
Computer Projects 164
Writing Projects 165
Computations and Expl165orations 165
3 Mathematical Reasoning 167
3．1 Methods of Proof 167
3．2 Mathematical Induction 186
3．3 Recursive Definitions 202
3．4 Recursive Algorithms 214
3．5 Program Correctness 219
Key Terms and Results 225
Review Questions 226
Supplementary Exercises 227
Computer Projects 229
Writing Projects 230
Computations and Explorations 230
4 Counting 232
4．1 The Basics of Counting 232
4．2 The Pigeonhole Principle 244
4．3 Permutations and Combinations 250
4．4 Discrete Probability 260
4．5 Probability Theory 267
4．6 Generalized Permutations and Combinations 286
4．7 Generating Permutations and Combinations 296
Key Terms and Concept 301
Review Questions 302
Supplementary Exercises 303
Computations and Explorations 306
Computer Projects 306
Writing Projects 307
5．1 Recurrence Relations 308
5 Advanced Counting Techniques 308
5．2 Solving Recurrence Relations 319
5．3 Divide-and-Conquer Relations 332
5．4 Generating Functions 338
5．5 Inclusion-Exclusion 354
5．6 Applications of Inclusion-Exclusion 360
Key Terms and Results 368
Review Questions 369
Supplementary Exercises 369
Computer Projects 371
Writing Projects 372
Computations and Explorations 372
6．1 Relations and Their Properties 374
6 Relations 374
6．2 n-ary Relations and Their Applications 384
6．3 Representing Relations 390
6．4 Closures of Relations 396
6．5 Equivalence Relations 408
6．6 Partial Orderings 415
Key Terms and Results 430
Review Questions 431
Supplementary Exercises 432
Writing Projects 436
Computations and Explorations 436
Computer Projects 436
7．1 Introduction to Graphs 438
7 Graphs 438
7．2 Graph Terminology 445
7．3 Representing Graphs and Graph Isomorphism 456
7．4 Connectivity 467
7．5 Euler and Hamilton Paths 475
7．6 Shortest Path Problems 490
7．7 Planar Graphs 501
7．8 Graph Coloring 510
Key Terms and Results 519
Review Questions 521
Supplementary Exercises 522
Computer Projects 525
Computations and Explorations 526
Writing Projects 527
8 Trees 528
8．1 Introduction to Trees 528
8．2 Applications of Trees 541
8．3 Tree Traversal 547
8．4 Trees and Sorting 562
8．5 Spanning Trees 570
8．6 Minimum Spanning Trees 580
Key Terms and Results 587
Supplementary Exercises 588
Review Questions 588
Computations and Explorations 591
Computer Projects 591
Writing Projects 592
9 Boolean Algebra 593
9．1 Boolean Functions 593
9．2 Representing Boolean Functions 600
9．3 Logic Gates 604
9．4 Minimization of Circuits 611
Key Terms and Results 625
Review Questions 625
Supplementary Exercises 626
Computer Projects 627
Writing Projects 628
Computations and Explorations 628
10．1 Languages and Grammars 629
10 Modeling Computation 629
10．2 Finite-State Machines with Output 640
10．3 Finite-Satae Machines with No Output 647
10．4 Language Recognition 656
10．5 Turing Machines 666
Key Terms and Results 674
Supplementary Exercises 675
Review Questions 675
Computer Projects 677
Writing Projects 678
Computations and Explorations 678