Discrete Mathematics

by Ross, Kenneth A.; Wright, Charles R.B.

• ISBN13: 9780130652478
• ISBN10: 0130652474
• Edition: 5th
• Format: Paperback
• Copyright: 2002-08-21
• Publisher: Pearson

Summary

Key Benefit:This book presents a sound mathematical treatment that increases smoothly in sophistication.Key Topics:The book presents utility-grade discrete math tools so that any reader can understand them, use them, and move on to more advanced mathematical topics.Market:A handy reference for computer scientists.

Table of Contents

Preface to the Fifth Edition	xi
To the Student Especially	xv
Sets, Sequences, and Functions	1	(49)
Some Warm-up Questions	1	(6)
Factors and Multiples	7	(9)
Office Hours	15	(1)
Some Special Sets	16	(6)
Set Operations	22	(6)
Functions	28	(6)
Sequences	34	(5)
Properties of Functions	39	(11)
Office Hours	46	(2)
Supplementary Exercises	48	(2)
Elementary Logic	50	(45)
Informal Introduction	50	(8)
Propositional Calculus	58	(8)
Getting Started with Proofs	66	(5)
Methods of Proof	71	(6)
Office Hours	76	(1)
Logic in Proofs	77	(9)
Analysis of Arguments	86	(9)
Supplementary Exercises	94	(1)
Relations	95	(33)
Relations	95	(5)
Digraphs and Graphs	100	(6)
Matrices	106	(6)
Equivalence Relations and Partitions	112	(7)
The Division Algorithm and Integers Mod p	119	(9)
Supplementary Exercises	127	(1)
Induction and Recursion	128	(53)
Loop Invariants	128	(9)
Mathematical Induction	137	(8)
Office Hours	144	(1)
Big-Oh Notation	145	(8)
Recursive Definitions	153	(7)
Recurrence Relations	160	(7)
More Induction	167	(4)
The Euclidean Algorithm	171	(10)
Supplementary Exercises	179	(2)
Counting	181	(44)
Basic Counting Techniques	181	(8)
Elementary Probability	189	(8)
Inclusion-Exclusion and Binomial Methods	197	(7)
Counting and Partitions	204	(9)
Office Hours	212	(1)
Pigeon-Hole Principle	213	(12)
Supplementary Exercises	220	(5)
Introduction to Graphs and Trees	225	(44)
Graphs	225	(7)
Edge Traversal Problems	232	(7)
Trees	239	(5)
Rooted Trees	244	(7)
Vertex Traversal Problems	251	(6)
Minimum Spanning Trees	257	(12)
Supplementary Exercises	266	(3)
Recursion, Trees, and Algorithms	269	(49)
General Recursion	269	(8)
Recursive Algorithms	277	(9)
Depth-First Search Algorithms	286	(12)
Polish Notation	298	(6)
Weighted Trees	304	(14)
Supplementary Exercises	315	(3)
Digraphs	318	(31)
Digraphs Revisited	318	(7)
Weighted Digraphs and Scheduling Networks	325	(8)
Office Hours	333	(1)
Digraph Algorithms	333	(16)
Supplementary Exercises	347	(2)
Discrete Probability	349	(40)
Independence in Probability	349	(10)
Random Variables	359	(7)
Expectation and Standard Deviation	366	(8)
Probability Distributions	374	(15)
Supplementary Exercises	387	(2)
Boolean Algebra	389	(35)
Boolean Algebras	389	(9)
Boolean Expressions	398	(7)
Logic Networks	405	(7)
Karnaugh Maps	412	(5)
Isomorphisms of Boolean Algebras	417	(7)
Supplementary Exercises	422	(2)
More on Relations	424	(38)
Partially Ordered Sets	424	(9)
Special Orderings	433	(6)
Multiplication of Matrices	439	(7)
Properties of General Relations	446	(6)
Closures of Relations	452	(10)
Supplementary Exercises	459	(3)
Algebraic Structures	462	(53)
Groups Acting on Sets	462	(8)
Fixed Points and Subgroups	470	(6)
Counting Orbits	476	(11)
Group Homomorphisms	487	(8)
Semigroups	495	(6)
Other Algebraic Systems	501	(14)
Supplementary Exercises	512	(3)
Predicate Calculus and Infinite Sets	515	(21)
Quantifiers and Predicates	515	(7)
Elementary Predicate Calculus	522	(5)
Infinite Sets	527	(9)
Supplementary Exercises	534	(2)
Dictionary	536	(2)
Answers and Hints	538	(69)
Index	607

Excerpts

In writing this book we have had in mind both computer science students and mathematics majors. We have aimed to make our account simple enough that these students can learn it and complete enough that they won't have to learn it again. The most visible changes in this edition are the 274 new supplementary exercises and the new chapters on probability and on algebraic structures. The supplementary exercises, which have complete answers in the back of the book, ask more than 700 separate questions. Together with the many end-of-section exercises and the examples throughout the text, these exercises let students practice using the material they are studying. One of our main goals is the development of mathematical maturity. Our presentation starts with an intuitive approach that becomes more and more rigorous as the students' appreciation for proofs and their skill at building them increase. Our account is careful but informal. As we go along, we illustrate the way mathematicians attack problems, and we show the power of an abstract approach. We and our colleagues at Oregon have used this material successfully for many years to teach students who have a standard precalculus background, and we have found that by the end of two quarters they are ready for upperclass work in both computer science and mathematics. The math majors have been introduced to the mathematics culture, and the computer science students have been equipped to look at their subject from both mathematical and operational perspectives. Every effort has been made to avoid duplicating the content of mainstream computer science courses, but we are aware that most of our readers will be coming in contact with some of the same material in their other classes, and we have tried to provide them with a clear,mathematicalview of it. An example of our approach can be seen first in Chapter 4, where we give a careful account of while loops. We base our discussion of mathematical induction on these loops, and also, in Chapter 4 and subsequently, show how to use them to design and verify a number of algorithms. We have deliberately stopped short of looking at implementation details for our algorithms, but we have provided most of them with time complexity analyses. We hope in this way to develop in the reader the habit of automatically considering the running time of any algorithm. In, addition, our analyses illustrate the use of some of the basic tools we have been developing for estimating efficiency. The overall outline of the book is essentially that of the fourth edition, with the addition of two new chapters and a large number of supplementary exercises. The first four chapters contain what we regard as the core material of any serious discrete mathematics course. These topics can readily be covered in a quarter. A semester course can add combinatorics and some probability or can pick up graphs, trees, and recursive algorithms. We have retained some of the special features of previous editions, such as the development of mathematical induction from a study of while loop invariants, but we have also looked for opportunities to improve the presentation, sometimes by changing notation. We have gone through the book section by section looking for ways to provide more motivation, with the result that many sections now begin where they used to end, in the sense that the punch lines now appear first as questions or goals that get resolved by the end of the section. We have added another "Office Hours" section at the end of Chapter 1, this one emphasizing the importance of learning definitions and notation. These sections, which we introduced in the fourth edition, allow us to step back a bit from our role as text authors to address the kinds of questions that our own students have Asked. They give us a chance to suggest how to study the material and focus on what's important. You may want to reinforce our words, or you may wa