DISCRETE MATHEMATICS WITH APPLICATIONS, 5th Edition, Metric 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.
Author(s): Susanna Epp
Edition: 5
Publisher: Cengage Learning
Year: 2019
Language: English
Commentary: Vector PDF
Pages: 984
City: Boston, MA
Tags: Algorithms; Graph Theory; Recursion; Number Theory; Probability Theory; Discrete Mathematics; Proofs; Set Theory; Regular Expressions; Mathematical Logic; Combinatorics; Mathematical Induction; Algorithm Analysis; Finite-State Automata
Cover
Contents
Preface
Chapter 1: Speaking Mathematically
1.1 Variables
1.2 The Language of Sets
1.3 The Language of Relations and Functions
1.4 The Language of Graphs
Chapter 2: The Logic of Compound Statements
2.1 Logical Form and Logical Equivalence
2.2 Conditional Statements
2.3 Valid and Invalid Arguments
2.4 Application: Digital Logic Circuits
2.5 Application: Number Systems and Circuits for Addition
Chapter 3: The Logic of Quantified Statements
3.1 Predicates and Quantified Statements I
3.2 Predicates and Quantified Statements II
3.3 Statements with Multiple Quantifiers
3.4 Arguments with Quantified Statements
Chapter 4: Elementary Number Theory and Methods of Proof
4.1 Direct Proof and Counterexample I: Introduction
4.2 Direct Proof and Counterexample II: Writing Advice
4.3 Direct Proof and Counterexample III: Rational Numbers
4.4 Direct Proof and Counterexample IV: Divisibility
4.5 Direct Proof and Counterexample V: Division into Cases and the Quotient-Remainder Theorem
4.6 Direct Proof and Counterexample VI: Floor and Ceiling
4.7 Indirect Argument: Contradiction and Contraposition
4.8 Indirect Argument: Two Famous Theorems
4.9 Application: The Handshake Theorem
4.10 Application: Algorithms
Chapter 5: Sequences, Mathematical Induction, and Recursion
5.1 Sequences
5.2 Mathematical Induction I: Proving Formulas
5.3 Mathematical Induction II: Applications
5.4 Strong Mathematical Induction and the Well-Ordering Principle for the Integers
5.5 Application: Correctness of Algorithms
5.6 Defining Sequences Recursively
5.7 Solving Recurrence Relations by Iteration
5.8 Second-Order Linear Homogeneous Recurrence Relations with Constant Coefficients
5.9 General Recursive Definitions and Structural Induction
Chapter 6: Set Theory
6.1 Set Theory: Definitions and the Element Method of Proof
6.2 Properties of Sets
6.3 Disproofs and Algebraic Proofs
6.4 Boolean Algebras, Russell's Paradox, and the Halting Problem
Chapter 7: Properties of Functions
7.1 Functions Defined on General Sets
7.2 One-to-One, Onto, and Inverse Functions
7.3 Composition of Functions
7.4 Cardinality with Applications to Computability
Chapter 8: Properties of Relations
8.1 Relations on Sets
8.2 Reflexivity, Symmetry, and Transitivity
8.3 Equivalence Relations
8.4 Modular Arithmetic with Applications to Cryptography
8.5 Partial Order Relations
Chapter 9: Counting and Probability
9.1 Introduction to Probability
9.2 Possibility Trees and the Multiplication Rule
9.3 Counting Elements of Disjoint Sets: The Addition Rule
9.4 The Pigeonhole Principle
9.5 Counting Subsets of a Set: Combinations
9.6 r-Combinations with Repetition Allowed
9.7 Pascal's Formula and the Binomial Theorem
9.8 Probability Axioms and Expected Value
9.9 Conditional Probability, Bayes' Formula, and Independent Events
Chapter 10: Theory of Graphs and Trees
10.1 Trails, Paths, and Circuits
10.2 Matrix Representations of Graphs
10.3 Isomorphisms of Graphs
10.4 Trees: Examples and Basic Properties
10.5 Rooted Trees
10.6 Spanning Trees and a Shortest Path Algorithm
Chapter 11: Analysis of Algorithm Efficiency
11.1 Real-Valued Functions of a Real Variable and Their Graphs
11.2 Big-O, Big-Omega, and Big-Theta Notations
11.3 Application: Analysis of Algorithm Efficiency I
11.4 Exponential and Logarithmic Functions: Graphs and Orders
11.5 Application: Analysis of Algorithm Efficiency II
Chapter 12: Regular Expressions and Finite-State Automata
12.1 Formal Languages and Regular Expressions
12.2 Finite-State Automata
12.3 Simplifying Finite-State Automata
Appendix A: Properties of the Real Numbers
Appendix B: Solutions and Hints to Selected Exercises
Index
