Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 115
Текст из файла (страница 115)
2. Если в какой-либо формуле порядка выше первого каждое входящее в нее отрицание формулы первого порядка заменить связанной с ней конъюнктивно нормированной формулой, то формула, которая при этом получится, будет иметь порядок, меньший порядка первоначальной формулы. Закончив эти приготовления, мы теперь укажем способ, позволяющий преобразовать любую наперед заданную 1-К-[Ч-формулу в некоторую связанную с ней конъюнктивно нормированную формулу.
Сначала мы исключим из исходной формулы все вхождения импликации, заменив каждое выражение Я вЂ” «6 соответствующим ему выражением ) (Яй [Е). Обозначим получившуюся в результате этого формулу через (О. Либо формула Я является конъюнктивно нормированной и тогда наша процедура заканчивается, либо она содержит по меньшей мере одну составную часть: вида ) 6, где 6 — формула первого порядка.
Для каждой такой составной части 16 мы следующим образом построим некоторую коиъюнктивно нормированную формулу, которой будем ее заменять. Будучи формулой первого порядка, 6 содержит по меньшей мере один конъюнктивный член ) й первого порядка, т. е. либо 6, вообще состоит из Одной такой формулы 1 й, либо 6 имеет вид Яй ) й или же переходит в формулу такого вида в результате перестановки последнего члена первого порядка с идущими за ним конъюнктивными членами нулевого порядка.
В первом случае ) 6 имеет вид ) ) й. Убрав двойное отрицание, мы получим формулу нулевого порядка и, значит, конъюик* тивно нормированную формулу. Во втором случае 16 либо уже имеет аид 1(Яй )й), либо переходит в формулу этого вида после соответствующей перестановки некоторых коиъюнктивных членов. В более подроб- ной записи ) 6 будет иметь вид ~(Яй 1(ф[й...йф3)), где $1, ..., [1[,— примарные выражения. Тогда мы заменим это выражение сначала выражением 1(Я й 1 $1) й 1(Я й 1 $3) й... й 1(Я й 1 ф,), а затем выражением )(ЙйО3)й ~(ЯйС3)й...й ~(Яй~) где (при 1=1, ..., г) ь1, в том случае, когда [р, представляет собой формульную переменную, является примарным выражением ) 11)„а в случае, когда ч), представляет собой отрицание формульной переменной, является этой формульной переменной.
В обоих этих случаях О, является примарным выражением. Таким образом, формула 16 заменена конъюнкцией [63й 163й...й [6д, где каждая из формул 6„..., 6, содержит меньше конъюнктивных членов первого порядка, чем 6; действительно, в 6, вместо конъюнктивного члена 1 й формулы 6, который имеет первый порядок, фигурирует примарное выражение ь3[.
Повторив эту процедуру достаточное число раз, мы заменим формулу ) 6 конъюнкцией )бпла где формулы 6,*, ..., 6„*вообще не содержат конъюнктивных членов первого 'порядка и, следовательно, являются формулами нулевого порядка, так что конъюнкция 1 61й...й 1 бй является формулой первого порядка и тем самым конъюнктивно нормированной формулой. Заменив, согласно этому предписанию, в формуле Й каждую составную часть второго порядка вида ) 6 соответствующей конъюнктивно нормированной формулой, мы получим вместо чо некот- РУ К-И-формулу, имеющую порядок, меньший порядка (о. Этот опроцесс надо будет повторить достаточное число раз, и тогда мы ззв ззэ ТОЖДЕСТВЕННЫЕ ЬК-Н-ФОРМУЛЫ ПРИЛОЖЕНИЕ пп придем к некоторой К-И-формуле первого порядка, т. е.
к конъюнктивио нормированной формуле. То, что полученная таким образом конъюнктивно нормированная формула связана с той (-К-Р(-формулой, из которой мы исходили, т. е. что она определяет ту же самую истинностную функцию, что и исходная формула, вытекает из того, что описанная процедура складывается из составных частей следующих типов (детали, касающиеся лишь способа записи, мы в расчет не принимаем); 1) замена выражения Я- 6 выражением 1(Яй) 6), 2) замена выражения Яй(бйб) выражением (Яйб)йб; 3) замена выражения Яй6 выражением 6йЯ; 4) замена выражения 1 ) Я выражением Я; 5) замена выражении 1(Я й 1(6 й 6)) выражением 1 (Я й 16) й й 1(Яй1 Я)- '1Шаги последнего типа позволяют осуществлять переходы от выражений типа 1(Я й ) (йч й " й 'р~)) к соответствующим выражениям "~(Яй 161) й...й 1(Яй )й),) 1 В самом деле, при понимании импликации, конъюнкции и отрицания как истинностных функций каждая из этих пяти замен ни при каком наборе истинностных значений формульных переменных не меняет значений преобразуемого выражения.
Теперь мы должны еще установить, что любая 1-К-Р(-формула дедуктивно равна (относительно схем (5,) — ($,)) той конъюнктивно нормированной формуле, которая получается для нее в результате применения описанной процедуры. Для доказательства этого факта мы можем воспользоваться замечаниями, сделанными в конце з 2 по поводу выводимости формул с помощью схем (51) — (Ь,). В силу этих замечаний и в случае применения схем (51) — (Б„) к 1-К-Х-формулам схема силлогизма, схема соединения посылок и схема Я, 6 Яйб будут производными схемами вывода, схемы формул Яйб-~-бйЯ, Я й (6 й 5) -~- (Я й 6) й (4 и (Я й 6) й Я вЂ” ~- Я й (6 й 5) будут выводимыми, а любая формула Я - 6 й 5 будет дедуктивно равна формуле (Я вЂ -6) й (Л~- В). Схема Яйб обрагдения которой Яй6 Яйб н Я 6 непосредственно получаются из схем (3,), (8,) и (81), сама является производной схемой.
Из этого следует, что если формулы д)) и % дедуктивно равны на основе схем (8,) — (8,) формулам %, и у1, соответственно, то на основе этих схем формула Ю1 йе1 будет дедуктивно равна формуле И, йй)ь К этому мы добавим следующие утверждения, относящиеся к выводам с помощью схем (51) — (5,): С помощью схем (51), (Ве) и (Б,) может быть получена схема формул 1(Яй 1Я), а из нее с помощью (Б,) — схема формул Я вЂ” «1)Я.
На основании этой схемы и схемы (Б,) любая формула Я дедуктивно равна формуле 1 1Я. С помощью схем (Я,), (Б,), (О,), (5,) и схемы силлогизма получается — с использованием производной схемы вывода 1( 16й Я) — схема контрапозиции Я-э.6 С помощью схем ($,), (8,), (8,) и схемы силлогизма получается схема вывода 1 (Я й 6) которая представляет собой обращение схемы ($,), а также схема вывода 1(Яй 16) 54! ТОЖДЕСТВЕННЫЕ !-К.Н-ФОРМУЛЫ З4О и!! ПРИЛОЖЕНИЕ Обращение этой повледней выводится с помощью схем (8,), ($4) и схемы силлогизма.
Таким образом, любая формула Я -» ) Е дедуктивно равна . формуле )(ЯйЕ), а любая формула Я-»6 дедуктивно равна формуле ) (й й ) 6). Применим сказанное к формулам вида, )(Яй )(ей6)). Такая формула, как только что было замечено, дедуктивно равна формуле Я вЂ” »Ей6; а эта в свою очередь, как, уже упоминалось, дедуктивно равна формуле (Я-»6) й(й-1-6). ' Но члены этой конъюнкции дедуктивно равны формулам ) (Я й ) 6) и ) (Яй ) 6) соответственно, а отсюда, в силу одного отмеченного выше утверждения, получается, что формула (Я-»6) й(й-»6) дедуктивно равна формуле ~(йй 16) й 1(йй ) 6).
Значит, последняя формула также дедуктивно равна формуле 1 (Я й ) (6 й 6)). Полученные утверждения теперь уже делают вполне очевидным тот факт, что все шаги замены 1) — 5), на которые распадается рассмотренная нами процедура перехода от заданной 1-К-)Ч-формулы к связанной с ней конъюнктивно нормированной формуле, таковы, что на каждом шаге некоторое выражение заменяется другим, дедуктивно равным ему на основе схем (В!) — (8,) выражением.
Теперь для установления интересующего нас дедуктивного равенства нам осталось только убедиться, что при любой замене в 1-К-Ы-формуле какого-либо выражения, фигурирующего в каче- ' стве ее составной части, дедуктивно равным ему выражением получается формула, дедуктивно равная исходной. С учетом структуры 1-К-Х-формул для этого достаточно показать, что если 1-К-И-формулы Я и 6 дедуктивно равны (по отношению к выводам с помощью схем 3! — 3,), то для любой 1-К-И-формулы 6 формула 6-»й дедуктивно равна формуле 6-4-6, формула Я- 6 дедуктивно равна формуле 6-»6, формула йй6 дедуктивно равна формуле Ей 6, формула 6 йй дедуктивно равна формуле 6йЕ и формула ) Я дедуктивно равна формуле ) Е. Это доказывается аналогично тому, как в З 2 было доказано аналогичное утверждение о схемах (5,) — ($„) и о 1-К-формулах: соответствующие дедуктивные равенства, справедливость которых, утверждается в предположении дедуктивного равенства формул Я, и 6, получатся из наших утверждений о аыводимостях с помощью схем (3!) — (В,), если мы сможем показать, что если 1-К-й)-фор-: мулы Я и 6 дедуктивно равны по отношению к схемам ($!) — (Б,), то с помощью применений этих схем к 1-К-11-формулам могут быть выведены импликации Я-»6 и 6- Л.
д это может быть получено из теоремы о посылках. В самом. деле, условия этой теоремы, если рассматривать выводы с помощью схем (З!) — (Вв) выполняются (даже в том случае, если брать произвольные формулы, лишь бы они содержали в числе связок импликацию, конъюнкцию и отрицание).
Именно, выполнимость условий этой теоремы применительно к выводам при помощи схем (5!) — Ь,) мы установили в ) 2. В результате присоединения схем (8,), (5,) и (3,) требуется еще проверить, что следующие две схемы вывода: 6-+. (Я -+ 6), 6-+ (Я -» ~ 6) .",р- !Я $-» )(Яй6) 6-»(Т1-» ~6) — являются производными схемами. Но в том, что это справедливо, легко убедиться следующим: образом. Из двух формул $- (Я- 6) и 9-»(Я-» )6) с помощью производной схемы соединения посылок мы получим формулы ейй-»6 и 6йй-» ~6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
