General information

Course type AMUPIE
Module title Logic and Computation
Language English
Module lecturer prof. dr hab. Wojciech Buszkowski
Lecturer's email
Lecturer position Professor
Faculty Faculty of Mathematics and Computer Science
Semester 2024/2025 (winter)
Duration 60
USOS code 06-S2MA03-F11717


Module aim (aims)

· Connections between mathematical logic and computer science· Logical methods in programming

Pre-requisites in terms of knowledge, skills and social competences (where relevant)

Basic notions of logic and set theory


Week 1: Computable functions (computability, recursive functions and relations). Week 2: Properties of recursive functions and relations, Church thesis. Week 3: The register machine. Week 4: Encoding programs and computations. Week 5: Some theorems on recursive functions. Week 6: Recursively enumerable relations. Week 7: Propositional logic. Week 8: Resolution proofs and tableau proofs in PL. Week 9: First-order logic. Week 10: Interpretations, models , truth, entailment. Week 11: Herbrand models, the Herbrand theorem. Week 12: Horn programs, minimal Herbrand models. Week 13: Linear resolution. Week 14: Completeness of linear resolution.Week 15: Computational completeness of Horn programs.

Reading list

1. A. Nerode, R.A. Shore, Logic for Applications, Springer, 1997.2. N. Cutland, Computability. An introduction to recursive function theory, Cambridge University Press, 1980.