Advanced course in classical logic
(Дополнительные главы классической логики)
(полугодовой спецкурс на английском языке)
Е.Е.Золин

Чтобы сдавать данный курс, напишите лектору по email (см. на главной странице).

Весна 2018

Темы прошедших лекций:
  1. 2018.02.16: Classical propositional logic (reminder). // Syntax, semantics. Axiomatic system. Completeness and strong completeness. Compactness. Interesting facts: axiomatization of the implication fragment of CL (classical logic) and Int (intuitionistic logic); axiomatization with only one axiom for CL and Int; axiomatizations for other connectives (equivalence, Sheffer stroke, Pierce's arrow); undecidability of the problem of recognizing axiomatizations of CL, Int and (almost any) other logic.
  2. 2018.03.02: Algebraic semantics for the classical propositional logic. // Boolean algebras: definition, examples. Interpretation in an algebra. Completeness and strong completeness: the construction of the Lindenbaum algebra. (Strong completeness is not in the PDF yet.)
  3. 2018.03.16: Sequent calculus for the classical propositional logic. // Axioms and rules; completeness. Decidability of the provability problem as a consequence.
  4. 2018.03.23: The Cook–Levin theorem. // Turing machines. The classes of problems P, NP: definition, examples. Polynomial reduction of one problem to another problem; its basic properties.
  5. 2018.03.30: Infinitary propositional logic. // Syntax, semantics. The cardinality of the set of formulas. Axiomatization. Deduction theorem.
  6. 2018.04.06: Classical predicate logic: reminder. // Syntax: terms, formulas. Semantics: valid formulas. Axiomatization: classical predicate calculus. Main results: Completeness (Godel), Compactness (Maltsev), Undecidability (Church, Turing).
  7. 2018.04.13: Ehrenfeucht games.
  8. 2018.04.20:
  9. 2018.04.27:
  10. 2018.05.04:
  11. 2018.05.11:
  12. 2018.05.18:

Весна 2017

Конспект лекций: [ pdf ]

Вопросы к экзамену: [ pdf ]

Примеры задач: [ pdf ]

Весна 2016

Конспект лекций: [ pdf ]

Вопросы к экзамену: [ pdf ]

Примеры задач: [ pdf ]


Литература

  1. Верещагин Н.К., Шень А.Х. Языки и исчисления, 4-е издание, Москва, МЦНМО, 2014. [доступно в сети: pdf ]
  2. Chang C.C., Keisler H.J. Model Theory, North-Holland Pub. Co., 1990. [доступно в сети]
    Кейслер Г., Чэн Ч.Ч. Теория моделей, Москва, Мир, 1977. [доступно в сети]
  3. Sikorski R. Boolean Algebras, 3rd edition, Springer, 1969. [доступно в сети]
    Сикорский Р. Булевы алгебры, Москва, Мир, 1969. [доступно в сети]
  4. Bell J.L., Slomson A.B. Models and Ultraproducts: An Introduction, North-Holland Pub. Co., 1969. [доступно в сети]
  5. Keisler H.J. Model Theory for Infinitary Logic. North-Holland Pub. Co., 1971. [доступно в сети]
  6. Zolin E. Undecidability of the problem of recognizing axiomatizations of superintuitionistic propositional calculi, Studia Logica, 102(5):1021-1039, 2014. [ pdf ]
  7. Bokov - статьи (напишу позже)