Skip to content

Preface

About this book

Discrete mathematics is the mathematics of things that can be counted one by one: true and false, the whole numbers, finite sets, the vertices and edges of a network, the states of a machine. It is the mathematics on which computing is built. A programmer who reasons about a loop is using induction; a database query is a formula of predicate logic; a password policy is a counting problem; a route planner searches a graph; the padlock in a web browser is modular arithmetic; and every processor is a circuit of Boolean algebra.

This book is a first course in the subject. It is written for students who have finished school mathematics and are beginning a university course in computing, mathematics or engineering, and for anyone who wants to learn the subject on their own. No calculus is needed. What is needed is a willingness to read slowly, to work examples with a pencil, and to ask, at every step, why is this true?

The book has two aims. The first is to teach the content: logic, sets, functions, relations, induction, counting, probability, recurrences, number theory, graphs, trees, Boolean algebra and automata. The second, which matters more in the long run, is to teach you to read and write proofs. Every chapter states its definitions precisely, proves its theorems, and shows the reasoning in full in worked examples, so that by the end you can do the same.

In brief

Fourteen chapters, from propositional logic to finite automata. Each chapter starts with learning outcomes, builds from examples to precise definitions and theorems with proofs, works many examples in full, and ends with a summary, exercises with folded answers and a short quiz. A glossary and a list of further reading close the book.

How to use this book

Each chapter is built the same way.

  • Learning outcomes at the top say what you should be able to do when you have finished.
  • Sections numbered 1.1, 1.2, ... introduce one idea at a time. Definitions are in note boxes, the key ideas in tip boxes, and common mistakes in warning boxes.
  • Worked examples are in example boxes. Read the problem, try it yourself, and only then read the solution.
  • A summary collects the main points of the chapter.
  • Exercises follow, each with its answer folded underneath. Open the answer only after you have written your own.
  • A quiz of a few short questions lets you check yourself; the page marks your answers.

The chapters are meant to be read in order, but there is some freedom. Chapters 1 to 3 (logic and proof) are the foundation for everything else. Chapters 4 to 6 (sets, functions, relations, induction) come next. After that, the counting chapters (7 to 9), the number theory chapter (10), the graph chapters (11 and 12) and the computing chapters (13 and 14) can be taken in almost any order, with a few cross-references between them.

How to read mathematics

Mathematics is not read like a novel. Read a definition and immediately make up an example of something that satisfies it and something that does not. Read a theorem and test it on a small case before reading the proof. Read a proof with a pencil, checking each line. If a step is unclear, it is usually because a definition has slipped your mind: go back and look it up.

What the chapters cover

Part I, Logic and proof. Chapter 1 is propositional logic: connectives, truth tables, equivalence and the rules of inference. Chapter 2 adds predicates and the quantifiers "for all" and "there exists", which are needed to say anything about infinitely many objects. Chapter 3 is about proof itself: direct proof, contraposition, contradiction, cases, and how to write a proof that another person can follow.

Part II, Structures. Chapter 4 introduces sets and functions, the language in which the rest of mathematics is written. Chapter 5 studies relations, especially equivalence relations, which sort objects into classes, and partial orders, which arrange them in levels. Chapter 6 is mathematical induction and recursion, the two faces of one idea: to handle the case \(n\), lean on the cases before it.

Part III, Counting. Chapter 7 develops the counting principles: the sum and product rules, permutations and combinations, the binomial theorem, the pigeonhole principle and inclusion-exclusion. Chapter 8 uses them for discrete probability: events, conditional probability, independence, Bayes' theorem, random variables and expectation. Chapter 9 solves recurrence relations, the equations that describe how a sequence grows, by the characteristic equation and by generating functions.

Part IV, Number theory. Chapter 10 is the arithmetic of the integers: divisibility, primes, the greatest common divisor and Euclid's algorithm, congruences, modular inverses, Fermat's little theorem, the Chinese remainder theorem, and the RSA public-key cryptosystem that rests on them.

Part V, Graphs. Chapter 11 introduces graphs: degrees, paths and connectivity, Euler and Hamilton circuits, planar graphs and Euler's formula, and colouring. Chapter 12 is about trees: their characterisations, rooted and binary trees, traversals, and minimum spanning trees by the algorithms of Kruskal and Prim.

Part VI, Computation. Chapter 13 is Boolean algebra and its use in designing logic circuits, including the simplification of expressions with Karnaugh maps. Chapter 14 introduces formal languages and finite automata: deterministic and nondeterministic machines, regular expressions, and a first look at the limits of what a finite machine can recognise.

Notation

The book uses standard notation, which is introduced as it is needed. A few symbols appear early and often.

Symbol Meaning
\(\mathbb{N}\) the natural numbers \(\{0, 1, 2, \dots\}\) (this book includes \(0\))
\(\mathbb{Z}\) the integers \(\{\dots, -2, -1, 0, 1, 2, \dots\}\)
\(\mathbb{Z}^{+}\) the positive integers \(\{1, 2, 3, \dots\}\)
\(\mathbb{Q}\), \(\mathbb{R}\) the rational numbers, the real numbers
\(a \mid b\) \(a\) divides \(b\)
\(\lfloor x \rfloor\), \(\lceil x \rceil\) the floor and the ceiling of \(x\)
\(\lvert A \rvert\) the number of elements of a finite set \(A\)
\(\blacksquare\) the end of a proof

Table 0.1. Symbols used throughout the book.

Authors differ on whether \(0\) is a natural number. This book counts \(0\) as natural, and writes \(\mathbb{Z}^{+}\) when it means the positive integers. Some programs for the examples are written in Python, a language that is easy to read even if you have not used it; nothing in the book depends on running them.