Т. А. Сливина математическая логика и теория алгоритмов

5. Закон исключенного третьего: ├
Доказательство: Воспользуемся доказуемой формулой
├ (10)
и, сделав в ней подстановку , получим
├ (11)
Также сделаем подстановку в формуле (7), заменяя х на , а у на :
├ (12)
Используя закон соединения посылок, будем иметь
├ (13)
Из формул (11) и (13) по правилу силлогизма получим
├ (14)
Из формулы (14) по правилу контрпозиции следует ├
Используя оба правила снятия двойного отрицания, получаем
├ (15)
Пусть теперь у – любая доказуемая формула R, тогда из формул ├R и ├ по правилу заключения получаем
├
6. ├
Доказательство: Сделаем подстановку в аксиоме III₃, заменяя в ней z на :
├ (16)
Из аксиом II₁ и II₂ имеем:
├ (17)
├ (18)
Применяя к формулам (17) и (18) правило контрпозиции, получим
├ (19)
├ (20)
Используя правило снятия двойного отрицания, будем иметь:
├ (21)
├ (22)
Применяя к формулам (16), (21) и (22) правило сложного заключения, получим
├ (23)
Применяя к формуле (23) правило контрпозиции, а затем правило снятия двойного отрицания, получаем ├ .


§6. Связь между алгеброй высказываний и исчислением высказываний

Формулы исчисления высказываний можно интерпретировать как формулы алгебры высказываний. Для этого будем трактовать переменные исчисления высказываний как переменные алгебры высказываний, то есть переменные в содержательном смысле, принимающие два значения: истина и ложь (1 и 0).

Операции , , , – определим так же, как в алгебре высказываний. При этом всякая формула исчисления высказываний при любых входящих в нее переменных будет принимать одно из значений 1 или 0, вычисляемое по правилам алгебры высказываний.
Введем понятие значения формулы исчисления высказываний.
Пусть А – формула исчисления высказываний, x₁, х₂, ..., х_п – попарно различные переменные, среди которых находятся все переменные, входящие в формулу А.
Обозначим через а₁, а₂, ..., a_n набор значений этих переменных, состоящий из 1 и 0, длины n. Очевидно, что вектор (а₁, а₂, …, а_n) имеет 2ⁿ значений.
Определим значение формулы А на одном таком наборе значений переменных, обозначая его через :
1. Если для формулы А ее подформула самой большой глубины есть x_i, то .
2. Если определены значения всех подформул глубины (k+1), то подформулы глубины k, полученные в результате операций , , и будут иметь значения:
,
,
,
.
Например, формула на наборе значений (0,1,1,0) переменных х₁, х₂, х₃, х₄ имеет значение R₀₁₁₀( ) = 1.
Действительно, эта формула имеет:
– подформулы первой глубины,
– подформулы второй глубины,
х₄, х₂, – подформулы третьей глубины,
х₃ – подформула четвертой глубины.
Отсюда R₀₁₁₀ (x₃) = 1,
, R₀₁₁₀ (x₂) = 1, R₀₁₁₀ (x₄) = 0,
=0, , R₀₁₁₀ (x₁) = 0,
)= =1,
R₀₁₁₀( )=R₀₁₁₀( )R₀₁₁₀( )=1.

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