Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 114
Текст из файла (страница 114)
(1)), а потому, ввиду выводимости формулы 9! -Ф- (6-у. Я а 6) и формула Я-Р(6-+.6). Укажем на еще один вариант формулировки, которую можно придать полученной нами теореме, характеризующей позитивно тождественные 1-К-формулы как формулы, выводимые с помощью применен " менений к 1-К-формулам схем (8,) — (8,). Заметим, что выводы, производимые в области 1 К.формул при помощи схем (8,) — (,), — 8 протекают совершенно аналогично выводам схем формул, производимым прн помощи указанных пяти схем безотносительно акой-либо конкретной области формул, исключительно путем оперирования с обозначениями формул, связываемые дру друг с гом знаками имплнкации и конъюнкции.
Зто приводит нас к следующей теореме: Схемы формул, выводимые из схем (8,) — (84) без указания какой-лнбо конкретной области формул, совпадают со схемами, получающимися из позитивно тождественных 1-К-формул в результате замены формульиых переменных буквами, обозначающими произвольные формулы. й 3. Тождественные 1-К-й1-формулы В проведенном нами в гл. Ч Ц 5, п. б)1 рассуждении пока отсутствует доказательство утверждения ') о том, что любая схема формул, соответствующая тождественно истинной формуле исчисления высказываний и не содержащая дизъюнкции, выводима с помощью схем (8,) — (84), схем вывода й)-э 6 Я-ъ -16 ~ (Я сс 6) Я-м )6 схемы формул и правила замены любой эквивалентности Я 6 соответствую- 4) См.
с, 433 — 434. (84) )Я 1(Я 8 6) (8,) Я- ~6 ) ~Я вЂ” мЯ. (8,) Легко видеть, что применение этих схем к формулам исчисления высказываний дает только тождественно истинные формулы, Мы должны доказать, что для 1-К-Х-формул имеет место "бращение этого утверждения, а именно что любая тождественно "сти"ная 1-К-К-формула может быть выведена с помощью применений схем (8,) — (8,) к [-К-д-формулам. щим ей выражением (Я -+.6) Зс(6-+.Я) (и, разумеется, этого выражения указанной эквивалентностью]. Б этом утверждении мы можем заменить схемы формул, соответствующие тождественно истинным формулам, самими этими формулами, считая, что используемые в выводах схемы применяются к формулам исчисления высказываний, ке содержащим знака дизъюнкции. Это вытекает из упомянутого в конце предыдущего параграфа результата, утверждающего, что выводы, производимые с помощью схем, применяемых к формулам исчисления высказываний, протекают совершенно аналогично выводам, применяемым к схемам формул, получающимся из соответствующих формул в результате замены формульных переменных буквами, обозначающими произвольные формулы.
Далее, при доказательстве этого утверждения мы можем отвлечься от эквивалентности, так как всякая тождественно истинная формула исчисления высказываний при замене каждой ее составной части Я 6 соответствующим выражением (Я-Р6) сс сч(6-мЯ) переходит снова в тождественно истинную формулу, и поэтому всякая тождественно истинная формула, не содержащая знака дизъюнкции, с помощью правила замены для эквивалентности может быть получена из некоторой тождественно истинной формулы, не содержащей знаков дизъюнкции и эквивалентности. Следовательно, мы можем ограничиться рассмотрением таких формул исчисления высказываний, которые в качестве логических символов содержат только импликацию, конъюнкцию и отрицание.
Формулы этого рода мы будем кратко называть 1-К-М-формулами. Наряду со схемами (8,) — (8,) рассмотрим еще следующие три схемы вывода: П!1 ТОЖДЕСТВЕННЫЕ 1.К-М-ФОРМУЛЫ 534 П РИ ЛОЖЕН ИЕ 4з1 Для этого мы воспользуемся одной модификацией конъюнктнвной нормальной формы ') обычного исчисления высказываний ').
Как мы знаем, при истолковании формул исчисления высказываний, получающемся на основе понимания связок исчисления высказываний как нстинностных функций, любая формула равнозначна некоторой конъюнкции, члены которой являются либо формульными переменными, либо отрицаниями формульных переменных — выражения этих двух типов мы будем называть п римарными выражениями'),— либо дизъюнкциями, состоящими из нескольких примарных выражений. При этом упомянутая равнозначность имеет место в том смысле, что соответствующая конъюнкция задает ту же самую истинностную функцию, что и первоначальная формула. Любая дизъюнкция примарных выражений задает ту же истинностную функцию, что и отрицание некоторой конъюнкции примарных выражений.
Тем самым каждая формула исчисления высказываний в указанном смысле равнозначна такой конъюнкции, у которой каждый член является либо примарным выражением, либо отрицанием конъюнкции примарных выражений. Формулу такого рода в данном' рассмотрении мы будем называть конъюн кти в но норм и рован ной, а какую либо конъюнктивно нормированную формулу, равнозначную формуле 9(, мы будем называть конъюнктиано нормированной формулой, связанной с формулой 6.
По конъюнктивно нормированной формуле можно непосредственно установить, является ли она тождественно истинной, Действительно„ это, как легко убедиться, имеет место тогда и только тогда, когда каждый ее дизъюнктивный член является отрицанием 1) См. т. 1, с, 82 — 85 н 96 — 98. я) Как некоторую моднфннапню получаемого с помощью конъюнктнвной нормальной формы метода доказательства полноты систем аксиом исчисления высказываний можно рассматривать доказательство, которое недавно дали ' Гермес н Шалая для первоначально установленного Лукасевнчем факта, что формулы Г» вместе с формулой () А -» ) В)-ь(В -~ А) прн использовании подстановок н схемы заключения представляют собой систему, достаточную для вывода всех тождественно истинных формул нсчнслення высказываний, построенных с помощью одних' толька знаков нмплнкацнн н отрицания. Смл Нег»лез Н,, 8сь о! я Н.
Е!и пеаег»о1!я!апб!Е)ге1!зьеже)я Гйг бая ге., бцх!ег!е Ргейеясье Ах!ошепяуя!оп бея Апяяайеп)га!йй!я. — Рогзсьппйеп хпг 1.ой!й ппб япг с»гцпб!ейная бег ехай!еп Цг!яяепясьа((еп, !937, № !. Роль аналога конъюнкции»простых» днзъюнкцнй в случае канъюнктнвной нормальной формы здесь нграют конечные множества нмплнкацнй некоторого специального вида. ») Это понятие прнмарного выражения не находится нн в какой сааза с введенным в т. 1 (с. 188 н 280) понятием прнмарной Е)армрлы.
такой конъюнкции, у которой имеются два члена, один из которых является отрицанием другого. Такая структура тождественно истинных конъюнктивно нормированных формул позволяет заключить, что каждая из них выводима с помощью применяемых к 1-К-)х)-формулам схем (Зг) — (Зя). Действительно, если Й является конъюнкцией примарных выражений, среди которых имеется некоторое выражение Н вместе с его отрицанием, то с помощью схем (51) — (Бз) будут выводимы ') формулы й-+!! н й — ь )Ц) но из них с помощью схемы (За) мы получим формулу ) Й. Поэтому тождественно истинная конъюнктивно нормированная формула является коньюнкцней формул, выводимых с помощью схем (Ях) — (Бе), а из этих формул с помощью схем (Ях) — (Зя) может быть выведена и сама эта конъюнктивно нормированная формула.
Если мы теперь заметим, что конъюнктивно нормированная формула, связанная с тождественной истинной формулой, является тождественно истинной, то отсюда яо только что доказанному получится, что для обоснования нашего утверждения о выводи- мести любой тождественно истинной 1-К-)х)-формулы путем применения схем (Ят) †(5я) к 1-К-ц»)-формулам достаточно показать, что для каждой 1-К-Х-формулы можно указать такую связанную с ней конъюнктнвно нормированную формулу, которая дедуктивно равна ей относительно схем (51) — (Ья), применяемых к 1-К-)ч(-формулам.
Это мы проделаем следующим образом: сначала мы укажем некоторую процедуру, сопоставляющую каждой 1-К-Х-формуле некоторую связанную с ней конъюнктивно нормированную формулу, а затем покажем, что формула, полученная при помощи этои процедуры, дедуктивно равна относительно схем (51) — (Яз) исходной формуле, Для того чтобы изложить упомянутую процедуру, мы воспользуемся одной классификацией формул, построенных нз формульных переменных с помощью знаков конъюнкции и отрицания (такие формулы мы будем называть К-)ч)-формулами).
Каждой Такой формуле мы припишем следующим образом некоторый параметр, который назовем ее порядком. Знак отрицания будет назы- 1 ) Г)рн дедуктивных преобразованнях конъюнкций нужно помаять, что а саответствнн с вашими соглашениями бесскобочная конъюннцня Г»»аг...мз( авл 1 " в вляется сокращением лля выра»кення (" ° (Ц»ййя)й ..бгйн 1)йяв. ТОЖДЕСТВЕННЫЕ 1-К-Н.ФОРМУЛЫ пн ПРИЛОЖЕНИЕ ваться примариым, если он входит в примарное выражение. Далее, два или большее число знаков отрицания, входящих в какую-либо К-И-формулу, будут называться н а с л а и в а ющимися друг на друга, если по меньшей мере одна формульная переменная данной формулы попадает в область действия каждого из этих знаков. Порядок данной К-Ы-формулы мы определим как максимальное число входящих в нее наслаивающихся друг на друга непримарных отрицаний.
Согласно этому определению примарное выражение всегда имеет нулевой порядок. Отрицание какой-либо К-М-формулы и-го порядка, не состоящей из одной только формульной переменной, является формулой (и+1)-го порядка, а порядок конъюнкции К-(ч-формул равен максимальному из порядков ее членов. К-1ч-формула является конъюнктивно нормированной тогда и только тогда, когда ее порядок не превосходит единицы. Далее, из определения порядка можно извлечь следующие два предложения: 1. Любая К-М-формула порядка выше первого содержит в качестве составной части по меньшей мере одно отрицание какой- либо формулы первого порядка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
