You are here

Discrete Mathematics

Jean Gallier
Publication Date: 
Number of Pages: 
[Reviewed by
Gabriella Pinter
, on

This book provides a rigorous introduction to standard topics in this field: logical reasoning, sets, functions, graphs and counting techniques. Its intended audience is computer science undergraduate students, but could also be used in a course for mathematics majors.

What sets this book apart from similar texts is the first chapter, on “Mathematical Reasoning, Proof Principles and Logic.” This 100-page chapter provides a formalization of the basic rules of reasoning, and aims to rigorously answer the question: What is a proof? The author’s take on it is the following:

In these notes I define the notion of proof as a certain kind of tree whose inner nodes respect certain proof rules presented in the style of a natural deduction system “a la Prawitz”.

While this level of formalism might delight a logician, and might indeed provide a rigorous approach to these notions, this chapter is hard to read, especially for students at the beginning of their training in abstract reasoning. It would cause considerable trouble to a great majority of mathematics majors. To be fair, the author states in the Preface:

My unconventional approach of starting with logic may not work for everybody, as some individuals find such material too abstract. It is possible to skip the chapter on logic and proceed directly with sets, functions and so on. I admit that I have raised the bar higher than average compared to other books on discrete maths.

The rest of the book seems to be much easier to read, and indeed, it does not rely heavily on the first chapter. Highlights in the second chapter include triangular numbers, Cantor’s theorem, the Erdős-Szekeres theorem, and Hilbert’s space filling curve. Two chapters cover basic and more advanced notions of graph theory: directed and undirected graphs, cycles, connectivity, trees, cocycles, flows, tensions, Eulerian and Hamiltonian cycles, network flow problems, bipartite and planar graphs. Several algorithms are given in pseudo-code in these chapters. There is a chapter on counting problems, and one on partial orders, lattices and the RSA public key cryptosystem including a section on finding large primes, signatures and the security of RSA.

Each chapter has a summary and a generous number of exercises (without solutions). The exposition is structured as a series of propositions and theorems that are proved clearly and in detail. Historical remarks and an abundance of photographs of mathematicians enliven the text. There are also false “proofs,” hints and remarks that guide the reader to a deeper understanding of the material. While there is certainly more material than can be covered in one semester, an instructor can carefully choose topics from the book that fit the goals of a particular course and its audience.

Gabriella Pinter is Associate Professor of Mathematics at the University of Wisconsin Milwaukee.

Mathematical Reasoning, Proof Principles and Logic.- Relations, Functions, Partial Functions.- Graphs, Part I: Basic Notions.-  Some Counting Problems; Multinomial Coefficients.- Partial Orders, GCD's, RSA, Lattices.- Graphs, Part II: More Advanced Notions.- Answers to Selected Problems.