Essential Discrete Mathematics for Computer Science

One may wonder whether physical quantities are discrete or continuous. Calculus has certainly helped to model all kinds of physical phenomena, but when digging deep enough, we are confronted with quantum physical aspects that show a more discrete character of nature. When looking at a large scale, then it is generally assumed that our universe is immense but finite. So we might consider the physical world to be a finite and discrete system.

Digital computers are also by definition finite and discrete, but at a much smaller scale than the cosmological universe and coarser than the subatomic level, although modern basic hardware components using nanotechnology are scraping against an atomic scale. The software that runs on this hardware is essentially a sequence of bits describing how bits are transformed into bits, and hence also this is finite and discrete. So one may say that calculus formulates continuous models as approximation of a discrete reality and numerical analysis simulates these models on computers by producing a discrete approximation at a much coarser level of the continuous models.

To describe the behaviour of a computer, it is clear that it can be in many, but eventually, only a finite number of different states. No wonder that students in computer science will have to learn about discrete mathematics. This involves traditionally graphs, Boolean calculus, complexity, and sometimes also algebraic relations and structures like (finite) groups, rings, etc.

In the early days of computer science, it was the playground of engineers and mathematicians who simulated their numerical models. Therefore many of the "discrete mathematics courses for computer science" were given to mathematics or engineering students who wanted to specialize in computers. However computer science is now a mature topic in its own right, and students of computer science may not have the traditional mathematical background of previous generations. This book is taking this observation into account, and starts at a very elementary mathematical level, even explaining proof techniques, while introducing the first concepts of induction, sets, formal logic,... Although starting with a very elementary introduction, not all the chapters are at this introductory level, and at some point require the introduction of calculus elements like limits, infinite series, integrals, and de l'Hôpital's rule. The text is largely self-contained. All the required concepts and notations are defined, and all the statements are proved in full. A computer could be used occasionally to solve the exercises but one can perfectly do without.

The text has 31 relatively short chapters, each followed by an itemized summary and about a dozen exercises. Some of the chapters are related, like for example the ones on probability, but others can be skipped without a problem. The main global topics include formal logic, graphs, automata, and complexity. The pages have a wide outside margin where all the notes and illustrations are included.

To illustrate how the chapters are built up, let's look at the first one which is an illustration of the pigeonhole principle. A simple concept, and yet, it starts with ideas about a mathematical theorem which is all about formulating and proving a general proposition, rather than just a particular case, but it runs up to the fundamental theorem of arithmetic (every positive integer is a unique product of prime numbers) and the proof that there are infinitely many prime numbers. Further proof techniques are illustrated with other (elementary) results from number theory.

The book continues with sets, used to introduce relations and functions, and induction lead to countable sets, but also to strings generated from an alphabet using syntax rules. Venn diagrams are an introduction to propositional logic, Boolean algebra, and logic circuits.

Graphs are a major part and return in several chapters. They are first introduced by describing a computer model as a discrete state space machine that executes an algorithm. This is a strange choice to see a graph appear for the first time, but it may be motivating for computer science students. However, graphs are studied for their own right: directed and undirected graphs, connectivity, trees, and coloring. Previous topics are retraced with finite automata to construct and analyse strings.

Two mathematical intermezzos introduce limits, integrals, series, and big-O and small-o notation to define orders of magnitude and another one defines infinite summations and series expansions. These are prerequisites to deal with counting problems (combinatorics), discrete probabilities (including conditional probability and Bayes's theorem). Complexity theory might have been another application, but that is not included. The two chapters about modular arithmetic and some elements of cryptography conclude the book.

This is a relatively low level introduction to some elements of discrete mathematics for students in computer science with only a minimal mathematical background. It has a pleasant lay-out for studying, but is a bit overweight (bout 1.2 kg) to take it along. The number of exercises is limited but sufficient for the depth at which the subjects are treated. There are many text books that treat the same subjects (most of them at a higher level though), but there are not many that take this particular approach.

Adhemar Bultheel
Book details

This is a textbook about discrete mathematics. It starts at a very elementary mathematical level explaining sets, relations and functions introducing the pigeon hole principle, proof techniques and induction, and continuing with principles of formal logic, Boolean algebra, graph theory, automata, combinatorics, and discrete probability.

Author:  Publisher: 
9780691179292 (hbk); 9780691190617 (ebk)
USD 75.00 (hbk)