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

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

(p ® q) ® ( p ® q).

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

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

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

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

Определение. Пара множеств (W, R), где W – непустое множество, а RÍW´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 Î h(p), и ложным в других случаях.

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

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

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

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

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

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

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

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

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

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

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

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

Упражнение 1

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

9) M, t |= Ø(А Ú В), если и только если M, t |= ØА & ØВ;

10) M, t |= Ø А, если и только если M, t |= àØА;

11) M, t |= ØàА, если и только если M, t |= ØА.

Упражнение 2

Пусть p, q Î 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 Ï {p, q}.

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

1) р верно в 1 и 3, ложно в 4;

2) Øр верно в 3, 0 верно в 3;

3) àq & àØq верно в 1, q ложно в 1;

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

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