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 Institute of Electrical and Electronics Engineers (IEEE) recommended a freshman discrete mathematics course. The Association for Computing Machinery (ACE) and IEEE accreditation guidelines mandated a discrete mathematics course. This edition, like its predecessors, includes topics such as algorithms, combinatorics, sets, functions, and mathematical induction endorsed by these groups. It also addresses understanding and constructing proofs and, generally, expanding mathematical maturity.

 

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 Instructors Guide contains solutions to the exercises not included in the book.