About This Book
This updated edition is intended for a one- or two-term
introductory course in discrete mathematics, based on my experience in teaching
this course over many years and requests from users of previous editions.
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 (MAA)
endorsed a year-long course in discrete mathematics. The Educational Activities
Board of the
Logic and
Proofs Changes
The changes in this book, the seventh edition, result
from comments and requests from numerous users and reviewers of previous
editions of the book. The biggest change from the sixth to the seventh edition
occurs in Chapters 1–3. The first chapter in the sixth edition, Logic and
Proofs, has been divided into two chapters in the seventh edition: Logic
(Chapter 1) and Proofs (Chapter 2). Except for the section on sets, Chapters 2
(The Language of Mathematics) and 3 (Relations) in the sixth edition have been
combined into Chapter 3 (Functions, Sequences, and Relations) in the seventh
edition. Pre-publication reviews have been very enthusiastic about these
changes.
The section on sets is now the first section of the book.
This change permits the use of set terminology throughout the book. It makes
sets available for proofs in examples and exercises, thus providing more
interesting examples earlier than in the previous editions. We can even use
sets to introduce proofs (e.g., proving that two sets are equal, proving that
one set is a subset of another) before fully discussing proofs and proof
techniques.
The discussion about how to construct proofs has been
greatly expanded. Sections 2.1 and 2.2 are new extended sections on
mathematical systems and proof techniques. In addition, there are expanded
subsections on proofs of equivalence and existence proofs (including
constructive and nonconstructive existence proofs). Nearly every proof is
preceded by a Discussion section and/or accompanied by a figure. The
Problem-Solving Tips sections include expanded advice, examples, and so on, on
how to do proofs, how to write up proofs, and common errors in proofs. There
are two new Problem-Solving Corners, one on quantifiers, the other on proofs
(see Proving Some Properties of Real Numbers).
The discussion of arguments and rules of inference for
propositions has been moved to follow the discussion of propositions. The rules
of inference for quantified statements are integrated within the quantifiers
section.
The number of examples and exercises has been vastly
expanded. In the sixth edition, there were approximately 1370 worked examples
and exercises in the first three chapters. In the seventh edition, there are
approximately 1640 worked examples and exercises in the first three chapters.
Of course, not just the quantity of examples and exercises is important, it is
also the quality. In most of the examples found in the sixth edition, the
discussion has been expanded and additional motivation has been added.
Other Changes
from the Sixth Edition
Other changes from the sixth edition are as follows:
Ø The description and notation for
integers (Z, Z+, Z–,
Znonneg), rational
numbers with Z replaced by Q, and real numbers (with Z replaced by R) are introduced early (in Section 1.1, Sets).
Ø Proofs, rather than sketches of
proofs as in the sixth edition, are provided for Theorems 5.1.17 and 5.1.22,
which give the greatest common divisor and least common multiple of two
integers given their prime factorizations.
Ø Recursive algorithms are given
(Algorithms 5.3.9 and 5.3.10) to compute the greatest common divisor of two
integers a and b, gcd(a,b), and to compute integers s and t satisfying gcd(a,b) = sa
+ tb.
Ø The Inclusion-Exclusion Principle
has been added to Section 6.1.
Ø Internet addressing is now
included in Section 6.1.
Ø Several practice exercises have
been added to Section 6.1 that specifically say to use either the
Multiplication Principle or the Addition Principle. These exercises precede
other exercises that require the reader to figure out which Principle to use or
require using both Principles.
Ø The section on Generalized
Permutations and Combinations (Section 6.6 in the sixth edition) now follows
Sections 6.1 and 6.2 (Basic Principles, Permutations and Combinations) since
generalized permutations and combinations are so closely related to the
material in Sections 6.1 and 6.2.
Ø Several relatively
straightforward “warm-up” exercises have been added before the main pigeonhole
exercises (Section 6.8).
Ø More exercises on graph
isomorphism have been added (Section 8.6). The exercises have been divided into
those that ask for a proof that two given graphs are isomorphic, those that ask
for a proof that two given graphs are not isomorphic, and those that ask the
reader to determine, with a proof, whether two given graphs are isomorphic.
Ø In Section 9.3, there are several
new backtracking exercises including the popular Sudoku puzzle.
Ø More examples and exercises are
included to highlight common errors (for example, the subsection Some Common
Errors that precedes the Section 2.1 Review Exercises discusses some common
errors in proofs, and Example 6.2.24 illustrates a common counting error).
Ø 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 over 650. (There were approximately 600 in the sixth
edition.)
Ø The number of exercises has been
increased to nearly 4200. (There were approximately 4000 in the sixth edition.)
Contents and
Structure
This book includes
Ø Sets and logic (including
quantifiers). Practical examples such as using the Google search engine are
included (Example 1.2.13). Translating between English and symbolic expressions
is discussed as is logic in programming languages. A logic game, which offers an alternative way to determine whether a
quantified propositional function is true or false, is discussed in Example
1.6.15.
Ø Proofs (Chapter 2). Proof
techniques discussed include direct proofs, counterexamples, proof by
contradiction, proof by contrapositive, proofs by cases, proofs of equivalence,
existence proofs (constructive and nonconstructive), and mathematical
induction.
Ø Functions, sequences, sum and
product notations, strings, and relations (Chapter 3), including motivating
examples such as the new 13-character international standard book number
(ISBN), an introduction to hash functions, and pseudorandom number generators
(Section 3.1); an application of partial orders to task scheduling (Section
3.3); and relational databases (Section 3.6).
Ø A thorough discussion of
algorithms, recursive algorithms, and the analysis of algorithms (Chapter 4). A
number of examples of algorithms are presented before getting into big-oh and
related notations (Sections 4.1 and 4.2), thus providing a gentle introduction
and motivating the formalism that follows. An algorithmic approach is taken
throughout this book. 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). The algorithms are written in
a flexible form of pseudocode, which resembles currently popular languages such
as C, C++, and Java. (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.4), 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). 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.
Ø Combinations, permutations,
discrete probability, and the Pigeonhole Principle (Chapter 6). Two optional
sections (Sections 6.5 and 6.6) 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 nonisomorphic 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
and/or motivated by special Discussion sections. 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
more than 160 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 4200 exercises, 145 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. 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 over 650 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.