Department of Computer Science and Technology

Discrete Mathematics

Course pages 2023–24

# Discrete Mathematics

## Proofs, Numbers, and Sets

• Notes
• Lectures
Michaelmas term
Lecture 1: introduction; proof; implication; modus ponens; bi-implication.
Lecture 2: bi-implication; divisibility; congruence; universal quantification; equality; conjunction.
Lecture 3: existential quantification; unique existence; disjunction.
Lecture 4: Fermat's Little Theorem; reciprocal in modular arithmetic; negation; proof by contradiction; proof by contrapositive.
Lecture 5: proof by contradiction; natural numbers; monoids; commutativity; semirings; cancellation; inverses; integers; rationals; rings; fields.
Lecture 6: division theorem; division algorithm; modular arithmetic; integer linear combinations.
Lecture 7: sets; membership; comprehension; set equality; sets of common divisors; gcd; Euclid's Algorithm.
Lecture 8: properties of gcds; Euclid's Theorem; extended Euclid's Algorithm; 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.
Lecture 11: powerset axiom; cardinality of powersets; powerset Boolean algebra; pairing axiom; ordered pairs.
Lecture 12: pairing axiom; ordered pairs; products; big unions; big intersections; union axiom; disjoint unions.
Lent term
Lecture 13 (Hypertext): relations; internal diagrams; relational extensionality; relational composition; matrices.
Lecture 14 (Hypertext, Slides): relations and matrices; directed graphs; adjacency matrix; preorders; reflexive-transitive closure.
Lecture 15 (Hypertext): partial functions; functions; inductive definitions.
Lecture 16 (Hypertext): retractions and sections; bijections; equal cardinality; equivalence relations; set partitions.
Lecture 17 (Hypertext, Slides): calculus of bijections; characteristic functions; finite cardinality; infinity axiom.
Lecture 18 (Hypertext): surjections and injections; axiom of choice; enumerability; uncountable and unbounded cardinality.
Lecture 19 (Script, Hypertext): direct and inverse images; replacement axiom; set-indexed constructions; foundation axiom.

## Formal Languages and Automata

• Notes
• Lectures
Lent term
Lecture 20 (Slides): formal languages; inductive definitions; rule induction.
Lecture 21 (Slides): regular expressions; pattern matching.
Lecture 22 (Slides, Hypertext): finite automata.
Lecture 23 (Slides): regular languages; Kleene's Theorem.
Lecture 24 (Slides): Pumping Lemma .