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

• Автор: Кудинов, Андрей Валерьевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 92 с. : ил.

Оглавление
Введение
1 Обзор определений
1.1 Описание языка
1.2 Аксиомы и логики
1.3 Топологическая семантика
1.4 Семантика Крипке
1.5 Топологические пространства и шкалы Крипке с выделенными точками
1.6 р -морфизмы
1.7 Некоторые свойства топологических пространств с выделенными точками
1.8 Свойства шкал Крипке
1.9 Каноничность аксиом
1.10 Фильтрация канонической модели
2 Логики некоторых классов топологических пространств
2.1 Логики класса всех пространств и класса всех плотных в себе пространств
2.2 Логики нульмерных и Д-пространств
3 Логика пространства Еп, для п
3.1 Аллеи
3.2 Доказательство полноты
4 Логики вещественной прямой и окружности
А Сложность изучавшихся логик
В Сводимость к гибридной логике

ВВЕДЕНИЕ
Актуальность темы
Диссертация посвящена топологической семантике пропозициональных модальных логик.
Как раздел математической логики, модальная логика появилась в начале XX века (в работах К. Лыоиса [Lewis, 1918], К. Гёделя [Gödel, 1933] и др.). В настоящее время модальная логика активно развивается, благодаря разнообразным применениям — в том числе, в информатике, математической лингвистике и основаниях математики. Основное отличие модальной логики от классической — использование дополнительных связок («модальностей»), таких как «необходимо», «возможно» и др.
В топологических моделях можно интерпретировать модальность □ («необходимо») как канторовскую операцию внутренности, а двойственную к ней модальность О («возможно») — как операцию замыкания. Основы для такой интерпретации были заложены К. Куратовским [Kuratowski, 1922], который предложил определение топологического пространства с помощью операции замыкания. Аксиомы Куратовского соответствуют аксиомам хорошо известной модальной логики S4. Более того, как показали Дж. Маккинси и А. Тарский [McKinsey, Tarski, 1944], логика S4 полна в топологической семантике.
В конце XX века была установлена связь между топологической семантикой модальных логик и задачами представления графической и про-

ВВЕДЕНИЕ

странственной информации, возникшими в теоретической информатике и информационных технологиях. В частности, для описания взаимного расположения пространственных объектов было предложено исчисление RCC8 [Randeil et al., 1992], использующее 8 основных отношений между регулярными областями в топологическом пространстве. Как вскоре выяснилось [Bennett, 1994], это исчисление вкладывается в модальную логику S4U (S4 с универсальной модальностью). В настоящее время RCC8 и аналогичные исчисления применяются в географических информационных системах (ГИС) [Smith, Park, 1992] и других областях информатики.
Топологическая семантика для связки □ может быть сформулирована эквивалентным образом: каждая пропозициональная формула интерпретируется как подмножество топологического пространства («множество точек, где формула считается истинной»). Тогда формула □ ф истинна в точке х, если ф истинна в некоторой окрестности х.
Начиная с конца 1950-х годов для модальной логики получила широкое распространение реляционная семантика Крипке, основанная на сходной идее [Kripke, 1959]. При этом формулы интерпретируются в реляционных структурах («шкалах Крипке»), а формула □ ф истинна в точке х, если ф истинна во всех точках, связанных с ж по данному бинарному отношению. Отметим, что для расширений логики S4 реляционная семантика является частным случаем топологической семантики: шкалы Крипке в точности соответствуют так называемым «александровским пространствам», в которых любое пересечение открытых множеств открыто.
Всевозможные расширения логики S4 описывают разнообразные свойства топологических пространств и шкал Крипке. Однако далеко не все свойства топологических пространств выразимы модальными формулами в стандартном языке с модальностью □. Так, в работе [McKinsey, Tarski,
Глава! Обзор определений

компонентно, но не является локально 1-компонентым, тогда как множество рациональных чисел <0> не является локально А;-компонентным ни для какого к.
Лемма 1.56. Пусть X = (X,АД)—пространство с выделенными точками, тогда следующие два условия эквивалентны:
1) X (= АТ,
2) X — пространство с замкнутыми выделенными точками.
Доказательство. 1) =Ф- 2) Пусть X |= А1. Докажем, что для любой выделенной точки ж множество и = X — {х} открыто.
Если X = {ж}, то и — открыто, и утверждение очевидно.
Определим оценку в на X таким образом, что 9{р) — II (и произвольным образом — на других переменных). Тогда х |= [ф]р и х (= АТ, а значит,
ж И [ФРр-
Возьмем у ф х, тогда у |= □ р, т.е. у принадлежит и вместе с некоторой своей окрестностью. Следовательно, множество и открыто.
1) 2) Пусть X — пространство с замкнутыми выделенными точками,
и пусть X, /9, ж = [ф]р для х Е Ах, тогда в(р) 3 1- {ж}. Чтобы доказать, что х |= [ф]Пр, мы должны показать, что у = Ор для всех у Е X — {ж}. Возьмем произвольную точку у Е X— {ж}. Т.к. X — {ж} открыто, то у = Пр, следовательно, ж [= [ф]Пр. □
ЛЕММА 1.57. Пусть X = (X,Ах)—пространство с выделенными точками, тогда следующие два условия эквивалентны:
1) X И ОБ;
2) X плотно в выделенных точках.