General information

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 2021/2022 (winter)
Duration 60
USOS code 000


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.