Propositional and Predicate Logic

Other variants: the parallel lecture in Czech ZS 2014/15, the previous lecture in Czech ZS 2013/14.

Schedule: Monday 14:00-15:30, room S11.
Lecturer: Petr Gregor (gregor(at)ktiml.mff.cuni.cz)
Information on the lecture: 2/2 Zk/Z NAIL062 in SIS

Plan of the lecture
The plan is only preliminary, almost surely it will not be fulfilled.

Introduction
• 06.10. Lecture 1: A brief history, paradoxes, the language of mathematics, relation of syntax and semantics, preliminaries, trees, König's lemma.

Propositional Logic
• 13.10. Lecture 2: Basic syntax and semantics, adequacy of logical connectives, normal forms, 2-SAT.
• 20.10. Lecture 3: Horn-SAT, semantics in a theory, properties of theories, algebra of propositions. Tableau method - introduction.
• 27.10. Lecture 4: Tableau method: systematic tableau, soundness and completeness.
• 03.11. Lecture 5: Compactness. Resolution method, soundness and completeness, linear resolution.

Predicate Logic
• 10.11. Lecture 6: Resolution in Prolog. Hilbert's calculus. Predicate Logic: Basic syntax, instances and variants. Basic semantic, structures.
• 17.11. no lecture (state vacation).
• 24.11. Lecture 7: Validity in a structure, in a theory, model of a theory. Properties of theories. Substructures, expansion, reduct.
• 01.12. Lecture 8: Open theories, theorem on constants. Boolean algebras. Tableau method in predicate logic.
• 08.12. Lecture 9: Systematic tableau, equality, soundness, completeness, corollaries.
• 15.12. Lecture 10: Extension by definitions. Prenex form, Skolemisation, Herbrand's theorem. Resolution method in predicate logic. Hilbert's calculus in predicate logic.

Appendix. Model theory, incompleteness.
• 05.01. Lecture 11: Elementary equivalence, completeness, categoricity. Decidable theories, recursive axiomatizations. Incompleteness theorems.

Recommended literature

• 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.

Exam
The exam consists of an exam test and an oral exam. Details on the form and extent of the exam are specified here. An example of an exam test is here. A prerequisite for the exam is the credit from the seminar. Exam dates will be available in SIS.

Previous exam tests: 4.2.

Consultation hours
Monday 15:40-17:00, or by an (email) appointment.

Note
Any comments on inaccuracy or unclear parts of the lecture slides are most welcome.