Discrete Mathematics and Its Applications, 6th edition

Cover......Page 1
List of symbols......Page 2
Title page......Page 5
Contents......Page 7
Preface......Page 11
The MathZone Companion Website......Page 22
To the Student......Page 24
1.1 Propositional Logic......Page 27
1.2 Propositional Equivalences......Page 47
1.3 Predicates and Quantifiers......Page 56
1.4 Nested Quantifiers......Page 76
1.5 Rules of Inference......Page 89
1.6 Introduction to Proofs......Page 101
1.7 Proof Methods and Strategy......Page 112
End-of-Chapter Material......Page 130
2.1 Sets......Page 137
2.2 Set Operations......Page 147
2.3 Functions......Page 159
2.4 Sequences and Summations......Page 175
End-of-Chapter Material......Page 189
3.1 Algorithms......Page 193
3.2 The Growth of Functions......Page 206
3.3 Complexity of Algorithms......Page 219
3.4 The Integers and Division......Page 226
3.5 Primes and Greatest Common Divisors......Page 236
3.6 Integers and Algorithms......Page 245
3.7 Applications of Number Theory......Page 257
3.8 Matrices......Page 272
End-of-Chapter Material......Page 283
4.1 Mathematical Induction......Page 289
4.2 Strong Induction and Well-Ordering......Page 309
4.3 Recursive Definitions and Structural Induction......Page 320
4.4 Recursive Algorithms......Page 337
4.5 Program Correctness......Page 348
End-of-Chapter Material......Page 354
5.1 The Basics of Counting......Page 361
5.2 The Pigeonhole Principle......Page 373
5.3 Permutations and Combinations......Page 381
5.4 Binomial Coefficients......Page 389
5.5 Generalized Permutations and Combinations......Page 396
5.6 Generating Permutations and Combinations......Page 408
End-of-Chapter Material......Page 412
6.1 An Introduction to Discrete Probability......Page 419
6.2 Probability Theory......Page 426
6.3 Bayes' Theorem......Page 443
6.4 Expected Value and Variance......Page 452
End-of-Chapter Material......Page 468
7.1 Recurrence Relations......Page 475
7.2 Solving Linear Recurrence Relations......Page 486
7.3 Divide-and-Conquer Algorithms and Recurrence Relations......Page 500
7.4 Generating Functions......Page 510
7.5 Inclusion-Exclusion......Page 525
7.6 Applications of Inclusion-Exclusion......Page 531
End-of-Chapter Material......Page 539
8.1 Relations and Their Properties......Page 545
8.2 n-ary Relations and Their Applications......Page 556
8.3 Representing Relations......Page 563
8.4 Closures of Relations......Page 570
8.5 Equivalence Relations......Page 581
8.6 Partial Orderings......Page 592
End-of-Chapter Material......Page 607
9.1 Graphs and Graph Models......Page 615
9.2 Graph Terminology and Special Types of Graphs......Page 623
9.3 Representing Graphs and Graph Isomorphism......Page 637
9.4 Connectivity......Page 647
9.5 Euler and Hamilton Paths......Page 659
9.6 Shortest-Path Problems......Page 673
9.7 Planar Graphs......Page 683
9.8 Graph Coloring......Page 692
End-of-Chapter Material......Page 701
10.1 Introduction to Trees......Page 709
10.2 Applications of Trees......Page 721
10.3 Tree Traversal......Page 736
10.4 Spanning Trees......Page 750
10.5 Minimum Spanning Trees......Page 763
End-of-Chapter Material......Page 769
11.1 Boolean Functions......Page 775
11.2 Representing Boolean Functions......Page 783
11.3 Logic Gates......Page 786
11.4 Minimization of Circuits......Page 792
End-of-Chapter Material......Page 807
12.1 Languages and Grammars......Page 811
12.2 Finite-State Machines with Output......Page 822
12.3 Finite-State Machines with No Output......Page 830
12.4 Language Recognition......Page 843
12.5 Turing Machines......Page 853
End-of-Chapter Material......Page 864
Appendixes A-1......Page 871
A-2 Exponential and Logarithmic Functions A-7......Page 877
A-3 Pseudocode A-10......Page 880
Suggested Readings B-1......Page 887
Answers to Odd-Numbered Exercises S-1......Page 895
Photo Credits C-1......Page 985
Index of Biographies I-1......Page 987
Index I-2......Page 988