Discrete Mathematics and its Applications [8th ed.]

Description

Contents......Page 3 Preface......Page 6 Online Resources......Page 13 To the Student......Page 16 1.1 Propositional Logic......Page 19 1.2 Applications of Propositional Logic......Page 35 1.3 Propositional Equivalences......Page 44 1.4 Predicates and Quantifiers......Page 58 1.5 Nested Quantifiers......Page 78 1.6 Rules of Inference......Page 91 1.7 Introduction to Proofs......Page 102 1.8 Proof Methods and Strategy......Page 114 End-of-Chapter Material......Page 133 2.1 Sets......Page 139 2.2 Set Operations......Page 151 2.3 Functions......Page 165 2.4 Sequences and Summations......Page 183 2.5 Cardinality of Sets......Page 197 2.6 Matrices......Page 206 End-of-Chapter Material......Page 213 3.1 Algorithms......Page 218 3.2 The Growth of Functions......Page 233 3.3 Complexity of Algorithms......Page 248 End-of-Chapter Material......Page 261 4.1 Divisibility and Modular Arithmetic......Page 267 4.2 Integer Representations and Algorithms......Page 276 4.3 Primes and Greatest Common Divisors......Page 287 4.4 Solving Congruences......Page 306 4.5 Applications of Congruences......Page 319 4.6 Cryptography......Page 326 End-of-Chapter Material......Page 340 5.1 Mathematical Induction......Page 346 5.2 Strong Induction and Well-Ordering......Page 369 5.3 Recursive Definitions and Structural Induction......Page 380 5.4 Recursive Algorithms......Page 396 5.5 Program Correctness......Page 408 End-of-Chapter Material......Page 413 6.1 The Basics of Counting......Page 420 6.2 The Pigeonhole Principle......Page 435 6.3 Permutations and Combinations......Page 443 6.4 Binomial Coefficients and Identities......Page 452 6.5 Generalized Permutations and Combinations......Page 460 6.6 Generating Permutations and Combinations......Page 472 End-of-Chapter Material......Page 476 7.1 An Introduction to Discrete Probability......Page 483 7.2 Probability Theory......Page 491 7.3 Bayes’ Theorem......Page 508 7.4 Expected Value and Variance......Page 517 End-of-Chapter Material......Page 534 8.1 Applications of Recurrence Relations......Page 541 8.2 Solving Linear Recurrence Relations......Page 554 8.3 Divide-and-Conquer Algorithms and Recurrence Relations......Page 567 8.4 Generating Functions......Page 577 8.5 Inclusion–Exclusion......Page 593 8.6 Applications of Inclusion–Exclusion......Page 599 End-of-Chapter Material......Page 606 9.1 Relations and Their Properties......Page 612 9.2 n-ary Relations and Their Applications......Page 624 9.3 Representing Relations......Page 634 9.4 Closures of Relations......Page 641 9.5 Equivalence Relations......Page 651 9.6 Partial Orderings......Page 663 End-of-Chapter Material......Page 678 10.1 Graphs and Graph Models......Page 685 10.2 Graph Terminology and Special Types of Graphs......Page 697 10.3 Representing Graphs and Graph Isomorphism......Page 715 10.4 Connectivity......Page 726 10.5 Euler and Hamilton Paths......Page 740 10.6 Shortest-Path Problems......Page 755 10.7 Planar Graphs......Page 765 10.8 Graph Coloring......Page 774 End-of-Chapter Material......Page 783 11.1 Introduction to Trees......Page 792 11.2 Applications of Trees......Page 804 11.3 Tree Traversal......Page 819 11.4 Spanning Trees......Page 832 11.5 Minimum Spanning Trees......Page 846 End-of-Chapter Material......Page 852 12.1 Boolean Functions......Page 858 12.2 Representing Boolean Functions......Page 866 12.3 Logic Gates......Page 869 12.4 Minimization of Circuits......Page 875 End-of-Chapter Material......Page 890 13.1 Languages and Grammars......Page 895 13.2 Finite-State Machines with Output......Page 907 13.3 Finite-State Machines with No Output......Page 914 13.4 Language Recognition......Page 927 13.5 Turing Machines......Page 937 End-of-Chapter Material......Page 948 1 Axioms for the Real Numbers and the Positive Integers......Page 953 2 Exponential and Logarithmic Functions......Page 959 3 Pseudocode......Page 962 Suggested Readings......Page 968 Answers to Odd-Numbered Exercises......Page 976 Index of Biographies......Page 1074 Index......Page 1075