COMP0009 Logic

University College London · Computer Science · 2026–27

Second-year course on mathematical logic for computer scientists, organised around one question: how can we be sure? The course runs from propositional logic to Gödel's theorems and on to the design of logics for particular problems. These notes accompany the lectures and contain the full mathematics, the exercises and the story that connects the weeks.

Part 1: Type Theory

Notes for Chapters 1–5, with slides and problem sheets for Chapters 1–4, last updated .

  • Chapter 1: The Combinator Calculus
    Why a type checker says no before a program runs: combinators, reduction, and the typing that polices them.
  • Chapter 2: Hilbert Proofs
    What a proof is: Hilbert-style proofs as checkable certificates, and why the compiler was checking one all along.
  • Chapter 3: Natural Deduction
    Proofs as trees: Gentzen's natural deduction, its equivalence with the Hilbert system, the λ-calculus, and the typed calculus in which every derivation is a program.
  • Chapter 4: Quantifiers
    Specifications: predicates and quantifiers, dependent types, first-order natural deduction and its side conditions, generics, and a first look at second-order logic and System F.
  • Chapter 5: Second-Order Logic (optional)
    Quantifying over propositions, the connectives defined from → and ∀, generics as second-order logic, the polymorphic λ-calculus (System F), normalisation and parametricity.

Part 2: Automated Reasoning

Notes and problem sheets for Chapters 6–8, with slides for Chapter 6 (the others to follow). Last updated .

  • Chapter 6: Model Theory
    What it means for a sentence to be true in a structure and for one sentence to follow from others, and how derivations meet truth: the rules of classical natural deduction derive exactly the sentences that follow.
  • Chapter 7: SAT Solving
    Searching for a counter-model instead of a derivation: satisfiability, growing a valuation, conjunctive normal form, DPLL and its practice, clause forms, Herbrand's theorem and a procedure for first-order logic.
  • Chapter 8: Incompleteness
    Why no specification captures the counting numbers and no procedure decides what follows: computation as a theory, the undecidability of halting and of first-order logic, specifications, and Gödel's two incompleteness theorems.

Introduction to Proof-theoretic Semantics

ESSLLI 2025 · Taught with Tao Gu

A five-day introductory course on proof-theoretic semantics (P-tS): an inferentialist alternative to the model-theoretic tradition, on which the meaning of a logical expression is constituted by the rules governing its use in proof rather than by reference to truth conditions in a model. The course was designed for graduate students, young researchers, and other non-specialists with a working knowledge of logic, and does not presuppose prior exposure to P-tS.

Across five lectures, the course develops the subject from first principles: proof theory and the shift from denotational to inferential semantics; Prawitz's theory of proof-theoretic validity; Sandqvist's base-extension semantics for classical and intuitionistic logic, and its connections to resolution calculi and logic programming; base-extension semantics for classical logic set against Kripke's model-theoretic semantics, and its extension to modal logic; and its extension to substructural logics, illustrated through intuitionistic multiplicative linear logic and inferentialist resource semantics.

Lecture Slides

  • Lecture 1: General Proof Theory
    What logic is, natural deduction and proof theory, and the shift from denotationalism to inferentialism as a theory of meaning.
  • Lecture 2: Proof-theoretic Validity
    Prawitz's normalization theorem and the analysis of proof-theoretic validity, including Prawitz's Conjecture.
  • Lecture 3: Base-extension Semantics
    Sandqvist's base-extension semantics for classical and intuitionistic propositional logic, and its connections to resolution calculi and logic programming.
  • Lecture 4: Classical Logic & Kripke Semantics
    Base-extension semantics for classical logic set against Kripke's model-theoretic semantics, and its extension to modal and intuitionistic logic.
  • Lecture 5: Substructural Logic
    Base-extension semantics for substructural logics, with intuitionistic multiplicative linear logic as a case study, and its application to inferentialist resource semantics.