Discrete Mathematics
Principal lecturers: Prof Marcelo Fiore, Prof Frank Stajano
Taken by: Part IA CST
Hours: 24
Suggested hours of supervisions: 6
Prerequisites: This course is a prerequisite for all theory courses.
This course is a prerequisite for: Category Theory, Compiler Construction, Computation Theory, Cryptography, Formal Models of Language, Introduction to Probability, Machine Learning and Bayesian Inference, Multicore Semantics and Programming
Past exam questions
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).