Модальные логики топологических пространств тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА

Механико-математический факультет

На правах рукописи УДК 510.643: 515.122.2

РГБ ОД

2 2 Ш 2000

ШЕХТМАН Валентин Борисович

МОДАЛЬНЫЕ ЛОГИКИ ТОПОЛОГИЧЕСКИХ ПРОСТРАНСТВ 01.01.06 — математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Москва 2000

Работа выполнена в Институте проблем передачи информации РАН

Официальные оппоненты:

доктор физико-математических наук

доктор физико-математических наук, профессор

доктор физико-математических наук

М.В. Захарьящев В.И. Пономарев А.В. Чагров

Ведущая организация -

Институт математики Сибирского отделения РАН

Защита диссертации состоится "3," И.ЮМЛ. 2000 г. в 16 час. 15 мин. на заседании диссертационного совета Д.053.05.05 при Московском государственном университете им. М.В. Ломоносова по адресу: 119899, ГСП, Москва, Воробьевы горы, МГУ, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан ап^еиЛ 2000 г.

Ученый секретарь диссертационного совета Д.053.05.05 при МГУ доктор физико-математических наук, профессор

В.Н. Чубариков

зил, ^ ¿гз

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В настоящей диссертации исследуются аксиоматические теории топологических пространств, основанные на модальной логике.

Изучение логики модальностей было начато еще в античные времена и на протяжении многих столетий велось в рамках гуманитарных дисциплин (главным образом, в философии и лингвистике). Первые модально-логические исчисления были сформулированы только в начале 20-го века (К. Льюис, 1918), а осознание теории модальностей с математической точки зрения началось лишь в 1940-1950-е гт., благодаря работам А. Тарского, Дж. Маккинсн, Б. Йонссона, С. Крнпке н др. Появление многочисленных приложений модальных логик: в информатике, теории искусственного интеллекта, математической лингвистике, а также в основаниях математики, - привело в конце 1970-х гг. к стремительному росту этой области, который продолжается и сегодня. Современная модальная логика представляет собой сложившуюся математическую дисциплину с собственным кругом задач и методов; она оказывает влияние на развитие математической логики в целом и связана с рядом других областей математики, в особенности с универсальной алгеброй, теорией категорий и общей топологией.

В языках модальных логик обычно имеются классические (булевы) логические связки, а также дополнительные модальные связки (например, "необходимо", "возможно", "завтра" и др.). По сравнению с классической логикой, модальные логики отличаются большим разнообразием синтаксиса и семантики; этим объясняется широкий круг их приложений.

В диссертации модальные логики рассматриваются как формальные теории топологических пространств. Использование математической логики в топологии началось достаточно давно и развивалось по нескольким направлениям.

С одной стороны, в теоретико-множественной топологии активно применяется аксиоматическая теория множеств; на этом пути был получен ряд глубоких результатов о независимости в топологии (и в частности, в дескриптивной теории множеств)1,2.

1 И. Юхас. Результаты о непротиворечивости в топологии. В кн. Справочная книга по математической логике, под ред. Дж. Барвайса. т.2: Теория множеств, с. 213-234. М. "Наука", 1982.

- В. Г. Кановей. Проективная иерархия H.H. Лузина: современное состояние теории. В кн. Справочная книга по математической логике, под ред. Дж. Барвайса, т. 2: Теория множеств, с. 273-364. М. "Наука", 1982.

С другой стороны, А. Робинсоном3 была поставлена проблема создания "топологической теории моделей", аналогичной теории моделей классической логики первого порядка. Принципиальная трудность здесь состоит в том, что топологические структуры невозможно определить средствами классической логики первого порядка, не прибегая к понятию множества, поскольку для задания топологического пространства нужно говорить и о точках, и о множествах точек. Поэтому приходится использовать либо аксиоматическую теорию множеств, либо теории второго порядка4,5. Достоинством теорий второго порядка является богатство их выразительных возможностей, а недостатком — алгоритмическая неразрешимость.

Альтернативный подход к теориям топологических пространств предлагает модальная логика. Модальные исчисления обычно имеют меньшую выразительную силу, чем классические теории, но они, как правило, оказываются разрешимыми, часто с полиномиальной памятью.

Сама идея построения простых исчислений "алгебраического типа", в которых можно доказывать топологические теоремы, принадлежит К.Куратовскому6. Предложенное им исчисление, как позднее заметили А.Тарский, М. Стоун, Тан, полностью эквивалентно известной модальной логике Б4 Льюиса:

Аксиомы Куратовского Аксиомы Э4

(i - оператор внутренности, 1 - все пространство; □ - модальная связка

"необходимо", Т - константа "истина", zd — импликация,--эквиваленция).

Аксиомы Куратовского можно рассматривать как абстрактные алгебраические тождества; булева алгебра с дополнительной операцией, удовлетворяющей этим тождествам, называется топобулевой. Каждому топологическому пространству X отвечает топобулева алгебра, состоящая из всех его подмножеств с булевскими операциями и операцией внутренности. Тождествам в топобулевой сигнатуре

3 A. Robinson. Mctamalhematical problems. Journal of Symbolic Logic, v. 38 (1973), 159-171.

4 i. Flum, M. Ziegler. Topological model theory. Lecture Motes in Mathematics, v. 769. Springer-Verlag,

Berlin, 1980.

5 J. Flum. Model theory of topological structures. In: Quantifiers: Logics, Models and Computation, v. I,

pp. 297-312. Ed. M. Krynicki et al. Kluwer Academic Publishers, 1995.

6 C. Kuratowski. Sur I'operation A de l'Analysis Situs. Fundamenta Mathematical, v.3 (1922), 181-199.

Как явно отмечает автор, в этой работе принята аксиоматическая точка зрения: выводятся следствия из сформулированных им четырех аксиом и аксиом "алгебры логики" (т.е. булевых).

i(X1nX2) = iXiniX2 iX-ici iXi iX-isX-i ¡1 = 1

□ (Р1лр2)~Пр1лПр2

□ р1=>СШр1

□ P1=>P1

□т~т

соответствуют формулы в модальном языке: тождество t = r, где t, г — термы, можно переписать в виде формулы логики высказываний, если заменить символы операций и константы п , и, —, 1, i соответственно на логические связки и константы л, v, -i, Т, □, знак равенства - на а предметные переменные Xi, Х2,... - на пропозициональные переменные pi, Р2,-.- Обратно, каждой модальной формуле А отвечает тождество tft = 1 , где 1д - соответствующий топобулев терм. Это соответствие позволяет интерпретировать модальные формулы в топологических пространствах.

Систематическое изучение топобулевых алгебр было начато Маккинси и Тарским7. Здесь одной из центральных задач стало исследование многообразий, или, двойственным образом, эквациокальных теорий топобулевых алгебр. Благодаря известной теореме Линденбаума, эти теории в точности соответствуют модальным Э4-логикам (т.е. нормальным расширениям S4-).

Топологическая семантика модальных формул очевидным образом переносится и на обобщение топологических пространств — окрестностные шкалы, т.е. множества с одной или несколькими операциями на подмножествах, не обязательно удовлетворяющими аксиомам Куратовского.

С помощью перевода Гёделя - Тарского в логике S4 интерпретируется интуиционистская логика высказываний8. Этот перевод ставит в соответствие каждой интуиционистской формуле А модальную формулу т(А), которая получается навешиванием □ на все подформулы А. Поэтому интуиционистские формулы также могут интерпретироваться в топологических пространствах. Посредством перевода т, суперинтуиционистские логики (т.е. расширения интуиционистской логики) оказываются фрагментами S4-noniK и потому могут рассматриваться в контексте общей теории модальных логик. Известно, что множество всех суперинтуиционистских логик (а следовательно, и всех 34-логик) имеет мощность континуума9.

Основным теоретико-модельным инструментом в исследовании модальных н суперинтуиционистских логик стала реляционная семантика Крипке. Ее можно рассматривать как частный случай окрестностной (топологической) семантики. В семантике Крипке формулы интерпретируются в реляционных системах (шкалах Крипке). Для случая 34-логик — это квазиупорядоченные множества; они соответствуют топологическим пространствам, в которых пересечение любого

7 I.C.C. McKinsey, A. Tarski. The algebra of topology. Annals of Mathematics, v. 45 (1944), 141-191.

8 J.C.C. McKinsey, A. Tarski. On closed elements in closure algebras. Annals 0/Mathematics, v. 47 (1946),

122-162.

9 В. А. Янков. Построение последовательности сильно независимых суперинтуиционистских

исчислений. Доклады АН СССР, т. 181 (1968), N1, 33-34.

семейства открытых множеств открыто. Реляционные структуры обычно проще описываются, чем топологические; в частности, к ним применимы методы классической теории моделей. К середине 1990-х гт. исследование модальных S4-логик средствами-реляционной семантики было, в основном, завершено. В этой области был получен рад глубоких результатов о полноте, разрешимости, первопорядковой определимости, допустимости правил вывода, интерполяционном свойстве и т.д.; большинство этих результатов изложено в недавней монографии.10

Напротив, свойства произвольных топологических моделей модальных логик-после классических работ Маккинси — Тарского изучались недостаточно. Так, было доказано, что в топологической семантике не все логики полны11, а из полноты в топологической семантике не следует полнота в реляционной семантике1-. Однако аналогичные проблемы для суперинтуиционистских логик, поставленные A.B. Кузнецовым в 1974 г.13, решены не полностью (эти вопросы исследуются и в настоящей диссертации, см. далее). С другой стороны, совсем недавно было установлено, что степени неполноты модальных логик в обеих семантиках совпадают14. Почти полвека оставались открытыми и вопросы Маккинси — Тарского о свойствах оператора деривации в евклидовых пространствах, которые решаются в данной диссертации.

В последние годы исследования модальных логик топологических пространств заметно оживились, благодаря развитию прикладных разделов математической логики. В этой связи полезным оказывается эквивалентное определение топологической семантики в терминах "возможных миров", предложенное Р. Монтепо15 и Д. Скоттом16: модальная формула оценивается как истинная или ложная в зависимости от точки наблюдения ("возможного мира"), причем формула DA истинна в мире t, если А истинна в некоторой окрестности t. Таким образом,

