As in the first edition, the purpose of this book is to present an extensive range and depth of topics in discrete mathematics and also work in a theme on how to do proofs. Proofs are introduced in the first chapter and continue throughout the book. Most students taking discrete mathematics are mathematics and computer science majors. Although the necessity of learning to do proofs is obvious for mathematics majors, it is also critical for computer science students to think logically. Essentially, a logical bug-free computer program is equivalent to a logical proof. Also, it is assumed in this book that it is easier to use (or at least not misuse) an application if one understands why it works. With few exceptions, the book is self-contained. Concepts are developed mathematically before they are seen in an applied context.

Additions and alterations in the second edition:

• More coverage of proofs, especially in Chapter 1.
• Added computer science applications, such as a greedy algorithm for coloring the nodes of a graph, a recursive algorithm for counting the number of nodes on a binary search tree, or an efficient algorithm for computing a^b mod n for very large values of a, b, and n.
• An extensive increase in the number of problems in the first eight chapters.
• More problems are included that involve proofs.
• Additional material is included on matrices.
• Inclusion of finite states with output and Turing machines.
• True-False questions at the end of each chapter.
• Summary questions at the end of each chapter.
• A glossary at the end of each chapter.
• Functions and sequences are introduced earlier (in Chapter 2).

Calculus is not required for any of the material in this book. College algebra is adequate for the basic chapters. However, although this book is self-contained, some of the remaining chapters require more mathematical maturity than do the basic chapters, so calculus is recommended more for giving maturity, than for any direct uses.

This book is intended for either a one- or two-term course in discrete mathematics. The first eight chapters of this book provide a foundation in discrete mathematics and would be appropriate for a first-level course for freshmen or sophomores. These chapters are essentially independent, so that the instructor can pick the material he/she wishes to cover. The remainder of the book contains appropriate material for a second course in discrete mathematics. These chapters expand concepts introduced earlier and introduce numerous advanced topics. Topics are explored from different points of view to show how they may be used in different settings. The range of topics include:

• Logic—Including truth tables, propositional logic, predicate calculus, circuits, induction, and proofs.
• Set Theory—Including cardinality of sets, relations, partially ordered sets, congruence relations, graphs, directed graphs, and functions.
• Algorithms—Including complexity of algorithms, search and sort algorithms, the Euclidean algorithm, Huffman's algorithm, Prim's algorithms, Warshall's algorithm, the Ford-Fulkerson algorithm, the Floyd-Warshall algorithm, and Dijkstra's algorithms.
• Graph Theory—Including directed graphs, Euler cycles and paths, Hamiltonian cycles and paths, planar graphs, and weighted graphs.
• Trees—including binary search trees, weighted trees, tree transversal, Huffman's codes, and spanning trees.
• Combinatorics—including permutations, combinations, inclusion-exclusion, partitions, generating functions, Catalan numbers, Sterling numbers, Rook Polynomials, derangements, and enumeration of colors.
• Algebra—Including semigroups, groups, lattices, semilattices, Boolean algebras, rings, fields, integral domains, polynomials, and matrices.

There is extensive number theory and algebra in this book. I feel that this is a strength of this book, but realize that others may not want to cover these subjects. The chapters in these areas are completely independent of the remainder of the book and can be covered, or not, as the instructor desires. This book also contains probability, finite differences, and other topics not usually found in a discrete mathematics text.

Organization

The first three chapters cover logic and set theory. It is assumed in this book that an understanding of proofs is necessary for the logical construction of advanced computer programs.

