Discrete Mathematics, 7th Edition
©2009 |Pearson | Out of print
Richard Johnsonbaugh, DePaul University
©2009 |Pearson | Out of print
For a one- or two-term introductory course in discrete mathematics.
Focused on helping students understand and construct proofs and expanding their mathematical maturity, this best-selling text is an accessible introduction to discrete mathematics. Johnsonbaugh’s algorithmic approach emphasizes problem-solving techniques. The Seventh Edition reflects user and reviewer feedback on both content and organization.
• 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 – The algorithms are written in a flexible form of pseudocode, which resembles currently popular languages such as C, C++, and Java.
• Over 500 worked examples throughout the text.
• Over 3500 exercises – Approximately one third have answers at the back of the book.
• Extensive applications with an emphasis on computer science.
• 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 characterize 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 algorithm notation used in the book on the inside covers.
• Increased number of examples and exercises throughout:
– Also expands discussion and adds motivation for most of the examples.
– More examples and exercises are included to highlight common errors
• Expanded treatment of problem solving:
– Problem-Solving Tips sections include expanded advice and examples on how to do proofs, how to write up proofs, and common errors in proofs.
– Two new Problem-Solving Corners have been added, one on quantifiers, the other on proofs (see Proving Some Properties of Real Numbers).
• Expanded discussion of proof writing:
– Sections 2.1 and 2.2 are new extended sections on mathematical systems and proof techniques.
– There are expanded subsections on proofs of equivalence and existence proofs (including constructive and nonconstructive existence proofs).
– Nearly every proof is preceded by a Discussion section and/or accompanied by a figure.
Reorganization of introductory chapters:
– The first chapter from the previous edition (Logic and Proofs) has been divided into two chapters – Logic (Chapter 1) and Proofs (Chapter 2).
– Except for the section on sets, Chapters 2 (The Language of Mathematics) and 3 (Relations) in the sixth edition have been combined into Chapter 3 (Functions, Sequences, and Relations) in this revision.
• Earlier introduction of sets – Now the first section of the book.
– Permits the use of set terminology throughout the book.
– Makes sets available for proofs in examples and exercises, thus providing more interesting examples earlier than in the previous editions.
• Content-specific changes:
– The description and notation for integers (Z, Z+ , Z− , Znonneg), rational numbers (with Z replaced by Q), and real numbers (with Z replaced by R) are introduced early (in Section 1.1, Sets).
– Proofs, rather than sketches of proofs as in the sixth edition, are provided for Theorems 5.1.17 and 5.1.22, which give the greatest common divisor and least common multiple of two integers given their prime factorizations.
– Recursive algorithms are given (Algorithms 5.3.9 and 5.3.10) to compute the greatest common divisor of two integers a and b, gcd(a, b), and to compute integers s and t satisfying gcd(a, b) = sa + tb.
– The Inclusion-Exclusion Principle has been added to Section 6.1.
– Internet addressing is now included in Section 6.1.
– Several practice exercises have been added to Section 6.1 that specifically say to use either the Multiplication Principle or the Addition Principle. These exercises precede other exercises that require the reader to figure out which Principle to use or require using both Principles.
– The section on Generalized Permutations and Combinations (Section 6.6 in the sixth edition) now follows Sections 6.1 and 6.2 (Basic Principles, Permutations and Combinations) since generalized permutations and combinations are so closely related to the material in Sections 6.1 and 6.2.
– More exercises on graph isomorphism have been added (Section 8.6). The exercises have been divided into those that ask for a proof that two given graphs are isomorphic, those that ask for a proof that two given graphs are not isomorphic, and those that ask the reader to determine, with a proof, whether two given graphs are isomorphic.
– In Section 9.3, there are several new backtracking exercises including the popular Sudoku puzzle.
• Updated Web site at http://condor.depaul.edu/~rjohnson/dm7th/
– Includes expanded explanations of difficult material and links to other sites for additional information about discrete mathematics topics.
– A WWW icon signals that an expanded explanation or a link is at the book’s web site.
– Also includes supplementary material, computer programs, and an errata list.
1 Sets and Logic
1.3 Conditional Propositions and Logical Equivalence
1.4 Arguments and Rules of Inference
1.6 Nested Quantifiers
Problem-Solving Corner: Quantifiers
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 Notes Chapter Review Chapter Self-Test Computer Exercises
3 Functions, Sequences, and Relations
Problem-Solving Corner: Functions
3.2 Sequences and Strings
3.4 Equivalence Relations
Problem-Solving Corner: Equivalence Relations
3.5 Matrices of Relations
3.6 Relational Databases
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.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.2 Solving Recurrence Relations
Problem-Solving Corner: Recurrence Relations
7.3 Applications to the Analysis of Algorithms
8 Graph Theory
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.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.2 A Maximal Flow Algorithm
10.3 The Max Flow, Min Cut Theorem
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
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
B Algebra Review
Hints and Solutions to Selected Exercises Index
Pearson offers affordable and accessible purchase options to meet the needs of your students. Connect with us to learn more.
K12 Educators: Contact your Savvas Learning Company Account General Manager for purchase options. Instant Access ISBNs are for individuals purchasing with credit cards or PayPal.
Savvas Learning Company is a trademark of Savvas Learning Company LLC.
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.
We're sorry! We don't recognize your username or password. Please try again.
The work is protected by local and international copyright laws and is provided solely for the use of instructors in teaching their courses and assessing student learning.
You have successfully signed out and will be required to sign back in should you need to download more resources.