2. Доказательетво независимости рассматриваемой системы исходных формул; еще одно доказательство независимости.

Изложенный способ доказательства мы теперь обобщим таким образом, чтобы его можно было использовать для проведения доказательств независимости. Обобщение это будет заключаться в том, что вместо определений для

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

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

Чтобы показать, что данная формула II не может быть выведена из формул

будет достаточно указать оценку со следующими свойствами. Выражения

принимают одни только выделенные значения. Если, далее, выражения принимают только выделенные значения, то тем же свойством обладает и Выражение II, напротив, принимает также и невыделенные значения.

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

Теперь, пользуясь этим методом, мы для каждой из формул докажем ее невыводимость из остальных формул системы.

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

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

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

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

Таблицу доказательств независимости для формул II — V мы зададим следующим образом:

(см. скан)

Из приведенных в этой таблице оценок можно также извлечь и некоторые дополнительные следствия. Например, оценка, доказывающая независимость формулы II 3), вместе с тем показывает также, что в системе формул эту формулу нельзя заместить формулой

действительно, при этой оценке, которая задается определяющим равенством

рассматриваемая формула, равно как и формулы I, II 1), 2), III — V, всякий раз принимает значение а, в то время как для формулы II 3) это неверно.

Далее, используемая для доказательства независимости формулы V 3) оценка, задаваемая определяющим равенством

показывает, что формула V 3) не может быть выведена из формул и формулы

и что, стало быть, в системе формул формулу V 3) нельзя заместить формулой Действительно, при упомянутой оценке все формулы также формула тождественно принимают значение а, в то время как для V 3) это места не имеет.

Теперь осталось провести доказательства независимости для формул группы Здесь дело обстоит не так просто, как в предыдущих случаях, ввиду того, что символ -> встречается в формулах всех пяти групп.

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

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

Для любых значений имеют место равенства

а также

Эти условия, как легко убедиться, совместимы друг с другом. Получающиеся из них определяющие равенства мы будем называть основными равенствами. К ним всякий раз будут добавляться те или иные дополнительные определяющие равенства.

Для доказательства независимости формулы I 1) мы возьмем оценку с четырьмя значениями Для нее дополнительными определяющими равенствами будут

Для так определенной оценки значение каждой из формул тождественно равняется а.

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

То, что формула I 1)

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

Для указанных значений значение принимает также и формула

Отсюда следует, что она не может быть выведена из формул

Тем же самым способом можно убедиться, что формулы

также не выводятся из формул 12), 3),

Далее, из того обстоятельства, что при рассматриваемой оценке формулы и тождественно принимают значение а, следует, что в системе формул формулу I 1)

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

Независимость формулы I 2) устанавливается с помощью оценки с тремя значениями , впервые рассмотренной Лукасевичем. Для этой оценки дополнительные равенства имеют следующий вид:

( вполне определяются уже при помощи основных равенств).

То, что эта оценка доставляет каждой из формул значение а, легко усматривается из следующей арифметической интерпретации: суть соответственно числа при представляет собой арифметическую разность а в противном случае АВ равно представляет собой наибольшее, — наименьшее из значений есть абсолютная величина равно . Формула I 2):

принимает при этой оценке значение у, если положить

Точно так же устанавливается, что ни одна из формул

не является тождественно равной а. Таким образом, эти формулы не выводимы из формул

И наконец, чтобы доказать независимость формулы I 3), возьмем оценку с четырьмя значениями и со следующими дополнительными определяющими равенствами:

далее, для

наконец, для любых значений

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

Теперь можно проверить, что при этой оценке формулы тождественно принимают значение а. Между тем формула I 3):

при принимает значение

При этой оценке формула

при принимает значение Следовательно, эта формула не может быть выведена из системы формул без использования формулы I 3).

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

которую мы приводили выше в качестве примера тождественно истинной, но не позитивно тождественной импликативной формулы, не может быть выведена из системы формул без использования формулы V 3).

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

При так определенной оценке все формулы тождественно принимают значение а, а формула

при принимает значение у. Значит, эта формула действительно не выводима из формул То же самое верно и в отношении тождественно истинной формулы

которая в рассматриваемой оценке при также принимает значение у.