10 A. Chagtov, М. Zakharyaschev. Modal logic. Oxford University Press, ¡997.

11 M. Gerson. The inadequacy of the neighbourhood semantics for modal logic. Journal of Symbolic Logic, v. 40 (1975), No.2, 141-147.

12 M. Gerson. An extension of S4 complete for the neighbourhood semantics but incomplete for the relational semantics. Studia Lógica, v. 34 (1975), 333-342.

13 A.B. Кузнецов. О сулеринтунционисгских логиках. Математические исследования, т. 10 (1975), вып. 2, 150-157.

14 L. Chagrova. On the degree of neighborhood incompleteness of normal modal logics. In: Advances in

Modal Logic, volume 1. M.fCracht, M. de Rijke, H. Wansing and M. Zakharyaschev, eds. CSL1 Publications, 1998, pp. 63-72. Автор отмечает неожиданность данного результата, поскольку топологическая и реляционная семантика неэквивалентны.

15 R. Montague. Pragmatics. In: Contemporary Philosophy. A survey. I. Ed. R. Klibansky. Florence, 1968,

pp. 102-122.

16 D. Scott. Advice on modal logic. In: Philosophical Problems in Logic. Some Recent Development, ed.

K. Lambert Reidel, 1970, pp. 143-172.

"необходимость" понимается в топологической семантике как локальная истинность. Аналогичное описание реляционной семантики было дано С. Крипке17: формула DA истинна в мире t, если А истинна во всех мирах, достижимых из t.

Из приложений топологической семантики модальных логик можно отметить лингвистический анализ локативов, времени и вида18 , начинающееся в последнее время использование модальных логик в релятивистской теории пространства-времени19, и особенно в задачах искусственного интеллекта. По мнению специалистов, можно говорить уже о развитии новой области — пространственной логики. Целью прикладных исследований здесь является создание логических исчислений, которые могут моделировать естественные качественные рассуждения о пространственных конфигурациях. Подобные задачи возникают в разнообразных информационных системах, работающих с графическими данными: географических, медицинских, биологических и т.д.20,-1. Исследователи в этой области постепенно перешли от классических теорий первого порядка к модальным логикам с топологической семантикой. Так, например, "исчисление связности областей" (RCC), введенное Д. Рэнделлом, 3. Юои и А. Коном,2- оказалось интерпретируемым в модальной логике с локальной и универсальной модальностями,23 которая изучается в настоящей диссертации.

В свою очередь, развитие приложений вызвало в последние годы новый интерес к общим проблемам топологической семантики модальных логик. Так, в недавней работе М. Аиелло — Й.Ван Бентема24 изучается понятие бискмуляции для тогшогических моделей и обсуждаются различные варианты модальных исчислений для описания топологии и геометрии. Как отмечают авторы (р. 39), "в целом, в старой доброй 'топологической интерпретации' обнаруживается гораздо больше, чем кажется на первый взгляд, лишь только мы начинаем обращаться к ее следствиям..."25

17 S. Kripke. Semantical analysis of modal logic , I. Zeitschtift fiir mathematische Logikund Grundlagen

der Mathematik, v. 9 (1963), 67-96.

18 L. Aqvist, F. Gunther. Fundamentals of a theory of vetb aspect and events. In: Studies in Formal

Semantics, ed. F.Gunther and C.Rohrer. North Holland, 1978, pp. 167-200.

19 R. Goldblatt. Orthogonality and space-time geometry. Springer, !991.

20 A. G. Cohn. Calculi for qualitative spatial reasoning. In: Artificial intelligence and Symbolic Matliemarical Computation. Lecture Notes in Computer Science, V. 1138, pp. 124-143. Springer, 1996.

21 D.S. Weld, J. De Kleer, eds. Readings in qualitative reasoning about physical systems. Morgan Kaufman, San Mateo, 1990.

~ D.A. Randell, Z. Cui, A.G. Cohn. A spatial logic based on regions and connection. In: Proceedings of the iri International Conference on Knowledge Representation and Reasoning, pp. 165-176. Morgan Kaufman, San Mateo, 1992.

23 B. Bennett. Modal logics for qualitative spatial reasoning. Logic Journal of the [GPL , v.4 (1996), No. 1,

23-45.

24 M. Aiello, J. Van Benthem. Logical patterns in space. Manuscript, 1999. http://www.illc.uva.nl/~johan.

23 В оригинале; "All in all, there is much more to the good old 'topological interpretation' than meets the

Цель работы. Исследование модальных и суперинтуиционистских логик высказываний с точки зрения топологической (окрестностной) семантики: изучение свойств полноты н сильной полноты (компактности); построение и исследование модальных логик, описывающих конкретные виды топологических пространств: связные метрические, евклидовы, нульмерные и др. — в языках с локальной и универсальной модальностями; с деривационной модальностью; с временными и топлогическими модальностями.

Научная новизна. Все результаты диссертации явлются новыми.

Основные результаты диссертации —следующие:

1. В классе расширений логики Гжегорчика построены модальные логики, неполные в топологической семантике.

2. Доказана неэквивалентность топологической семантики и семантики Крипке для суперинтуиционистских логик.

3. Доказано, что для всех модальных логик, содержащих К4, и для всех суперинтуиционистских логик из полноты по Крипке следует сильная полнота в топологической семантике.

4. В языке с операторами локальной и универсальной истинности построена система аксиом и доказана финитная аппроксимируемость логики произвольного связного плотного в себе сепарабельного метрического пространства.

5. Построены системы аксиом и доказана финитная аппроксимируемость деривационных логик для пространств 1ЧП и для нульмерных плотных в себе подмножеств действительной прямой.

6. В языке с временными операторами и оператором локальной истинности построены системы аксиом и доказана финитная аппроксимируемость для логики рациональной прямой и логики класса всех линейных порядков.

Методы исследования. В диссертации используются и развиваются теоретико-модельные методы модальной логики: канонические модели, фильтрации, р-морфизмы. Эти методы обогащаются различными топологическими конструкциями, как например, введенная автором конструкция ультрабукета топологических пространств; надстройка шкалы Крипке с помощью фильтров до топологического пространства; топологические аналоги р-морфизмов, впервые неявно появившиеся в работах Тарского и Маккинси, и их обобщения.

eye, once one starts following through its implications..."

Теоретическая и практическая ценность. Диссертация имеет теоретический характер, ее результаты могут применяться в дальнейших исследованиях по модальной и алгебраической логике, теории моделей, обшей топологии, универсальной алгебре. Полученные результаты могут быть полезны и при решении прикладных задач описания пространственной информации.

Результаты работы могут найти применение в исследованиях, проводимых в Математическом институте РАН, его Петербургском отделении. Институте математики Сибирского отделения РАН; Московском, Тверском, Новосибирском, Красноярском государственных университетах, Институте прикладной математики РАН, Вычислительном центре РАН, других университетах и математических институтах.

Апробация работы. Результаты диссертации докладывались в течение 1980 - 1999 гг. на научно-исследовательском семинаре кафедры математической логики и теории алгоритмов механико-математического факультета МГУ, на научном семинаре Института проблем передачи информации РАН, научных семинарах университетов Амстердама (Нидерланды), Лейпцига (Германия), Милана, Сиены (Италия), Хиросимы (Япония). Они были представлены и доложены на научных конференциях: 6-й Международный Конгресс по логике, философии и методологии науки (Ганновер, 1979), 8-я Всесоюзная конференции по логике и методологии науки (Паланга, 1982), Всесоюзный коллоквиум по логике и лингвистике (Телави, 1983), Европейский логический коллоквиум (Берлин, 1989), Итальянская конференция по логике и философии науки (Виареджо, 1990), Конференция по истории логики (Краков, 1990), Совещание проекта MEDLAR (Лондон, 1991), Европейский логический коллоквиум (Клермон-Ферран, 1994), 1-я и 2-я Международные конференции по модальной логике (Берлин, 1996; Уппсала, 1998), Александровские чтения (Москва, 1999).

Публикации. Основное содержание диссертации опубликовано в 8 работах; их список приведен в конце автореферата.

Структура и объем диссертации. Диссертация объемом 187 страниц состоит из введения, шести глав, разбитых на 42 параграфа, списка литературы и указателя терминов. Библиография содержит 126 наименований, включая 21 работу автора.

ОБЗОР СОДЕРЖАНИЯ ДИССЕРТАЦИИ

Глава 1 содержит вспомогательный материал. Здесь приводятся основные определения и факты из теории модальных логик, а также результаты, которые используются далее.

Под п-людалыюй формулой в диссертации понимается формула в языке классической логики высказываний с дополнительными одноместными связками □l,...,Dn (при л=1 пишем □ вместо Di); (нормальной) П-модальной логикой называется любое непротиворечивое множество n-модальных формул, содержащее все классические тавтологии, все формулы вида □¡(р1пр2)з(0|р-1оПр2). где и

А АпВ

замкнутое относительно произвольных подстановок, правила modus ponens: g А

и правил Ui-введения: "р?д ■

Для модальных логик используются распространенные обозначения:

Кп — минимальная п-модальная логика,

Л+А — наименьшая логика, содержащая логику Л и формулу А, К = К1,

К4 = К + ОргзСЮр ,

D4 = К4 + -Ф-Т,

54 = K4+Dpz3p,

Grz - S4+D(D(p->Dp)3p)op (логика Гжегорчика ),

55 = S4+^Op3p.

(Здесь обозначает "оператор возможности" O-i.)

Модальная логика, содержащая данную логику Л, называется кратко Л-логикой.

Интуиционистские формулы также рассматриваются только для логики высказываний; суперинтуиционистская логика — это (непротиворечивое) множество интуиционистских формул, содержащее все аксиомы интуиционистского исчисления высказываний Хейтинга, замкнутое относительно произвольных подстановок и правила modus poneos.

Перевод Гёделя — Тарского г — это отображение интуционистских формул в I -модальные, ставящее □ перед каждой подформулой. Для каждой 34-логики А множество

г-1(Л) = {Ае1Р|т(А)еА}

является суперпнтуицнонистской логикой26, которая называется сут-рыитуицчонистским фрагментом логики А; говорят, что логика Л — модальным напарник логики Т~1(Л). Среди модальных напарников суперинтуиционистской логики I. = Н+Э имеется наименьший:

т( I) = 34+{т(А) | АбЭ} и наибольший:

а(1) = Ог2+{т(А)|Ае Э}.

Справедлива также следующая теорема Блока — Эсакиа: перевод а есть изоморфизм решетки суперинтуиционистских логик на решетку Спг-логик27.

Наиболее общей семантикой модальных логик является алгебраическая, при которой формулы интерпретирутся в модальных алгебрах. П-модалыюй алгеброй называется булева алгебра с дополнительными одноместными операциями ¡1,...,1п, удовлетворяющими тождествам: 1к(хпу) = ¡кХ^кУ, ¡к1 = 1- Каждой п-модальной формуле А соответствует терм ^ в сигнатуре п-модальных алгебр; формула А общезначима в модальной алгебре Ю, если в 2) справедливо тождество ¡д = 1. Множество всех формул, общезначимых в алгебре 'Ц является модальной логикой; она называется модальной логикой алгебры £) и обозначается 1_(Ю). Теорема Линденбаума утверждает, что всякая модальная логика есть логика некоторой модальной алгебры, т.е. что все модальные логики полны в алгебраической семантике.

