Кафедра математической логики и теории алгоритмов

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

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

  • Для сдачи экзамена напишите лектору (адрес — на главной странице), чтобы договориться о дате и времени (экзамен по с/к проводится индивидуально). Экзамены проходят дистанционно (Zoom).
  • (new) Программа (pdf) (вопросы к экзамену).
  • (new) Задачи (pdf)

Лекции читаются (и весной будут читаться) по пятницам в 19:00 дистанционно (через Zoom).
Для получения Zoom-ссылки, если вы еще не входите в рассылку, напишите письмо лектору (адрес на главной странице).

Все видео с лекциями

Слайды (опечатки исправлены):

  1. 2020.09.25: Лекция 01 (pdf)
  2. 2020.10.02: Лекция 02 (pdf)
  3. 2020.10.09: Лекция 03 (pdf)
  4. 2020.10.16: Лекция 04 (pdf)
  5. 2020.10.23: Лекция 05 (pdf)
  6. 2020.10.30: Лекция 06 (pdf)
  7. 2020.11.06: Лекция 07 (pdf)
  8. 2020.11.13: Лекция 08 (pdf)
  9. 2020.11.20: Лекция 09 (pdf)
  10. 2020.11.27: Лекция 10 (pdf)
  11. 2020.12.04: Лекция 11 (pdf) + уточнения (pdf) (эти уточнения имеются в слайдах, лишь вынесены отдельно для удобства тех, кто слушал лекцию или видео; последнее будет перезаписано с многими (мелкими) исправлениями). На самом деле, нашлось совсем простое доказательство той самой теоремы! В новом видео оно будет предъявлено.
  12. 2020.12.11: Лекция 12 (pdf)

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

Весна 2020: экзамен:
Вопросы | Задачи | Конспект

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

  • 2020.04.10: Лекция 6. Характеристическая формула (транзитивного) конечного конуса.
    Слайды | Видео (лишь часть 1; часть 2 не записалась; но на слайдах вся лекция)
  • 2020.04.17: Лекция 7. Аксиоматизация модальной логики конечной транзитивной шкалы.
    Слайды | Видео
  • 2020.04.24: Лекция 8. Полимодальные логики, отсутствие теоремы Макинсона для них, неполная по Крипке бимодальная логика.
    Слайды | Видео
  • 2020.05.08: Лекция 9. Бисимуляция. Связь с модальной эквивалентностью. Стандартный перевод модальных формул в язык первого порядка. Теорема ван Бентема о характеризации (формулировка).
    Слайды | Видео
  • 2020.05.22: Лекция 10. Модальная компактность. Теорема ван Бентема о характеризации модального языка внутри языка первого порядка. Лемма о манёвре. Вариации теоремы ван Бентема.
    Слайды | Видео

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

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, стр. 265-305. [ pdf ]
  • Одинцов С.П., Сперанский С.О., Дробышевич С.А. Введение в неклассические логики. Учебное пособие. Новосибирск, РИЦ НГУ, 2014. [ 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) ]
покрывает следующие темы (но отличается от изложения на лекциях):
— операции на шкалах и моделях, теоремы о сохранении;
— фильтры и ультрафильтры, в том числе счетно-неполные;
— ультрапроизведения и теорема Лося;
— ультрарасширение модели Крипке;
— модально компактные классы шкал;
— насыщенные модели первого порядка;
— модально насыщенные модели Крипке;
— теорема Гольдблатта-Томасона.
Усовершенствованное изложение теоремы Гольдблатта-Томасона дается в
конспекте 2016-2017 года (глава 10)

Литература

  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. [Доступно в сети]
Состав кафедры