About This Book
This book is intended for a one- or two-term introductory
course in discrete mathematics, based on my experience in teaching this course over
many years. Formal mathematics prerequisites are minimal; calculus is not required. There are no computer
science prerequisites. The book includes examples, exercises, figures, tables,
sections on problem-solving, sections containing problem-solving tips, section
reviews, notes, chapter reviews, self-tests, and computer exercises to help the
reader master introductory discrete mathematics.
In the early 1980s there were few textbooks appropriate
for an introductory course in discrete mathematics. However, there was a need
for a course that extended students’ mathematical maturity and ability to deal
with abstraction, which also included useful topics such as combinatorics,
algorithms, and graphs. The original edition of this book (1984) addressed this
need and significantly influenced the development of discrete mathematics
courses. Subsequently, discrete mathematics courses were endorsed by many
groups for several different audiences, including mathematics and computer
science majors. A panel of the Mathematical Association of America (MA)
endorsed a year-long course in discrete mathematics. The Educational Activities
Board of the
Changes from the Fifth Edition
The changes in the book result from comments and requests
from numerous users and reviewers of previous editions of the book. The changes
are as follows:
§
The
first chapter on logic and proofs has been considerably
expanded. The single section on quantifiers in the fifth edition has been
divided into two sections. The first quantifiers section (Section 1.3) deals
with singly quantified statements, and the following section (Section 1.4)
deals with nested quantifiers. The single section on mathematical induction in
the fifth edition has been divided into two sections. The first induction
section (Section 1.7) introduces induction in which the inductive step is:
Assume S(n), prove S(n+1). A discussion of loop invariants
has been added to this section. The second section (Section 1.8) continues with
strong induction and the well-ordering property. As an example of the use of
the well-ordering property, we prove the quotient-remainder theorem.
§
The
exposition, examples, and motivating material have been expanded throughout the
chapter. We have added examples of logic in programming languages (e.g., the
use of and, or, not, and De Morgan’s
laws). There is a more detailed explanation of necessary and sufficient
conditions. Examples have been added to show how ordinary English relates to
symbolic logic. Throughout the chapter there are more examples of proving statements
and how to construct proofs. In this chapter, the number of worked examples has
been increased from 59 to 90, and the number of exercises has been increased
from 391 to 521.
§
In
Chapter 2, a number of examples have been added to show how, using the material
in Chapter 1, to prove statements dealing with sets, functions, sequences, and
strings (e.g., how to prove that a
given function is one-to-one).
§
A
number of examples of algorithms are now presented before getting into big-oh and related notations (Sections 4.1 and
4.2), thus providing a gentler introduction and motivating the formalism that
follows. We mention that many modern algorithms do not have all the properties
of classical algorithms (e.g., many modern algorithms are not general, deterministic,
or even finite). To illustrate the point, an example is given of a randomized
algorithm (Example 4.2.4).
§
A
new chapter (Chapter 5) on introductory number theory combines some material
from the fifth edition (e.g., representation of integers, greatest common
divisor) and expands some topics (e.g., algorithmic number theory). This
chapter includes classical results (e.g., divisibility, the infinitude of
primes, fundamental theorem of arithmetic), as well as algorithmic number
theory [e.g., the Euclidean algorithm to find the greatest common divisor,
exponentiation using repeated squaring, computing s and t such that gcd(a,b)
= sa + tb, computing an inverse modulo an integer]. The major application
is the RSA public-key cryptosystem (Section 5.4). The calculations required by
the RSA public-key cryptosystem can be performed using the algorithms
previously developed in the chapter.
§
Problem-Solving
Tips sections have been added to the ends of many sections, especially in the
early chapters. As the name implies, these sections help students to focus on
the techniques required to solve the problems. Placed at the ends of sections,
Problem-Solving Tips review, highlight, and help tie together the
problem-solving techniques of the section.
§
There
are new Problem-Solving Corners on functions and number theory.
§
The
style of the pseudocode has been updated to Java-like (which also resembles C
and C++) from Pascal-like. Students will more likely be familiar with this
style. In addition, the description of the pseudocode has been moved to the
appendix (Appendix C), making it possible to bring in code examples earlier
(for those so inclined).
§
A
number of recent books and articles have been added to the list of references.
Several book references have been updated to current editions.
§
The
number of worked examples has been increased to nearly 600. (There were
approximately 500 in the fifth edition.)
§
The
number of exercises has been increased to nearly 4000. (There were
approximately 3500 in the fifth edition.)
Contents and Structure
This book includes
§
Logic
(including quantifiers), proofs, proofs by resolution, and mathematical
induction (Chapter 1). A logic game,
which offers an alternative way to determine whether a quantified propositional
function is true or false, is discussed in Example 1.4.15.
§
Sets,
functions, sequences, sum and product notations, strings, and relations
(Chapters 2 and 3), including motivating examples such as an introduction to
hash functions and pseudorandom number generators (Section 2.2), an application
of partial orders to task scheduling (Section 3.1), and relational databases
(Section 3.4).
§
A
thorough discussion of algorithms, recursive algorithms, and the analysis of
algorithms (Chapter 4). In addition, an algorithmic approach is taken
throughout this book. The algorithms are written in a flexible form of
pseudocode. (The book does not assume any computer science prerequisites; the
description of the pseudocode used is given in Appendix C.) Among the
algorithms presented are tiling (Section 4.4), the Euclidean algorithm for
finding the greatest common divisor (Section 5.3), the RSA public-key
encryption algorithm (Section 5.4), generating combinations and permutations
(Section 6.3), merge sort (Section 7.3), Dijkstra’s shortest-path algorithm
(Section 8.4), backtracking algorithms (Section 9.3), breadth-first and
depth-first search (Section 9.3), tree traversals (Section 9.6), evaluating a
game tree (Section 9.9), finding a maximal flow in a network (Section 10.2),
finding a closest pair of points (Section 13.1), and computing the convex hull
(Section 13.2).
§
A
full discussion of the “big oh,” omega, and theta notations for the growth of
functions (Section 4.3). Having all of these notations available makes it
possible to make precise statements about the growth of functions and the time
and space required by algorithms.
§
An
introduction to number theory (Chapter 5).
§
Combinations,
permutations, discrete probability, and the Pigeonhole Principle (Chapter 6).
Two optional sections (Sections 6.4 and 6.5) treat discrete probability.
§
Recurrence
relations and their use in the analysis of algorithms (Chapter 7).
§
Graphs,
including coverage of graph models of parallel computers, the knight’s tour,
Hamiltonian cycles, graph isomorphisms, and planar graphs (Chapter 8). Theorem
8.4.3 gives a simple, short, elegant proof of the correctness of Dijkstra’s
algorithm.
§
Trees,
including binary trees, tree traversals, minimal spanning trees, decision trees,
the minimum time for sorting, and tree isomorphisms (Chapter 9).
§
Networks,
the maximal flow algorithm, and matching (Chapter 10).
§
A
treatment of Boolean algebras that emphasizes the relation of Boolean algebras
to combinatorial circuits (Chapter 11).
§
An
approach to automata emphasizing modeling and applications (Chapter 12). The SR flip-flop circuit is discussed in
Example 12.1.11. Fractals, including the von Koch snowflake, are described by
special kinds of grammars (Example 12.3.19).
§
An
introduction to computational geometry (Chapter 13).
§
Appendixes
on matrices, basic algebra, and pseudocode.
§
A
strong emphasis on the interplay among the various topics. As examples,
mathematical induction is closely tied to recursive algorithms (Section 4.4); the
Fibonacci sequence is used in the analysis of the Euclidean algorithm (Section
5.3); many exercises throughout the book require mathematical induction; we
show how to characterize the components of a graph by defining an equivalence
relation on the set of vertices (see the discussion following Example 8.2.13);
and we count the number of n-vertex
binary trees (Theorem 9.8.12).
§
A
strong emphasis on reading and doing proofs. Most proofs of theorems are
illustrated with annotated figures. Separate sections (Problem-Solving Corners)
show students how to attack and solve problems and how to do proofs. Special
end-of-section Problem-Solving Tips highlight the main problem-solving
techniques of the section.
§
A
large number of applications, especially applications to computer science.
§
Figures
and tables to illustrate concepts, to show how algorithms work, to elucidate
proofs, and to motivate the material.
Several figures illustrate proofs of theorems. The captions of these
figures provide additional explanation and insight into the proofs.
§
Section
review exercises.
§
Notes
sections with suggestions for further reading.
§
Chapter
reviews.
§
Chapter
self-tests.
§
Computer
exercises.
§
A
reference section containing 159 references.
§
Front
and back endpapers that summarize the mathematical and algorithm notation used
in the book.
Each chapter is organized as follows:
Overview
Section
Section
Review Exercises
Section
Exercises
Section
Section
Review Exercises
Section
Exercises
.
.
.
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
Section review exercises review the key concepts,
definitions, theorems, techniques, and so on, of the section. All section
review exercises have answers in the back of the book. Although intended for
reviews of the sections, section review exercises can also be used for
placement and pretesting.
Notes contain suggestions for further reading. Chapter
reviews provide reference lists of the key concepts of the chapters. Chapter
self-tests contain four exercises per section, with answers in the back of the
book.
Computer exercises include projects, implementation of
some of the algorithms, and other programming related activities. Although there
is no programming prerequisite for this book and no programming is introduced
in the book, these exercises are provided for those readers who want to explore
discrete mathematics concepts with a computer.
In addition, most chapters have Problem-Solving Corners.
Exercises
The book contains nearly 4000 exercises, 147 of which are
computer exercises. Exercises felt to be more challenging than average are
indicated with a star Exercise numbers in color (approximately one-third of the
exercises) indicate that the exercise has a hint or solution in the back of the
book. The solutions to the remaining exercises may be found in the Instructor's Guide. A handful of
exercises are clearly identified as requiring calculus. No calculus concepts
are used in the main body of the book and, except for these marked exercises,
no calculus is needed to solve the exercises.
Examples
The book contains nearly 600 worked examples. These
examples show students how to tackle problems in discrete mathematics,
demonstrate applications of the theory, clarify proofs, and help motivate the
material.
Problem-Solving Corners
The Problem-Solving Corner sections help students attack
and solve problems and show them how to do proofs. Written in an informal
style, each is a self-contained section following the discussion of the subject
of the problem. Rather than simply presenting a proof or a solution to a
problem, in these sections the intent is to show alternative ways of attacking
a problem, to discuss what to look for in trying to obtain a solution to a
problem, and to present problem-solving and proof techniques.
Each Problem-Solving Corner begins with a statement of a
problem. After stating the problem, ways to attack the problem are discussed.
This discussion is followed by techniques for finding a solution. After a
solution is found, a formal solution is given to show how to correctly write up
a formal solution. Finally, the problem-solving techniques used in the section
are summarized. In addition, some of these sections include a Comments
subsection, which discusses connections with other topics in mathematics and
computer science, provides motivation for the problem, and lists references for
further reading about the problem. Exercises conclude some Problem-Solving
Corners.
Instructor Supplement
An Instructor's Guide is available at no cost from
the publisher to instructors who adopt or sample this book. It should be
requested from your local Prentice Hall representative. The Instructor’s Guide contains solutions to the exercises not included in the
book.