Частным случаем модальных алгебр являются алгебры окресткостных шкал, л-модалъная окрестностпая шкала определяется как множество с операциями на его

подмножествах X = (X, ¡1.....¡п), которые вместе с булевыми операциями составляют

модальную алгебру модальная логика этой алгебры называется модальной

логикой шкалы X и обозначается Аяалогично, говорят, что формула А

общезначима в окрестностной шкале X (обозначение: X НА), если она общезначима в ее модальной алгебре.

Оценкой в шкале X = (X, 1-],___,1П) называется отображение ф, переводящее каждую

пропозициональную переменнную в подмножество X; пара М=(.Т,ф) называется окрестностной моделью над X . Оценка очевидным образом продолжается на все модальные формулы в соответствии с операциями в алгебре МА{Х). Формула А называется истинной в точке окрестностной модели М - (Х,ц>), если \«е<р(А); обозначение: Мду Н А. Легко видеть, что формула общезначима над X, если и только если она истинна в любой точке любой окрестностной модели над %.

26 Л.Л. Максимова, В.В. Рыбаков. О решетке нормальных модальных логик. Алгебра и логика, т. 13, N2 (1974), 186-216.

27 A. Chagrov, М. Zakharyaschev. Modal logic. Oxford University Press, 1997.

Модальная логика некоторого класса окрестиоапных шкал С — это пересечение модальных логик всех шкал из С. Модальная логика Л называется (семантически) полной в классе С (или аппроксимируемой классом С), если Л есть логика некоторого подкласса С.

Эти определения переносятся на интуиционистский случай посредством перевода Геделя — Тарского: интуиционистская формула А общезначима в топологическом пространстве X, если т(А) общезначима в X; все такие формулы образуют суперинтуиционистскую логику X, обозначаемую 11_(ЛГ), и т. д.

В диссертации рассматриваются, в основном, три вида семантической полноты.

1. Полнота в классе всех окрестносгных шкал (или всех топологических пространств — для случая S-4-логик). В этом случае семантически полная логика называется окрестпостно полной (гаи N-полной, или топологизируемой).

2. Полнота по Кринке (или K-no.vtoma). п-модальной шкалой Кринке называется

непустое множество с П бинарными отношениями: F = (W,R-|.....Rn). Окрестностной

шкалой, ассоциированной с F, называется структура вида

N(F) = (W, ¡i...Jn). где ¡kY = {xeW j Rk(x)cY}. Соответственно, формула называется общезначимой « F, если она общезначима в N(F), и т.д. Окрестностные модели над N(F) называются моделями Кринке над F. Модальная логика полна по Кринке, если она есть логика некоторого класса шкал Крипке. В интуиционистском случае все шкалы Крипке должны быть квазиупорядоченными множествами.

3. Полнота в классе всех конечных окрестносгных шкал (или, что эквивалентно, в классе всех конечных шкал Крипке). В этом случае семантически полная логика называется финитно аппроксимируемой. Понятие финитной аппроксимируемости важно с алгоритмической точки зрения, так как из финитной аппроксимируемости и конечной аксиоматизируемости модальной (или суперинтуиционистской) логики следует ее разрешимость. Более того, исходя из описания конечных шкал Крипке для данной логики, можно оценивать сложность проблемы разрешения28.

Проблемам полноты в модальной логике было посвящено значительное число работ на протяжении последних 30 лет.

Если 2 - некоторый класс модальных или суперинтуиционистских логик, то очевидны следующие включения:

(О) Финитно аппроксимируемые С К-полные С N-полные С ~Е

логики из 2 логики из 2 логики из Z

-8 A. Chagrov, М. Zakharyaschev. Modal logic. Oxford University Press, 1997.

Дпя некоторых классов логик установлена строгость этих включений; доказательства обычно нетривиальны. В этой связи отметим, что многие конкретные модальные и суперинтуицнонистские логики финитно аппроксимируемы; на сегодняшний день известно более сотни таких логик и их семейств. Нарушения этого свойства совсем не были известны до конца 1960-х гг.; существовала даже гипотеза о финитной аппроксимируемости всех суперннтуиционистских логик. Контрпример был обнаружен В.А. Янковым29; затем аналогичные контрпримеры были построены для конечно аксиоматизируемых временных30, мономодальных31 и суперинтуиционистских32 логик.

