|Module title||Logic and Computation|
|Module lecturer||prof. dr hab. Wojciech Buszkowski|
|Faculty||Faculty of Mathematics and Computer Science|
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.
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.