skip to primary navigationskip to contentDiscrete 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 .
Exercises
Additional notes
