Discrete Mathematics, 8th edition

Richard Johnsonbaugh DePaul University

eTextbook

per month

Anytime, anywhere learning with the Pearson+ app
Easy-to-use search, navigation and notebook
Simpler studying with flashcards

Print

from$133.32

Hardcover, paperback or looseleaf edition
Affordable rental option for select titles

For 1- or 2-term introductory courses in Discrete Mathematics.

An accessible introduction that helps expand students' mathematical maturity

Discrete Mathematics, 8th Edition provides ample opportunities to practice, apply and demonstrate conceptual understanding. Exercise sets feature a large number of applications, especially to computer science. Worked examples provide ready reference for students as they work. It models various problem-solving techniques in detail, then encourages students to practice these techniques; it 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. URLs throughout direct students to relevant applications, extensions, and computer programs.

Hallmark features of this title

Problem Solving Corners help students attack and solve problems, and show them how to do proofs.
Strong emphasis on reading and writing proofs illustrates most proofs of theorems with annotated figures to provide additional explanation and insight into the proofs.
Extensive discussion of algorithms, recursive algorithms, and the analysis of algorithms: Algorithms are written in a flexible form of pseudocode resembling languages such as C, C++ and Java.
Figures and tables illustrate concepts, show how algorithms work, elucidate proofs, and motivate the material.
Short URLs give easy access to corresponding web pages, especially with a mobile device.

New and updated features of this title

Additional real-world examples provide more context for ideas and concepts. Also, 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 3 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.
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.

1. Sets and Logic

1.1 Sets
1.2 Propositions
1.3 Conditional Propositions and Logical Equivalence
1.4 Arguments and Rules of Inference
1.5 Quantifiers
1.6 Nested Quantifiers
Problem-Solving Corner: Quantifiers

2. Proofs

2.1 Mathematical Systems, Direct Proofs, and Counterexamples
2.2 More Methods of Proof
Problem-Solving Corner: Proving Some Properties of Real Numbers
2.3 Resolution Proofs
2.4 Mathematical Induction
Problem-Solving Corner: Mathematical Induction
2.5 Strong Form of Induction and the Well-Ordering Property

3. Functions, Sequences, and Relations

3.1 Functions
Problem-Solving Corner: Functions
3.2 Sequences and Strings
3.3 Relations
3.4 Equivalence Relations
Problem-Solving Corner: Equivalence Relations
3.5 Matrices of Relations
3.6 Relational Databases

4. Algorithms

4.1 Introduction
4.2 Examples of Algorithms
4.3 Analysis of Algorithms
Problem-Solving Corner: Design and Analysis of an Algorithm
4.4 Recursive Algorithms

5. Introduction to Number Theory

5.1 Divisors
5.2 Representations of Integers and Integer Algorithms
5.3 The Euclidean Algorithm
Problem-Solving Corner: Making Postage
5.4 The RSA Public-Key Cryptosystem

6. Counting Methods and the Pigeonhole Principle

6.1 Basic Principles
Problem-Solving Corner: Counting
6.2 Permutations and Combinations
Problem-Solving Corner: Combinations
6.3 Generalized Permutations and Combinations
6.4 Algorithms for Generating Permutations and Combinations
6.5 Introduction to Discrete Probability
6.6 Discrete Probability Theory
6.7 Binomial Coefficients and Combinatorial Identities
6.8 The Pigeonhole Principle

7. Recurrence Relations

7.1 Introduction
7.2 Solving Recurrence Relations
Problem-Solving Corner: Recurrence Relations
7.3 Applications to the Analysis of Algorithms

8. Graph Theory

8.1 Introduction
8.2 Paths and Cycles
Problem-Solving Corner: Graphs
8.3 Hamiltonian Cycles and the Traveling Salesperson Problem
8.4 A Shortest-Path Algorithm
8.5 Representations of Graphs
8.6 Isomorphisms of Graphs
8.7 Planar Graphs
8.8 Instant Insanity

9. Trees

9.1 Introduction
9.2 Terminology and Characterizations of Trees
Problem-Solving Corner: Trees
9.3 Spanning Trees
9.4 Minimal Spanning Trees
9.5 Binary Trees
9.6 Tree Traversals
9.7 Decision Trees and the Minimum Time for Sorting
9.8 Isomorphisms of Trees
9.9 Game Trees

10. Network Models

10.1 Introduction
10.2 A Maximal Flow Algorithm
10.3 The Max Flow, Min Cut Theorem
10.4 Matching
Problem-Solving Corner: Matching

11. Boolean Algebras and Combinatorial Circuits

11.1 Combinatorial Circuits
11.2 Properties of Combinatorial Circuits
11.3 Boolean Algebras
Problem-Solving Corner: Boolean Algebras
11.4 Boolean Functions and Synthesis of Circuits
11.5 Applications

12. Automata, Grammars, and Languages

12.1 Sequential Circuits and Finite-State Machines
12.2 Finite-State Automata
12.3 Languages and Grammars
12.4 Nondeterministic Finite-State Automata
12.5 Relationships Between Languages and Automata

13. Computational Geometry

13.1 The Closest-Pair Problem
13.2 An Algorithm to Compute the Convex Hull

Appendices

A. Matrices
B. Algebra Review
C. Pseudocode

References

Hints and Solutions to Selected Exercises

Index

About our author

Richard Johnsonbaugh is Professor Emeritus of Computer Science, Telecommunications and Information Systems, DePaul University, Chicago. Prior to his 20-year service at DePaul University, he was a member and sometime chair of the mathematics departments at Morehouse College and Chicago State University. He has a B.A. degree in mathematics from Yale University, M.A. and Ph.D. degrees in mathematics from the University of Oregon, and an M.S. degree in computer science from the University of Illinois, Chicago. His most recent research interests are in pattern recognition, programming languages, algorithms, and discrete mathematics. He is the author or co-author of numerous books and articles in these areas. Several of his books have been translated into various languages. He is a member of the Mathematical Association of America.

Need help? Get in touch

Pearson+
All in one place. Pearson+ offers instant access to eTextbooks, videos and study tools in one intuitive interface. Students choose how they learn best with enhanced search, audio and flashcards. The Pearson+ app lets them read where life takes them, no wi-fi needed. Students can access Pearson+ through a subscription or their MyLab or Mastering course.

Privacy and cookies

By watching, you agree Pearson can share your viewership data for marketing and analytics for one year, revocable by deleting your cookies.

Video transcript (PDF | 16KB)

Pearson eTextbook: What’s on the inside just might surprise you

They say you can’t judge a book by its cover. It’s the same with your students. Meet each one right where they are with an engaging, interactive, personalized learning experience that goes beyond the textbook to fit any schedule, any budget, and any lifestyle.