Discrete Mathematics, 8th edition
Published by Pearson (March 6, 2017) © 2018
- Richard Johnsonbaugh DePaul University
eTextbook
- Anytime, anywhere learning with the Pearson+ app
- Easy-to-use search, navigation and notebook
- Simpler studying with flashcards
- 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