Fall term 2024/25, course code NMAG331, Tuesday 10:40, room K334KA
Consultations: after each lecture, or drop me an email to arrange a meeting
More resources on Jan Krajíček’s website
Syllabus
- Review of basic syntax and semantics of propositional and first-order logic. The completeness and compactness theorems.
- Computability: Turing machines, computable functions, universal TM, the halting problem.
- Formal arithmetic: Peano arithmetic, arithmetization of syntax, Gödel’s incompleteness theorems.
Exam questions
This lecture in fall term 2023/24, fall term 2022/23
Exercises (voluntary) from 2023/24
Lecture notes from 2023/24 (courtesy of J. Novák)
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 (1 Oct 2024)
- 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.
- Conjunctive and disjunctive normal form.
Exercises
#2 (8 Oct 2024)
- Size of formulas, complexity of SAT.
- De Morgan laws, Boolean algebra laws.
- Propositional proof system. Deduction theorem.
- Propositional soundness and completeness theorem.
Exercises
#3 (15 Oct 2024)
- Propositional compactness theorem. De Bruijn–Erdős theorem.
- First-order languages, structures, terms, formulas.
- Free and bound variable occurrences, substitution.
- Expansion with constants, evaluation of terms.
Exercises
#4 (22 Oct 2024)
- Satisfaction relation, theories, models, entailment.
- Prenex normal form.
- First-order proof system. Deduction theorem.
- First-order soundness and completeness theorem.
Exercises
#5 (29 Oct 2024)
- Proof of the completeness theorem.
- Downwards Löwenheim–Skolem theorem.
#6 (12 Nov 2024)
- Compactness theorem, Löwenheim–Skolem theorem, Vaught’s test.
- The Entscheidungsproblem. Models of computation, the Church–Turing thesis.
Exercises
#7 (19 Nov 2024)
- Turing machines. Computable sets and functions.
- Variant definitions. Example.