Модальная логика
(годовой спецкурс, 2018—2019)
с.н.с. Е.Е.Золин

Темы прошедших лекций:
  1. 2018.09.14: (Вводная лекция) Краткий обзор: различные семантики модальной логики (понимания связки «необходимость»): семантика возможных миров (Крипке), алгебраическая, топологическая, доказуемостная семантика.
    Синтаксис модальных формул. Семантика Крипке: шкала, модель, истинность. Истинность модальной формулы в точке модели как игра (точнее, как наличие у одного из игроков выигрышной стратегии в описанной на лекции игре).
    Общезначимость формулы на шкале. Понятие логики шкалы. Задача «Логики кластеров» — установить включения и равенства между логиками шкал (конечных и бесконечных) с универсальным отношенем R = W × W.
  2. 2018.09.21:

Модальная логика
(годовой спецкурс, 2016—2017)
с.н.с. Е.Е.Золин

Конспект лекций: [ pdf ]
Про ультра-расширение и ТГТ: pdf ]
Вопросы к экзамену: [ pdf ]
Задачи к экзамену: [ pdf ]

Слайды-обзор критериев: [ rus ] [ eng ]

Литература

  1. Valentin Goranko & Martin Otto «Model Theory of Modal Logic», Chapter 5 of Handbook of Modal Logic, Patrick Blackburn, Johan van Benthem, Frank Wolter, editors. Elsevier, 2007. [доступно в сети]
  2. Johan van Benthem «Modal Logic for Open Minds», CSLI Lecture Notes, volume 199, 2000. [доступно в сети]
  3. Krister Segerberg «An Essay in Classical Modal Logic», 1971. (Revised version of his PhD Thesis) [ pdf ] (typeset by me, incomplete)
  4. Melvin Fitting «Proof Methods for Modal and Intuitionistic Logics», Synthese Library, volume 169, 1983. [доступно в сети]

Модели неклассических логик
(годовой спецкурс, 2015—2016)
Е.Е.Золин, И.Б.Шапировский


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

Отдельный текст pdf ] покрывает следующие темы (но отличается от изложения на лекциях):
- операции на шкалах и моделях, теоремы о сохранении;
- фильтры и ультрафильтры, в том числе счетно-неполные;
- ультрапроизведения и теорема Лося;
- ультрарасширение модели Крипке;
- модально компактные классы шкал;
- насыщенные модели первого порядка;
- модально насыщенные модели Крипке;
- теорема Гольдблатта-Томасона.

Литература

  1. Modal Logic — Patrick Blackburn, Maarten de Rijke, and Yde Venema. Cambridge Tracts in Theoretical Computer Science, Volume 53, Cambridge University Press, 2001. [Доступно в сети]
  2. Modal Logic — Alexander Chagrov and Michael Zakharyaschev. Oxford Logic Guides, Volume 35, Oxford University Press, 1997. [Доступно в сети]
  3. Logics of Time and Computation, 2nd Edition — Robert Goldblatt. CSLI Lecture Notes, No. 7. CSLI Publications, 1992. [Доступно в сети]

Модальная логика и ее приложения
(годовой спецкурс, 2014—2015)
Е.Е.Золин, И.Б.Шапировский


Программа курса: [ pdf ]

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


Литература

    Часть 1. Синтаксис и семантика модальной логики. Операции на шкалах и моделях. Модальная определимость. Модальные исчисления. Каноническая модель. Полные по Крипке логики. Разрешимость минимальной модальной логики. Кодирование проблемы домино и неразрешимые логики.
  1. Modal Logic — Patrick Blackburn, Maarten de Rijke, and Yde Venema. Cambridge Tracts in Theoretical Computer Science, Volume 53, Cambridge University Press, 2001. [Доступно в сети]
  2. Modal Logic — Alexander Chagrov and Michael Zakharyaschev. Oxford Logic Guides, Volume 35, Oxford University Press, 1997. [Доступно в сети]
    Часть 2. Расширенные модальные языки: Обратные модальности, временная логика (tense logic). Универсальная модальность. Модальность транзитивного замыкания.
  3. Logics of Time and Computation, 2nd Edition — Robert Goldblatt. CSLI Lecture Notes, No. 7. CSLI Publications, 1992. [Доступно в сети]
  4. Элементарное доказательство полноты логики K, расширенной модальностью транзитивного замыкания — Е.Е.Золин, 2015. [ pdf ]
    Часть 3. Дескрипционная логика.
  5. Е.Е.Золин. Дескрипционная логика (конспект лекций годового спецкурса), 2013.
  6. The Description Logic Handbook: Theory, Implementation and Applications, 2nd Edition — Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, editors. Cambridge University Press, 2007. [Доступно в сети]
  7. A Description Logic Primer — Markus Krotzsch, Frantisek Simancik, Ian Horrocks, 2013. Available at arXiv:1201.4089.
    Часть 4. Пропозициональная динамическая логика PDL.
  8. Logics of Time and Computation, 2nd Edition — Robert Goldblatt. CSLI Lecture Notes, No. 7. CSLI Publications, 1992. [Доступно в сети]
  9. Dynamic Logic — David Harel, Dexter Kozen, Jerzy Tiuryn. Foundations of Computing Series. The MIT Press, 2000. [Доступно в сети]
  10. A Concise Introduction to Propositional Dynamic Logic — Krister Segerberg, 1993 (short book). [ pdf ]
  11. An elementary proof of the completeness of PDL — Dexter Kozen, Rohit Parikh. Theoretical Computer Science, 1981, vol.14, pp. 113-118. [ pdf ]
    Часть 4. Логики деревьев вычислений (CTL, LTL). Верификация моделей (model checking).
  12. Верификация моделей программ: model checking — Э.М.Кларк мл., Д.Пелед, О.Грамберг. Переводчики: В.Захаров, Р.Кончаков, Д.Царьков, Р.Смелянский. Издательство МЦНМО, 2002. [Доступно в сети]