General information
Course type | AMUPIE |
Module title | Logic and Computation |
Language | English |
Module lecturer | prof. dr hab. Wojciech Buszkowski |
Lecturer's email | buszko@amu.edu.pl |
Lecturer position | Professor |
Faculty | Faculty of Mathematics and Computer Science |
Semester | 2024/2025 (winter) |
Duration | 60 |
ECTS | 6 |
USOS code | 06-S2MA03-F11717 |
Timetable
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
Syllabus
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.