Discrete Mathematics with Applications

Citation

Epp, S. S. (2020). Discrete Mathematics with Applications (5th ed.). Cengage Learning.

Chapter Summary

The book has twelve chapters plus appendices; Cengage's description of the student solutions manual mentions answers to selected exercises in Appendix B. The first four chapters build the language, logic and proof techniques; Chapters 5–8 treat induction, sets, functions and relations; Chapters 9–12 treat counting and probability, graphs and trees, algorithm efficiency, and automata. Cengage's description of the fifth edition says that strings and graphs are introduced in Chapter 1 and then integrated with applications throughout, and that the handshake theorem has moved from Chapter 12 to Chapter 4.

Chapter 1: Speaking Mathematically

The opening chapter teaches the vocabulary used in the rest of the book through four sections: variables, the language of sets, the language of relations and functions, and the language of graphs.

Chapters 2–3: The Logic of Compound Statements; The Logic of Quantified Statements

Chapter 2 covers logical form and logical equivalence, conditional statements, and valid and invalid arguments, and ends with two applications: digital logic circuits, and number systems with circuits for addition. Chapter 3 repeats the pattern for quantifiers: predicates and quantified statements (two sections), statements with multiple quantifiers, and arguments with quantified statements.

Chapter 4: Elementary Number Theory and Methods of Proof

This chapter is the heart of the book's treatment of proof. Six sections of direct proof and counterexample cover an introduction, writing advice, rational numbers, divisibility, division into cases and the quotient-remainder theorem, and floor and ceiling. Two sections on indirect argument cover contradiction and contraposition and two famous theorems, and the chapter ends with applications: the handshake theorem and algorithms.

Chapter 5: Sequences, Mathematical Induction, and Recursion

Chapter 5 begins with sequences, then devotes sections to induction for proving formulas, applications of induction, and strong induction with the well-ordering principle, followed by the correctness of algorithms. The second half turns to recursion: defining sequences recursively, solving recurrence relations by iteration, second-order linear homogeneous recurrences with constant coefficients, and general recursive definitions with structural induction.

Chapters 6–8: Set Theory; Properties of Functions; Properties of Relations

Chapter 6 covers the element method of proof, properties of sets, disproofs and algebraic proofs, and a closing section on Boolean algebras, Russell's paradox and the halting problem. Chapter 7 studies functions on general sets, one-to-one, onto and inverse functions, composition, and cardinality with applications to computability. Chapter 8 treats relations on sets, reflexivity, symmetry and transitivity, equivalence relations, modular arithmetic with applications to cryptography, and partial order relations.

Chapter 9: Counting and Probability

Chapter 9 runs from an introduction through possibility trees and the multiplication rule, the addition rule, the pigeonhole principle, combinations, r-combinations with repetition allowed, Pascal's formula and the binomial theorem, probability axioms and expected value, and conditional probability, Bayes' formula and independent events.

Chapters 10–12: Theory of Graphs and Trees; Analysis of Algorithm Efficiency; Regular Expressions and Finite-State Automata

Chapter 10 covers trails, paths and circuits, matrix representations of graphs, isomorphisms, trees and rooted trees, and spanning trees with a shortest path algorithm. Chapter 11 introduces real-valued functions and their graphs, O-, Ω- and Θ-notations, exponential and logarithmic functions, and two applications to analysing the efficiency of algorithms. Chapter 12 covers formal languages and regular expressions, finite-state automata, and simplifying finite-state automata.

Key Concepts

Chapters 1–4: Language, logic and proof

• Logical form and equivalence: the basis for analysing compound statements in Chapter 2.
• Quantified statements: Chapter 3's treatment of predicates, multiple quantifiers and arguments with quantifiers.
• Direct proof, counterexample and indirect argument: the proof methods taught in Chapter 4 using number theory.
• Quotient-remainder theorem: the division result introduced in Section 4.5.

Chapters 5–8: Induction, sets, functions, relations

