Семантика модальной логики

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

Семантика модальной логики (p ® q) ® ( Семантика модальной логики p ® Семантика модальной логики q).

Такие семантики относятся к нормальным. Рассмотрим одну из них.

Семантика Крипке

Рассматривается множество миров. Модальное высказывание aА считается истинным, если А истинно в некоторых из возможных миров. Истинность обычных формул измеряется по отношению к текущему миру. (Идея принадлежит Лейбницу, и была разработана Сеулом Крипке).

Возьмём произвольное множество W; его элементы будем называть мирами или состояниями. Рассмотрим произвольное бинарное отношение R на W. Если значение предиката R(t, w) равно 1, то w называется возможным или доступным миром для t.

Определение. Пара множеств (W, R), где W – непустое множество, а RIW´W – бинарное отношение на W, называется шкалой Крипке. Отношение R называется отношением доступности.

Пример 1

Пусть W = {1, 2, 3, 4, 5}, R = {(1, 1), (1, 2), (2, 3), (1, 5), (5, 4), (4, 4), (4, 3)}. Шкалу Крипке (W, R) можно рассматривать как ориентированный граф, вершинами которого служат элементы из W, а рёбрами – пары, принадлежащие R. Например, для мира 1 будут доступны миры 1, 2 и 5, ибо (1, 1), (1, 2) и (1, 5) принадлежат R.

Пример 2

Каждое частично упорядоченное множество (Х, ?) будет шкалой Крипке, имеющей множество миров Х и отношение доступности ?. В частности, N = (w, ?), (Z, ?), (Q, ?), (R, ?) – множества натуральных, целых, рациональных и действительных чисел, с обычным отношением порядка будут составлять шкалы Крипке.

Пример 3

Существуют шкалы с циклами, например, W = {1, 2, 3, 4} с отношением R = {(1, 2), (2, 3), (3, 4), (4, 1)}.

Можно привести искусственные примеры, такие, как шкала рекурсии Макинсона (w, R), где R состоит из пар (m, n), для которых m ? n + 1.

Модели Крипке

Чтобы задать интерпретацию модальных формул, надо задать функцию на атомах (из P). Значения этой функции зависят также от состояний. Оценкой называется функция h: P ® P(W), определённая на множестве всех атомов и принимающая значения во множестве всех подмножеств множества W. Атом p называется истинным в мире w, если w I h(p), и ложным в других случаях.

Тройка (W, R, h) называется моделью Крипке. Шкала Крипке может быть превращена в модели Крипке в зависимости от функции оценки h.

Пусть М = (W, R, h) – модель Крипке. Для формулы А и мира t I W определим утверждение M, t |= A с помощью индукции:

1) если р – атом, то M, t |= р тогда и только тогда, когда t I h(p);

2) M, t |= 1 (всегда);

3) M, t |= OА тогда и только тогда, когда утверждение M, t |= А ложно;

4) M, t |= АВ тогда и только тогда, когда M, t |= А и M, t |= В;

5) M, t |= Семантика модальной логики А тогда и только тогда, когда М, u |= А для всех таких u I W, что tRu.

Запись: tRu означает, что (t, u) I R. Выражение M, t |= А читается: «М удовлетворяет в мире t формуле А», или «формула А выполняется в мире t для модели М». Другие обозначения: М |= А(t), М |=t А, Семантика модальной логики .

Легко видеть, что имеют место утверждения, дополняющие свойства 1 – 5:

6) M, t |= А U В, если и только если M, t |= А или M, t |= В;

7) M, t |= (А ® В) если и только если из M, t |= А следует, что M, t |= В;

8) M, t |= aА, если и только если M, t |= А для некоторого u I W такого, что tRu.

Упражнение 1

Следующие утверждения предлагается проверить самостоятельно:

9) M, t |= O(А U В), если и только если M, t |= OАOВ;

10) M, t |= O Семантика модальной логики А, если и только если M, t |= aOА;

11) M, t |= OaА, если и только если M, t |= Семантика модальной логики OА.

Упражнение 2

Пусть p, q I P. Рассмотрим модель M = (W, R, h), где W = {1, 2, 3, 4, 5},
R = {(1, 1), (1, 2), (2, 3), (1, 5), (5, 4), (4, 4), (4, 3)}, h(p) = {1, 2, 5}, h(q) = {1, 3, 4} и
h(r) = ? для всех r I {p, q}.

(Высказывание р верно в мирах 1, 2 и 5; q – в 1, 3 и 4). Проверить утверждения:

1) Семантика модальной логики р верно в 1 и 3, ложно в 4;

2) Семантика модальной логики Oр верно в 3, Семантика модальной логики 0 верно в 3;

3) aqaOq верно в 1, Семантика модальной логики q ложно в 1;

4) aq, Семантика модальной логики q оба верны в 2, ибо только 3 доступно из 2;

5) a1 ® aq верно во всех мирах, т.е. эта формула – тавтология модели М.

24.01.2015 Маргарита Ниязова: Семантика модальной логики


Добавьте постоянную ссылку в закладки. Вы можете следить за комментариями через RSS-ленту этой статьи.
Комментарии и трекбеки сейчас закрыты.