Discrete Mathematics, Fifth Edition
By Kenneth A. Ross and Charles R. B. Wright
Contents:
Preface to the Fifth Edition xi
To the Student Especially xv
1 Sets, Sequences, and Functions 1
1.1 Some Warm-up Questions 1
1.2 Factors and Multiples 7
Office Hours 15
1.3 Some Special Sets 16
1.4 Set Operations 22
1.5 Functions 28
1.6 Sequences 34
1.7 Properties of Functions 39
Office Hours 46
Supplementary Exercises 48
2 Elementary Logic 50
2.1 Informal Introduction 50
2.2 Propositional Calculus 58
2.3 Getting Started with Proofs 66
2.4 Methods of Proof 71
Office Hours 76
2.5 Logic in Proofs 77
2.6 Analysis of Arguments 86
Supplementary Exercises 94
3 Relations 95
3.1 Relations 95
3.2 Digraphs and Graphs 100
3.3 Matrices 106
3.4 Equivalence Relations and Partitions 112
3.5 The Division Algorithm and Integers Mod p 119
Supplementary Exercises 127
4 Induction and Recursion 128
4.1 Loop Invariants 128
4.2 Mathematical Induction 137
Office Hours 144
4.3 Big-Oh Notation 145
4.4 Recursive Definitions 153
4.5 Recurrence Relations 160
4.6 More Induction 167
4.7 The Euclidean Algorithm 171
Supplementary Exercises 179
5 Counting 181
5.1 Basic Counting Techniques 181
5.2 Elementary Probability 189
5.3 Inclusion-Exclusion and Binomial Methods 197
5.4 Counting and Partitions 204
Office Hours 212
5.5 PigeonHole Principle 213
Supplementary Exercises 220
6 Introduction to Graphs and Trees 225
6.1 Graphs 225
6.2 Edge Traversal Problems 232
6.3 Trees 239
6.4 Rooted Trees 244
6.5 Vertex Traversal Problems 251
6.6 Minimum Spanning Trees 257
Supplementary Exercises 266
7 Recursion, Trees, and Algorithms 269
7.1 General Recursion 269
7.2 Recursive Algorithms 277
7.3 Depth-First Search Algorithms 286
7.4 Polish Notation 298
7.5 Weighted Trees 304
Supplementary Exercises 315
8 Digraphs 318
8.1 Digraphs Revisited 318
8.2 Weighted Digraphs and Scheduling Networks 325
Office Hours 333
8.3 Digraph Algorithms 333
Supplementary Exercises 347
9 Discrete Probability 349
9.1 Independence in Probability 349
9.2 Random Variables 359
9.3 Expectation and Standard Deviation 366
9.4 Probability Distributions 374
Supplementary Exercises 387
10 Boolean Algebra 389
10.1 Boolean Algebras 389
10.2 Boolean Expressions 398
10.3 Logic Networks 405
10.4 Kamaugh Maps 412
10.5 Isomorphisms of Boolean Algebras 417
Supplementary Exercises 422
11 More on Relations 424
11.1 Partially Ordered Sets 424
11.2 Special Orderings 433
11.3 Multiplication of Matrices 439
11.4 Properties of General Relations 446
11.5 Closures of Relations 452
Supplementary Exercises 459
12 Algebraic Structures 462
12.1 Groups Acting on Sets 462
12.2 Fixed Points and Subgroups 470
12.3 Counting Orbits 476
12.4 Group Homomorphisms 487
12.5 Semigroups 495
12.6 Other Algebraic Systems 501
Supplementary Exercises 512
13 Predicate Calculus and Infinite Sets 515
13.1 Quantifiers and Predicates 515
13.2 Elementary Predicate Calculus 522
13.3 Infinite Sets 527
Supplementary Exercises 534
Dictionary 536
Answers and Hints 538
Index 607
Preface to the Fifth Edition:
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, mathematical view 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 want to take issue
with them when you talk with your own students. In any case, the Office Hours
provide an alternative channel for us to talk with our readers without being formal,
and perhaps they will help your students open up with their own questions in class
or in the office.
We have always believed that students at this level learn best from examples,
so we have added examples to the large number already present and have revised
others, all to encourage students to read the book. Our examples are designed to
accompany and illustrate the mathematical ideas as we develop them. They let
the instructor spend time on selected topics in class and assign reading to fill
out the presentation. Operating in this way, we have found that we can normally
cover a section a day in class. The instructor’s manual, available from Prentice
Hall, indicates which sections might take longer and contains a number of suggestions
for emphasis and pedagogy, as well as complete answers to all end-ofsection
exercises.
The end-of-chapter supplementary questions, which are a new feature of this
edition, are designed to give students practice at thinking about the material. We see
these exercises as representative of the sorts of questions students should be able to
answer after studying a chapter. We have deliberately not arranged them in order of
difficulty, and we have deliberately also not keyed them to sections-indeed, many
of the exercises bring together material from several sections. To see what we mean,
look at the supplementary exercises for Chapter 5, on combinatorics, where we have
included an especially large number of problems, many of which have a variety
of essentially different parts. A few of the supplementary questions, such as the
ones in Chapter 12 on algorithms to solve the Chinese Remainder and Polynomial
Interpolation problems, also extend the text account in directions that would have
interrupted the flow of ideas if included in the text itself. Some of the questions
are very easy and some are harder, but none of them are meant to be unusually
difficult. In any case, we have provided complete answers to all of them, not just the
odd-numbered ones, in the back of the book, where students can use them to check
their understanding and to review for exams.
The new chapters on probability and algebraic structures respond to requests
from current and past users who were disappointed that we had dropped these topics
in going from the third edition to the fourth. Since those were two of our favorite
chapters, we were happy to reinstate them and we have taken this opportunity to
completely revise each of them. In Chapter 9 we now work in the setting of discrete
probability, with only tantalizing, brief allusions to continuous probability, most
notably in the transition to normal distributions from binomial distributions. The
material on semigroups, rings, and fields in Chapter 12 is not changed much from
the account in the third edition, but the discussion of groups is dramatically different.
The emphasis is still on how groups act on sets, but in the context of solving some
intriguing combinatoric problems we can develop basic abstract ideas of permutation
group theory without getting bogged down in the details of cycle notation. As another
response to reader feedback, we have moved the section on matrix multiplication
from Chapter 3 to Chapter 11, which is the first place we need it.
Naturally, we think this edition is a substantial improvement and worth all of
the effort it has taken. We hope you will agree. We welcome any comments and
of course especially welcome reports of errors or misprints that we can correct in
subsequent printings.
Supplements
The Instructor’s Resource Manual, which course instructors may obtain gratis from
Prentice Hall, contains complete answers to all exercises in the text. In addition,
Prentice Hall publishes inexpensive student workbooks of practice problems on discrete
mathematics, with full solutions to all exercises. The Prentice Hall Companion
Web site for this text contains information about such materials.
Acknowledgments
This is a better book because of the many useful suggestions from our colleagues
and correspondents Patrick Brewer, William Kantor, Richard M. Koch, Eugene Luks,
George Matthews, Christopher Phillips, and Brad Shelton. Dick Koch’s gentle questions
and suggestions, based on his incisive ideas and point of view, were especially
helpful. We also benefitted from suggestions provided by the following reviewers
and other anonymous reviewers: Dr. Johannes Hattingh, Georgia State University;
Bharti Temkin, Texas Tech; Marjorie Hicks, Georgia State University; and Timothy
Ford, Florida Atlantic University.
Thanks are also due to our wonderful production editor, Bob Walters, and to
the superb compositors at Laserwords. Our editor for this edition was George Lobell,
whose suggestions for improvements and overall support have been as helpful as his
guidance through the production process.
KENNETH A. Ross
ross@ math.uoregon.edu
CHARLES R. B. WRIGHT
wright@math.uoregon.edu