Fall term 2025/26, course code NMAG331, Friday 14:00, room K8
Consultations: after each lecture, or drop me an email to arrange a meeting
Syllabus
- Review of basic syntax and semantics of propositional and first-order logic. The completeness and compactness theorems.
- Computability: Turing machines, computable functions, universal Turing machine, the halting problem.
- Formal arithmetic: Peano arithmetic, arithmetization of syntax, Gödel’s incompleteness theorems.
Lecture notes
This lecture in fall term 2024/25,
fall term 2023/24,
fall term 2022/23
More resources on Jan Krajíček’s website
Exam questions
You will get a question chosen randomly from the following list:
- Syntax and semantics of first-order logic. The completeness and compactness theorems.
- Turing machines, decidable and semidecidable sets. Universal Turing machine, the halting problem and its undecidability.
- Robinson and Peano arithmetic and its incompleteness (Gödel’s first incompleteness theorem). Undecidability of first-order logic (Hilbert’s Entscheidungsproblem).
Recommended literature
- Lou van den Dries, Lecture notes on mathematical logic
- Vítězslav Švejdar, Logika: neúplnost, složitost a nutnost, Academia, Praha, 2002
- Michael Sipser, Introduction to the theory of computation, 2nd ed., Thomson, 2006
- René Cori and Daniel Lascar, Mathematical logic: A course with exercises (Part I and Part II), Oxford University Press, 2000
- Joseph R. Shoenfield, Mathematical logic, Addison-Wesley, London, 1967
NB: These electronic materials are provided strictly for individual study purposes, not for further distribution. I hold no copyrights to any of these.
Further resources
Lectures
#1 (3 Oct 2025)
- Propositional atoms, connectives, De Morgan language, formulas in infix and prefix notation, unique readability.
- Boolean assignments, tautologicity and entailment, satisfiability.
- Boolean functions, functional completeness of the De Morgan language.
Exercises
#2 (10 Oct 2025)
- Conjunctive and disjunctive normal form. Size of formulas, complexity of SAT.
- Boolean algebra laws, De Morgan laws.
- Propositional proof system. Deduction theorem.
- Propositional soundness and completeness theorem.
Exercises
#3 (17 Oct 2025)
Plan:
- Proof of the propositional completeness theorem.
- Propositional compactness theorem. De Bruijn–Erdős theorem.
- First-order languages, structures, terms, formulas.
- Free and bound variable occurrences, substitution.