Discrete Mathematics with Proof

The book begins with an introductory chapter that provides some explanation and examples of what discrete mathematics is about, which is a unique feature to this discrete mathematics text. The formal setting is introduced in Chapter 2 where sets, logic, and Boolean algebra are discussed. Chapter 3 then discusses axiomatic mathematics as a system and subsequently focuses on proof techniques. The proof techniques are extensively illustrated throughout the rest of the book. For example, complete induction with the "optimality of the Deferred Acceptance Algorithm for suitors" in Chapter 3; proof by contradiction with The Halting Problem in Chapter 4; and constructive proofs with "a finite projective plane of order n iff n-1 mutually orthogonal Latin squares of order n" in Chapter 8. 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. Technology is introduced when it will enhance understanding. For example, several applications that explore the inner workings of recursion are presented in Chapter 7, a simple perl script (also a web page front-end to that script) that enables students to practice creating regular expressions is discussed in Chapter 9, and a java application that allows students to rubber-band graphs to check for planarity is featured in Chapter 10. Combinatorics receives more coverage than is typical, and additional unique topics include container problems (advanced counting), Latin squares, finite projective planes, balanced incomplete block designs, coding theory, Ramsey numbers, and systems of distinct representatives. Additional topical coverage includes counting, finite probability theory, recursion, formal models in computer science, graph theory, trees, the concepts of functions and relations. Several other topics receive more coverage than is typical, including expressing algorithms, Bayes' theorem, the Halting problem, and regular expressions.

Eric Gossett is Professor of Mathematics and Computer Science at Bethel University.