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

2019–2020 учебный год:

С конца марта лекции читаются онлайн через ZOOM.
День и время: пятница 19:00.
Ссылка для подключения постоянная:
https://zoom.us/j/5052868569
Идентификатор конференции:
505 286 8569

Слайды и видео онлайн-лекций:


Некоторые задачи для размышления на материал лекций:

1. Всякая нормальная логика либо содержится в Ver, либо содержит KD = K + ⋄T.

2. Почему аналогичного расщепления (решетки всех нормальных логик) не дает логика Triv? Иначе говоря, докажите, что среди нормальных логик, не содержащихся в Triv, нет наименьшей. Один из способов это сделать — предъявите убывающую последовательность логик, не содержащихся в Triv, такую что пересечение этих логик содержится в Triv.

3. В классе же транзитивных нормальных логик логика Triv дает расщепление. Найти его. То есть постройте логику L0=K4+A, такую что всякая нормальная логика над K4 либо содержится в Triv, либо содержит L0.

4. Пусть шкала F=(W,R) имеет |W|=2n точек. Постройте формулу, которая может служить характеристической формулой шкалы F и которая содержит лишь n переменных. Указание: постройте n подмножеств множества W, из которых можно породить (с помощью булевых операций) все подмножества множества W.

5. Мы доказали, что теорема Макинсона не верна для бимодальных логик. Верна ли для них слабая теорема Макинсона? Она гласит: логика всякой шкалы содердится в логике некоторой одноточечной шкалы. Для начала постройте 4 бимодальных одноточечных шкалы. Далее постройте бимодальную шкалу, логика которой не содержится ни в одной из логик одноточечных шкал.

Материалы:


Видео по теме Modal Logic (плейлисты и отдельные видео):

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

Весна 2019:


• Конспект: [ pdf ]

• Вопросы: [ pdf ]

• Задачи: [ pdf ]


Краткое содержание лекций 2018-2019 учебного года

Элементарное доказательство полноты логики K, расширенной модальностью транзитивного замыкания — Е.Е.Золин, 2015. [ pdf ]

Новые книги и статьи:

Осень 2018:

• Вопросы к экзамену для слушавших лекции осенью 2018 года: [ pdf ]
• Вопросы к экзамену для не слушавших лекции осенью 2018 года: [ pdf ]
Разница в последних трёх вопросах: вместо фильтрации — модальная насыщенность (конспект 2016-2017, раздел 6 без 6.2)
• Задачи: [ pdf ]

Модальная логика
(годовой спецкурс, 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. [Доступно в сети]