WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 |
Московский Государственный Университет имени М. В. Ломоносова Механико–математический факультет

На правах рукописи

УДК 510.643 КУДИНОВ Андрей Валерьевич Топологические модальные логики с модальностью неравенства 01.01.06 — математическая логика, алгебра, теория чисел

АВТОРЕФЕРАТ

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

Москва 2008

Работа выполнена на кафедре математической логики и теории алгоритмов Механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Научный консультант: доктор физико-математических наук, профессор В. Б. Шехтман.

Официальные оппоненты: доктор физико-математических наук, профессор А. В. Чагров (Тверской государственный университет);

кандидат физико-математических наук, Р. Э. Яворский (Математический институт им. В. А. Стеклова Российской академии наук).

Ведущая организация: Институт математики им. С. Л. Соболева Сибирского отделения РАН.

Защита диссертации состоится 5 декабря 2008 года в 16 часов 40 минут на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М. В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, Механико-математический факультет, аудитория 14-08.

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

Автореферат разослан 5 ноября 2008 года.

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

Общая характеристика работы

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

Как раздел математической логики, модальная логика появилась в начале XX века (в работах К. Льюиса, К. Г и др.). В настоящее время модальная еделя логика активно развивается, благодаря разнообразным применениям — в том числе, в информатике, математической лингвистике и основаниях математики.

Основное отличие модальной логики от классической — использование дополнительных связок («модальностей»), таких как «необходимо», «возможно» и др.

В топологических моделях можно интерпретировать модальность («необходимо») как канторовскую операцию внутренности, а двойственную к ней модальность («возможно») — как операцию замыкания. Основы для такой интерпретации были заложены К. Куратовским, который предложил определение топологического пространства с помощью операции замыкания. Аксиомы Куратовского соответствуют аксиомам хорошо известной модальной логики S4.

Более того, как показали Дж. Маккинси и А. Тарский1, логика S4 полна в топологической семантике.

В конце XX века была установлена связь между топологической семантикой модальных логик и задачами представления графической и пространственной информации, возникшими в теоретической информатике и информационных технологиях. В частности, для описания взаимного расположения пространственных объектов было предложено2 исчисление RCC8, использующее 8 основных отношений между регулярными областями в топологическом пространстве.

Как вскоре выяснилось3, это исчисление вкладывается в модальную логику S4U (S4 c универсальной модальностью). В настоящее время RCC8 и аналогичные исчисления применяются в географических информационных системах4 (ГИС) J.C.C. McKinsey, A. Tarski. The algebra of topology Annals of Mathematics, v.45(1944), 141-191.

D.A. Randell, Z. Cui and A. G. Cohn. A spatial logic based on regions and connections. In Principles of Knowledge Representation and Reasoning: Proceedings of the 3rd International Conference, pp. 165–176.

Morgan Kaufmann, 1992.

B. Bennett. Spatial reasoning with propositional logic. In: Proceedings of the 4th International Conference on Knowledge Representation and Reasoning, pp. 51–62. Morgan Kaufmann, 1994.

Smith, T. and Park, K. An algebraic approach to spatial reasoning. International Journal of и других областях информатики.

Топологическая семантика может быть сформулирована эквивалентным образом: каждая пропозициональная формула интерпретируется как подмножество топологического пространства («множество точек, где формула считается истинной»). Тогда формула истинна в точке x, если истинна в некоторой окрестности x.

Начиная с конца 1950-х годов для модальной логики получила широкое распространение реляционная семантика Крипке, основанная на сходной идее. При этом формулы интерпретируются в реляционных структурах («шкалах Крипке»), а формула истинна в точке x, если истинна во всех точках, связанных с x по данному бинарному отношению. Отметим, что для расширений логики Sреляционная семантика является частным случаем топологической семантики:

шкалы Крипке в точности соответствуют так называемым «александровским пространствам», в которых любое пересечение открытых множеств открыто.

Всевозможные расширения логики S4 описывают разнообразные свойства топологических пространств и шкал Крипке. Однако далеко не все свойства топологических пространств выразимы модальными формулами в стандартном языке с модальностью. Так, в работе Дж. Маккинси и А. Тарского (1944) доказано, что в стандартной топологической семантике логика S4 полна относительно любого сепарабельного плотного в себе метрического пространства.

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

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

Первоначальное изучение модальности было начато также в работе Дж. Маккинси и А. Тарского (1944). Логики с деривационной модальностью подробно Geographical Information Systems, 6:177–192, 1992.

исследовались в работах5,6,7, где был получен ряд результатов о полноте и выразимости. С помощью модальности удается выразить такие свойства, как плотность в себе и аксиому отделимости T1.

Универсальная модальность [] интерпретируется следующим образом: формула [] истинна, если истинна во всех точках. При добавлении модальности [] можно выразить новые топологические свойства, как, например, связность8.

Модальность неравенства [ =], изучению которой посвящена данная диссертация, интерпретируется следующим образом: формула [ =] истинна, если истинна во всех точках, кроме, быть может, данной. Эта модальность впервые введена К. Сегербергом9 и исследована позднее рядом авторов (см. например10). (Отметим, что [] выражается через [ =]: [] [ =].) Как было замечено11,12, при добавлении модальности [ =] становятся выразимыми многие свойства топологических пространств типа связности, плотности в себе и отделимости.

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

Также отметим, что в настоящее время активно исследуются другие многоG. Bezhanishvili, L. Esakia, D. Gabelaia. Some results on modal axiomatization and definability for topological spaces. Studia Logica 81(3), pp 325-355, 2005.

Л.Л. Эсакиа. Слабая транзитивность — реституция. Логические исследования, т.8, стр.244245. Москва, Наука, 2001.

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

