Department of Computer Science and Technology

Discrete Mathematics

Course pages 2021–22

# Discrete Mathematics

## Proofs, Numbers, and Sets

• Notes
• Lectures
Michaelmas term
Lecture 1: introduction; proof; implication; contrapositive; modus ponens; bi-implication; divisibility.
Lecture 2: divisibility; congruence; universal quantification; equality; conjunction.
Lecture 3: existential quantification; disjunction.
Lecture 4: Fermat's Little Theorem; negation; contrapositive; proof by contradiction.
Lecture 5: natural numbers; monoids; commutativity; semirings; cancellation; inverses; integers; rationals; rings; fields; unique existence; division theorem and algorithm.
Lecture 6: modular arithmetic; sets; membership; comprehension; sets of common divisors; gcd; Euclid's Algorithm.
Lecture 7: gcd; Euclid's Algorithm; properties of gcds; Euclid's Theorem.
Lecture 8: extended Euclid's Algorithm; integer linear combinations; Diffie-Hellman cryptographic method: shared secret key, key exchange.
Lecture 9: mathematical induction; Fundamental Theorem of Arithmetic; Euclid's infinitude of primes.
Lecture 10: sets; extensionality; subsets and supersets; separation principle; Russell's paradox; empty set; cardinality; powerset axiom; cardinality of powersets.
Lecture 11: powerset Boolean algebra; pairing axiom; ordered pairs; products; big unions.
Lecture 12: big unions; big intersections; union axiom; disjoint unions; relations.
• Lent term

•   Lecture 13: relations; internal diagrams; relational extensionality; relational composition; relations and matrices.
Lecture 14: directed graphs; adjacency matrix; preorders; reflexive-transitive closure.
Lecture 15: partial functions; functions; inductive definitions.
Lecture 16: inductive definitions; bijections; retractions; sections; equal cardinality.
Lecture 17: equivalence relations; set partitions; calculus of bijections.
Lecture 18: calculus of bijections; finite cardinality; characteristic functions; infinity axiom; surjections; enumerability.
Lecture 19: uncountable and unbounded cardinality; axiom of choice; injections; direct and inverse images; replacement axiom; set-indexed constructions; foundation axiom.
• Exercises
Michaelmas term
1   On proofs
2   On numbers
3   More on numbers
4   On induction
Lent term
5   On sets
6   On relations, partial functions, and functions
7   On bijections and equivalence relations
8   On surjections, injections, and countability
• Note on enumerability.

## Formal Languages and Automata

• Videos

The following annotated snapshot of the official playlist gives the mapping between the videos and the corresponding lectures. Taking advantage of the fact that we are not constrained by another class of students using the room and/or you having to run off to another lecture theatre, these virtual "lectures" are sometimes slightly shorter and sometimes slightly longer than 50 minutes, in order not to split an explanation in mid-topic. Subscribe to my channel, Frank Stajano Explains, to be notified whenever I publish new videos.

• 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