Course pages 2019–20
Discrete Mathematics
Lectures 1-19: Proofs, Numbers, and Sets
- Lecture notes
- Lecture slides and topics
Michaelmas term
Lecture 1 (Nov 8): proof; implication; contrapositive.
Lecture 2 (Nov 11): modus ponens; bi-implication; divisibility; congruence; universal quantification; equality.
Lecture 3 (Nov 13): conjunction; existential quantification; unique existence.
Lecture 4 (Nov 15): disjunction; Fermat's Little Theorem.
Lecture 5 (Nov 18): negation; contrapositive; proof by contradiction; natural numbers; monoids; commutativity; natural numbers; semirings; cancellation; inverses; integers; rationals.
Lecture 6 (Nov 20): division theorem and algorithm.
Lecture 7 (Nov 22): modular arithmetic; sets; membership; comprehension; gcd; Euclid's Algorithm.
Lecture 8(Nov 25)
Lecture 9(Nov 27)
Lecture 10(Nov 29)
Lecture 11 (Dec 2): properties of gcds; Euclid's Theorem; fields of modular arithmetic; extended Euclid's Algorithm; integer linear combinations; mathematical induction; Fundamental Theorem of Arithmetic.
Lecture 12 (Dec 4): Euclid's infinitude of primes; sets; extensionality; subsets and supersets; separation principle; Russell's paradox; empty set; cardinality; powerset axiom; cardinality of powersets; powerset Boolean algebra.
Lent term
Lecture 13 (Jan 17): pairing axiom; ordered pairs; products; big unions.
Lecture 14 (Jan 20): big intersections; union axiom; disjoint unions; relations; internal diagrams; relational extensionality; relational composition.
Lecture 15 (Jan 22): relations and matrices; directed graphs; adjacency matrix; preorders.
Lecture 16 (Jan 24): reflexive-transitive closure; partial functions; functions.
Lecture 17 (Jan 27): retractions; sections; bijections; equal cardinality; equivalence relations; set partitions.
Lecture 18 (Jan 29): calculus of bijections; characteristic functions; finite cardinality; infinity axiom; injections; surjections; enumerability.
Lecture 19 (Jan 31): axiom of choice; direct and inverse images; replacement axiom; unbounded cardinality; set-indexed constructions; foundation axiom. - A note on enumerability.
- Exercises
Michaelmas term
Lent term - Past exam questions
Xmas break
2019 Paper 2 Question 7 [solution notes]
2018 Paper 2 Questions 9 (a) [solution notes]
2018 Paper 2 Questions 8 (a) [solution notes]
2018 Paper 2 Questions 7 (a) [solution notes]
2017 Paper 2 Question 9 (a) [solution notes]
2017 Paper 2 Question 8 (a) [solution notes]
2017 Paper 2 Question 7 (a) [solution notes]
2016 Paper 2 Question 9 (a) [solution notes]
2016 Paper 2 Question 8 (a) & (b) [solution notes]
2016 Paper 2 Question 7 (a) [solution notes]
2015 Paper 2 Question 9 (a) [solution notes]
2015 Paper 2 Question 8 (a) & (b) [solution notes]
2015 Paper 2 Question 7 (a) & (b) [solution notes]
2014 Paper 2 Question 7 [solution notes]
2007 Paper 2 Question 3 [solution notes]
2006 Paper 2 Question 3 [solution notes]
2006 Paper 2 Question 4 [solution notes]
Easter break
2019 Paper 2 Question 9 [solution notes]
2017 Paper 2 Question 9 (b) & (c) [solution notes]
2017 Paper 2 Question 8 (b) & (c) [solution notes]
2017 Paper 2 Question 7 (b) [solution notes]
2016 Paper 2 Question 9 (b) & (c) [solution notes]
2016 Paper 2 Question 8 (c) [solution notes]
2016 Paper 2 Question 7 (b) [solution notes]
2015 Paper 2 Question 9 (b) & (c) [solution notes]
2015 Paper 2 Question 8 (c) [solution notes]
2015 Paper 2 Question 7 (c) [solution notes]
2014 Paper 2 Question 8 [solution notes]
2013 Paper 2 Question 5 [solution notes]
2011 Paper 2 Question 5 [solution notes]
2009 Paper 1 Question 4 [solution notes]
2008 Paper 2 Question 3 [solution notes]
2007 Paper 2 Question 5 [solution notes]
2006 Paper 2 Question 5 [solution notes]
Lectures 20-24: Formal Languages and Automata
- Lecture notes (2 up, with large margins for your own scribbles)
- Lecture slides (1 up)
- Example sheet, including list of relevant past exam questions by topic