The basic concepts of a proof are given and illustrated with numerous examples. In Chapter 2, the student is given the opportunity to prove some elementary concepts of set theory. In Chapter 3, the concept of an axiom system for number theory is introduced. The student is given the opportunity to prove theorems in a familiar environment. Proofs using induction are also introduced in this chapter. Throughout the remainder of the book, many proofs are presented and many of the problems are devoted to proofs. Problems, including proofs, begin at the elementary level and advance in level of difficulty `throughout the book.

Relations, functions, and graphs are introduced in Chapter 2. Functions are then continued in Chapter 4. However, the development of functions in Chapter 4 is independent of the material in Chapter 2. Similarly, the development of graphs in Chapter 6 does not depend on their development as relations in Chapter 2.

Matrices, permutations, and sequences are introduced in Chapter 4 as special types of functions. Further properties of functions and matrices follow in Chapter 5. Algorithms for matrices are introduced and further properties of matrices are developed, which will be used in later chapters on algebra, counting, and theory of codes.

Permutations are used for counting in Chapter 8 and also for applications in algebra and combinatorics in later chapters. Again, the material in Chapter 8, while related to Chapter 4, can be studied independently.

Chapter 5 is independent of the previous chapters except for the matrices in the previous chapter. Algorithms are developed, including sorting algorithms. The complexity of algorithms is also developed in this chapter. Prefix and suffix notation are introduced here. They are, again, discussed in Chapter 15 with regard to traversing binary trees. Binary and hexadecimal numbers are also introduced in Chapter 5.

Many elementary concepts of graphs, directed graphs, and trees are covered in Chapter 6. These concepts are covered in more depth in Chapters 14-16. Chapter 6 is independent of the previous chapters.

In Chapters 7 and 10, the basics of number theory are developed. These chapters are necessary for applications of number theory in Chapter 22, but are otherwise completely independent of the other chapters and may be omitted if desired.

Chapter 8 is the beginning of extensive coverage of combinatorics. This is continued in many of the chapters including Chapters 12, 13, and 17. Chapter 8 also introduces basic ideas in probability which is not common in most other discrete mathematics books.

Chapters 9 and 20 cover the basic concepts of algebra, including semigroups, groups, semilattices, lattices, rings, integral domains, and fields. These chapters use Sections 3.6, and 4.3 for examples of groups and rings. Chapter 9 is necessary for the applications in Chapters 17-21.

In many ways Chapters 11, 12, and 13 form a cluster. Recursion is continued in Chapter 11. In addition to the standard linear recurrence relations normally covered in a discrete mathematics text, the theory of finite difference is also covered. Chapter 6 should be covered before this chapter unless the student already has some knowledge of recursion. Chapter 12 continues the counting introduced in Chapter 8. It covers topics introduced in Chapter 8, such as occupancy problems and inclusion-exclusion. It also introduces derangements and rook polynomials. It is closely related to Chapter 11. Many of the same topics are covered from different points of view. One example of this is Stirling numbers. However neither chapter is dependent on the other.

Chapters 11 and 12 are tied together in Chapter 13, where generating functions are used to continue the material in both chapters. In particular, generating functions provide a powerful tool for the solution of occupancy problems.

Chapters 14-16 continue the study of trees and graphs begun in Chapter 6. They obviously depend on the material in Chapter 6, but are virtually independent of most of the preceding chapters. One exception is the use of matrices in some of the algorithms. Many of the standard topics of graphs and trees are covered, including planar graphs, Hamiltonian cycles, binary trees, spanning trees, minimal spanning trees, weighted trees, shortest path algorithms, and network flows.

Chapters 17-22 form another cluster consisting of number theory, algebra, combinatorics, and their application. The theory of computation is introduced in Chapter 17. This includes codes, regular languages, automata, grammars, Turing machines, and their relationship. This chapter uses semigroups from Section 9.2. Chapter 18 introduces special codes, such as error detecting codes and error correcting codes. This chapter requires knowledge of group theory, found in Section 9.4, and some knowledge of matrices, found in Chapters 4 and 5. Codes are explored from yet another direction in Chapter 22 where cryptography is introduced. This chapter is dependent on the previous chapters on number theory.

In Chapter 19, algebra and combinatorices are combined for the development of Burnside's Theorem and Polya's Theorem for the enumeration of colors. It primarily depends on a knowledge of permutations found in Section 9.4.

Chapter 21 is a simple application of groups and semigroups and their mapping onto the complex plane. The prerequisites for this chapter are Sections 9.2 and 9.4.

Chapter 22 gives three important applications of number theory. The study of Hashing functions and cryptography are particularly relevant to computer science.

When teaching a beginning course, I normally cover Chapters 1-5 in their entirety, Sections 8.1-8.5, and the first three sections Chapter 6. As mentioned previously, the material in the first eight chapters is arranged for maximal flexibility.