This book has three great strengths: it provides an excellent introduction to rigorous concepts from first principles, while avoiding excessive formalism; it is very successful in illustrating concepts and techniques which may seem highly abstract to a student who first encounters them, by applying them to concrete problems; finally, the attention to detail in the pedagogical treatment is impressive—after each new definition it seems that all possible points of confusion which might occur have been anticipated and addressed in a short discussion, while the coverage of topics in problems at the end of each chapter is as complete as can be desired. If the book has a weakness, it is that the number of topics covered seems to preclude excursions in depth into any single topic. However, the lecturer may desire this breadth for an introductory course in rigorous discrete mathematics for college freshmen or even for a high school senior honors course. If greater depth is desired for an upper level course, a subset of topics may be chosen, with classroom time spent on concepts covered in the exercises. For lecturers who wish to make major excursions, two main avenues of enrichment seem natural based on this material: greater depth in computer algorithms in the style of A. V. Aho, J. E. Hopcroft, and J. D. Ullman [The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass., 1975; MR0413592], or greater depth in graph theory in the style of C. Berge [Graphs and hypergraphs, second edition, North Holland, Amsterdam, 1976; MR0384579]. A summary outline of the topics covered follows. In Chapter 1 the author introduces the concepts of sets and set notation, with a well-motivated introduction to mathematical induction, leading naturally to the principle of inclusion-exclusion and concrete examples. Chapter 2 contains an intuitively motivated introduction to enumerating permutations and combinations, with a section giving an effective procedure for generating permutations. In Chapter 3 he introduces a large set of rigorous concepts with definitions: ordered pairs, binary and higher order relations, transitivity, equivalence relations and partitions, partial ordering, lattices, chains and antichains, functions, etc. Sections on relational data bases and job scheduling provide concrete examples. In Chapter 4 he defines graph-theoretic concepts: undirected and directed graphs, multigraphs, weighted graphs, paths and circuits, Eulerian and Hamiltonian circuits, factors of a graph, planar graphs, etc. Concrete examples include Dijkstra's algorithm for finding a shortest path, and a worst case bound on a simple heuristic for the travelling salesman problem. In Chapter 5 he investigates trees, with emphasis on path length: minimum spanning trees, prefix codes, binary search trees, and cut sets are covered; this leads to a study of transportation networks and a proof of the max-flow min-cut theorem. In Chapter 6 he introduces generating functions using only basic concepts of high school algebra. Generating functions are used in Chapter 7 to solve recurrence relations, and the value of the technique is illustrated by a section analyzing the number of comparison steps needed by various sorting algorithms. The last two chapters are somewhat more abstract. In Chapter 8 the author introduces groups and rings, derives Burnside's theorem and makes an interesting excursion into coding theory. In Chapter 9 he studies Boolean algebra, with applications to digital networks and switching circuits.
Reviewer: O'Neil, P. E. [form MathSciNet]