2. Заменимость; правила замены.

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

Для краткости мы будем говорить, что два составных высказывания заменимы друг другом, если они представляют одну и ту же истинностную функцию. Только что сформулированные утверждения вытекают из следующих легко устанавливаемых соотношений замен мости:

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

которая ложна, если оба аргумента истинны, и истинна в противном случае, а также функцию

которая истинна, если оба ложны, и ложна в противном случае; все ранее рассмотренные нами истинностные функции могут быть выражены через каждую из этих двух.

Факт этот доказывается очень просто. Если для истинностной функции, представленной посредством выражения ввести в качестве обозначения символ Шеффера то, как легко убедиться,

А с помощью отрицания и конъюнкции, как мы уже знаем, можно представить и дизъюнкцию, и импликацию, и эквивалентность.

Совершенно аналогичным образом устанавливается выразимость пяти рассмотренных истинностных функций и через связку «ни А, ни В».

От рассмотрения соотношений заменимости мы приходим к «исчислению высказываний», сформулировав на базе этих соотношений некоторые правила преобразования составных высказываний. Термин преобразование здесь должен пониматься в смысле взаимной заменимости; это значит, что произвольное заданное выражение можно будет заменять всяким другим выражением, представляющим ту же самую истинностную функцию. При этом речь идет о таких выражениях, которые составлены из переменных с помощью знаков и

Из определения заменимости мы прежде всего можем извлечь следующие, универсальные по своему характеру правила подстановки:

S1. Пусть выражение II заменимо выражением ; пусть переменные, фигурирующие в выражениях и пусть получается а из путем подстановки выражений вместо переменных Тогда заменимо выражением .

S2. Пусть выражение II заменимо выражении , а выражение содержит в качестве составной части. Пусть получается из подстановкой выражения вместо этой составной части Тогда заменимо выражением

Далее, мы приведем ряд утверждений о заменимости, получающихся из определений истинностных функций в сочетании с правилом Эти утверждения будут носить специальный характер, в дальнейшем мы будем пользоваться ими в качестве правпл замены-. (Прописные готические буквы обозначают выражения рассматриваемого нами типа.)

1. Правила для конъюнкции и дизъюнкции:

а) заменимы посредством .

б) Конъюнкция и дизъюнкция ассоциативны и коммутативны.

в) Имеет место закон взаимной дистрибутивности:

заменимо посредством заменимо посредством (

2. Правила для отрицания:

а) заменимо посредством .

б) заменимо посредством

заменимо посредством

Правила выражают формальные свойства конъюнкции, дизъюнкции отрицания. К ним примыкают правила замены еще одного вида, являющиеся следствием того факта, что функции В тождественно принимают значение «истина», а функции — значение «ложь».

3. Правила сокращения и распространения:

В дальнейшем нам понадобятся следующие, уже упоминавшиеся преобразования, с помощью которых могут быть выражены через и

4. Правила устранения и введения импликации эквивалентности:

а) заменимо посредством

б) заменимо посредством