V. Shehtman. “Everywhere” and “Here”. Journal of Applied Non-classical Logics, v.9 (1999), No 2/3, 369-380.

K. Segerberg. A note on the logic of elsewhere. Theoria, v. 46, No 2/3, pp. 183–187, 1980.

V. Goranko. Modal definability in enriched languages. Notre Dame, Journal of Formal Logic, No.1, pp.

81–105, 1989.

B. ten Cate, D. Gabelaia, D. Sustretov. Modal languages for topology: expressivity and definability. To appear in Annals of Pure and Applied Logic, 2008.

A. Kudinov. Topological modal logics with difference modality. In: Advances in Modal Logic, V.6, College Publications, London, 2006, 319-332.

T. Litak. Isomorphism via translation. In: Advances in Modal Logic, V.6, College Publications, London, 2006, 333-351.

модальные логики, связанные с топологией: комбинированные пространственновременные логики, динамические топологические логики, логики произведений топлогических пространств и логики метрических пространств (см. Справочник по пространственным логикам14).

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

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

1) Найдены конечные аксиоматизации топологических модальных логик с модальностью неравенства для класса всех плотных в себе топологических пространств, для класса всех T1-пространств и для класса всех плотных в себе T1-пространств; доказана финитная аппроксимируемость и разрешимость этих логик.

2) Показано, что логика с модальностью неравенства пространства Rn для n 2 не зависит от n. Найдена конечная аксиоматизация этой логики, доказана финитная аппроксимируемость и разрешимость этой логики.

3) Доказана конечная неаксиоматизируемость топологических модальных логик с модальностью неравенства для прямой и окружности. Более того, доказана неаксиоматизируемость этих логик формулами с фиксированным конечным числом переменных.

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

Для доказательства финитной аппроксимируемости используются метод канонической модели и метод фильтрации.

Handbook of Spatial Logics. Editors: M. Aiello, I. Pratt-Hartmann, J. van Benthem. Springer, 2007.

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

Для доказательства конечной неаксиоматизируемости логик прямой и окружности используются понятие «n-эквивалентности» на шкалах Крипке и характеристические формулы типа Янкова-Файна.

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

Апробация работы Результаты диссертации докладывались в 2000-2008 гг.:

• на научно-исследовательском семинаре кафедры математической логики и теории алгоритмов механико-математического факультета МГУ под руководством академика РАН С.И. Адяна, член-корр. РАН Л.Д. Беклемишева и проф. В.А. Успенского, и других семинарах кафедры;

• на Международной конференции «Алгебраические и топологические методы в неклассических логиках II» (Барселона, Испания, 2005);

• на Международной конференции «Приложения модальной логики в информатике» (Москва, 2005);

• на Международной конференции «Advances in Modal Logic, 2006» (Нуза, Австралия, 2006), • на XXIX конференции молодых ученых (МГУ, 2007);

• на международной конференции «Алгебраические и топологические методы в неклассических логиках III» (Оксфорд, Великобритания, 2007).

Публикации Результаты автора по теме диссертации опубликованы в 4 работах, список которых приводится в конце автореферата.

Структура и объем диссертации Диссертация состоит из введения, четырех глав, двух приложений и библиографии (40 наименований). Общий объем диссертации составляет 92 страницы.

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

Фиксируем счетное множество пропозициональных переменных Prop. Для натурального n 1 n-модальные формулы строятся рекурсивно с помощью множества Prop, константы «ложь» (), импликации () и n одноместных модальностей (,,..., ).

1 2 n Двойственные модальности определяются следующим образом: = i i ¬ ¬.

i Множество всех n-модальных формул называется n-модальным языко м и обозначается ML(,,..., ).

1 2 n Пропозициональной n-модальной логикой называется множество n-модальных формул, содержащее все классические тавтологии, аксиомы нормальности (p q) ( p q), для всех i = 1,..., n;

i i i и замкнутое относительно правил подстановки, Modus Ponens, введение модальности:

A(pi) A, A B A (Sub), (MP ), ( ).

i A(B) B A i Пусть даны n-модальная логика L и множество формул, тогда через L + мы будем обозначать минимальную n-модальную логику содержащую L.

В диссертации рассматриваются только 1-модальные и 2-модальные логики.

При этом,, [ =] и = соответственно обозначают,, и.

1 1 2 Определение 1. Фиксируем порядок пропозициональных переменных. Модальная формула называется m-формулой, если в ней встречается не более m первых переменных. Логика L называется m-аксио матизируе мой, если её можно аксиоматизировать с помощью m-формул.

Введем обозначение [] [ =].

Перечислим дополнительные аксиомы, использующиеся в диссертации:

(BD) p [ =] = p (4-) p [ =]p [ =][ =]p D (T ) p p (4 ) p p (D ) []p p (AT1) [ =]p [ =] p (DS) [ =]p p (AC) []( p ¬p) []p []¬p k+1 k+(AEk) [ =]p ¬p (p Qk) (p ¬Qk), i=1 i i=1 i где для данного k формулы Qk (i = 1... k + 1) определяются следующим обраi зом:

i-1 k Qk = ¬q1, Qk = qj ¬qi (для 1 < i k), Qk = qj.

1 i k+j=1 j=Рассматриваются следующие логики:

S4 = K1 + {T, 4 }, S4D = K2 + T, 4, BD, 4-, D, D S4DS = S4D + DS, S4DT1 = S4D + AT1, S4DT1S = S4DT1 + DS, Lk = S4DT1S + AEk, LCk = Lk + AC.

Определение 2. Пусть X — топологическое пространство. Топо логической моде лью на X называется пара (X, ), где функция : prop P(X) (оценка) сопоставляет каждой пропозициональной переменной p prop множество (p) X.

Pages:     || 2 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»