CONTENTS
1 Discrete Models = 1
2 Foundations = 13
2.1 Basic Concepts of Sets = 14
2.2 Russell's Paradox = 26
2.3 Functions-Basic Concepts = 28
2.4 Further Properties of Functions = 41
2.5 Exponential and Logarithmic Functions = 49
2.6 Finite series = 58
Review Exercises - Chapter 2 = 66
3 Logic = 71
3.1 Introduction to Logic = 72
3.2 Propositional Logic = 77
3.3 Connectives = 81
3.4 Evaluating More Complex Expressions = 91
3.5 Predicate Logic = 99
3.6 Rules of Inference = 111
3.7 Mathematical Induction = 126
3.8 Combinational Circuits = 136
Review Exercises - Chapter 3 = 148
4 Algorithms = 153
4.1 Algorithms = 154
4.2 Asymptotic Domination = 169
4.3 Analysis and Verification of Algorithms = 179
4.4 Inefficient Algorithms and Intractable Problems = 193
4.5 Searching Algorithms = 200
Review Exercises - Chapter 4 = 209
5 Elementary Number Theory = 215
5.1 Introduction = 216
5.2 Prime Numbers = 223
5.3 Divisibility Properties = 230
5.4 Positional Notation = 239
5.5 Congruence = 251
Review Exercises - Chapter 5 = 257
6 Recursion = 259
6.1 Introduction to Recurrence Equations = 260
6.2 Solving Recurrence Equations = 272
6.3 Linear, First-Order Recurrence Equations = 283
6.4 Linear, Second-Order Recurrence Equations = 292
6.5 Recursive Algorithms = 305
6.6 More Recursive Algorithms = 322
Review Exercises - Chapter 6 = 333
7 Combinatorics and Discrete Probability = 337
7.1 The Addition and Multiplication Principles = 338
7.2 Permutations = 348
7.3 Combinations = 362
7.4 Applications and Properties of the Binomial Coefficient = 374
7.5 Probability Models = 382
7.6 Computing Discrete Probabilities = 393
7.7 Conditional Probability, Independence, and Expectation = 400
Review Exercises - Chapter 7 = 410
8 Relations = 415
8.1 Basic Concepts = 417
8.2 Properties of Relations = 426
8.3 Order Relations = 438
8.4 Operations on Relations = 452
Review Exercises - Chapter 8 = 466
9 Graph Theory = 469
9.1 Introduction = 470
9.2 Euler Circuits and Hamiltonian Cycles = 482
9.3 Graph Isomorphisms and Representations = 497
9.4 Planar Graphs = 511
Review Exercises - Chapter 9 = 522
10 Trees = 525
10.1 Introduction to Trees = 527
10.2 Spanning Trees = 535
10.3 Rooted Trees = 547
10.4 Applications of Binary Trees in Computer Science = 559
Review Exercises - Chapter 10 = 577
Appendixes = 579
A Arrays = 579
B Introduction to Matrices = 591
C Simultaneous Linear Equations and Gaussian Elimination = 607
D Matrix Inversion = 627
E Complex Numbers and Recurrence Equations = 641
F Counting Equivalence Relations = 649
Glossary of Key Terms = 653
Answers to Odd-numbered Exercises = 661
Index = 680
