WWW.DISSERS.RU

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

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

Pages:     | 1 ||

Истинность формулы в точке x в топологической модели (X, ) (обозначение:

X,, x |= ) определяется по индукции:

X,, x |= p x (p), X,, x |=, X,, x |= X,, x |= или X,, x |=, X,, x |= U(x)y U(x) (X,, y |= ) x I {y | X,, y |= }, X,, x |= [ =] y = x (X,, y |= ).

Определение 3. Формула общезначима в пространстве X, если она истинна в любой точке любой модели на X (обозначение: X |= ).

Определение 4. Топо логической модальной логи кой с модальностью неравенства или D-логикой класса топологических пространств T (обозначение:

LD(T )) называется множество всех формул языка ML(, [ =]), общезначимых во всех пространствах класса T.

Логика L полна относительно T, если LD(T ) = L.

Если X — топологическое пространство, то LD({X}) сокращается до LD(X).

Определение 5. Шкалой Крипке с n отношениями (или n-шкалой Крипке ) называется кортеж F = (W, R1,..., Rn) такой, что W = и Ri W W для всех i = 1,..., n.

Определение 6. Моделью Крипке на шкале F = (W, R, RD) называется пара M = (F, ), где : prop P(W ) — оценка. Истинность формулы в точке x модели Крипке M определяется по индукции. Истинность атомарных формул и формул вида определяется, как в Определении 2, а истинность формул с модальностями — следующим образом:

M, x |= y(xRy M, y |= A) M, x |= [ =] y(xRDy M, y |= ) Определение 7. Формула общезначима в шкале F, если она истинна в любой точке любой модели на F (обозначение: F |= ).

Определение 8. (Модальной) логикой класса шкал Крипке F (обозначение:

L(F)) называется множество всех формул, общезначимых во всех шкалах класса F.

Для шкалы F мы пишем L(F ) вместо L({F }).

Определение 9. Шкала Крипке F называется L-шкалой для модальной логики L, если L L(F ).

Определение 10. Логика L называется полной относительно класса шкал C, если L(C) = L. Логика L называется полной по Крипке, если она полна относительно некоторого класса шкал.

Определение 11. Пусть F = (W, R, RD) — шкала Крипке, S = R RD, S — транзитивное и рефлексивное замыкание S. Шкала F называется конусом, если S(x) = W для некоторого x W.

Хорошо известно, что любая полная по Крипке логика полна относительно некоторого класса конусов.

Известно, что логика S4D полна относительно класса всех топологических пространств. Это следует из того, что она полна относительно всех шкал Крипке вида (W, R, =), где R транзитивно и рефлексивно.

В первой главе также доказывается полнота по Крипке всех рассматриваемых логик методом канонической модели.

Определение 12. Логика L называется финитно аппроксимируемой, если она полна относительно некоторого класса конечных шкал.

Теорема 13. Логики S4DS, S4DT1, S4DT1S, а также все логики Lk, LCk финитно аппроксимируемы.

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

Следствие 14. Логики S4DS, S4DT1, S4DT1S, а также все логики Lk, LCk разрешимы.

Это сразу следует из конечной аксиоматизируемости и финитной аппроксимируемости.

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

Теорема 15. Логика S4DS полна относительно класса всех плотных в себе пространств.

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

Теорема 16. S4DT1S полна относительно произвольного нульмерного плотного в себе пространства.

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

Следствие 17. S4DT1S полна относительно класса всех плотных в себе T1пространств.

Следствие 18. S4DT1 полна относительно класса всех нульмерных пространств.

Следствие 19. S4DT1 полна относительно класса всех T1-пространств.

В третьей главе изучаются D-логики пространств Rn, n 2. Доказывается Теорема 20. Для любого n 2, логика LC1 полна относительно Rn.

План доказательства состоит в следующем. Сначала доказывается, что логика LC1 полна относительного класса конечных шкал Крипке специального вида, которые называются аллеями. Затем доказывается, что для любой аллеи F существует отображение из Rn, где n 2, на F, сохраняющее общезначимость.

Так как Rn |= LC1, то отсюда следует утверждение теоремы.

В четвертой главе изучаются D-логики действительной прямой и окружности.

Включение LD(R) LC2 легко проверяется. В действительности оказывается, что LD(R) = LC2 и, более того, справедлива Теорема 21. D-логика прямой LD(R) не является n-аксиоматизируемой ни для какого n.

Доказательство проходит следующим образом. Для любого LC2-конуса F мы определяем характеристический граф (F ), обладающий свойством: если существует отображение R F, сохраняющее общезначимость, то граф (F ) эйлеров15.

Граф называется эйлеровым, если в нем существует путь проходящий по всем ребрам ровно по одному разу.

Затем, аналогично работе16, мы строим две бесконечные последовательности LC2-конусов (Fn)n 1 и (Fn)n 1, такие что для любого n (1) шкалы Fn и Fn не различимы с помощью n-формул;

(2) граф (Fn) не эйлеров;

(3) существует отображение R Fn, сохраняющее общезначимость.

Отсюда, используя характеристические формулы типа Янкова-Файна, мы получаем утверждение теоремы.

Аналогично, но с использованием несколько иной последовательности конечных шкал, доказывается Теорема 22. D-логика окружности LD(S1) не является n-аксиоматизируемой ни для какого n.

В приложении A приведены оценки сложности логик, изучавшихся в диссертации.

В приложении B дается определение гибридного языка и гибридных логик.

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

Благодарности Автор благодарит своего научного руководителя, доктора физико-математических наук, профессора Валентина Борисовича Шехтмана за постановку задачи, внимание к работе и постоянную помощь. Автор также благодарит заведующего кафедры математической логики и теории алгоритмов, доктора физикоматематических наук, профессора Владимира Андреевича Успенского и всех сотрудников кафедры за творческую атмосферу, которая способствовала научной работе.

Л. Л. Максимова, Д. П. Скворцов, В. Б. Шехтман, Невозможность конечной аксиоматизации логики финитных задач Медведева Доклады АН СССР, т.245, №5, 1979, 1051-Работы автора по теме диссертации [1] А.В. Кудинов. О топологической модальной логике R с неравенством.

Успехи математических наук, 2008, 63:1(379), 163–164.

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

[3] A. Kudinov. Difference modality in topological space s. In: Algebraic and Topological Methods in Non-classical Logics II, Barcelona, 2005, Abstracts, Universitat de Barcelona, 50-51.

[4] A. Kudinov. Topological modal logic with the difference modality. In: Computer science applications of modal logic, Independent University of Moscow, September 5-9, 2005, Abstracts, 27-28.

Pages:     | 1 ||






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