Discrete Mathematics with Applications: Fifth Edition

Main subject categories: • Discrete mathematics • Number theory • Methods of proof • Mathematical induction • Mathematical recursion • Set theory • Functions • Probability • Algorithms • Regular expressions • Finite-state automataDiscrete Mathematics with Applications, 5th Edition, explains complex, abstract concepts with clarity and precision and provides a strong foundation for computer science and upper-level mathematics courses of the computer age. Author Susanna Epp presents not only the major themes of discrete mathematics, but also the reasoning that underlies mathematical thought. Students develop the ability to think abstractly as they study the ideas of logic and proof. While learning about such concepts as logic circuits and computer addition, algorithm analysis, recursive thinking, computability, automata, cryptography and combinatorics, students discover that the ideas of discrete mathematics underlie and are essential to today's science and technology. 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 "DISCRETE MATHEMATICS WITH APPLICATIONS, 5th Edition, explains complex, abstract concepts with clarity and precision and provides a strong foundation for computer science and upper-level mathematics courses of the computer age. Author Susanna Epp presents not only the major themes of discrete mathematics, but also the reasoning that underlies mathematical thought. Students develop the ability to think abstractly as they study the ideas of logic and proof. While learning about such concepts as logic circuits and computer addition, algorithm analysis, recursive thinking, computability, automata, cryptography and combinatorics, students discover that the ideas of discrete mathematics underlie and are essential to today's science and technology." --Amazon