This book equips readers to apply discrete mathematics and provides opportunities for practice of the concepts presented. Coverage of algorithms is included. Combinatorics receives more coverage than in other books.

*"synopsis" may belong to another edition of this title.*

This book has been written for a sophomore-level course in Discrete Mathematics. The material has been directed towards the needs of mathematics and computer science majors, although there is certainly material that is of use for other majors. Students are assumed to have completed a semester of college-level calculus. This assumption is primarily about the level of mathematical maturity of the readers. The material in a calculus course will not often be used in the text.

This textbook has been designed to be suitable for a course that requires students to read the textbook. Many students find this challenging, preferring to just let the instructor tell them "everything they need to know" and using the textbook as a repository of homework exercises and corresponding examples. A typical course in Discrete Mathematics will require much more from the students. Consequently, the textbook needs to support this transition towards greater mathematical maturity.

I have successfully used this text by requiring students to read a section and submit some simple exercises from that section at the start of a class period where I discuss the material for the first time. The following class period, the students will submit more difficult exercises. Consequently, extra care has been taken to ensure that students can follow the presentation in the book even before the material is presented in class. While most instructors do not structure their course in this manner, a textbook that has been written to stand on its own will certainly be of value to the students.

I imagine that this book will work well with a distance education format. However, I feel that personal interaction between the student and the instructor (or a knowledgeable teaching assistant) greatly enhances the learning experience.

**DISTINGUISHING CHARACTERISTICS OF THIS TEXT**

There are currently many textbooks on the market for a course in Discrete Mathematics. Although there is an assumed common core of topics and level, there is still sufficient variation to provide instructors with viable options for choosing a textbook. Here are some of the features that characterize this book.

