skip to primary navigationskip to content

Department of Computer Science and Technology

Discrete Mathematics

 

Course pages 2024–25

Discrete Mathematics

Proofs, Numbers, and Sets

  • Notes
  • Lectures
    Michaelmas term
      Lecture 1: introduction; proof; implication; modus ponens;
      Lecture 2: modus ponens; bi-implication; divisibility; congruence; universal quantification; equality; conjunction.
      Lecture 3: existential quantification; unique existence; disjunction.
      Lecture 4: disjunction; Fermat's Little Theorem; reciprocal in modular arithmetic; negation; proof by contradiction.
      Lecture 5: proof by contrapositive; 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: integer linear combinations; 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; powerset axiom; cardinality of powersets.
      Lecture 11: powerset Boolean algebra; pairing axiom; ordered pairs; products.
      Lecture 12: big unions; big intersections; union axiom; disjoint unions.
    Lent term
      Lecture 13: relations; internal diagrams; relational extensionality; relational composition; matrices.
      Lecture 14: relations and matrices; directed graphs; adjacency matrix; preorders; reflexive-transitive closure.
      Lecture 15: partial functions; functions; inductive definitions.
      Lecture 16: retractions and sections; bijections; equal cardinality; equivalence relations; set partitions.
      Lecture 17: calculus of bijections; characteristic functions; finite cardinality; infinity axiom.
      Lecture 18: surjections and injections; axiom of choice; enumerability; uncountable and unbounded cardinality.
      Lecture 19: direct and inverse images; replacement axiom; set-indexed constructions; foundation axiom.

Formal Languages and Automata

Exercises

Additional notes