For one-/two- semester, freshman courses in Discrete Mathematics. This carefully organized, very readable text covers every essential topic in discrete mathematics in a logical fashion. Placing each topic in context, it covers concepts associated with discrete mathematical systems that have applications in computer science, engineering, and mathematics. The author introduces more basic concepts at the freshman level than are found in other texts, in a simple, accessible form. Introductory material is balanced with extensive coverage of graphs, trees, recursion, algebra, theory of computing, and combinatorics. Extensive examples throughout the text reinforce concepts.
Preface
While there are many discrete mathematics books on the market, none of the available books covers the desired range and depth of topics in discrete mathematics in this book and also works in a theme on how to do proofs. Proofs are introduced in the first chapter and continued throughout the book. Most students taking discrete mathematics are mathematics and computer science majors. While 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.
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 the basic chapters.
This book is intended for either a one- or two-term course in discrete mathematics. The first eight chapters of this book provide a solid foundation in discrete mathematics and would be appropriate for a first-level course at the freshman or sophomore level. These chapters are essentially independent so that the instructor can pick the material he 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 includes
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.
Tree—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 text, 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 continually become more advanced throughout the book.
Relations and graphs are introduced in Chapter 2. Relations lead naturally into functions, which are introduced 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 6. 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 this chapter.
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 9 the basics of number theory are developed. These chapters are necessary for applications of number theory in Chapter 23 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 covers probability, which is not common in most other discrete mathematics books.
Chapters 9 and 20 cover the basic concepts of algebra including semigroups, groups rings, 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 package. 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-23 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 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 a knowledge of matrices, found in Chapters 4 and 5. Codes are explored from yet another direction in Chapter 23 where cryptography is introduced. This chapter is dependent on the previous chapters on number theory.
In Chapter 19, algebra and combinatorics 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 is particularly relevant to computer science.
When teaching a beginning course, I normally cover Chapters 1-5 in their entirety, Sections 8.1-8.3 and try to cover the first three sections of Chapter 6. As mentioned previously, the material in the first eight chapters is arranged for maximal flexibility. SUPPLEMENTS
A solutions manual is available from the publisher with complete solutions to all problems. A website is available at prenhall/janderson. This website includes links to other interesting sites in discrete mathematics, quizzes, and additional problems. ACKNOWLEDGMENTS
First I would like to thank George Lobell for his leadership in the development of this book and Barbara Mack for coordinating our efforts. I would like to thank Kristin and Philip Musik for their excellent artwork. I am especially grateful to James Bell for the tremendous amount of work that he has contributed. I am sorry that he was unable to co-author this book with me. I miss having him as a partner. I would also like to thank my colleagues Dan Cooke, Ed Wilde, Rick Chow, M. B. Ulmer, and Jerome Lewis for their help. I would like to thank Soledad Sugai for the errors she found while a student in my course. I would also like to thank students Jody Dean, Jessica Dones, Grace Ellison, Vinny Chin Fai Ip, Priscilla Lapierre, Esther Ly, Badral Madani, Julie Norris, Tracy Quin and Robert Wiegert, who survived the first voyage through this material.
Please feel free to e-mail me with comments and suggestions for future improvements.
James A. Anderson
janderson@gw.uscs
