As the discipline of computer science has matured, it has become clear that a study of discrete 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 mathematical structures that naturally describe much of the content of the computer science discipline, including many structures that are frequently used in modeling and implementing 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 everincreasing 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 propositions 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 chapters 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.