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

(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 |= А ложно;

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

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

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

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

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

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

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

Упражнение 1

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

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

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

8) 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 верно во всех мирах, т.е. эта формула – тавтология модели М.

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

Понятие модели Крипке (W, R, h) такое же, как для модальной логики. Определяется истинность формул [F]А и [P]А, вместо А.

Если tRu, то говорят, что t – прошлое для u, а u – будущее для t. (Напомним, что tRu означает (t, u) Î R.)

Обычно отношение R предполагается транзитивным в том смысле, что из tRu и uRv следует: tRv (исключением являются шкалы с циклическим временем). Утверждения для интерпретации А заменяются на следующие:

1) M, t |= [F]А, если и только если M, u |= А для всех u Î W таких, что tRu.

2) M, t |= [P]А, если и только если M, u |= А для всех u Î W таких, что uRt.

Упражнение 3

Доказать утверждения:

1) M, t |= <F>А, если и только если существует u Î W такой, что tRu и M, u |= А.

2) M, t |= <P>А, если и только если существует такой u Î W, что uRt и M, u |= А.

Тавтологии

Будем рассматривать тавтологии относительно семантики Крипке. Формула А называется тавтологией если M, t |= А для любых модели M = (W, R, h) и мира t Î W. Формула А называется выполнимой, если существуют такие модель М и мир t, что M, t |= А. Формулы А и В называются эквивалентными, если для любых модели М и мира t утверждение M, t |= А равносильно утверждению M, t |= В.

Упражнение 4

Доказать утверждения:

1) А тавтология, если и только если ØА невыполнимо;

2) А выполнимо, если и только если ØА не тавтология;

1) А и В эквивалентны тогда и только тогда, когда А « В – тавтология.

2) тавтологии и исчисления высказываний являются тавтологиями модальной логики;

3) ØА эквивалентно àØА;

4) Ø (А ® В) эквивалентно à(А & ØВ).

Теорема (о нормальности). Для любых формул А и В имеет место тавтология:

 (А ® В) ® (А ® В).

Доказательство. Пусть M = (W, R, h) – модель Крипке, t Î W – мир. Предположим выполнение M, t |=  (А ® В). Докажем, что А ® В верно в мире t. С этой целью докажем, что из M, t |= А следует M, t |= В. Пусть u Î W – мир, для которого (t, u) Î R.  Если верно  M, t |= А,  то  M, u |= А.  По предположению,  M, t |=  |=  (А ® В), значит, M, u |= А ® В. Получаем из M, u |= А  и  M, u |= А ® В, что M, u |= |= В. Теорема доказана.

Условные тавтологии

Чтобы охватить формулы, верные при дополнительных условиях (аксиомах), рассматриваются модели с фиксированной шкалой или набором шкал.

Формула А называется верной в модели M = (W, R, h), если она верна для всех tÎW. Формула А называется тавтологией относительно шкалы, если она верна для любой модели с данной шкалой. Формула А называется тавтологией относительно класса шкал С, если она является тавтологией относительной каждой шкалы из класса С.

Теорема (о рефлексии). Пусть р – атом. Формула р ® р является тавтологией относительно шкалы (W, R), если и только если R – рефлексивное отношение (т.е. wRw для всех w Î W).

Доказательство. Пусть R – рефлексивно. Пусть М – модель со шкалой (W, R), tÎW – произвольный мир и пусть M, t |= р ® р. Поскольку модель М – произвольная, то р ® р – тавтология относительно шкалы (W, R).

Пусть, наоборот, р ® р – тавтология относительно (W, R). Пусть t Î W. Докажем, что (t, t) Î R. С этой  целью определим модель М = (W, R, h), полагая (при фиксированном t)

h(p) = {u Î W : (t, u) Î R}.

Ясно, что M, t |= р. Но р ® р верно, стало быть, M, t |= р. Отсюда t Î h(p). Следовательно, (t, t) Î R, что и требовалось доказать.

Упражнение 5

Доказать, что если R Í W ´ W – рефлексивно, то А ® А – тавтология относительно шкалы (W, R) для любой формулы А.

Формула (А ® В) ® (А ® В) является тавтологией относительно класса всех шкал Крипке. Такие формулы называют естественно истинными. Формула А ® А верна относительно некоторого класса шкал. Такие формулы называются условно истинными.