Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 25
Текст из файла (страница 25)
Следует обратить внимание на тот факт, что во всех этих доказательствах независимости определение символа-+. остается прежним, так что каждая приведенная в таблице оценка обладает тем свойством, что если две формулы Я и 1О -э 2 тождественно принимают значение а, то и Й также обладает этим свойством.
Таблицу доказательств независимости для формул Н вЂ” т' мы аададим следующим образом: $ 11 МЕТОД ОЦЕНОК И ДОКАЗАТЕЛЬСТВА НЕЗАВИСИМОСТИ тээ ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИИ 1ГЛ. 111 $08 Из приведенных в атой таблице оценок моясно также извлечь и некоторые дополнительные следствия. Например, оценка, доказывающая независимость формулы 11 3), вместе с тем показывает так«ке, что в системе формул 1 — У эту формулу нельзя заместить формулой (А -«. В) & (А «- С) «- (А — «- В & С); действительно, при этой оценке, которая задается определяющим равенством А &В=р, рассматриваемая формула, равно как и формулы1, 11 1), 2), 111— У, всякий раэ принимает значение а, в то время как для формулы 11 3) это неверно. Далее, используемая для доказательства независимости формулы У 3) оценка, задаваемая определяющим равенством )А=а, показывает, что формула Ч 3) не может быть Выведена из формул 1 — 1У, У 1), 2) и формулы АУ ~А и что, стало быть, в системе формул 1 — Ч формулу У 3) нельзя ааместить формулой А 1/ ~А.
Действительно, при упомянутой оценке все формулы 1 — 1У, У 1), 2), а также формула А 1/ ~ А тождественно принимают значение а, в то время как для У 3) это места не имеет. Теперь осталось провести доказательства независимости для формул группы 1. Здесь дело обстоит не так просто, как в предыдущих случаях, ввиду того, что символ-«- встречается в формулах всех пяти групп. Независимость формул 1 1), 2), 3) мы докажем с помощью трех существепно отличающихся друг от друга оценок. Общим у этих оценок будет то, что всякий раз в качестве единственного выделенного значения мы будем брать а. Условие, состоящее в том, что если Я н б-э;ь тождественно принимают значение а, то и ь тождественно принимает это значение, будет выполняться вследствие того, что во всех трех оценках выражение а -«.
А для А ~ и будет принимать значение, отличное от и. Далее, эти оценки будут обладать следующим, общим для них свойством: Для любых значений А и В имеют место равенства А&В=В&А, А«/В=В)/А, А В=В А, А-«А=а, А&А=-А, А ««/А=А, А А=и, А -«-а=а, р — «-А=а, А&а=-А, А ~/а=а, А&р=(6, А 1/р=А, а также 1а = р, 1() = и. Эти условия, как легко убедиться, совместимы друг с другом. Получающиеся из них определяющие равенства мы будем называть основными равенствами. К ним всякий раз будут добавляться те или иные дополнительные определяющие равенства. Для доказательства независимости формулы 1 1) мы возьмем оценку с четырьмя значениями и, р, у, 6.
Для нее дополнительными определяющими равенствами будут Для так определенной оценки значение каждой из формул 1 2), 3), П вЂ” У тождественно равняется и. В целях облегчения проверки следует заметить, что: А-«- В всегда принимает одно из значений и или р; А & В и А ««/ В всегда принимают одно из значений А, В. Следует также отметить еще и ту особенность нашей оценки, что для выражений, построенных из а и р с помощью наших пяти логических символов, она согласуется с нормальной оценкой. То, что формула 1 1) А — «- ( — ~ А) не всегда принимает значение и, можно обнаружить при помощи различных систем значений переменных: например, при А = 6 и В = а рассматриваемая формула принимает значение р.
Для указанных значений А и В значение р принимает также и формула А -«. (В -«. А & В). Отсюда следует, что она не может быть выведена из формул 1 2), 3), 11 — У. Тем же самым способом можно убедиться, что формулы А ~/ 1А, 1(А & 1А), (А †«- ~А) †«- 1А, А †«-( 1А -э 1В) также не выводятся из формул 1 2), 3), 11 — Ч. Далее, иэ того обстоятельства, что при рассматриваемой оценке формулы А «- А и В -«- (А -«. А) тождественно принимают значение а, следует, что в системе формул 1 — У формулу 1 1) а — р=р, ау =(6=0, у-«б=р, 17=6, А-В=р у=~, и- 6=(), 6- у=и, уЧ6=Ъ ~6=у, для А чь В.
$43 МЕТОД ОЦЕНОК И ДОКАЗАТЕЛЬСТВА НЕЗАВИСИМОСТИ 1гл. н> ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИИ нельзя заместить формуламиА-+ А и В- (А- А). Формула 11) будет невыводимой и в том случае, если к формулам 1 2), 3), 11 — Ч добавить не только формулы А ->- А и  — (А >- А), но, кроме того, еще и формулы А Ч' > А, ~ (А & ~ А), а такясе схему И-' 1сс . Действительно, в этом случае выводимыми оказались ~и бы лишь такие формулы, которые при рассматриваемой оценке принимают только значения а и у. Независимостьформулы1 2) устанавливается с помощью оценки с тремя зкачениями и, Р и у, впервые рассмотренной Лукасевичем. Для этой оценки дополнительные равенства имеют следующий вид: и р = р, и у = у, и р = р, и1-у=-у, р1-у =у, ~у=у (А & В и А Ч' В вполне определяются уже при помощи основных равенств).
То, что эта оценка доставляет каждой из формул 1 1), 3), 11— — Ч значение а, легко усматривается из следующей арифметической интерпретации: и, р и у суть соответственно числа О, ! и — „; А — ~ В при А -~В представляет собой арифметическую разность  — А, а в противном случае А — ~ В равно О; А & В представляет собой наибольшее, а А 1/  — наименьшее из значений А и В; А В есть абсолютная величина А — В; 1 А равно 1 — А.
Формула 1 2): (А — +- (А -~ В)) >. (А — ~ В) принимает при этой оценке значение у, если положить А = у и В=)). Точно так же устанавливается, что ни одна из формул (А -+- (А ->. В)) ->. (А & А ->- В), А ~/ 1А, ~(А & 1А), (А — >- 1А) >- ~А не является тождественно равной и. Таким образом, эти формулы не выводимы из формул 1 1), 3), 11 — Ч. И наконец, чтобы доказать неаависимость формулы 1 3), возьмем оценку с четырьмя значениями и, р, у, 6 и со следующими допол- нительными определяющими равенствами: ~у=6, ~6 =у, у & 6 = р, у 'Ч' 6 = и, а ->.
р = у, у ->- (1 = 6, 6->- б = у; далее, для А, В~~, А~В А-~В=В; наконец, для любых значений А и В А В = (А ->. В) & ( — >. А). Легко убедиться, что эти равенства совместимы друг с другом, а также и с основными равенствами, и что рассматриваема н оценка вполне ими определяется. 2 1 Теперь можно проверить, что при этой оценке формулы 1 1), ), 1 — Ч тождественно принимают значение а. Между тем формула 1 3): (А ->- В) — +- ((В -+.
С) -э (А ->- С)) при А = а, В =- р и С = 6 принимает значение 6. При этой оценке формула А -~ ((А ->- В) — В) при А = а и В = р принимает значение 6. Следовательно, эта формула,не может быть выведена из системы формул 1 — Ч без использования формулы 1 3). Тем самым независимость всех формул 1 — Ч доназана. В до- полнение к сказанному, воспользовавшись еще одной оценкой, мы покажем, что формула ((А — >- В) ->. А) — >- А, которую мы приводили выше >) в качестве примера тождественно истинной, но не позитивно тождественной импликативной форму- лы, не может быть выведена из системы формул 1 — Ч без исполь- зования формулы Ч 3).
Для этого мы возьмем оценку с тремя значениями а Я и "„. Д нее как ивп , как и в предыдущих случаях, должны будут выполняться основные равенства и, кроме того, мы добавим к ним следующие дополнительные: и->-()=р, и ~.у — ., ~ р а р = 'р, а у = у, () у =- р 3 у = р При так определенной оценке все формулы 1 — 1Ч, Ч 1), 2) тождественно принимают значение а, а формула ((А ->- В) ->. А) ->- А при А = у и В = (1 принимает значение у.
Значит, зта формула действительно не выводима из формул 1 — 1Ч, Ч 1), 2). То же самое верно и в отношении тоя<дественно истинной формулы А >/ (А — 1- В), которая в рассматриваемой оценке при А = у и В = () также принимает значение у. >) См. с. 101. ?гл, хп ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИИ ?12 3.
Применение метода оценок к вопросу о замене формул схемами, Наш метод введения функций, подходящим образом заданных па конечных областях, может быть без изменений использован также и в таких доказательствах независимости, в которых речь идет об изменении не только системы формул, но и набора применяемых правил. Так, например, оценка, которую мы построили для докааательства независимости формулы 1 1), показывает, что формулу 1 1) нельзя заместить схемой и 6-» и Действительно, от любой формулы, тождественно принимающей при упомянутой оценке значение и, зта схема снова ведет к формуле с тем ясе свойством, так как при этой оценке значение А — «и тождественно равно и.
Таким образом, и при добавлении упомянутой схемы выводимыми из формул? 2), 3), 11 — У окажутся лишь такие формулы, которые в рассматриваемой оценке тождественно принимают значение а, в то время как формула 1 1) зтим свойством не обладает. Таким же способом можно доказать и то, что формула 11 3): (А — «В) -«((А — «С) -«(А -«В & С)) не может быть замещена схемой Р?-«З Я-«6 если мы ограничимся формулами групп 1 — П1. Таким образом, даже если мы добавим схему (8) в качестве формального правила вывода, то формула П 3) будет не выводима из формул 1, 11 1), 2), 1П. Для доказательства мы рассмотрим оценку, состоящую из четырех элементов и, р, у и б. Среди ннх выделенным снова будет только а.
По-прежнему будем считать, что имеют место основные равенства, а з качестве дополнительных равенств возьмем А — «В = В для А ~ В, А чь ~; у & б = р, у ~/ б = и. Прежде всего, в силу этих определяющих равенств значение каждой из формул 1, 11 1), 2), Н1 тождественно равно а. Затем, если значения выражений Я и Я вЂ” «Й тождественно равны а, то тогда н;ь обладает этим свойством; таким образом, применяя з ы метод оцннок и доклзлтельствл ннзлвисимости 118 схему заключения к формулам, которые тождественно принимают значение и, мы снова получаем формулу с этим свойством. Но то же самое справедливо и в отношении присоединяемой схемы (8): именно, если Я, З и 6 — выражения такие, что Я -«З и Я -«6 тоя<дественно принимают значение и, то и выражение Я -«3 & 6 всегда будет принимать зто значение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
