Skip to main content

Trinity College Dublin, The University of Dublin

Trinity Menu Trinity Search

You are here Courses > Undergraduate > Courses & Modules

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.

Prof. Colm Ó Dúnlaing
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.