Discrete Mathematics with Applications

Description

Title Page......Page 2 Copyright Page......Page 3 Contents......Page 6 Preface......Page 14 1.1: Variables......Page 24 1.2: The Language of Sets......Page 29 1.3: The Language of relations and functions......Page 38 1.4: The Language of Graphs......Page 47 2.1: Logical Form and Logical Equivalence......Page 60 2.2: Conditional Statements......Page 76 2.3: Valid and Invalid Arguments......Page 89 2.4: Application: Digital Logic Circuits......Page 102 2.5: Application: Number Systems and Circuits for Addition......Page 116 3.1: Predicates and Quantified Statements I......Page 131 3.2: Predicates and Quantified Statements II......Page 145 3.3: Statements with Multiple Quantifiers......Page 154 3.4: Arguments with Quantified Statements......Page 169 Chapter 04: Elementary Number theory and Methods of Proof......Page 183 4.1: Direct Proof and Counterexample I: Introduction......Page 184 4.2: Direct Proof and Counterexample II: writing Advice......Page 196 4.3: Direct Proof and Counterexample III: Rational Numbers......Page 206 4.4: Direct Proof and Counterexample IV: Divisibility......Page 213 4.5: Direct Proof and Counterexample V: Division into Cases and the Quotient-Remainder Theorem......Page 223 4.6: Direct Proof and Counterexample VI: Floor and Ceiling......Page 234 4.7: Indirect argument: Contradiction and Contraposition......Page 241 4.8: Indirect Argument: Two Famous Theorems......Page 251 4.9: Application: The Handshake Theorem......Page 258 4.10: Application: Algorithms......Page 267 5.1: Sequences......Page 281 5.2: Mathematical Induction I: proving Formulas......Page 298 5.3: Mathematical Induction II: Applications......Page 312 5.4: Strong Mathematical Induction and the Well-Ordering principle for the Integers......Page 324 5.5: Application: Correctness of Algorithms......Page 337 5.6: Defining Sequences Recursively......Page 348 5.7: Solving Recurrence Relations by Iteration......Page 363 5.8: Second-Order Linear Homogeneous Recurrence Relations with Constant Coefficients......Page 375 5.9: General Recursive Definitions and Structural Induction......Page 387 6.1: Set Theory: Definitions and the Element Method of Proof......Page 400 6.2: Properties of Sets......Page 414 6.3: Disproofs and Algebraic Proofs......Page 430 6.4: Boolean Algebras, Russell’s Paradox, and the Halting Problem......Page 437 7.1: Functions Defined on General Sets......Page 448 7.2: One-to-One, Onto, and Inverse Functions......Page 462 7.3: Composition of functions......Page 484 7.4: Cardinality with Applications to Computability......Page 496 8.1: Relations on Sets......Page 510 8.2: Reflexivity, Symmetry, and Transitivity......Page 518 8.3: Equivalence Relations......Page 528 8.4: Modular Arithmetic with Applications to Cryptography......Page 547 8.5: Partial Order relations......Page 569 9.1: introduction to Probability......Page 587 9.2: Possibility Trees and the Multiplication rule......Page 596 9.3: Counting elements of Disjoint Sets: The Addition rule......Page 612 9.4: The Pigeonhole Principle......Page 627 9.5: Counting Subsets of a Set: Combinations......Page 640 9.6: r-Combinations with repetition Allowed......Page 657 9.7: Pascal’s Formula and the Binomial Theorem......Page 665 9.8: Probability Axioms and expected Value......Page 678 9.9: Conditional Probability, Bayes’ Formula, and independent events......Page 685 10.1: Trails, Paths, and Circuits......Page 700 10.2: Matrix Representations of Graphs......Page 721 10.3: isomorphisms of Graphs......Page 736 10.4: Trees: Examples and Basic Properties......Page 743 10.5: Rooted Trees......Page 755 10.6: Spanning Trees and a Shortest Path Algorithm......Page 765 11.1: Real-Valued Functions of a Real Variable and Their Graphs......Page 783 11.2: Big-O, Big-Omega, and Big-Theta Notations......Page 792 11.3: Application: Analysis of Algorithm Efficiency I......Page 810 11.4: Exponential and Logarithmic Functions: Graphs and Orders......Page 823 11.5: Application: Analysis of Algorithm Efficiency II......Page 836 Chapter 12: Regular Expressions and Finite-State Automata......Page 851 12.1: Formal Languages and Regular Expressions......Page 852 12.2: Finite-State Automata......Page 864 12.3: Simplifying Finite-State Automata......Page 881 Appendix A: Properties of the real Numbersp......Page 895 Appendix B: Solutions and Hints to Selected Exercises......Page 898 Index......Page 1036