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 | 2023/2024 (winter) |
| Duration | 60 |
| ECTS | 6 |
| USOS code | 06-DLWIUM0-E |
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.