A discrete mathematics course has more than one purpose. Students should learn a particular
set of mathematical facts and how to apply them; more importantly, such a course should teach
students how to think logically and mathematically. To achieve these goals, this text stresses
mathematical reasoning and the different ways problems are solved. Five important themes
are interwoven in this text: mathematical reasoning, combinatorial analysis, discrete structures,
algorithmic thinking, and applications and modeling. A successful discrete mathematics course
should carefully blend and balance all five themes.
I. Mathematical Reasoning: Students must understand mathematical reasoning in order to
read, comprehend, and construct mathematical arguments. This text starts with a discussion
of mathematical logic, which serves as the foundation for the subsequent discussions of
methods of proof. Both the science and the art of constructing proofs are addressed. The
technique of mathematical induction is stressed through many different types of examples
of such proofs and a careful explanation of why mathematical induction is a valid proof
2. Combinatorial Analysis: An important problem-solving skill is the ability to count or enumerate objects. The discussion ofenumeration in this book begins with the basic techniques
of counting. The stress is on performing combinatorial analysis to solve counting problems
and analyze algorithms, not on applying formulae.
A course in discrete mathematics should teach students how to work
with discrete structures, which are the abstract mathematical structures used to represent
discrete objects and relationships between these objects. These discrete structures include
sets, permutations, relations, graphs, trees, and finite-state machines.
Certain classes of problems are solved by the specification of an
algorithm. After an algorithm has been described, a computer program can be constructed
implementing it. The mathematical portions ofthis activity, which include the specification of
the algorithm, the verification that it works properly, and the analysis ofthe computer memory
and time required to perform it, are all covered in this text. Algorithms are described using
both English and an easily understood form of pseudocode.
Discrete mathematics has applications to almost every conceivable area of study. There are many applications to computer science and data networking in
this text, as well as applications to such diverse areas as chemistry, botany, zoology, linguistics, geography, business, and the Internet. These applications are natural and important uses
of discrete mathematics and are not contrived. Modeling with discrete mathematics is an
extremely important problem-solving skill, which students have the opportunity to develop
by constructing their own models in some of the exercises.