For one- or two-term introductory courses in discrete mathematics.

An accessible introduction to the topics of discrete math, this best-selling text also works to expand students’ mathematical maturity.

With nearly 4,500 exercises, Discrete Mathematics provides ample opportunities for students to practice, apply, and demonstrate conceptual understanding. Exercise sets features a large number of applications, especially applications to computer science. The almost 650 worked examples provide ready reference for students as they work. A strong emphasis on the interplay among the various topics serves to reinforce understanding. The text models various problem-solving techniques in detail, then provides opportunity to practice these techniques. The text also builds mathematical maturity by emphasizing how to read and write proofs. Many proofs are illustrated with annotated figures and/or motivated by special Discussion sections. The side margins of the text now include “tiny URLs” that direct students to relevant applications, extensions, and computer programs on the textbook website.

Extend students’ mathematical maturity and ability to deal with abstraction

• Strong emphasis on reading and writing proofs — Illustrates most proofs of theorems with annotated figures to provide additional explanation and insight into the proofs.

  • EXPANDED! More than 100 new exercises have been added to the first three chapters: Sets and Logic, Proofs, and Functions, Sequences, and Relations. There are now more than 1,750 worked examples and exercises in these chapters.
  • Problem Solving Corners, a hallmark feature that helps students attack and solve problems and show them how to do proofs.
• Extensive discussion of algorithms, recursive algorithms, and the analysis of algorithms — The algorithms are written in a flexible form of pseudocode, which resembles currently popular languages such as C, C++, and Java.
• Extensive applications with an emphasis on computer science. Approximately 150 computer exercises are included throughout the book.
• Emphasis on the interplay among the various topics — For example, mathematical induction is closely tied to recursive algorithms; the Fibonacci sequence is used in the analysis of the Euclidean algorithm; many exercises throughout the book require mathematical induction; demonstrations of how to characterise the components of a graph by defining an equivalence relation on the set of vertices; and more.
• Figures and tables — Illustrate concepts, show how algorithms work, elucidate proofs, and motivate the material. Figure captions provide additional explanation and insight into figures accompanying proofs.
• Summaries of the mathematical and algorithmic notation used in the book on the inside covers.

Breadth of examples and exercises help students master introductory discrete mathematics

• Nearly 4,500 exercises and 650 worked examples.
• EXPANDED! More than 300 new exercises increase the total to nearly 4,500. The previous edition featured approximately 4,200.
• UPDATED! Nearly 650 worked problems examples show students how to tackle problems, demonstrate applications of the theory, and clarify proofs.
• UPDATED! Chapter self-test exercises read more like real exams, no longer identifying relevant sections within the exercises. Hints to these exercises identify relevant sections for further reference.
• EXPANDED! Additional real-world examples provide more context for complex ideas and concepts.
• Additional exercises give examples of algebraic systems in which prime factorisation does not hold.

About the Book

• Short URLs give easy access to corresponding web pages, especially with a mobile device. These URLs replace previous web icons to create a more web-friendly experience.
• Chapter self-test exercises read more like real exams, no longer identifying relevant sections within the exercises. Hints to these exercises identify relevant sections for further reference.

• Updates to examples include:

  • Additional real-world examples provide more context for ideas and concepts.
  • Examples that are worked problems now clearly identify where the solution begins and ends.
  • Examples have been added to illustrate diverse approaches to developing proofs and alternative ways to prove a particular result.

• More than 300 new exercises increase the total to nearly 4,500.

  • More than 100 new exercises and examples have been added to the first three chapters: Sets and Logic; Proofs; and Functions, Sequences, and Relations. There are now more than 1,750 worked examples and exercises in these chapters.
  • Exercises have been added to give an example of an algebraic system in which prime factorization does not hold.
• Recent books and articles have been added to the list of references, with several updated book references.

Content Updates

• Chapter 3 has an altered definition of sequence (Definition 3.2.1) to provide more generality and make subsequent discussion smoother (e.g., the discussion of subsequences).
• Chapter 5 now has exercises added (Exercises 40–49, Section 5.1) to give an example of an algebraic system in which prime factorization does not hold.
• Chapter 6 contains an application of the binomial theorem used to prove Fermat’s little theorem (Exercises 40 and 41, Section 6.7).
• Chapter 7 now has the Closest-Pair Problem (Section 13.1 in the seventh edition) integrated. The algorithm to solve the closest-pair problem is based on merge sort, which is discussed and analyzed in Chapter 7. Chapter 13 in the seventh edition, which has now been removed, had only one additional section.
• Chapter 8 now has a randomized algorithm to search for a Hamiltonian cycle in a graph (Algorithm 8.3.10).