Интерпретации исчисления высказываний

Семантика исчисления L определяется с помощью произвольной функции е:S {0,1}=I, удовлетворяющей для всех А,В S соотношениям и е(А В)=е(А) е(В).

Функция е называется интерпретацией исчисления L.

Лемма 1 (об интерпретации исчисления L). Для каждой функции f: Р I, заданной на множестве букв исчисления L, существует единственная интерпретация е_f: S I исчисления L, ограничение которой на Р равно f, в том смысле, что
е_f(p) = f(p), для всех p P.

Доказательство. Пусть S₀ = P, S_n+1 = S_n { A: A S_n} {(A B):A,B S_n}. Утверждение леммы доказывается по индукции. Положим e_f(A)=f(A) для A S₀. Предполагая, что e_f уже определена на S_n, продолжим её на S_n+1 следующим образом: Если А= В, для некоторого В S_n, то положим e_f(A) = ; аналогично, в случае A=(B C) при некоторых В, С S_n, положим e_f(B C) = e_f(B) e_f(C). В результате получаем функцию , ограничение которой на Р равно f.

Формула А исчисления L называется тавтологией, если е(А)=1, для любой интерпретации е:S I исчисления L.

Теорема (о полноте). Формула А исчисления высказываний L является тавтологией тогда и только тогда, когда она является теоремой исчисления L.

Доказательство. Если формула А является теоремой исчисления L, то, поскольку аксиомы являются тавтологиями и применение MP к тавтологиям Р и Р Q даёт тавтологию, мы можем заключить, что А – тавтология. Это доказывает, что каждая теорема является тавтологией. Для доказательства обратного утверждения нам понадобится следующая лемма.

Лемма 2. Пусть формула А содержит переменные а₁, а₂, …, а_n, и пусть задана некоторая функция f: { а₁,а₂,…,а_n } I={0,1}. Тогда _L А’, где и А’ обозначают следующие формулы:

Здесь e_f обозначает интерпретацию исчисления L для случая, когда Р={ а₁,а₂,…,а_n}, по лемме об интерпретации e_f определяется функцией f единственным образом.

Доказательство леммы проведем по индукции, по количеству логических связок и в формуле А. В случае, когда А = а – переменная, имеем: а _L а и а _L а.

Пусть А = В. Если e_f(B) = 1, то e_f(A) = 0 и А’ = А = В. По предположению индукции _L В. Пользуясь теоремой _L В В, получаем: _L В = А’. Если же e_f(B) = 0, то e_f(A) = 1 и А’ = А= В. По предположению индукции: _L В и В =А’.

Рассмотрим случай А = (В С). По предположению индукции:

_L В’ и _L С’.

Если e_f(B) = 0, то независимо от значения e_f(C) имеем: e_f(A)=1 и В’ = В, А’ = А. Но _L В. С помощью теоремы _L В (В С), получаем: _L В С.

Если e_f(B) = 1, то возможны 2 случая: – e_f(C) = 1 или e_f(C) = 0. В случае e_f(C) = 1 имеем: e_f(A) = 1 и С’ = С, А’ = А = (В С). Имеем: _L С и
_L С (В С) (по аксиоме А1), следовательно, _L В С. В случае e_f(В) = 1 и e_f(С) = 0 имеют место: А’ = A= (B C), B’ = B, C’ = C. Имеем:

_L В, _L С.

Пользуясь теоремой _L В ( С (В С)), получаем:

_L (В С) =А’. Лемма доказана.

Вернёмся к доказательству теоремы о полноте. Пусть А – тавтология. Тогда по доказанной лемме: _L А, ибо e_f(A) = 1 для любой интерпретации букв . Значит, существуют выводы: _L А, и _L А. По теореме о дедукции: _L а_n А и _L a_n А. Пользуясь теоремой _L (а_n А) (( а_n А) А) и применяя MP, получаем: _L А. Повторяя этот процесс ещё n – 1 раз, приходим к теореме: _L А, что и требовалось доказать.

Упражнение

Доказать выводимость формул:

_L В В,

_L В (В С),

_L В ( С (В С))

Следствие (теорема о непротиворечивости). Исчисление высказываний L непротиворечиво в том смысле, что не существует формулы А исчисления L, для которых А и А были бы теоремами.

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