- There is a heavy emphasis on proof throughout the text (as indicated by the book's title). The formal setting is introduced in Chapter 2 as sets, logic, and Boolean algebras are discussed. Chapter 3 then discusses axiomatic mathematics as a system and subsequently focuses on proof techniques. The proof techniques are extensively illustrated in the rest of the text. For example: proof by contradiction in Chapter 4 with The Halting Problem; constructive proofs in Chapter 8 with "a finite projective plane of order
*n*iff*n*— 1 mutually orthogonal Latin squares of order*n*"; complete induction in Chapter 3 with the "optimality (for suitors) of the Deferred Acceptance Algorithm". Combinatorial proof is introduced in Chapter 5 and used in Chapter 8 to establish the necessary conditions for the existence of a balanced incomplete block design.

Many of the more difficult proofs are accompanied by illustrative examples that can be read in parallel with the proof. For instance, Theorem 8.20 on page 486 and Examples 8.49 and 8.50 that appear after the proof. - The text has been written for students to read actively. The text contains more detailed explanations than some competing texts. Homework problems have been designed to reinforce reading. Most cannot be completed by merely finding a clone example to copy and modify. The chapters include Quick Check problems at critical points in the reading. These are problems that should be solved before continuing to read. Detailed solutions are presented at the end of the chapter.
- Technology is introduced when it will enhance understanding. For example: a simple perl script for testing regular expressions in Chapter 9; a Java Application (and Applet) that allows students to rubber-band graphs to check for planarity in Chapter 10; several applications that explore the inner workings of recursion in Chapter 7; a Java Application (and Applet) for checking Quine-McCluskey minimizations of binary expressions in Chapter 12. There are also web links to Applets that animate critical algorithms and structures: Boyer-Moore in Chapter 4; finite automata in Chapter 9; logic circuits in Chapter 12. These can all be found at:

**http://www.prenhall.com/gossett/**

or

**http://www.mathcs.bethel.edu/~gossett/DiscreteMathWithProof/** - Combinatorics receives a full chapter (Chapter 8) beyond the standard "combinations and permutations" material presented in Chapter 5. The non-standard topics include Latin squares, finite projective planes, balanced incomplete block designs, coding theory, knapsack problems, Ramsey numbers, partitions, occupancy problems, Stirling numbers, and systems of distinct representatives. The chapter begins with an overview of the major themes that unify the field of combinatorics.
- There are several major examples that present significant algorithms. Examples include: Chapter 1: the Deferred Acceptance Algorithm (the Stable Marriage Problem); Chapter 4: Boyer-Moore algorithm for pattern matching; Chapter 7: recursive algorithms for Sierpinski curves, persian rugs, and adaptive quadrature.

Other examples cover problems with a significant history. Examples include: Chapter 7: the Josephus problem; Chapter 8: Kirkman's Schoolgirl Problem; Chapter 10: the 5 regular polyhedra and a proof of the Five Color Theorem.

There are also some important examples from the field of computer science. These include: Chapter 4: The Halting problem; Chapter 9: Shannon's mathematical model of information; Chapter 11: XML; and Chapter 12: Normal Forms in relational databases - The Discrete Mathematics course at Bethel College is equally populated with mathematics majors and computer science majors. Consequently, this text was designed to be appropriate for courses for mathematics majors, courses for computer science majors, and courses with bimodal populations. There is sufficient material to design a one-semester course for any of these three options. It is also possible to design a two-semester course that covers the entire book.

An example of using the text with a bimodal group can be found in the chapter on recursion. Chapter 7 starts with an algorithmic approach and then presents recurrence relations (a mathematical approach). Both sets of students see the concept (recursion) in a form that is oriented towards their own major. In addition, they are exposed to an alternative viewpoint. - Several other topics receive more coverage than is typical. These include: Chapter 4: expressing algorithms, the Halting Problem; Chapter 6: Bayes' Theorem; several topics in Chapter 8; Chapter 9: regular expressions.
- The text begins with an introductory chapter that provides some explanation and examples of what discrete mathematics is about. This is rare among discrete mathematics textbooks.
- Limitations are discussed where appropriate. For example, the solution of linear homogeneous recurrence relations with constant coefficients that is presented in Chapter 7 requires the factorization of polynomials. There is no general factorization technique for polynomials of degree 6 or higher. The text also contains guidelines to determine whether recursion is an appropriate solution technique for a particular problem.
- An instructor's solution manual with detailed solutions to every problem is available for use by student graders and professors. Appendix G is a free student's solution manual containing detailed solutions to selected exercises.

**TEXT ORGANIZATION**

The chapters in the book are briefly summarized in the following paragraphs.

**Chapter 1: Introduction**

Chapter h provides a working definition of *discrete mathematics* and then offers the reader some brief glimpses at some of the topics that will be covered in the remaining chapters. The chapter also introduces the stable marriage problem and the deferred acceptance algorithm. This material is covered in some detail and appears again in several other chapters.

The exposition of the stable marriage problem introduces a non-trivial algorithm and some proofs. The problem, the algorithm, and the proofs are all fairly intuitive. They prepare the reader for the more detailed expositions of algorithms and proofs that will follow in future chapters. The problem also shows the reader that the material in this course may be different from what they have studied in previous mathematics courses.

**Chapter 2: Sets, Logic, and Boolean Algebras**

Much of the material in this chapter is not what students tend to rate as most interesting. However, it is foundational to much of what follows. It is even more important than in previous decades because many students are now graduating from high school without ever learning the basics of set theory. Many have never been exposed to either the basic terminology (element, union, intersection) or the standard notation (E, U, f1).

The basic concepts of propositional and predicate logic are introduced in this chapter. They also serve as a basis for the proof strategies introduced in chapter 3.

The basic properties of sets and logic are presented in a similar style to emphasize the similarities. This parallel exposition provides a natural introduction to Boolean algebras. Boolean algebras serve to unify some important aspects of set theory and logic. The early introduction also provides a nontrivial example of an axiomatic system. This example can then be recalled when the axiomatic system is more formally introduced in chapter 3.

The chapter also contains brief sections on informal logic and analyzing claims. Both sections...

*"About this title" may belong to another edition of this title.*

Published by
Prentice Hall
(2002)

ISBN 10: 0130669482
ISBN 13: 9780130669483

New
Hardcover
Quantity Available: 1

Seller

Rating

**Book Description **Prentice Hall, 2002. Book Condition: New. Brand New, Unread Copy in Perfect Condition. A+ Customer Service!. Bookseller Inventory # ABE_book_new_0130669482

More Information About This Seller | Ask Bookseller a Question

Published by
Prentice Hall
(2002)

ISBN 10: 0130669482
ISBN 13: 9780130669483

New
Hardcover
Quantity Available: 1

Seller

Rating

**Book Description **Prentice Hall, 2002. Hardcover. Book Condition: New. United States ed. Bookseller Inventory # DADAX0130669482

More Information About This Seller | Ask Bookseller a Question

Published by
Prentice Hall
(2002)

ISBN 10: 0130669482
ISBN 13: 9780130669483

New
Hardcover
Quantity Available: 1

Seller

Rating

**Book Description **Prentice Hall, 2002. Hardcover. Book Condition: New. book. Bookseller Inventory # 0130669482

More Information About This Seller | Ask Bookseller a Question

Published by
Prentice Hall
(2002)

ISBN 10: 0130669482
ISBN 13: 9780130669483

New
Hardcover
Quantity Available: 3

Seller

Rating

**Book Description **Prentice Hall, 2002. Hardcover. Book Condition: New. Bookseller Inventory # P110130669482

More Information About This Seller | Ask Bookseller a Question

Published by
Prentice Hall

ISBN 10: 0130669482
ISBN 13: 9780130669483

New
Hardcover
Quantity Available: 1

Seller

Rating

**Book Description **Prentice Hall. Hardcover. Book Condition: New. 0130669482 New Condition. Bookseller Inventory # NEW4.0044739

More Information About This Seller | Ask Bookseller a Question

ISBN 10: 0130669482
ISBN 13: 9780130669483

New
Quantity Available: 1

Seller

Rating

**Book Description **Book Condition: Brand New. Book Condition: Brand New. Bookseller Inventory # 97801306694831.0

More Information About This Seller | Ask Bookseller a Question