Discrete math used to be an advanced undergraduate subject, but it has migrated earlier in the curriculum and is often taught at the freshman or sophomore level today. These courses serve both math majors and computer science majors. The present text is slanted towards mathematics, although it gives heavy weight to algorithms and their analysis. At the authors’ institution (University of Oregon) the corresponding course is given to math majors in their freshman year and, in addition to providing subject matter, acts as a bridge to abstract mathematics course.
The exposition is slanted heavily towards examples rather than theories or methods. A typical section would introduce a couple of concepts, talk about the kinds of problems that use these, and then launch into half a dozen or a dozen examples. In the Preface (p. xii) the authors say, “We have always believed that students at this level learn best from examples, so we have added examples to the large number already present and have revised others, all to encourage students to read the book.” The examples are very well chosen and usually deal with serious mathematical problems rather than contrived ones. The exercises range from simple to moderately difficult, and tend toward numerical examples of things discussed in the body. There are answers and hints for the odd-numbered problems in the back of the book; most of these are brief.
There is not a lot of hand-holding, and it is not a cookbook where you can look up how to apply particular methods or solve particular problems — you have to study the examples.
The “bridge” part is fairly modest. Chapter 2 is an introduction to logic, with a lot of information about the structure of proofs woven in. The Preface says (p. xi), “One of our main goals is the development of mathematical maturity. Our presentation starts with an intuitive approach that becomes more and more rigorous as the students’ appreciation for proofs and their skill at building them increase.” There’s only a modest amount of proving in this book, both in the body and in the exercises. I thought the proofs themselves did not become any more rigorous as the book progressed, but the difficulty of the proofs and the number of things that are proved do increase.
Very Good Feature: the treatment of group theory emphasizes its combinatorial uses. The book includes Burnside’s Lemma (p. 477), although not labeled as such.
Very Interesting Feature: mathematical induction is explained using while loops and loop invariants rather than ladders or steps.
Although this is a fifth edition, the book has not been revised since 2003 and the publisher may be letting it approach the end of its life. The Preface (p. xiii) refers to a Companion Website, which seems not to exist. The amount of supplemental material is small by the standards of today’s beginning undergraduate texts, consisting of an instructor’s solutions manual (in print form). The review copy I received seems to be a black-and-white reprinting of a color book; the things that you would expect to be in color appear in a dithered gray.
The book seems to be pitched lower than most of its competition, but I think it is a good choice for a freshman or sophomore course. The examples provide an accessible look at a great deal of real mathematics. The dominant text in this field is probably Rosen’s Discrete Mathematics and its Applications, but that’s a much more difficult (and expensive) book. Despite the preponderance of examples in the present book, it is not very similar to Lipschutz & Lipson’s Schaum’s Outline of Discrete Mathematics; the present book has much better explanations and examples.
Allen Stenger is a math hobbyist and retired software developer. He is an editor of the Missouri Journal of Mathematical Sciences. His mathematical interests are number theory and classical analysis.
|1. Sets, Sequences, and Functions.
Some Warm-up Questions. Factors and Multiples. Office Hours 1.2. Some Special Sets. Set Operations. Functions. Sequences. Properties of Functions. Office Hours 1.7. Supplementary Exercises.2. Elementary Logic.
Informal Introduction. Propositional Calculus. Getting Started with Proofs. Methods of Proof. Office Hours 2.4. Logic in Proofs. Analysis of Arguments. Supplementary Exercises.3. Relations.
Relations. Digraphs and Graphs. Matrices. Equivalence Relations and Partitions. The Division Algorithm and Integers Mod p. Supplementary Exercises.4. Induction and Recursion.
Loop Invariants. Mathematical Induction. Office Hours 4.2. Big-Oh Notation. Recursive Definitions. Recurrence Relations. More Induction. The Euclidean Algorithm. Supplementary Exercises.5. Counting.
Basic Counting Techniques. Elementary Probability. Inclusion-Exclusion and Binomial Methods. Counting and Partitions. Office Hours 5.4. Pigeon-Hole Principle. Supplementary Exercises.6. Introduction to Graphs and Trees.
Graphs. Edge Traversal Problems. Trees. Rooted Trees. Vertex Traversal Problems. Minimum Spanning Trees. Supplementary Exercises.7. Recursion, Trees and Algorithms.
General Recursion. Recursive Algorithms. Depth-First Search Algorithms. Polish Notation. Weighted Trees. Supplementary Exercises.8. Digraphs.
Digraphs Revisited. Weighted Digraphs and Scheduling Networks. Office Hours 8.2. Digraph Algorithms. Supplementary Exercises.9. Discrete Probability.
Independence in Probability. Random Variables. Expectation and Standard Deviation. Probability Distributions. Supplementary Exercises.10. Boolean Algebra.
Boolean Algebras. Boolean Expressions. Logic Networks. Karnaugh Maps. Isomorphisms of Boolean Algebras. Supplementary Exercises.11. More on Relations.
Partially Ordered Sets. Special Orderings. Multiplication of Matrices. Properties of General Relations. Closures of Relations. Supplementary Exercises.12. Algebraic Structures.
Groups Acting on Sets. Fixed Points and Subgroups. Counting Orbits. Group Homomorphisms. Semigroups. Other Algebraic Systems. Supplementary Exercises.13. Predicate Calculus and Infinite Sets.
Quantifiers and Predicates. Elementary Predicate Calculus. Infinite Sets. Supplementary Exercises.Dictionary.