Discrete Mathematics
8th Edition
Published on 24. July 2013
Book
Hardback
768 pages
978-0-321-96468-7 (ISBN)
Description
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.
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.
More details
Edition
8th edition
Language
English
Place of publication
United States
Publishing group
Pearson Education (US)
Target group
College/higher education
Dimensions
Height: 257 mm
Width: 206 mm
Thickness: 30 mm
Weight
1370 gr
ISBN-13
978-0-321-96468-7 (9780321964687)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Person
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.
Content
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
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