Lectures in fall term 2023/24
All exercises in one file
#1 (3 Oct 2023)
Review of propositional logic:
- 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 2023)
- Conjunctive and disjunctive normal form, size of formulas, complexity of SAT.
- De Morgan laws, Boolean algebra laws.
- Propositional proof system, deduction theorem, completeness theorem.
Exercises
#3 (17 Oct 2023)
- Proof of the propositional completeness theorem. Compactness theorem.
- First-order languages, structures, terms, formulas.
- Free and bound variable occurrences.
Exercises
#4 (24 Oct 2023)
- Substitution.
- Satisfaction relation, theories, models, entailment.
- Prenex normal form.
- First-order proof system.
Exercises
#5 (31 Oct 2023)
- First-order deduction theorem.
- Soundness and completeness theorem.
#6 (7 Nov 2023)
- Finish the proof of the completeness theorem.
- Downward Löwenheim–Skolem theorem.
Exercises
#7 (21 Nov 2023)
- Compactness theorem.
- Löwenheim–Skolem theorem, Vaught’s test.
- Examples.
Exercises
#8 (5 Dec 2023)
- Models of computation, the Church–Turing thesis.
- Turing machines. Computable sets and functions.
- Variants, example.
#9 (12 Dec 2023)
- Universal Turing machine, encoding of Turing machines.
- Undecidability of the Halting problem.
- Many-one reducibility.
#10 (19 Dec 2023)
- Peano and Robinson arithmetic.
- Bounded quantifiers, Δ0 and Σ1 formulas, Σ1-completeness of Q.
- Pairing function, sequence encoding.
Exercises
#11 (9 Jan 2024)
- Sequence encoding, Σ1-definability of semidecidable sets.
- Computability of elements of syntax.
- Gödel’s first incompleteness theorem (undecidability and incompleteness of Σ1-sound extensions of Q.)
- Church’s theorem (undecidability of the Entscheidungsproblem), adjunctive set theory.
Exercises