Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 42
Текст из файла (страница 42)
с, 23 — 25. е) См. с. 36-37. ') См. с. 39. Исключать асе переменные а рассматраааемам случае пе тре'буется, то в логике высказываний истинна дизъюнкция Я, )/ ... )/ Лп, где Я;(1 =1, ..., и) представляет собой формулу Я(Ч» 'р(Ч) чР(Ч») ' б Х(Ч ° ' б) !) Следовательно, эта дизъюнкция получается подстановкой из неко- торой тождественно истинной формулы исчисления высказываний. Теперь мы можем освободиться от предположения о том, что формула 6 не содержит свободных переменных. Действительно, формула 6, в которую входят свободные переменные, дедуктивно равна некоторой формуле Же, получающейся из нее в резуль- тате замены индивидных переменных индивидными символами, а формульных переменных предикатнымя символами (такую замену мы уже делали при доказательстве первой в-теоремыа)).
Тогда в связанной с формулой 6е дизъюнкции»Л, 1/ ...'!/ Лп введенные нами индивидные и предикатные символы можно будет снова заменить соответствующими переменными. Дизъюнкция, получаю- щаяся в результате этой замены, тоже будет получаться подста- новкой из некоторой тождественно истинной формулы. Для установленной таким образом взаимосвязи между выво- димой средствами исчисления предикатов формулой 6 и получае- мой по ней истинной в логике высказываний днзъюнкции имеет также место следующее ее обращение: Если дизъюнкция Ж, имеющая вид Я(ЧН»Р(ЧА), чь(Чт), т„бм Х(Ч,, тт, бт), !А) )/ .. )/ Я(Чп» Ч»(Чп)»»р(Ча)» 'и бп»' Х(Чп» тп» Зп) !и)» палучоется ается Подстановкой из какой-либо тождественно истинной формулы исчисления высказываний, то формула ч. может быть выведена средствами исчисления предикатов.
Действительно, определим для термов, входящих в дизъюнк- цию 33, их кратность — число, которое указывает, сколько раз в терм такого рода входят функциональные знаки»р, ф или у. Затем мы расположим термы »р(Ч»), чЬ(Ч»), Х(Ч1, ть 61) (1=1, ..., и) (опустив, быть может, встречающиеся здесь повторения) в неко- торую последовательность т! См. с. З7-33. ч д Гнаьбер», П. Бернаае 195 ТЕОРЕМА ЭРБРАНА 194 е-СИМВОЛ И ЛОГИЧЕСКИИ ЭОРМАЛИЗМ егл. гп так, чтобы п и воз ас не у ывала.
р р танин индексов термов их кратность менные а, ... а А теперь возьмем какие-либо занумерованные свободные ные пере, ..., ах так, чтобы они не входили в формулу Ж. Заме- ним в этой формуле терм 1, переменной а„терм Е, переменной а.„..., терм 1Р переменной а„таким образом, чтобы замена терма 1, пе е- менной а; производилась всюду, где этот терм входит в Ж, ча за исключением тех мест, где он входит в качес тве составной асти какого-либо другого из числа термов 1 ...
1 . П ри этом формула О перейдет в некоторую формулу Ж„ которая тоже является истинной в логике высказываний. Д " указанной замене совпадение элементарных фо м л по виду будет сохраняться. ы формул по внешнему Дизъюнкцня Зе имеет внд Й(Ь а, (, а, с, с, Ь, аи, е))/... ... Ч ' ( „, ае„, ЕА, „, Ь„, ае, е„). ЕА' Здесь номера р, ..., р р рее " ~ Бю и ° ° ° е ЕА~ 1А~ °... ЕА суть числа из ряда 1, ..., р, для которых выполняются следующие н уме а ные условия: умерацион- 1. Пусть 1 †люб из чисел 1, ..., р. Если переменная а„ входит в какой-либо терм Ь;, то числа рр 11, 11 превосходят число е; если переменная а вхо ит дит в с или Ьр то число 11 превосходит число 1. 2. се числа е)„..., «„ отличны от каждого нз чисел 1, и 2.
Все ч 1; (1 =1, ..., п)1 точно так же каждое из чисел 1 , отлично от каждого из чисел Ее. 3. Число р; совпадает с числом Ьр а число 1; совпадает с И тогда и только тогда, когда терм Ь, совпадает с термом число й совпадает с числом 11 тогда и тольк о тогда, когда Ь, совпадает с Ь, с, совпадает с ср а Ь, совпадает с Ьр Действительно, Условие 1 получается следующим образом: если а, входит в, то в формуле Ж терм 1; входит в», и, следовательно, является составной частью терма ср(»,), а также термов ф(») и Х(»р с;„6,), т.
е. Е, является составной частью термоз Е ., Е и по этому кратность терма 1; меньше кратностей термов и 1,, а тем самым числа рр 1„и 11 превосходят число 1. Далее, если а, входит в с или в Ь то 1 входит фо, + 1 в формулу + в качестве составной части терма Е,; поэтому терм 1 имеет 11' меньшую кратность, чем 1, и, значит, число 1, превосходит й число с. Условие 2 следует из того, что терм ср(»,) всегда отличен от термов ф(»;) и Х(»п ср 6,); равным образом и терм ф(»,) отличен от терма Х(»р ер 6;). Условие 3 получается следующим образом: число р; совпадает с числом с) тогда и только тогда, когда в формуле Ж термы ср(»;) и ср(») совпадают, т.
е. когда», совпадает с»,. Но это имеет место тогда и только тогда, когда терм Ь; совпадает с Ь). Числа 1; и 1) совпадают тогда и только тогда, когда совпадают термы ер(»;) и ф(»;); необходимым и достаточным условием для этого является опять-таки совпадение термов Ь, н Ь,. Числа 1| и 1| совпадают тогда и только тогда, когда совпадают термы х(»п сь 6,) и х(»р ер 6,). необходимым и достаточным Условием для этого является совпадение»; с»р а также с; с с; и 6; с 611 а это снова имеет место тогда и только тогда, когда Ь; совпадает с Ь, сс совпадает с с, а Ь, совпадает с Ьр На основе этих свойств дизъюнкции е'.ь применяя правила (ЕА) и (ч) ') и устраняя встречающиеся повторения среди членов втой дизъюнкции, мы можем перейти от этой формулы обратно к формуле (Т.
Это может быть сделано следующим образом. Сначала, применяя правило (Ес), каждый дизъюнктивный член 91(Ь„аеп а~ с„дь ан, е;) мы преобразуем в соответствующую формулу Зев Я(Ь„а„, аь, с„ЬО а, сп). Если при этом некоторые члены дизъюнкции совпадут, то возникающие повторения мы опустим. В получившейся в результате этого дизъюнкции Же все встречающиеся в ней числа 1, будут отличными друг от друга. Действительно, при совпадении 1, с 1 вследствие условия 3 должны будут совпасть Ь| с Ь,, с; с с), д, с Ьр а потому также и е~ с с) и 1 с 1.
Тогда совпадут с-й и (-й члены дизъюнкции. Условимся для краткости термы Ьь с; и Ь| называть Ь-, с- и ь-термами. Рассмотрим те переменные из числа ам ..., а„, кото- е) см. с. !73. т* 197 теоРемА ЭРеРАНА 4.СИМВОЛ И ЛОГИЧЕСКИЙ ФОРМАЛИЗМ Ггл. ш рые входят в какие-либо из этих термов, и пусть среди рассматриваемых переменных переменная а,„имеет наибольший номер. Если в 1-м члене дизъюнкции а входит в Ь„с; или д„то, согласно условию 1, число 1, больше сп, а потому и больше номеров всех тех переменных, которые входят в какие-либо из Ь-, силн Ь-термов. По условию 2 это число не может совпадать ни с одним нз чисел 91, 1р а согласно сделанному ранее замечанию, оно не совпадает также ни с одним нз чисел 11 при 1Фс. Поэтому переменная а входит в дизыонкцию Ь, только один раз, и мы можем применить к 1-му члену дизъюнкции н к переменной а, правило (т).
В итоге, заменив переменную а связанной переменной г, мы получим вместо этого члена днзъюнкции новый член 4ссгЛвЛ(Ь„а,, ас, сь ьь г, в). Дважды применив правило (14), мы преобразуем этот член в формулу :-)иЗо4(гВвЛ (Ь„а ., а1, и, о, г, в). Аналогичным образом мы поступим и со всеми остальными членами днзъюнкцни, внутри которых переменная ам встречается в каком-либо из Ь-, с- или Ь-термов. Если при этом будут всвникать повторяющиеся члены днзъюнкции, то повторения мы будем вычеркивать.
Так мы придем к некоторой дизъюнкции Же. В этой дизъюнкции уже не будет с- илн Ь-термов, содержащих переменную а„„но переменная ам может входить в ней в какой- нибудь из Ь-термов. Член этой днзъюнкции, в котором имеется один из таких содержащих переменную ам Ь-термов, является одним из тех членов, которые с помощью правил (Р) и (ч) преобразовались в формулу вида :-)иВОЧгВвЯ(Ь„ае, аси и, о, г, в). Встречающиеся в нем номера переменных р; и 1„согласно условию 1, больше числа ас (поскольку Ь, содержит переменную а„,) и, тем самым, больше номеров всех тех переменных ар которые входят в какой-либо из еще имеющихся в Зе Ь-, с- или Ь-термов.
Рассматриваемое нами число 1ь не может также совпадать ни с одним из встречающихся в Ж чисел 91 при 1чь!. Действительно, в противном случае, в соответствии с условием 3, терм Ь; должен был бы совпадать с Ь;, а число 1, — с 1;; тогда терм Ь1 содеРжал бы пеРеменнУсо ае, и, значит, 1-й член Дизъюнкцни имел бы вид =)иВо4сг=)вЛ(Ь1, а, а,р и, о, г, в), а потому, согласи ласно только что сделанному замечанию, совпадал бы с членом ЗиВо~ссгВвЯ(Ь„а, ас, и, о, г, в), м как члены дизъюнкции 24 не повторяют ся. Таким между тем образом, число Ь, отлично от всех встречающи хся в х чисел Ь при (Ф 1. Наконец, ввиду условия 2 число Ь, отлично и от всех чи л чисел 1 и Ь.
Следовательно, переменная а . в дизъюнкции ', вс р к ии Ь вст ечается только на одном месте. То же самое верно и в отношении переменной аь, Поэтому к 1-му члену дизъюнкции можно применить ! правило (ч) — сначала по отношению к переменной асп ной а, а затем по отношению к переменной а., — и если р п и этом в качестве вводимых связанн ых переменных взять переменные х и у, то нас пол чится вместо рассматриваемого члена дизъюнкции у нас получ м ла фру 'ох'41уВи:егоУг3вй (Ьь х, у, и, о1 г, в).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
