Discrete Mathematics with Applications, Metric Version

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