Course pages 2014–15
Lectures 1-17: Proofs, Numbers, and Sets
- Notes and Workouts
- Supervision exercises
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]
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]
- A note on enumerability.
- Q&A forum
- Lecture slides and topics
Lecture 1 (Nov 7): proof; implication.
Lecture 2 (Nov 10): contrapositive; modus ponens; bi-implication; divisibility; congruence.
Lecture 3 (Nov 12): divisibility; congruence; universal quantification; equality; conjunction.
Lecture 4 (Nov 14): existential quantification; unique existence; disjunction.
Lecture 5 (Nov 17): disjunction; Fermat's Little Theorem; negation.
Lecture 6 (Nov 19): contrapositive; proof by contradiction; natural numbers.
Lecture 7 (Nov 21): natural numbers; monoids; commutativity; semirings; cancellation; inverses; integers; rationals; division theorem and algorithm.
Lecture 8 (Nov 24): the division theorem and algorithm; modular arithmetic.
Lecture 9 (Nov 26): sets; membership; comprehension; gcd; Euclid's Algorithm.
Lecture 10 (Nov 28): Euclid's Theorem; Extended Euclid's Algorithm; linear combinations; Diffie-Hellman cryptographic method: shared secret key, key exchange.
Lecture 11 (Dec 1): mathematical induction; Binomial Theorem; Fundamental Theorem of Arithmetic.
Lecture 12 (Dec 3): Euclid's infinitude of primes; sets; extensionality; subsets and supersets; separation principle; Russell's paradox; empty set; cardinality; powerset axiom; cardinality of powersets.
Lecture 13 (Jan 16): powerset axiom; powerset Boolean algebra; pairing axiom; ordered pairs; products; big unions.
Lecture 14 (Jan 19): big unions; big intersections; union axiom; disjoint unions; relations; internal diagrams; relational composition; relational extensionality; relations and matrices.
Lecture 15 (Jan 21): directed graphs; adjacency matrix; reflexive-transitive closure; preorders; partial functions.
Lecture 16 (Jan 23): functions; retractions; sections; bijections; equal cardinality; equivalence relations; set partitions.
Lecture 17 (Jan 26): calculus of bijections; characteristic functions; finite cardinality; infinity axiom; surjections; enumerability; injections; direct and inverse images; replacement axiom; set-indexed constructions; foundation axiom.
Lectures 18-24: Formal Languages and Automata
- Lecture notes [pdf].
- Slides [colour pdf]:
- Exercise sheet [pdf].
- List of corrections to the notes [pdf].
- Past exam questions This part of the course contains
material which until last year was lectured in courses called
Discrete Mathematics II and Regular Languages and Finite
Automata. Here is a list of recent relevant Tripos Questions:
- 2014 Paper 2 Question 9 – solution notes
- 2014 Paper 2 Question 10 – solution notes
- 2013 Paper 2 Question 6 – solution notes
- 2013 Paper 2 Question 8 – solution notes
- 2012 Paper 2 Question 6 – solution notes
- 2012 Paper 2 Question 8 – solution notes
- 2011 Paper 2 Question 8 – solution notes
- 2010 Paper 2 Question 5 – solution notes
- 2010 Paper 2 Question 9 – solution notes
- 2009 Paper 2 Question 5 – solution notes
- 2009 Paper 2 Question 9 – solution notes
- 2007 Paper 2 Question 6, part (a) – solution notes
- 2007 Paper 2 Question 8 – solution notes
- 2006 Paper 2 Question 6, part (b) – solution notes
- 2006 Paper 2 Question 8 – solution notes
- Further resources:
- The material in lectures 1 and 2 on inductively defined subsets and proof by rule induction is of fundamental importance for many computer science applications (especially those connected with semantics of languages). However, it is not as well covered in the literature as the material in lectures 3-7 (for which see the recommended text by Kozen, for example). One undergraduate text covering rule-based induction is: Moller, F and Struth, G (2013) Modelling Computing Systems, Springer Undergraduate Topics in Computer Science (ISBN 978-1-84800-321-7); see chapters 8 and 9.
- Russ Cox's article Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...). (Summary: "Regular expression matching can be simple and fast, using finite automata-based techniques that have been known for decades. In contrast, Perl, PCRE, Python, Ruby, Java, and many other languages have regular expression implementations based on recursive backtracking that are simple but can be excruciatingly slow. With the exception of backreferences, the features provided by the slow backtracking implementations can be provided by the automata-based implementations at dramatically faster, more consistent speeds.")
- The script of a stage play about regular expressions (really).