ПРОГРАММА
спецкурса "Модальные и временные логики"
2007-08 уч. г.
1. Пропозициональные модальные формулы.
2. Шкалы Крипке и модели Крипке. Истинность модальной формулы в мире (точке) модели Крипке. Истинность в модели Крипке. Общезначимость в шкале Крипке.
3. Нормальные модальные логики и исчисления. Дедуктивное замыкание.
4. Лемма о подстановке. Теорема корректности для семантики Крипке.
5. Полные модальные логики. Связь между выводимостью и логическим следованием.
6. Многообразия шкал Крипке. Примеры модальных логик и их многообразий.
7. Двойственность между многообразиями и полными модальными логиками.
8. Стандартный перевод пропозициональных модальных формул в классические формулы 1-го порядка. Общезначимость как истинность формулы 2-го порядка.
9. Элементарные и D-элементарные классы шкал. Элементарные и D-элементарные модальные формулы и логики. Примеры элементарных и неэлементарных модальных формул.
10. Классические теоремы: Гёделя о полноте, о компактности, Лёвенгейма —Сколема (без док.) Основная лемма о стандартном переводе: сведение модальной логики D-элементарного класса к классической теории 1-го порядка.
11. Элементарность конечно аксиоматизируемых D-элементарных модальных логик (теорема Ван Бентема).
12. Пример D-элементарной, но неэлементарной модальной логики.
Сохранение истинности формул для подалгебр и гомоморфных образов.
13. Логическое следование на счетных и конечных шкалах. Счетная и финитная аппроксимируемость. Счетная аппроксимируемость квази-D-элементарных модальных логик.
14. Рекурсивная аксиоматизируемость. Перечислимость рекурсивно аксиоматизируемых модальных логик и классических теорий 1-го порядка.
Рекурсивная аксиоматизируемость логики (теории) с перечислимым множеством аксиом.
15. R-элементарные классы шкал. R-элементарные и квази-R-элементарные
модальные логики. Перечислимость квази-R-элементарных логик.
16. Пропозициональные теории на основе модальных логик. Вывод в теории. Теорема дедукции. Непротиворечивость. Полные теории. Свойства полных непротиворечивых теорий. Лемма Линденбаума.
17. Каноническая модель Крипке для модальной логики. Теорема о канонической модели.
18. Канонические модальные логики. Примеры канонических логик.
19. Морфизмы шкал и моделей Крипке. Изоморфизмы. Конические подшкалы и р-морфизмы. Сохранение истинности и общезначимости.
20. Конусы. Теорема о конусах.
21. Несвязные суммы шкал Крипке. Логика несвязной суммы. Задание полной логики одной шкалой.
22. Теорема полноты для логики S4.2.
23. Деревья. Развертка шкалы и ее свойства.
24. Полнота логик Кn, Dn относительно деревьев. Полнота логик T, D4, S4 относительно древовидных шкал (замыканий деревьев).
25. Сюръективные фильтрации моделей Крипке. Лемма о фильтрациях.
26. Наибольшая и наименьшая фильтрации. Примеры применения наименьшей фильтрации.
27. Транзитивные фильтрации. Финитная аппроксимируемость логик K4.2, S4.2. S4.3.
28. Теорема Харропа о разрешимости финитно аппроксимируемых логик.
29. Различимые модели Крипке. Сведение произвольной модели к различимой.
30. Определимость подмножеств в конечных различимых моделях Крипке.
31. Общезначимость логики на шкале конечной различимой модели.
Равносильность логического следования на конечных моделях и шкалах.
31. k-различимые модели Крипке. Глубина точки в 1-шкале Крипке. Глубина
шкалы (модели) Крипке. Конечность k-различимой модели конечной глубины.
32. Ограниченная каноническая модель. Истинность модальной логики в ограниченной каноническая модели.
33. Модальные логики конечной глубины. Свойство конечной глубины. Финитная аппроксимируемость логик конечной глубины и со свойством конечной глубины.
34. Лемма об усечении. Свойство конечной глубины для К. Полнота К относительно конечных деревьев.
35. Логики ограниченной альтернативы; их полнота относительно конечных деревьев.
36. Сгустки в транзитивной шкале. Остов транзитивной шкалы.
37. Квазидеревья. Полнота К4 относительно конечных квазидеревьев. Полнота К4 относительно конечных рефлексивных квазидеревьев.
38. Каноничность логик К4.3, S4.3 и их временных аналогов. Их полнота относительно линейных шкал и финитная аппроксимируемость.
39. Бульдозерная конструкция и бульдозерная теорема.
40. Полнота логик К4.3, D4.3, LIN, LIND относительно строгих линейных
порядков.
41. Аксиома плотности; ее каноничность.
42. Финитная аппроксимируемость логик К, К4, К4.3, D4.3 с аксиомой плотности
и их временных аналогов.
43. Модальные логик шкал (Q,<), (R,<), (Q,<, >).
44. Аксиома полноты Дедекинда во временной логике; ее неэлементарность.
45. Определимость подмножеств в конечной профильтрованной модели.
46. Лемма о граничной точке для логики LR. Финитная аппроксимируемость LR.
47. Полнота LR относительно действительной прямой.
48. Селективная фильтрация.
49. Логика GL, ее многообразие, полнота, финитная аппроксимируемость.
50. Логика Grz, ее многообразие, полнота, финитная аппроксимируемость.
51. Модальная и временная логики конечных строгих линейных порядков.
52. Аксиома индукции в модальной логике. Логика шкалы (w,<); ее финитная аппроксимируемость.
53. Логика шкалы (w,<); ее финитная неаппроксимируемость.
54. Связки Until, Since; их выразимость через стандартные временные связки в определимо-иррефлексивных точках.
55. Правило иррефлексивности Габбая. Его допустимость в логиках иррефлексивных шкал.
56. Особые точки канонической модели временной логики. Специальные формулы. Лемма о зеркальном отражении.
57. Выполнимость непротиворечивых формул в особых точках. Селективная фильтрация на особых точках.
58. Логика строгих линейных порядков со связками Until, Since.
59. Бисимуляции моделей Крипке. Инвариантность модальных формул относительно бисимуляций. Невыразимость Until, Since через стандартные временные модальности.
60. Модальная аксиома сепарабельности Sep. Ее общезначимость на вещественной прямой. Невыводимость Sep в US-логике рациональной прямой с модальной аксиомой Дедекинда.
61. Функциональная полнота модального языка на классе шкал. Связки Стави. Их невыразимость в US-языке.
62. Чистые формулы модального языка. Отделимые формулы. Теорема Габбая об эквивалентности функциональной полноты и отделимости ( с доказательством одной импликации).
63. Результаты о функционально полных языках для (N,<), (Z,<), (R,<), всех линейных порядков (формулировки).
64. Погружение модальных логик в монадические теории 2-го порядка. Примеры разрешимых монадических теорий (без док.)
65. Погружение US-логики натурального ряда в U-логику (PTL). Погружение PTL во временную логику фон Вригта (PTL¨¡).
66. Упорядоченные моноиды. Реляционные упорядоченные моноиды. Вложение произвольного упорядоченного моноида в реляционный.
67. Полусистемы Туэ. Погружение неуничтожающих полусистем Туэ в модальные логики. Построение неразрешимых модальных исчислений с конечным числом аксиом.
