Discrete Mathematics

by Johnsonbaugh, Richard

• ISBN13: 9780135182420
• ISBN10: 0135182425
• Edition: 4th
• Format: Hardcover
• Copyright: 1996-07-01
• Publisher: Pearson College Div

Summary

Mild revision of top selling text. This text has the best coverage of topics in computer science. New edition features new Mathematician's Corner which is found in each chapter and shows students how to do proofs.

Table of Contents

1 LOGIC AND PROOFS	1	(62)
1.1 Propositions	2	(6)
1.2 Conditional Propositions and Logical Equivalence	8	(10)
1.3 Quantifiers	18	(16)
1.4 Proofs	34	(8)
1.5 Resolution Proofs	42	(4)
1.6 Mathematical Induction	46	(10)
Problem-Solving Corner: Mathematical Induction	56	(3)
Notes	59	(1)
Chapter Review	59	(2)
Chapter Self-Test	61	(2)
2 THE LANGUAGE OF MATHEMATICS	63	(79)
2.1 Sets	64	(9)
2.2 Sequences and Strings	73	(11)
2.3 Number Systems	84	(7)
2.4 Relations	91	(13)
Problem-Solving Corner: Relations	102	(2)
2.5 Equivalence Relations	104	(10)
Problem-Solving Corner: Equivalence Relations	111	(3)
2.6 Matrices of Relations	114	(4)
2.7 Relational Databases	118	(7)
2.8 Functions	125	(11)
Notes	136	(1)
Chapter Review	137	(2)
Chapter Self-Test	139	(3)
3 ALGORITHMS	142	(55)
3.1 Introduction	143	(1)
3.2 Notation for Algorithms	144	(7)
3.3 The Euclidean Algorithms	151	(6)
3.4 Recursive Algorithms	157	(9)
3.5 Complexity of Algorithms	166	(20)
Problem-Solving Corner: Design and Analysis of an Algorithm	182	(4)
3.6 Analysis of the Euclidean Algorithm	186	(3)
3.7 The RSA Public-Key Cryptosystem	189	(4)
Notes	193	(1)
Chapter Review	193	(1)
Chapter Self-Test	194	(3)
4 COUNTING METHODS AND THE PIGEONHOLE PRINCIPLE	197	(59)
4.1 Basic Principles	197	(13)
Problem-Solving Corner: Counting	207	(3)
4.2 Permutations and Combinations	210	(18)
Problem-Solving Corner: Combinations	225	(3)
4.3 Algorithms for Generating Permutations and Combinations	228	(7)
4.4 Generalized Permutations and Combinations	235	(7)
4.5 Binomial Coefficients and Combinatorial Identities	242	(6)
4.6 The Pigeonhole Principle	248	(5)
Notes	253	(1)
Chapter Review	253	(1)
Chapter Self-Test	254	(2)
5 RECURRENCE RELATIONS	256	(48)
5.1 Introduction	256	(14)
5.2 Solving Recurrence Relations	270	(17)
Problem-Solving Corner: Recurrence Relations	284	(3)
5.3 Applications to the Analysis of Algorithms	287	(15)
Notes	302	(1)
Chapter Review	302	(1)
Chapter Self-Test	302	(2)
6 GRAPH THEORY	304	(72)
6.1 Introduction	305	(11)
6.2 Paths and Cycles	316	(15)
Problem-Solving Corner: Graphs	330	(1)
6.3 Hamiltonian Cycles and the Traveling Salesperson Problem	331	(7)
6.4 A Shortest-Path Algorithm	338	(6)
6.5 Representations of Graphs	344	(6)
6.6 Isomorphisms of Graphs	350	(9)
6.7 Planar Graphs	359	(7)
6.8 Instant Insanity	366	(5)
Notes	371	(1)
Chapter Review	371	(1)
Chapter Self-Test	372	(4)
7 TREES	376	(79)
7.1 Introduction	377	(8)
7.2 Terminology and Characterizations of Trees	385	(7)
Problem-Solving Corner: Trees	390	(2)
7.3 Spanning Trees	392	(8)
7.4 Minimal Spanning Trees	400	(8)
7.5 Binary Trees	408	(7)
7.6 Tree Traversals	415	(7)
7.7 Decision Trees and the Minimum Time for Sorting	422	(7)
7.8 Isomorphisms of Trees	429	(11)
7.9 Game Trees	440	(10)
Notes	450	(1)
Chapter Review	450	(1)
Chapter Self-Test	451	(4)
8 NETWORK MODELS AND PETRI NETS	455	(45)
8.1 Network Models	456	(6)
8.2 A Maximal Flow Algorithm	462	(11)
8.3 The Max Flow, Min Cut Theorem	473	(5)
8.4 Matching	478	(8)
Problem-Solving Corner: Matching	484	(2)
8.5 Petri Nets	486	(10)
Notes	496	(1)
Chapter Review	497	(1)
Chapter Self-Test	498	(2)
9 BOOLEAN ALGEBRAS AND COMBINATORIAL CIRCUITS	500	(46)
9.1 Combinatorial Circuits	500	(9)
9.2 Properties of Combinatorial Circuits	509	(7)
9.3 Boolean Algebras	516	(8)
Problem-Solving Corner: Boolean Algebras	522	(2)
9.4 Boolean Functions and Synthesis of Circuits	524	(7)
9.5 Applications	531	(11)
Notes	542	(1)
Chapter Review	542	(1)
Chapter Self-Test	543	(3)
10 AUTOMATA, GRAMMARS, AND LANGUAGES	546	(47)
10.1 Sequential Circuits and Finite-State Machines	546	(8)
10.2 Finite-State Automata	554	(8)
10.3 Languages and Grammars	562	(11)
10.4 Nondeterministic Finite-State Automata	573	(9)
10.5 Relationships Between Languages and Automata	582	(7)
Notes	589	(1)
Chapter Review	590	(1)
Chapter Self-Test	590	(3)
11 COMPUTATIONAL GEOMETRY	593	(17)
11.1 The Closest-Pair Problem	593	(5)
11.2 A Lower Bound for the Closest-Pair Problem	598	(3)
11.3 An Algorithm to Compute the Convex Hull	601	(7)
Notes	608	(1)
Chapter Review	609	(1)
Chapter Self-Test	609	(1)
APPENDIX: MATRICES	610	(5)
REFERENCES	615	(6)
HINTS AND SOLUTIONS TO SELECTED EXERCISES	621	(66)
INDEX	687