Preface
As the discipline of computer science has matured, it has become clear that a study of dis-
crete mathematical topics is an essential part of the computer science major. The course in
discrete structures has two primary aims. The first is to introduce students to the rich math-
ematical structures that naturally describe much of the content of the computer science
discipline, including many structures that are frequently used in modeling and implement-
ing solutions to problems. The second is to help students develop the skills of mathematical
reasoning to learn new concepts and material in computer science. This learning takes place
not only while they are students but also after graduation and throughout their professional
life.
During the past few years, researchers in areas of computer science as diverse as
the analysis of algorithms, database systems, and artificial intelligence have made ever-
increasing use of discrete mathematical structures to clarify and explain key concepts and
problems. As a reflection of this emphasis, careful discussions of applications such as a
relational database system, the complexity of a computation, and normal forms of propo-
sitions are included in this text. The discussions of these topics build on a strong, focused
development of fundamental ideas about sets, logic, relations, and functions as well as
graph theory and combinatorics.
The diagram that follows gives an indication of the order in which the material can
be covered. The six chapters referred to in the box contain the fundamental topics. These
chapters are used to guide students in learning how to express mathematically precise ideas
in the language of mathematics.
The two chapters dealing with graph theory and combinatorics are also core material
for a discrete structures course, but this material always seems more intuitive to students
than the formalism of the first four chapters. Topics from the first four chapters are freely
used in these later chapters. The chapter on discrete probability builds on the chapter on
combinatorics. The chapter on the analysis of algorithms uses notions from the core chap-
ters but can be presented at an informal level to motivate the topic without spending a lot of
time with the details of the chapter. Finally, the chapter on recurrence relations primarily
uses the early material on induction and an intuitive understanding of the chapter on the
analysis of algorithms.
xix