Постепенно выяснилось, что для модальных логик все включения на диаграмме (О) — строгие, даже в классе 34-логик. Первые примеры К-неполных мономодальных логик были построены С. Томасоном33 и К. Файном34; вторая из этих логик содержит 34. Затем были найдены и другие примеры: В. В. Рыбаковым35 построена К-неполная логика в интервале между Э4 и (Згг. (т.е. модальный напарник интуиционистской лотки), а в работе автора [1] - К-неполное расширение йгг. У.Блок36 исследовал "степень неполноты" для реляционной семантики модальных логик, а Й. Ван Бентем37 нашел простые примеры неполных модальных логик, не содержащих в4. Наконец, С. Томасоном38 была доказана неразрешимость свойства К-полноты для всех модальных исчислений, а А. В. Чагровым39- для Э4-исчислений.

29 В. А. Янков. Построение последовательности сильно независимых суперинтуиционистских исчислений. Доклады АН СССР, т. 181 (1968), N1, 33-34.

30 R. Bull. An algebraic study offense logic with linear time. Journal of Symbolic Logic, v. 33 (1968), 27-

38.

31 D. Makinson. A normal modal calculus between T and S4 without the finite model property. Journal of

Symbolic Logic, v.34 (1969), 35-38.

32 A.B. Кузнецов, В.Я. Герчиу. О суперинтуиционистских логиках и финитной аппроксимируемости. Доклады АН СССР, т. 195, N 5 (1970), 1029-1032.

33 S.K. Thomason. An incompleteness theorem in modal logic. Theoria, v. 40 (1974), No. 1,30-34.

34 K. Fine. An incomplete logic containing S4. Theoria, v.40 (1974), No.l, 23-29.

35 B.B. Рыбаков. Некомпактные расширения логики S4. Алгебра и логика, т. 16 (1977), N 4, 472-

490.

36 W.J. Blok. On the degree of incompleteness in modal logics and the covering relation in the lattice of

modal logics. Technical Report 78-07. Department of Mathematics, University of Amsterdam, 1978.

37 J. Van Benthem. Two simple incomplete modal logics. Theoria, v. 44 (1978), 25-37.

38 S.K. Thomason. Undecidability of completeness in modal logic. ln\Universal algebra and applications.

Banach Centre Publications, Waiszawa, v.9 (1982), 341-345.

A.B. Чагров. Неразрешимые свойства суперинтуиционисгских логик. Математические вопросы кибернетики, вып. 5, 1994. Сборник работ под ред. С.В. Яблонского, 62-108.

Еще более парадоксальным представляется нарушение {^-полноты. Это свойство означает, что данная логика (или система тождеств) в точности охватывает все тождества, верные в некотором топологическом пространстве. Таким образом, Ы-неполная логика - это система тождеств, которая не соответствует никакому пространству. Тем не менее для Б4-логик М. Герсоном40,41 была установлена строгость второго и третьего включений на диаграмме (О); из результата Л.А. Чагровой4- следует существование континуума ^неполных модальных логик с одинаковым пополнением.

С другой стороны, были получены весьма сильные достаточные условия для финитной аппроксимируемости (К. Сегерберг, Л.Л. Максимова, А. В. Кузнецов, С.К. Соболев, К. Файн, М.В. Захарьящев, Ф. Волтер) и К-полноты (X. Салквист, К. Файн); большая часть этих результатов изложена в 43.

В ряде работ исследовался вопрос о связи свойств финитной аппроксимируемости и К-полноты для суперинтуиционистских логик и их модальных напарников. Легко видеть, что из М-полноты (соответственно, К-полноты; финитно аппроксимируемости) 34-логики следует аналогичное свойство для ее суперинтуиционистского фрагмента. Обратные теоремы гораздо менее тривиальны, и, как показано в диссертации, не всегда верны. М.В. Захарьящев44 доказал следующую гипотезу Даммета — Леммона:

Если суперинтуиционистская логика и К-полна (соответственно, финитно аппроксимируема), то ее наименьший модальный напарник т(Ц К-полон (соответственно, финитно аппроксимируем).

Для наибольших модальных напарников Л.Л. Максимовой, В.В. Рыбаковым45, Л.Л. Эсакиа46, был доказан следующий результат

Если суперинтуиционистская логика к финитно аппроксимируема, то ее наибольший модальный напарник о(Ц финитно аппроксимируем.

40 М. Gerson. The inadequacy of the neighbourhood semantics for modal logic. Journal of Symbolic Logic, v. 40 (1975), No.2, 141-147.

41 M. Gerson. An extension of S4 complete for the neighbourhood semantics but incomplete for the

relational semantics. Studia Logica, v. 34 (1975), 333-342.

42 L. Chagrova. On the degree of neighborhood incompleteness of normal modal logics. In: Advances in Modal Logic, volume I. M.Kracht, M. de Rijke, H. Warning and M. Zakharyaschev, eds. CSLI Publications, 1998, pp. 63-72.

43 A. Chagrov, M. Zakhtayaschev. Modal logic. Oxford University Press, 1997.

^M. В. Захарьящев. Модальные Напарники суперинтуиционистских логик: синтаксис, семантика, теоремы о сохранении.Математический Сборник, т. 180(1989),N !0, 1415-1427.

45 ЛЛ. Максимова, В-В. Рыбаков. О решетке нормальных модальных логик. Алгебра и логика, т. 13 (1974), N2, 186-216.

46 Л.Л. Эсакиа. К теории модальных и суперинтуиционистских систем. В кн. Логический вывод . М., Наука, 1979, с.147-172.

Наиболее распространенным методом доказательства финитной аппроксимируемости является метод фильтрации, введенный Э. Леммоном и Д. Скоттом в середине 1960-х гг. и модифицированный рядом авторов. Метод состоит в построении конечной модели Крнпке из дайной бесконечной модели. В диссертации используется его модификация, предложенная в [4], [5]; она применялась также автором в исследованиях по двумерным модальным логикам'0,48:

ОПРЕДЕЛЕНИЯ 1.8.1-1.8.2. Пусть SP — множество п-модальных формул,

замкнутое относительно взятия подформул. Пусть F = (W,Ri.....Rn) — шкала Крипке, и

М = (F,<p) — модель Крипке. Два мира x,yeW называются ^-эквивалентными (обозначение: х если в них истинны одны и те же формулы из Ч*.

Пусть h: W-WV' — сюръекция. Модель м' = (W ,r'1 ,...,Rn ,<р ) называется фильтрацией М через (*f ,h), если она удовлетворяет следующим условиям:

• <р (А) = h(c?(A)), если А — пропозициональная переменная из 'F,

• h(x) = h(y) => х&ру,

. xRjy => h(x)R'j h(y),

• h(x)R/jh(y)=»VA(DiAe4'A(M,x)»-aiA=i.(M,y)HA).

Отметим, что Д. Габбай49 рассматривал частный случай такой фильтрации,

I I

когда W определено, как \М=д для некоторого множества Дз*?, и h: W—>W —

"каноническая" сюръекция; традиционное же определение Леммона — Скотта соответствует случаю Д="Р в определении Габбая. При этом при фильтрации Леммона — Скотта мощность полученной конечной модели оценивается как экспонента от мощности ¥, в то время как при новом определении она может оказаться существенно больше. Это означает, что предложенный метод может быть полезен для логик, имеющих высокую сложность проблемы разрешения. Этот метод активно используется в главах 5 и 6.

В главах 2 и 3 диссертации исследуются проблемы общего характера. Глава 2 посвящена семантической полноте для модальных и суперинтуиционистских логик.

47 V.B. Shehtman. On some two-dimensional modal logics. In: 8th international Congress on Logic, Methodology, and Philosophy of Science. Abstracts, v. 1, pp. 326-330. Moscow, 1987.

48 D. Gabbay, V. Shehtman. Products of modal logics,pan 1. Journal of the IGPL, v. 6 (1998), No.l, 73146.

49 D.M. Gabbay. General filtration method for modal logic. Journal of Philosophical Logic, v.l (1972), 29-34.

Для суперинтуиционнстских логик вопрос о строгости второго и третьего включений на диаграмме (О) был поставлен A.B. Кузнецовым в докладе на Международном математическом конгрессе 1974 г.50; несколько ранее X. Оно51 поставил вопрос о существовании K-неполных суперинтуиционистскнх логик (т.е. о строгости хотя бы одного из этих включений).

Ответ на вопрос Оно был дан автором в [1]; этот результат был усилен в [2], где доказано несовпадение K-полноты и N-полноты для суперинтуицнонистских логик, т.е. строгость второго включения. Однако вопрос о существовании N-неполных супериктуиционистских логик (т.е. о строгости третьего включения) на сегодняшний день остается открытым.

Результаты этих работ излагаются в главе 2. Приведем их точные формулировки.

ТЕОРЕМА 2.4.4. Существует N-неполная модальная логика, содержащая логику Гжегорчика, аксиоматизируемая формулой с двумя пропозициональными переменными.

ТЕОРЕМА 2.5.6. Существует N-неполная модальная логика, содержащая логику Гжегорчика, аксиоматизируемая

(бесконечным) множеством формул с одной пропозициональной переменной.

ОПРЕДЕЛЕНИЯ 2.1.1, 2.1.2, 2.1.4. Пусть А — модальная или суперинтуиционистская логика, А — формула в языке Л, Ф — шкала Крипке или окрестностная шкала. Говорят, что Ф отделяет А от Л, если Ф Iя Л, но <Х> А. Формула А называется логическим следствием Л в семантике Крипке (соответственно, в окрестностной семантике), если она не отделяется от Л никакой шкалой Крипке (соответственно, окрестностной шкалой).

K-пополнением (соответственно, N-пополнением) логики Л называется множество всех ее логических следствий в семантике Крипке (соответственно, в окрестностной семантике). Логика Л называется оттсительно неполной, если ее К- и N-пополнение не совпадают.

ТЕОРЕМА 2.7.4. Существует относительно неполная суперинтуиционистская логика, аксиоматизируемая формулой с двумя пропозициональными переменными.

50 А.В. Кузнецов. О суперинтуиционистских логиках. Математические исследования, т. 10 (1975),

вып. 2, 150-157.

51 Н. Опо. Kripke models and intermediate logics. Publications RIMS Kyoto University, v. 6 (1970), 461476.

ТЕОРЕМА 2.7.6. (I) Существует относительно неполная S4-логкка, аксиоматизируемая формулой с двумя пропозициональными переменным«.

Все логики в этих теоремах строятся в явном виде. При используются модификации известной шкалы Файна5-. Для доказательства теорем об относительной неполноте шкала Файна специальным образом надстраивается с помощью фильтров до топологического пространства (мощности континуум). Отсюда получаются несколько следствий.

ТЕОРЕМА 2.7.5. Существует суперинтуиционистская логика с двумя переменными, которая N-полна н К-неполна.

ТЕОРЕМА 2.7.6. (2) Существует 34-логика с двумя переменными, которая N-полна и К-неполна.

СЛЕДСТВИЕ 2.4.5. Существует К-полная суперинтуиционистская логика с двуля переменными, наибольший модальный напарник которой не является даже N-полным.

Отметим, что теорема 2.7.6 усиливает результат Герсона53, который построил относительно неполную Э4-логаку с 6 переменными и бесконечным множеством аксиом. Вообще, в отношении количества переменных, доказанные результаты оптимальны, т.к. всякая суперинтуиционистская логика, аксиоматизируемая формулами с одной переменной, конечно аксиоматизируема54 и финитно аппроксимируема55, а всякая 34-логика, аксиоматизируемая конечным числом формул с одной переменной, финитно аппроксимируема56,57.

Глава 3 посвящена свойству сильной полноты. Это свойство рассматривалось ранее только для семантики Крите; в диссертации вводится и изучается его обобщение для топологической семантики.

Сильная полнота определяется следующим образом. Пусть S - множество модальных формул. Мы говорим, что S выполнимо в окрестностной шкале X, если в некоторой точке некоторой модели над X верны все формулы из S. Модальная логика

5- К. Fine. An incomplete logic containing S4. Theoria, v.40 (1974), No. 1, 23-29.

53 M. Gerson. An extension of S4 complete for the neighbourhood semantics but incomplete for the relational semantics. Studia Lógica, v. 34 (1975), 333-342.

54 I. Nishimura. On formulas in one variable in inmitionistic propositional calculus. Journal of Symbolic Logic, v.25 (1960), No. 1,327-331.

55 C.K. Соболев. О финитной аппроксимируемости суперинтуиционистских логик. Математический Сборник, т.102 (1977), N 2,289-301.

56 М. Zakharyaschev. Canonical formulas for K4. Part Ш: the finite model property. Journal of Symbolic Logic, v.62 (1997).

57 A. Chagrov, M. Zakharyaschev. Modal logic. Oxford University Press, 1997.

Л сильно окрестностио полни (или 5-\'-пол1ш), если всякое непротиворечивое в А множество формул выполнимо в какой-нибудь окрестностной шкале, где общезначима Л. Отметим, что для Ы-полной логики Б-Ы-полнота равносильна свойству компактности: множество формул выполнимо в каком-нибудь А-пространстве, если всякое его конечное подмножество выполнимо в каком-нибудь А-пространстве. Сильная полнота относительно шкал Крипке называется кратко Я-К-полнотой.

Для суперннтуиционистских логик определения аналогичны, с заменой множеств формул на пары множеств; при этом пара (Г,Д) называется выполнимой в точке, если в все формулы из Г в этой точке истинны, а все формулы из Д - ложны.

Связь свойств полноты и сильной полноты показана на диаграмме:

Б-К-полнота —> К-полнота

(©) 4- 4

5-1^-полнота —> К-полнота

Для суперинтуиционистских и 54-логик три из этих импликаций необратимы:

• Из К-полноты не следует Б-К-полнота, согласно известным результатам (см. ниже).

• Из К-полноты не следует К-полнота, согласно результатам главы 2.

• . В главе 3 получен следующий результат:

ТЕОРЕМА 3.5.11. (1) Существует 5-(\1~полная 34-логика, не являющаяся К-полной.

(2) Существует Э-М-полная суперинтуиционистская логика, не являющаяся К-полной.

Таким образом, из 5-1Ч-полноты не следует К-полнота (и тем более Э-К-полнота).

• С четвертой импликацией на диаграмме (0) дело обстоит сложнее. С одной стороны, в главе 4 для достаточно простой бимодальной логики <3гг.и (логики Гжегорчика с универсальной модальностью) доказано :

ТЕОРЕМА 4.6.2. Логика Сгги финитно аппроксимируема (и следовательно, К-полна).

ТЕОРЕМА4.6.5. Логика Сгги Б-М-неполна.

Поэтому для бимодальных логик из К-полноты (и тем более из ^полноты) не следует Б-М-полнота.

С другой стороны, в главе 3 получен следующий результат:

ТЕОРЕМА 3.5.10. Для всех Огг-логик М-полнота эквивалентна Э-М-полноте.

Вопрос о справедливости аналогичного утверждения в классе К4-логик, а также в классе суперинтуиционистских логик пока остается открытый.

Хотя общих синтаксических признаков Э-К-полноты и К-полноты, по-видимому, не существует: ввиду упоминавшихся выше результатов58, для конечно аксиоматизируемых логик эти свойства алгоритмически нераспознаваемы — известен ряд результатов о совпадении и несовпадении этих свойств. Во-первых, Б-К-полны все канонические логики (логика называется канонической , если она общезначима в своей канонической шкале Крнпке, состоящей из всех ультрафильтров алгебры Линденбаума). Более того, оказывается, что Э-К-полнота эквивалентна каноничности для большого класса логик - так называемых субфреймовых и конфинально субфреймовых К4-ЛОГИК59,60. Аналогичные результаты были получены для суперинтуиционистских логик61 и для субфреймовых логик, содержащих К62. Исходя из этого, можно построить много примеров логик, которые К-полны, но не Э-К-полны, - достаточно взять любую субфреймовую и неканоническую логику. Таковы, например, две известные логики: <3гг. и (лотка Гёделя—Лёба). Ряд других примеров получен в 63, м.

В противоположность этому, для Б-М-полноты доказываются следующие признаки.

ТЕОРЕМА 3.3.2. Всякая К-полная К4-логика 5-М-полна.

ТЕОРЕМА 3.4.4. Всякая К-полная суперинтуиционистская логика Б-М-полна.

Таким образом, для К4-логик и для суперинтуицинистских логик диаграмма (©) приобретает вид:

(О) Б-К-полнота —> К-полнота —» Б-М-полнота —) Я-полнота.

(*- ?)

58 А.В. Чагров. Неразрешимые свойства суперинтуиционистских логик. Математические вопросы кибернетики, вып. 5, 1994. Сборник работ под ред. С.В. Яблонского, 62-108.

59 К. Fine. Logics containing К4. П. Journal of Symbolic Logic, v.50(1985),No.3, 619-651.

60 M. Zakhaiyaschev. Canonical formulas for K4. Part II: со final subframe logics. Journal of Symbolic Logic, v.61 (1996), 421-449.

61 См. там же.

62 F. Wolter. Lattices of modal logic. Ph.D. Thesis, Berlin, 1993.

63 T. Shimura. On completeness of intermediate predicate logics with respect to Kripke semantics. Bulletin of

the Section of Logic, v. 24 (1995), No. 1,41 -45.

64 S. Ghilardi, P. Miglioli. On canonicity and strong completeness conditions in intermediate prepositional

logics- Studia Logica, v. 63 (1999), 1-33.

Эти результаты представляются достаточно неожиданными. Они указывают на различие семантики Крнпке и топологической семантики: оказывается, что свойство компактности, которое нарушается в семантике Крипке, можно восстановить с помощью некоторой топологической конструкции. Найденная конструкция -ультрабукет - позволяет посредством ультрафильтров строить из семейства шкал Крипке топологическое пространство и аналогична известной конструкции ультрапроизведения в классической теории моделей. Понятие ультрабукета определяется и для более широкого класса топологических пространств.

ОПРЕДЕЛЕНИЯ 3.5.1, 3.5.3. Пусть (Лп,хп), песо — семейство топологических пространств с отмеченными замкнутыми точками; причем .Тп задано на множестве Хп. Как обычно, букет Х=^/(Хп,хп) пунктированных множеств (Хп,хп) получается из песо

(несвязной) суммы Хп отождествлением всех точек хл. Пусть II — ультрафильтр в со. Ультрабукетом семейства (.Тп,хп) ПО называется букет X с топологией, при которой множество УсХ открыто, если и только если

• каждое множество \Ал(Хп —{хп}) открыто в Д'п;

• { л | хп — внутренняя точка \/пХП в ЗД-е 'II.

Ультрабукеты корректно определены для локальных Т¡-пространств, т.е. таких, где каждая точка замкнута в некоторой своей окрестности. Эта конструкция позволяет доказать следующий признак:

ТЕОРЕМА 3.5.8. Каждая модальная или суперинтуиционистская логика, аппроксимируемая локальными Т [-пространствами, в-М-полна.

Из этой теоремы следует эквивалентность И-полноты и 8-]\'-полноты для обширного класса логик, и в частности, для всех Огг-логик (теорема 3.5.10).

В трех последних главах диссертации изучаются конкретные модальные логики топологических пространств. Здесь принят более широкий взгляд на модальности в топологии, чем подход с помощью топобулевых алгебр, развитый Маккинси и Тарским. Это объясняется тем, что многие важные свойства топологических пространств (как, например, компактность, хаусдорфовость, связность и др.) вообще невыразимы в виде топобулевых тождеств: по известной теореме Маккинси -Тарского, модальная логика любого плотного в себе метризуемого пространства со счетной базой совпадает с 34. Поэтому для расширения выразительных возможностей языка можно использовать модальности, которые интерпретируются не

только как внутренность или замыкание, и для одного и того же пространства рассматривать различные окрестностные шкалы. Программа исследования модальных логик с разнообразными "пространственными" модальностями была предложена автором в [3] на основе некоторых идей А.Г. Драгалина.

В главе 4 рассматриваются модальные логики в языке с двумя основными модальностями: □ интерпретируется как локальная истинность (или как внутренность множества), а V - как универсальная истинность (или как внутренность множества в слабейшей топологии). Модальные логики с дополнительной универсальной модальностью в последние годы рассматривались рядом авторов 65, 6б, но в контексте топологической семантики они почти не изучены.

Логика Э4и класса всех топологических пространств в этом языке хорошо известна; она получается присоединением аксиомы УрэСЗр к аксиомам Э4 для □ и аксиомам Э5 для V.

Сравнительно недавно возникла идея использовать пространственные логики со связками □, V в исследованиях по искусственному интеллекту 67,68. В частности, было доказано, что базисное исчисление РСС-8, описывающее отношения между пространственными областями, интерпретируется в 84 и.

В диссертации изучается неизвестное ранее расширение Э4иС логики Э4и с помощью дополнительной аксиомы, выражающей связность:

Получены следующие результаты:

ТЕОРЕМА 4.5.2. 841/С есть логика произвольного связного плотного в себе сепарабельного метрического пространства.

ТЕОРЕМА 4.5.2. Логика 541_/С финитно аппроксимируема, и следовательно, разрешима.

При этом мощность конечной контрмодели оценивается так же, как в логике 34, т.е. как экспонента от длины данной формулы.

В главе 5 рассматривается еще одна интерпретация модальностей в топологии, при которой связке -Ф- отвечает канторовская операция деривации <1 (взятие

65 V. Goranko, S. Passy. Using the universal modality: gains and questions. Journal of Logic and

Computation v.2 (1992), 5-30.

66 E. Spaan. Complexity of modal logics. Doctoral dissertation. Institute for Logic, Language and Computation, University of Amsterdam, 1993.

67 B. Bennett. Modal logics for qualitative spatial reasoning. Logic Journal of the ¡GPL , v.4 (1996), No. 1,

23-45.

68 A,G. Cohn. B. Bennett, J. Gooday, N.M. Gotts. Representing and reasoning with qualitative spaiial relations about regions. Manuscript, 1998. http: //www.scs.leeds.ac.uk/spacenet/leedsqsr.html

производного множества). Таким образом, при этом подходе вместо топобулевых алгебр используются деривационные алгебры топологических пространств.

Аксиоматика топологических пространств типа Т, с помощью деривационных алгебраических тождеств предлагалась еще Куратовским69 и обсуждалась Маккинси и Тарским70. Соответствующая эквациональная теория в этом случае эквивалентна известной модальной логике К4. Для класса всех пространств получается более слабая логика

К4° = К + рлОрэСЮр.

Вообще, деривационная модальная логика пространства Я (обозначение: 1_с1(Л~)) определяется как логика его деривационной алгебры ОА(.У). Эту логику можно определить также в терминах возможных миров: 1_с1(.1') есть множество всех формул, которые <3-общезначимы в X. Понятие ¿-общезначимости аналогично понятию общезначимости; отличие состоит в том, что □ интерпретируется как "строгая локальная истинность". А именно, формула ОА считается истинной в мире V/, если А истинна всюду в некоторой проколотой окрестности ш.

Кроме К4, были известны еще некоторые примеры деривационных логик.

Л.Л.Эсакиа71 показал, что модальная логика Гёделя - Лёба 01_ = К + 0([1]р:эр):эр является деривационной логикой класса всех разреженных топологических пространств. М.А. Абашидзе 73 описал деривационные логики для топологических пространств ординалов.

Наконец, хорошо известная "модальная логика неравенства" (или логика связки "где-то еще")74, 75 01_ = К4° + -Ф-Оргэр, как нетрудно видеть, является деривационной логикой класса всех пространств со слабейшей топологией.

В работе Маккинси - Тарского76 теория деривационных алгебр и логик была лишь намечена. В частности, вопросы, поставленные там (р. 652), долгое время оставались открытыми. Ответы на них получены в главе 5 диссертации.

69 С. Kuratowski. Sur l'opération Ä de l'Analysis Situs. Fundamenta Mathematicae, v.3 (1922), 181-199.

70 J.C.C. McKinsey, A. Tarski. The algebra of topology. Annals of Mathematics, v. 45 (1944), 141-191.

71 ЛЛ. Эеакна. Диагональные конструкции, формула Лёба и разреженные пространства Кантора. В кн. Логико-семантические исследования. Тбилиси, Мецниереба, 128-143.

72 М.А. Abashidze. Ordinally complete normal extensions of the logic of provability. In: Logic, Methodology and Philosophy of Science, Moscow, 1987, Abstracts, v.5, part 1, 9-10.

73 М.А. Абашидзе. Ординальная полнота модальной системы Гёделя — Лёба. Интенсиональные логики и логическая структура теорий (Тетей, 1985). Тбилиси, Мецниереба, 1988,49-73.

74 К. Segeiberg. A note on the logic of elsewhere. Theoria , v. 46 (1980), no. 2-3, 183-187.

75 M. De Rijke. Extending modal logic. Ph. D. Thesis. ILLC Dissertation Series, Amsterdam, 1993

76 J.C.C. McKinsey, A. Tarski. The algebra of topology. Annals of Mathematics, v. 45 (1944), 141-191.

Вопросы Маккинси - Тарского касались справедливости следующих равенств:

МТ1. 1_с1(Рг)=04 .

МТ2. 1_с1(*1)=04 (гдeJ - канторов дисконтинуум).

МТЗ. 1_с1(С2)=04 .

МТ4. 1_<3(1Ч2)=04 -4- Ки.

МТ5. 1_<1(Кп)=1_с1(К2) при п>2 .

Здесь

Р4 = К4 + ^Т,

Ки=С]((ПрлрМС]-,рл-1р))=эС1руа-,р.

Формула Ки является аналогом тождества

с!((хос1(-х))и(-хп с!х)) = с1хг1с1(-х), обнаруженного Куратовскнм еще в 1920 г. Это тождество справедливо в алгебре ОА((Чп) при п>1, но нарушается в ОА(1-?).

В диссертации рассматриваются также обобщенные формулы Куратовского:

п _ п

кип= □( V аок)=> Х/0^0* • к=0 к=0

где

□ А = ОАлА, Ок = РклЛ{-,р]|]*к,0^]^п}. (Как нетрудно видеть, К11 и Ки1 дедуктивно эквивалентны).

Основные результаты главы 5 - следующие.

ТЕОРЕМА 5.6.5. Деривационная логика любого нульмерного плотного в себе сепарабельного метрического пространства совпадает с 04

Это подтверждает равенства МТ2, МТЗ.

ТЕОРЕМА 5.6.6. Деривационная логика класса всех нульмерных сепарабельных метрических пространств совпадает с К4.

СЛЕДСТВИЕ 5.П.3. Если пространство X локально гомеоморфно К", где п>1, то 1_с1(.Г) = ОА + Ки. ...

Это подтверждает равенства МТ4, МТ5.

СЛЕДСТВИЕ 5.12.7. Если пространство X локально гомеоморфно Я, то 1-с1(.Т) = 04 + ки2.

Это опровергает равенство МТ1.

ТЕОРЕМА 5.9.1. Все логики вида 04 + Кип финитно аппроксимируемы и следовательно, разрешимы.

Отметим, что последний результат другим методом (дающим, по-видимому, более сложный разрешающий алгоритм) доказан М.В. Захарьящевым77 .

Для доказательств теорем о полноте применяется модификация метода Маккинси — Тарского. Для этого строятся специальные отображения топологических пространств на шкалы Крипке — d-р-морфизмы. Их построение ведется индуктивно; дополнительные трудности возникают в связи с тем, что конечные шкалы для логик с обобщенными аксиомами Куратовского описываются достаточно сложно, поскольку эти аксиомы не соответствуют классическим формулам первого порядка.

В главе 6 изучаются логики топологических пространств, получающихся из линейно упорядоченных множеств с интервальной топологией. Эти логики строятся в 3-модальном языке: со связками локальной истинности (□) и "диодоровыми" временными модальностями: "всегда будет" (G), "всегда было" (Н).

Каждому линейно упорядоченному множеству (W,<) соответствует окрестностная шкала для этого языка, состоящая из двух противоположных шкал Крипке (W,<), (W,>) и интервального топологического пространства. Определение истинности в точке (при данной оценке пропозициональных переменных) выглядит следующим образом:

xhGA о Vy>x у НА; х*"НА о Vy<х у1=А;

xHDA -»31 (I - открытый интервал &хе l&Vz(ze 1 zt=A)). Как заметил Д. Скотт78, эта семантика позволяет интепретировать высказывания естественного языка с различными грамматическими временами:

FA=-iG-iA ("когда-нибудь будет А") соответствует простому будущему времени; РА=-,Н->А ("когда-то было А") — простому прошедшему времени; DA ("сейчас имеет место А") — настоящему продолженному времени (Present Progressive). Высказывания. вида FDA и PDA соответствуют временам Future Progressive и Past Progressive.

3-модальная логика линейно упорядоченного множества (W,<) - это множество всех общезначимых в нем 3-модальных формул; эта логика обозначается Несмотря на естественность таких логик, они не рассматривались в явном виде до появления работы [5].

77 M. ZaJcharyaschev. A sufficient condition for the finite model property of modal logics above K4. Bulletii

of the ICPL, v. 1 (1993), 13-21.

78 D. Scott. Advice on modal logic. In: Philosophical Problems in Logic. Some Recent Development, ed. K. Lambert ReideL, 1970, pp. 143-172.

Аналогичные результаты получены для логик замкнутых и полуоткрытых рациональных интервалов (теорема 6.5.1).

Необходимо отметить, что разрешимость некоторых логик вида вытекает из разрешимости универсальных монадических теорий второго порядка для (W,<), куда эти лотки стандартным образом погружаются. Из результатов Рабина, Гуревича и Бёрджесса следует, что теории такого вида для (R,<) и (Q,<) и для класса всех линейных порядков разрешимы79. Однако эти результаты не дают никакой конкретной аксиоматики для 3-модальных логик; получающаяся при этом разрешающая процедура имеет огромную вычислительную сложность, так как проблема разрешения теорий второго порядка, как правило, не элементарна по Кальмару80.

В доказательствах финитной аппроксимируемости используется модифицированный метод фильтрации, описанный в главе 1, а также специальная процедура повторной фильтрации.

Автор всегда будет хранить память о своем учителе — Альберте Григорьевиче Драгалине, который поддерживал его научную работу и привлек его внимание к новой области математики — модальной логике.

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. О неполных логиках высказываний. Цоклады АН СССР, т. 235 (1977), N 3, 542-545 .

2. Топологические модели пропозициональных логик. Семиотика и информатика, вып. 15 (1980), 74-98.

3. Modal logics of domains on the real plane. Studia Logica, v. 42 (1983), No. 1, 63-80.

4. Derived sets in Euclidean spaces and modal logic. ITLI Prepublication Series, X-90-05, University of Amsterdam, 1990,43 pp.

5. A logic with progressive tenses. In: Diamonds and Defaults. Studies in Pure and Applied Intensional Logic. (Ed. by M. Dc Rijke). Kluwcr Acadcmic Publishers, pp. 255-285, 1993.

6. On strong neighbourhood completeness of modal and intermediate propositional logics (Part 1).

In: Advances in Modal Logic, volume I. M.Kracbt, M. de Rijke, H. Wansiag and M. Zakbaryascbev, eds. CSLI Publications, pp. 209-222, 1998.

7. "Everywhere" and "here". Journal of Applied Non-Classical Logics, v. 9 (1999), No. 2-3, 369-

380.

79 D. Gabbay, I. Hodkinson. M. Reynolds. Temporal logic, v.l. Oxford University Press. 1994.

80 A.R. Meyer. The inherent complexity of theories of ordered sets. In: "Proceedings of the Internationc

Congress of Mathematicians, Vancom'er,1974", v.2, p.477-482, 1974.

8. On strong neighbourhood completeness of modal and intermediate prepositional logics (Part 11), 11 pp. In: JFAK. Essays dedicated to Julian Van Benthem on the occasion of his 50'' birthday. Edited by J. Gerbrandy, M. Marx, M. De Rijke, and Y. Venema. Vossiuspers, Amsterdam University Press, 1999. ISBN 90 5629 104 I. httpV/turing.wins.uva.nl/~j50 /cdrom

ВВЕДЕНИЕ.

ГЛАВА 1. ОСНОВНЫЕ ПОНЯТИЯ

1.1. Модальные и суперинтуционистские логики.

1.2. Модальные алгебры.

1.3. Окрестностные шкалы.

1.4. Шкалы Крипке.

1.5. Морфизмы окрестностных шкал.

1.6. Морфизмы шкал и моделей Крипке.

1.7. Канонические модели.

1.8. Фильтрации.

ГЛАВА 2. ОКРЕСТНОСТНАЯ ПОЛНОТА И ПОЛНОТА ПО КРИПКЕ

2.1. Пополнения.

2.2. Вспомогательные формулы и шкала Файна.

2.3. Пространства Гжегорчика.

2.4. Окрестностно неполное конечно аксиоматизируемое расширение логики Гжегорчика.

2.5. Окрестностно неполное расширение логики Гжегорчика с одной переменной.

2.6. Пространство У.

2.7. Относительно неполное суперинтуиционистское исчисление с двумя переменными.

ГЛАВА 3. СИЛЬНАЯ ОКРЕСТНОСТНАЯ ПОЛНОТА

3.1. Предварительные замечания.

3.2. Ультрабукеты шкал Крипке.

3.3. 8-К-полные модальные логики.

3.4. З-И-полные суперинтуиционистские логики.

3.5. Ультрабукеты топологических пространств.

ГЛАВА 4. ЛОГИКИ ТОПОЛОГИЧЕСКИХ ПРОСТРАНСТВ С УНИВЕРСАЛЬНОЙ МОДАЛЬНОСТЬЮ

4.1. Постановка задачи.

4.2. Логики и модели.

4.3. Логика 84иС; ее финитная аппроксимируемость.

4.4. с-р-морфизмы.

4.5. Окрестностная полнота S4UC.

ГЛАВА 5. ДЕРИВАЦИОННЫЕ МОДАЛЬНЫЕ ЛОГИКИ

5.1. Операция деривации и ее свойства.

5.2. Деривационные модальные логики.

5.3. Минимальная деривационная логика.

5.4. К4 и D4 как деривационные логики.

5.5. d-р-морфизмы: усиление леммы Маккинси - Тарского.

5.6. К4 и D4 как деривационнные логики нульмерных пространств,

5.7. Обобщенные формулы Куратовского.

5.8. Полнота по Крипке логик D4KUn.

5.9. Финитная аппроксимируемость логик D4KUn.

5.10. Подходящие шкалы.

5.11. D4KLH как деривационная логика.

5.12. D4KU2 как деривационная логика.

ГЛАВА 6. ВРЕМЕННЫЕ ЛОГИКИ С ОПЕРАТОРОМ ЛОКАЛЬНОЙ ИСТИННОСТИ

6.1. Постановка задачи.

6.2. Постулаты и полнота по Крипке для логик FPdI, FParj

6.3. Фильтрации.

6.4. Полнота FParj относительно линий времени.

6.5. Теоремы о полноте для других FPd-логик.

Модальные логики

Теория модальных логик - быстро развивающийся и сравнительно новый раздел математической логики. Изучение логических свойств модальностей было начато еще в античные времена, но на протяжении многих столетий велось лишь в рамках гуманитарных дисциплин (главным образом, философии и лингвистики). Первые модально-логические исчисления были сформулированы только в начале 20-го века (К. Льюис, 1918), а осознание теории модальностей с математической точки зрения началось лишь в 40-е - 50-е гг., благодаря работам А. Тарского, Дж. Маккинси, Б. Йонссона, С. Крипке и др.

Появление многочисленных приложений модальных логик: в информатике (Computer Science), теории искусственного интеллекта, математической лингвистике, а также в основаниях математики, - привело в конце 70-х гг. к стремительному росту этой области, который продолжается и сегодня. Современная модальная логика представляет собой сложившуюся математическую дисциплину с собственным кругом задач и методов; она оказывает влияние на развитие математической логики в целом и связана с рядом других областей математики, в особенности с универсальной алгеброй, теорией категорий и общей топологией.

Модальные логики считаются неклассическими, поскольку в них, кроме обычных логических связок ('и', 'или', 'не' ) используются дополнительные связки -модальности ('необходимо', 'возможно* и т.п.). По сравнению с классической логикой, модальные логики отличаются большим разнообразием синтаксиса и семантики; этим объясняется широкий круг их приложений.

Топологическая (окрестностная) семантика модальных логик

В данной диссертации модальные логики рассматриваются как формальные теории топологических пространств. Изучение топологических пространств средствами математической логики началось достаточно давно. Сама идея построения простого исчисления, в котором можно доказывать топологические теоремы, по существу, принадлежит К. Куратовскому [KURATOWSKJ 1922] (хотя похожая система аксиом предлагалась ранее Риссом [RIESZ 1909]). Проблема создания "топологической теории моделей", аналогичной теории моделей классической логики первого порядка была поставлена А. Робинсоном [ROBINSON 1973]. Принципиальная трудность здесь состоит в том, что топологические структуры невозможно определить в языке первого порядка, поскольку для задания топологического пространства нужно говорить и о точках, и о множествах точек. Таким образом, приходится использовать фрагменты 5 логики второго порядка, что существенно осложняет задачу. Тем не менее, в этом направлении ведутся активные исследования [FLUM, ZIEGLER 1980], [FLUM 1995]. Достоинством теорий второго порядка является богатство их выразительных возможностей, а недостатком — алгоритмическая неразрешимость (и во многих случаях, неперечислимость).

Альтернативный подход к теориям топологических пространств предлагает модальная логика. Хотя при этом получаются более слабые исчисления, они, как правило, оказываются разрешимыми. Теория моделей для этих исчислений активно разрабатывалась во 2-й половине 20-го века.

Использование модальной логики мотивируется непосредственно аксиоматикой Куратовского, которая, в терминах булевых операций и операции внутренности (i) аксиомы топологического пространства имеет вид: А1. ¡(YnZ') = iYniZ А2. iYciiY A3. i YcY A4. i 1 = 1

Здесь 1 - все пространство; Y, Z - его подмножества).

Аксиомы А1-А4 можно рассматривать как абстрактные алгебраические тождества; булева алгебра с дополнительной операцией, удовлетворяющей этим тождествам, называется топобулевой. Каждому топологическому пространству X отвечает топобулева алгебра МА(^), состоящая из всех его подмножеств с булевскими операциями и операцией внутренности.

С тождествами в сигнатуре топобулевых алгебр (n,u,-,0,l,i) естественно связаны формулы в языке модальной логики: тождество t = г, где t, г — топобулевы термы с переменными х-|, Х2,., можно переписать в виде формулы логики высказываний, если заменить символы операций и константы п, и, 0, 1, i соответственно на логические связки и константы л (и), v (или), -1 (не), 1 (ложь), Т (истина), □ (необходимо), знак равенства - на связку ~ (эквивалентно), а предметные переменные xi, Х2,. - на пропозициональные переменные p-j, р2,.

Обратно, каждой модальной формуле А отвечает тождество tA = 1 , где tA -соответствующий топобулев терм.

Модальная формула А называется общезначимой в топобулевой алгебре Д если тождество tA = 1 истинно в j6. Множество всех модальных формул, общезначимых в Д называется модальной логикой алгебры il 6

Модальная формула А общезначима в топологическом пространстве X, если она общезначима в алгебре Ык{%). Модальной логикой пространства % (обозначение: \~{Х)) называется модальная логика алгебры МА(Л^), т.е. множество всех модальных формул, общезначимых в X; модальной логикой класса пространств С (обозначение: L(C)) называется множество всех модальных формул, общезначимых во всех пространствах из С.

Если аксиомы А1-А4 записать в виде модальных формул, то получатся схемы аксиом известного модального исчисления S4: А1\ D(AaB)~DAADB А2'. DAoDDA A3'. DAz>A A4'. □Т~Т В постулаты S4 входят также схемы аксиом классической логики,

А, А:эВ правило modus ponens д

А~ В и правило эквивалентной замены □ А~ □ В

Под логикой S4 обычно понимается множество теорем этого исчисления1. Вообще (нормальной) (моно)модальной логикой принято называть множество модальных формул, содержащее все классические тавтологии и все формулы вида А1', A4' и замкнутое относительно правил подстановки, эквивалентной замены и modus ponens; S4- логики - это модальные логики, содержащие S4.

Классическим результатом является следующая теорема Линденбаума об алгебраической полноте:

34-логики суть в точности модальные логики топобулевых алгебр2.

Связь между аксиомами Куратовского и логикой S4 была обнаружена независимо в [STONE 1937], [TARSKI 1938], [TANG 1938]. В этих работах была доказана теорема о топологической полноте:

S4 есть модальная логика класса всех топологивческих пространств.

Систематическое исследование топобулевых алгебр было начато в [MCKJNSEY, TARSKI 1944]3. В этой области одной из центральных тем стало исследование

1 В дальнейшем будет использоваться несколько другая, эквивалентная аксиоматизация S4.

2 Эта теорема справедлива для более широкого класса пропозициональных логик и соответствующих алгебр.

3 Точнее говоря, в [MCKINSEY, TARSKI1944] изучается эквивалентное понятие — алгебры замыкания (closure algebras). 7 многообразий, или, двойственным образом, исследование эквациональных теорий топобулевых алгебр. Из теоремы Линденбаума следует, что эти теории в точности соответствуют 34-логикам.

Для дальнейшего изучения топологической семантики полезным оказалось эквивалентное определение общезначимости модальной формулы в терминах "возможных миров", предложенное в [MONTAGUE 1968], [SCOTT 1970]. Напомним это определение.

Оценкой в топологическом пространстве % называется отображение ср, сопоставляющее с каждой пропозициональной переменнной подмножество X. Оценка продолжается на все модальные формулы по следующему правилу: ф(-,А)«#-<р(А), ф(АлВ)=ф(А)пф(В), ф (AvB) =ф(А)иф( В), ф(ША)=Чф(А).

Формула А называется истинной в точке w пространства X при оценке ф, если шеф(А). (Сокращенно это обозначается через wNA.) Таким образом, общезначимость модальной формулы в X равносильна ее истинности во во всех точках при всех оценках.

Правило продолжения оценки эквивалентно индуктивному определению истинности в точке: wN-i A^wJ^A; wNAaBo(wNA и wl=B); wNAvB«(wNA rnmwNB); wNGA о {у I у NA} -окрестность w.

Если представлять себе точки пространства X как "возможные миры" или как наблюдателей, которые оценивают формулы как истинные или ложные, то данное определение достаточно естественно. В частности: w признает -iA, если он не признает А, w признает DA, если А признается истинной в окрестности w, т.е. если все наблюдатели, достаточно близкие к w, признают А.

Таким образом, в этой семантике "необходимость" интерпретируется как "локальная истинность" [SCOTT 1970].

Заметим еще, что окрестностную семантику можно определить и для модальных логик, не являющихся расширениями S4. В этом случае вместо топологических пространств используются окрестности ые шкалы, удовлетворяющие аксиомам А1, A4, но не обязательно А2 и A3, а вместо топобулевых алгебр - модальные алгебры. 8

Реляционная семантика модальных логик

Реляционная семантика (или семантика Крипке), ставшая основным инструментом в модальной логике, была введена неявно в [J6NSSON, TARSKI 1951], [J6NSS0N, TARSKI 1952], [DUMMETT, LEMMON 1959] и явно - в работах С. Крипке [KRIPKE 1959], [KRIPKE 1963]. Ее можно рассматривать как частный случай окрестностной семантики.

Напомним, что шкалой Крипке (Kripke frame) называется непустое множество (множество возможных миров) с заданным на нем бинарным отношением (отношением достижимости). Если (W,R) - шкала Крипке, то на множестве всех подмножеств W имеется операция iX = {x|Vy (xRy=i>yе X)}.

При этом, если R - квазипорядок (т.е. рефлексивное и транзитивное отношение), то операция i удовлетворяет аксиомам Куратовского, а в получающемся топологическом пространство N(W,R) пересечение любого числа открытых множеств открыто (такие пространства мы называем пространствами Крипке4). И обратно, всякое пространство Крипке получается из некоторой шкалы Крипке.

В случае шкал Крипке определение истинности в точке (для формулы вида ПА) приобретает вид: wNDA о Vv (wRv =>vHA), т.е. необходимость здесь понимается как истинность во всех достижимых мирах.

Модальной логикой шкалы Крипке (W,R) называется модальная логика соответствующего топологического пространства N(W,R).

Суперинтуиционистские логики

С топобулевыми алгебрами тесно связаны алгебры Хейтинга (или псевдобулевы) [TARSKI 1938], [MCKINSEY, TARSKI 1946]. Алгебру Хейтинга можно определить как дистрибутивную решетку с нулем и единицей и относительным псевдодополнением ("импликацией"): a-»b = U{x|anx^b}. Эти алгебры получаются также из полных топобулевых алгебр как алгебры открытых элементов (т.е. элементов вида ix).

Система тождеств, задающая многообразие алгебр Хейтинга, фактически является системой аксиом интуиционистской логики высказываний, а эквациональные теории алгебр Хейтинга соответствуют суперинтуиционистским логикам, т.е. расширениям интуиционистской логики. Суперинтуиционистские логики связаны с модальными посредством перевода Гёделя - Тарского. Он ставит в

4 Топология пространства N(W,R) называется также правой топологией, индуцированной отношением R (см. [БУРБАКИ 1968]). 9 соответствие каждой интуиционистской формуле А модальную формулу т(А) по следующим правилам:

• т (А) = А, если А - пропозициональная переменная; t(-iA) = D-i7(A) ; t(AvB) = t(A)vt(B); т(АлВ) = т(А)лт(В); t(A-*B) = D(t(A)z>t(B)).

Благодаря этому переводу, суперинтуиционистские логики оказываются фрагментами модальных 34-логик и потому могут рассматриваться в контексте общей теории модальных логик. Точнее говоря, каждой модальной логике Л отвечает суперинтуиционистский фрагмент, состоящий из всех интуиционистских формул, переводы которых принадлежат Л. Обратно, у каждой суперинтуиционистской логики L имеются модальные напарники, т.е. модальные логики с суперинтуиционистским фрагментом L; среди модальных напарников имеется наибольший r(L) и наименьший o(L).

Наибольшим модальным напарником интуиционистской логики является логика Гжегорчика Grz, получающаяся из S4 добавлением схемы аксиом □ (□(А=эйА)эА)эА.

Известно, что множество всех расширений Grz, упорядоченное по включению, изоморфно множеству всех суперинтуиционистских логик посредством отображения а (теорема Блока - Эсакиа; см. [ЧАГРОВ, ЗАХАРЬЯЩЕВ 1997]).

С помощью перевода г определяется также понятие общезначимости интуиционистской формулы в топологическом пространстве и суперинтуиционистская логика пространства X (обозначение: как множество всех интуиционистских формул, общезначимых в X.

Общая проблематика теории модальных и суперинтуиционистских логик.

В последние десятилетия исследования модальных и суперинтуиционистских логик и соответствующих им алгебр проводились по следующим основным направлениям:

• исследование решеток многообразий и решеток соответствующих логик;

• описание свободных алгебр в различных многообразиях и доказательство теорем о представлении;

• построение различных семантик неклассических логик и исследование их свойств;

• построение адекватных интерпретаций логик в других логиках и теориях;

• исследование алгоритмических проблем;

10

• исследование квазимногоообразий и допустимых правил вывода;

• исследование конкретных свойств логик и семейств логик: компактности, свойства Лёвенгейма - Сколема, конечной аксиоматизируемости, интерполяционного свойства, дизъюнктивного свойства и проч.

Во всех этих направлениях был достигнут существенный прогресс. Перечислим здесь лишь некоторые важные результаты, полученные в нашей стране: в работах [МАКСИМОВА, РЫБАКОВ 1974], [МАКСИМОВА 1975], [ЭСАКИА 1979], [ЭСАКИА 1979а] изучалась решетка модальных логик и связь между решетками модальных и суперинтуиционистских логик; в работах [МАКСИМОВА 1977], [МАКСИМОВА 1991] и др. были доказаны общие теоремы об интерполяционных свойствах суперинтуиционистских и модальных логик; в работе [ШЕХТМАН 1978] была впервые построена неразрешимая конечно аксиоматизируемая суперинтуиционистская логика (и, как следствие - 34-логика с аналогичными свойствами); позднее были найдены более простые примеры (см. [ЧАГРОВ, ЗАХАРЬЯЩЕВ 1997]); в работе [ШЕХТМАН 1978а] было дано описание свободных топобулевых и гейтинговых алгебр конечного ранга5; в работах [РЫБАКОВ 1984], [РЫБАКОВ 1985], [РЫБАКОВ 1994] и др. была показана разрешимость допустимости правил для многих модальных и суперинтуиционистских логик (и, как следствие, - разрешимость универсальных теорий соответствующих свободных алгебр); в работе [ЧАГРОВ 1994] была доказана неразрешимость для большинства известных свойств суперинтуиционистских и модальных исчислений; в работах [ЗАХАРЬЯЩЕВ 1989], [ЗАХАРЬЯЩЕВ 1996], [ЗАХАРЬЯЩЕВ 1997] был доказан ряд общих теорем о разрешимости модальных и суперинтуиционистских логик и о сохранении свойств при переходе от суперинтуиционистских логик к модальным.

Важнейшие результаты и общие методы теории модальных логик были систематизированы в недавно вышедшей монографии [ЧАГРОВ, ЗАХАРЬЯЩЕВ 1997].

Многомерные и пространственные модальные логики

Наряду с исследованием общих свойств логик, в 70-е гг. в модальной логике возникло новое направление, изучающее модальные логики многомерных структур:

5 Результаты работ [ШЕХТМАН 1978] и [ШЕХТМАН 1978а] изложены в кандидатской диссертации автора [ШЕХТМАН 1984]

11 геометрических, топологических и реляционных. В моделях этих логик "возможные миры" понимаются как пространственные объекты (точки, прямые, регулярные области и проч.) или же как абстрактные "точки с координатами".

Интенсивное развитие многомерных и пространственных логик вызвано их связями с целым рядом других областей:

• Классическая логика предикатов: изучение фрагментов логики предикатов первого порядка (в частности, в финитной области) и связанных с ними алгебраических структур — цилиндрических, полиадических и реляционных алгебр [MARX, VENEMA 1997], [VAN BENTHEM 1996].

• Неклассические логики предикатов: изучение фрагментов модальных и суперинтуиционистских предикатных логик, а также исследование семантик этих логик [СКВОРЦОВ, ШЕХТМАН 1993], [GABBAY, SHEHTMAN 1993], [WOLTER, ZAKHARYASCHEV 1999].

• Теоретическая информатика (Theoretical Computer Science): изучение логик систем переходов и алгебр процессов; построение и исследование логик паралллельных вычислений [REIF, SISTLA 1985], [LADNER, REIF 1986], [DE RDKE 1993], [SPAAN 1993], [ARNOLD 1994], [VAN BENTHEM 1996].

• Теория искусственного интеллекта (Artificial Intelligence): создание логических основ систем представления знаний (динамические логики дескрипций) [BAADER, OHLBACH 1995], [WOLTER, ZAKHARYASCHEV 1998], [WOLTER, ZAKHARYASCHEV 1998a]; построение и использование логик геометрических и топологогических структур в задачах качественного анализа пространственной информации [BENNETT

1996], [COHN, BENNETT, GOODAY, GOTTS 1998], [AIELLO, VAN BENTHEM 1999].

• Лингвистическая семантика: логический анализ временно-видовых и дейктических конструкций [ÁQVIST, GÜNTHER 1978], [NISHIMURA 1980],

• Математическая физика: построение и изучение временных логик для различных моделей пространства-времени [GOLDBLATT 1980], [ШЕХТМАН 1983], [RODRIGUEZ, ANGER 1993].

Хотя общая теория многомерных и пространственных модальных логик пока не создана, здесь уже получен ряд нетривиальных результатов. Например, активно исследовались произведения модальных логик: впервые в [ШЕХТМАН 1978b], [ШЕХТМАН 1987] и более глубоко в [GABBAY, SHEHTMAN 1998], [REYNOLDS, ZAKHARYASCHEV 1999], [WOLTER 1998], [MARX 1999], [KURUCZ 1999]. Проводилось также исследование модальных логик подмножеств действительной плоскости [ШЕХТМАН 1983], интервальных модальных логик [MARX, VENEMA

1997], [NISHIMRA 1980], модальных логик проективных плоскостей [BALBIANI, FARIÑAS DEL CERRO, TINCHEV, VAKARELOV 1997]. К пространственной логике

12 следует отнести и исследование модальных логик топологических пространств; разнообразные подходы к этим логикам и прикладные их аспекты обсуждалются в [BENNETT, GOODAY, GOTTS 1998], [AIELLO, VAN BENTHEM 1999].

Основные результаты диссертации

В настоящей диссертации модальные и суперинтуиционистские логики высказываний исследуются с точки зрения их топологической (окрестностной) семантики. При этом, как и в классической теории моделей, рассматриваются вопросы двух основных типов:

- построение логики, описывающей данный класс топологических пространств и исследование ее свойств;

- нахождение класса пространств, отвечающего данной логике.

В диссертации получены следующие основные результаты.

1. В классе расширений логики Гжегорчика найдены модальные логики, неполные в топологической семантике.

2. Доказана неэквивалентность топологической семантики и семантики Крипке для суперинтуиционистских логик.

3. Доказано, что для всех модальных логик, содержащих К4, и для всех суперинтуиционистских логик из полноты по Крипке следует сильная полнота в топологической семантике.

4. В языке с операторами локальной и универсальной истинности построена система аксиом и доказана финитная аппроксимируемость логики произвольного связного плотного в себе сепарабельного метрического пространства.

5. Построены системы аксиом и доказана финитная аппроксимируемость деривационных логик для пространств Rn и для нульмерных плотных в себе подмножеств действительной прямой.

6. В языке с временными операторами и оператором локальной истинности построены системы аксиом и доказана финитная аппроксимируемость для логики рациональной прямой и логики класса всех линейных порядков.

Содержание диссертации

Опишем теперь результаты диссертации более подробно.