• Mathematical induction and strong induction: the proof techniques of Sections 5.2–5.4, with structural induction in 5.9.
• Recurrence relations: solved by iteration (5.7) and, for the second-order linear homogeneous case, by a general method (5.8).
• Element method of proof: the way set properties are proved in Chapter 6.
• Equivalence relations and partial orders: the relation types of Chapter 8.

Chapters 9–12: Counting, graphs, algorithms and automata

• Pigeonhole principle, combinations and the binomial theorem: the counting tools of Chapter 9.
• Bayes' formula and expected value: the probability topics at the end of Chapter 9.
• Big-O, Omega and Theta notation: the notation of Chapter 11.
• Finite-state automata: the machines of Chapter 12.

Critical Analysis

Strengths

• Proof is taught, not assumed. Chapter 1 begins with the language of mathematics, Chapters 2–3 with logic, and Chapter 4 spreads direct proof, writing advice and indirect arguments over ten sections. Cengage's description says the book is "known for its accessible, precise approach" and emphasises the reasoning that underlies mathematical thought. The fifth edition revised the sections on quantifier use, the concept of proof, proof-writing advice and set-theory proofs.
• Worked examples with a two-step structure. According to Cengage's feature list, the book has over 500 worked examples in problem-solution format, and proof solutions are developed in two steps: a discussion of how to approach the proof, then a summary of the solution. Students can choose a faster or slower pace.
• A large exercise supply. The publisher reports more than 2,500 exercises, including applied problems and new exercise types that guide students through completing proofs in the online system.
• Computer science applications. Cengage lists a large number of computer science applications, and the contents bear this out: digital logic circuits and binary addition (2.4–2.5), algorithm correctness (5.5), cryptography with modular arithmetic (8.4), analysis of algorithm efficiency (11.3, 11.5) and automata (Chapter 12). New material in the fifth edition covers binary search trees, cryptographic hash functions and message authentication.

Limitations

• Counting and graphs come late. Counting, probability and graphs arrive only in Chapters 9–10 (Chapter 1 introduces the language of graphs briefly), so a course centred on combinatorics or graph theory has to skip ahead; the publisher says the organisation allows core and optional topics to be mixed.
• No dedicated number theory or cryptography chapter. Number theory appears as the vehicle for proof in Chapter 4 and cryptography as an application of modular arithmetic in Section 8.4; readers wanting a fuller treatment need another source.
• Length. The Asia edition is listed at 984 pages, a lot for a first course; instructors need to select chapters, and the organisation is intended to allow that.

Where It Fits in the Course

Epp is the proof-centred text in this course list. Rosen's Discrete Mathematics and Its Applications covers a wider range of topics in a more reference-like format and is a good second book, or an alternative for students who already reason comfortably. Oscar Levin's Discrete Mathematics: An Open Introduction is a free, inquiry-based introduction organised around counting, sequences, graph theory and logic, suited to students meeting mathematical reasoning for the first time; László Lovász, József Pelikán and Katalin Vesztergombi's Discrete Mathematics: Elementary and Beyond is a short, problem-driven book that works well alongside it. Graham, Knuth and Patashnik's Concrete Mathematics and van Lint and Wilson's A Course in Combinatorics are for later study: sums, recurrences and generating functions for the analysis of algorithms in the first, a graduate-level combinatorics text in the second.

How to Use This Book

Epp is aimed at students who need to learn how to read and write mathematical arguments while meeting the discrete structures used in computer science. It assumes school algebra and some comfort with symbols; calculus is not required.

A practical plan:

• Core (Chapters 1–5): read in order. Chapters 2–4 are where the habits of proof are built, and Section 4.2 (writing advice) is worth reading before any proof-writing assignment.
• Structures (Chapters 6–8): sets, functions and relations; these supply the vocabulary for almost everything later.
• Counting and graphs (Chapters 9–10): the combinatorial core of the book.
• Optional (Chapters 11–12): analysis of algorithms and automata suit students heading into computer science courses.

Work the exercises in each section, and use the worked examples as models for how to structure your own written proofs.