**Previous years:** ZS 2015/16 EN, ZS 2014/15 EN.

**Lecture in Czech:** ZS 2016/17 CZ

**Schedule:** Monday 17:20-18:50, 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.

*03.10.*Lecture 1: A brief history, paradoxes, the language of mathematics, relation of syntax and semantics, preliminaries, trees, König's lemma.*10.10.*Lecture 2: Basic syntax and semantics, adequacy of logical connectives, normal forms, 2-SAT.*17.10.*Lecture 3: Horn-SAT. Semantics in a theory, properties of theories, algebra of propositions. Tableau method - introduction.*24.10.*Lecture 4: Tableau method: systematic tableau, soundness and completeness. Compactness.*31.10.*Lecture 5: Hilbert's calculus. Resolution method: soundness and completeness, linear resolution, resolution in Prolog.*07.11.*Lecture 6: Predicate Logic: Basic syntax, instances and variants. Basic semantic, structures. Validity in a structure.*14.11.*Lecture 7: Semantics, models and properties of theories. Substructures, expansion, reduct. Open theories.*21.11.*Lecture 8: Theorem on constants. Boolean algebras. Tableau method in predicate logic: introduction, systematic tableau.*28.11.*Lecture 9: Tableau method: equality, soundness, canonical model, completeness, corollaries.*05.12.*Lecture 10: Extensions by definitions. Prenex form, Skolemisation, Herbrand's theorem.*12.12.*Lecture 11: Resolution method in predicate logic. Soundness and completeness.*19.12.*Lecture 12: Hilbert's calculus in predicate logic. Algebraic theories. Elementary equivalence, completeness. Isomorphisms, categoricity.*02.01. no lecture (vacations).**09.01.*Lecture 13: Decidable theories, recursive axiomatizations. Undecidability of predicate logic. Fixed-point theorem, undefinability of truth. Incompleteness theorems, corollaries.

**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. - W. Rautenberg,
*A concise introduction to mathematical logic*, Springer, 2009.

The lecture is accompanied by a practical seminar.

**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:** 24.1., 3.2.

**Consultation hours**

*Wednesday 17:20 - 18:00 (after the seminar)*, or by an (email) appointment.

**Note**

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