Course pages 2016–17

# Discrete Mathematics

**Principal lecturers:** Prof Marcelo Fiore, Prof Ian Leslie**Taken by:** Part IA CST 50%, Part IA CST 75%**Past exam questions**

No.of lectures: 24 (continued into Lent term)

Suggested hours of supervisions: 6 to 8

This course is a prerequisite for all theory courses as well as:
Probability, Security I, Artificial Intelligence, Compiler Construction and the
following Part II courses: Machine Learning and Bayesian Inference and
Security II

## Aims

The course aims to introduce the mathematics of discrete structures, showing it as an essential tool for computer science that can be clever and beautiful.

## Lectures

**Proof [5 lectures].**Proofs in practice and mathematical jargon. Mathematical statements: implication, bi-implication, universal quantification, conjunction, existential quantification, disjunction, negation. Logical deduction: proof strategies and patterns, scratch work, logical equivalences. Proof by contradiction. Divisibility and congruences. Fermat’s Little Theorem.

**Numbers [5 lectures].**Number systems: natural numbers, integers, rationals, modular integers. The Division Theorem and Algorithm. Modular arithmetic. Sets: membership and comprehension. The greatest common divisor, and Euclid’s Algorithm and Theorem. The Extended Euclid’s Algorithm and multiplicative inverses in modular arithmetic. The Diffie-Hellman cryptographic method. Mathematical induction: Binomial Theorem, Pascal’s Triangle, Fundamental Theorem of Arithmetic, Euclid’s infinity of primes.

**Sets [9 lectures].**Extensionality Axiom: subsets and supersets. Separation Principle: Russell’s Paradox, the empty set. Powerset Axiom: the powerset Boolean algebra, Venn and Hasse diagrams. Pairing Axiom: singletons, ordered pairs, products. Union axiom: big unions, big intersections, disjoint unions. Relations: composition, matrices, directed graphs, preorders and partial orders. Partial and (total) functions. Bijections: sections and retractions. Equivalence relations and set partitions. Calculus of bijections: characteristic (or indicator) functions. Finite cardinality and counting. Infinity axiom. Surjections. Enumerable and countable sets. Axiom of choice. Injections. Images: direct and inverse images. Replacement Axiom: set-indexed constructions. Set cardinality: Cantor-Schoeder-Bernstein Theorem, unbounded cardinality, diagonalisation, fixed-points. Foundation Axiom.

**Formal languages and automata [5 lectures].**Introduction to inductive definitions using rules and proof by rule induction. Abstract syntax trees.

Regular expressions and their algebra.

Finite automata and regular languages: Kleene’s theorem and the Pumping Lemma.

## Objectives

On completing the course, students should be able to

- prove and disprove mathematical statements using a variety of techniques;
- apply the mathematical principle of induction;
- know the basics of modular arithmetic and appreciate its role in cryptography;
- understand and use the language of set theory in applications to computer science;
- define sets inductively using rules and prove properties about them;
- convert between regular expressions and finite automata;
- use the Pumping Lemma to prove that a language is not regular.

## Recommended reading

Biggs, N.L. (2002).
*Discrete mathematics.*
Oxford University Press (Second Edition).

Davenport, H. (2008).
*The higher arithmetic: an introduction to the theory of numbers.*
Cambridge University Press.

Hammack, R. (2013).
*Book of proof.*
Privately published (Second edition). Available at:

`http://www.people.vcu.edu/ rhammack/BookOfProof/index.html`

Houston, K. (2009).
*How to think like a mathematician: a companion to undergraduate
mathematics.*
Cambridge University Press.

Kozen, D.C. (1997).
*Automata and computability*.
Springer.

Lehman, E.; Leighton, F.T.; Meyer, A.R. (2014).
*Mathematics for computer science.*
Available on-line.

Velleman, D.J. (2006).
*How to prove it: a structured approach.*
Cambridge University Press (Second Edition).