## Propositional and Predicate Logic

Winter semester 2022/23

Previous years: ZS 2021/22 EN (by Jakub Bulín), ZS 2018/19 EN (by Martin Pilát), ZS 2015/16 EN, ZS 2014/15 EN.
Lecture in Czech: ZS 2022/23 CZ (Jakub Bulín).

Schedule: Tuesday 14:00-15:30, room S5.
Lecturer: Petr Gregor (gregor(at)ktiml.mff.cuni.cz)
Information on the lecture: 2/2 Ex/C NAIL062 in SIS

Plan of the lecture
The plan is only preliminary. I will try to synchronize with the parallel lecture in Czech.

Introduction
• 04.10. Lecture 1: A brief history, paradoxes, the language of mathematics, relation of syntax and semantics. Basic syntax and semantics of propositional logic. Appendix.

• Propositional Logic
• 11.10. Lecture 2: Semantics in a theory, adequacy of logical connectives, normal forms, SAT.
• 18.10. Lecture 3: 2-SAT, Horn-SAT, DPLL. Properties of theories, algebra of propositions.
• 25.10. Lecture 4: Tableau method: proofs, systematic tableau, soundness.
• 01.11. Lecture 5: Completeness of tableau method. Compactness. Resolution method.

• Predicate Logic
• 08.11. Lecture 6: Linear resolution, resolution in Prolog, Hilbert's calculus in propositional logic. Predicate Logic: Basic syntax, instances and variants.
• 15.11. Lecture 7: Semantics, models and properties of theories. Substructures, expansion, reduct.
• 22.11. Lecture 8: Extensions by definitions. Definability. Boolean algebras. Tableau method in predicate logic: introduction.
• 29.11. Lecture 9: Tableau method: systematic tableau, equality, soundness, canonical model, completeness.
• 06.12. Lecture 10: Corollaries of completeness. Prenex form, Skolemisation, Herbrand's theorem.
• 13.12. Lecture 11: Resolution method in predicate logic, unification, soundness and completeness.

• Model theory, decidability, incompleteness.
• 20.12. Lecture 12: LI-resolution. Hilbert's calculus in predicate logic. Elementary equivalence, completeness. Isomorphisms, categoricity. Axiomatizability.
• 03.01. Lecture 13: Decidable theories, recursive axiomatizations. Undecidability of predicate logic. Fixed-point theorem, undefinability of truth. Incompleteness theorems, corollaries.

Recommended literature

• M. Pilát, Lecture Notes on Propositional and Predicate Logic, 2020.
• A. Nerode, R. A. Shore, Logic for Applications, Springer, 2nd edition, 1997.
• P. Pudlák, Logical Foundations of Mathematics and Computational Complexity - A Gentle Introduction, Springer, 2013.
• J. R. Shoenfield, Mathematical Logic, A. K. Peters, 2001.
• W. Hodges, Shorter Model Theory, Cambridge University Press, 1997.
• W. Rautenberg, A concise introduction to mathematical logic, Springer, 2009.
Tutorials
The lecture is accompanied by tutorials on Tuesday 15:40-17:10, room S11.

To obtain a credit from tutorials you need at least 120 points. There will be two tests during the semester (each for 45 minutes). The first one (in the mid of semester) will cover propositional logic, the other (at the end of semester) will cover predicate logic. For each test you can obtain max 100 points. Apart from that you can obtain max 20 points for occasional homework(s). At the end of semester it will be possible to write a remedial test that will replace the worst of the previous two test (during the first week of the exam period). There will be no other chances for remedy.

• 04.10. Tutorial 1: Statements expressed in formulas of various orders.
• 11.10. Tutorial 2: Semantics in a theory, adequacy, DNF and CNF, satisfiability.
• 18.10. Tutorial 3: 2-SAT and Horn-SAT. Semantics in a theory.
• 25.10. Tutorial 4: Semantics, analysis of theories over finite languages.
• 01.11. Tutorial 5: Tableau method in propositional logic (postponed from 25.10.).
• 08.11. Tutorial 6: Resolution method in propositional logic. Examples for the midterm test.
• 15.11. Tutorial 7: Midterm test. Basic syntax and semantics of predicate logic.
• 22.11. Tutorial 8: Semantics, substructures, theories, extensions, definability.
• 28.11. Tutorial 9: Semantics, substructures, theories, extensions, definability, (cont.)
• 06.12. Tutorial 10: Tableau method in predicate logic.
• 13.12. Tutorial 11: Prenex form, skolemization, resolution.
• 20.12. Tutorial 12: Resolution in predicate logic (cont.). Examples of test problems.
• 03.01. Tutorial 13: Examples of test problems. Final test.

Exam
The exam is oral with written preparation. Requirements for the exam correspond to the syllabus of the course in the extent that has been covered in the lecture. A prerequisite for the exam is the credit from the tutorials. Exam dates will be available in SIS. New: Details about the exam (questions, format, grading) are here.

Consultation hours
After the tutorials or by an (email) appointment.