Discrete Mathematics, 8th edition

Published by Pearson (March 6, 2017) © 2018

  • 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
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.

Video
Play
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.

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.Â