Discrete Mathematics and Its Applications

by ROSEN

• ISBN13: 9780070539655
• ISBN10: 0070539650
• Edition: 3rd
• Copyright: 1995-01-01
• Publisher: MCG

Table of Contents

Preface	xi	(10)
To the Student	xxi
1 The Foundations: Logic, Sets, and Functions	1	(96)
1.1 Logic	1	(12)
1.2 Propositional Equivalences	13	(8)
1.3 Predicates and Quantifiers	21	(16)
1.4 Sets	37	(9)
1.5 Set Operations	46	(12)
1.6 Functions	58	(13)
1.7 Sequences and Summations	71	(8)
1.8 The Growth of Functions	79	(10)
Key Terms and Results	89	(3)
Review Questions	92	(1)
Supplementary Exercises	93	(2)
Computer Projects	95	(1)
Computations and Explorations	95	(1)
Writing Projects	96	(1)
2 The Fundamentals: Algorithms, the Integers, and Matrices	97	(71)
2.1 Algorithms	98	(6)
2.2 Complexity of Algorithms	104	(7)
2.3 The Integers and Division	111	(15)
2.4 Integers and Algorithms	126	(10)
2.5 Applications of Number Theory	136	(14)
2.6 Matrices	150	(12)
Key Terms and Results	162	(1)
Review Questions	163	(1)
Supplementary Exercises	164	(2)
Computer Projects	166	(1)
Computations and Explorations	166	(1)
Writing Projects	167	(1)
3 Mathematical Reasoning	168	(63)
3.1 Methods of Proof	169	(14)
3.2 Mathematical Induction	183	(18)
3.3 Recursive Definitions	201	(10)
3.4 Recursive Algorithms	211	(6)
3.5 Program Correctness	217	(7)
Key Terms and Results	224	(1)
Review Questions	225	(1)
Supplementary Exercises	226	(3)
Computer Projects	229	(1)
Computations and Explorations	229	(1)
Writing Projects	230	(1)
4 Counting	231	(76)
4.1 The Basics of Counting	232	(11)
4.2 The Pigeonhole Principle	243	(7)
4.3 Permutations and Combinations	250	(11)
4.4 Discrete Probability	261	(7)
4.5 Probability Theory	268	(14)
4.6 Generalized Permutations and Combinations	282	(11)
4.7 Generating Permutations and Combinations	293	(5)
Key Terms and Concepts	298	(2)
Review Questions	300	(1)
Supplementary Exercises	301	(4)
Computer Projects	305	(1)
Computations and Explorations	305	(1)
Writing Projects	306	(1)
5 Advanced Counting Techniques	307	(48)
5.1 Recurrence Relations	307	(11)
5.2 Solving Recurrence Relations	318	(7)
5.3 Divide-and-Conquer Relations	325	(7)
5.4 Inclusion-Exclusion	332	(7)
5.5 Applications of Inclusion-Exclusion	339	(10)
Key Terms and Results	349	(1)
Review Questions	350	(1)
Supplementary Exercises	351	(2)
Computer Projects	353	(1)
Computations and Explorations	353	(1)
Writing Projects	354	(1)
6 Relations	355	(74)
6.1 Relations and Their Properties	355	(11)
6.2 n-ary Relations and Their Applications	366	(7)
6.3 Representing Relations	373	(8)
6.4 Closures of Relations	381	(12)
6.5 Equivalence Relations	393	(9)
6.6 Partial Orderings	402	(17)
Key Terms and Results	419	(2)
Review Questions	421	(1)
Supplementary Exercises	422	(4)
Computer Projects	426	(1)
Computations and Explorations	427	(1)
Writing Projects	427	(2)
7 Graphs	429	(102)
7.1 Introduction to Graphs	429	(8)
7.2 Graph Terminology	437	(12)
7.3 Representing Graphs and Graph Isomorphism	449	(13)
7.4 Connectivity	462	(10)
7.5 Euler and Hamilton Paths	472	(16)
7.6 Shortest Path Problems	488	(11)
7.7 Planar Graphs	499	(10)
7.8 Graph Coloring	509	(11)
Key Terms and Results	520	(2)
Review Questions	522	(1)
Supplementary Exercises	523	(5)
Computer Projects	528	(1)
Computations and Explorations	529	(1)
Writing Projects	529	(2)
8 Trees	531	(77)
8.1 Introduction to Trees	531	(16)
8.2 Applications of Trees	547	(7)
8.3 Tree Traversal	554	(17)
8.4 Trees and Sorting	571	(9)
8.5 Spanning Trees	580	(13)
8.6 Minimum Spanning Trees	593	(7)
Key Terms and Results	600	(2)
Review Questions	602	(1)
Supplementary Exercises	603	(3)
Computer Projects	606	(1)
Computations and Explorations	607	(1)
Writing Projects	607	(1)
9 Boolean Algebra	608	(43)
9.1 Boolean Functions	609	(7)
9.2 Representing Boolean Functions	616	(5)
9.3 Logic Gates	621	(8)
9.4 Minimization of Circuits	629	(16)
Key Terms and Results	645	(1)
Review Questions	646	(1)
Supplementary Exercises	646	(3)
Computer Projects	649	(1)
Computations and Explorations	649	(1)
Writing Projects	650	(1)
10 Modeling Computation	651
10.1 Languages and Grammars	652	(11)
10.2 Finite-State Machines with Output	663	(9)
10.3 Finite-State Machines with No Output	672	(10)
10.4 Language Recognition	682	(12)
10.5 Turing Machines	694	(9)
Key Terms and Results	703	(1)
Review Questions	704	(1)
Supplementary Exercises	705	(3)
Computer Projects	708	(1)
Computations and Explorations	709	(1)
Writing Projects	709
Appendixes	A-0
A.1 Exponential and Logarithmic Functions	A-0	(3)
A.2 Pseudocode	A-3	(6)
A.3 Generating Functions	A-9
Suggested Readings	B-0
Solutions to Odd-Numbered Exercises	S-1
Index of Biographies	I-0
Index	I-1