Module MAU11602: Introduction to Logic and Computation
- Credit weighting (ECTS)
- 5 credits
- Semester/term taught
- Hilary Term 2021-22
- Contact Hours
11 weeks, including tutorials which will be held in lecture slots, and a review period at the end of term.
- Learning Outcomes
- On successful completion of this module students will be able to
- Construct simple Turing machine programs.
- Construct proofs of formulae in propositional and first-order logic, including resolution, the Deduction Theorem, and derived rules.
- Define truth in a model, and distinguish between truth in a model and provability in a proof system.
- Determine the solvability or otherwise of various computational problems.
- Module Content
- Turing machines, universal Turing machine, halting problem, recursion (fixpoint) theorem, recursive separability.
- Propositional logic, resolution, Mendelson's axioms I--III, deduction theorem, completeness.
- First-order theories with Mendelson's axioms I--V, interpretations and models, Goedel's completeness theorem.
- Peano Arithmetic, and, if time permits, representability of arithmetic functions and Goedel's incompleteness theorems.
- Module Prerequisite
- None beyond JF level modules.
- Assessment Detail
(Under Covid-19 restrictions) 3-hour take-home examination counting for 70%. Coursework will contribute 30% to the overall mark. Re-assessments, if required, will be 100% exam.