Computer Laboratory

Course pages 2014–15

Discrete Mathematics

Principal lecturers: Prof Marcelo Fiore, Prof Andrew Pitts
Taken by: Part IA CST
Past exam questions
Information for supervisors (contact lecturer for access permission)

No.of lectures: 24 (continued into Lent term)
Suggested hours of supervisions: 8
This course is a prerequisite for all theory courses as well as Probability (Part IB), Security (Part IB and Part II), Artificial Intelligence (Part IB and Part II), Compiler Construction (Part IB) and Information Theory and Coding (Part 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 [7 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 [7 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.
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).