Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 37
Текст из файла (страница 37)
Разработанные адесь распоанающие процедуры затем удавалось оформить — частью прямьпа способом, частью с помощью упомянутой теоремы Эрбрана 1)— как методы распознавания выводимости формул или соответственно их опровержимости. Эти решения частных случаев проблемы раарешимости носят, однако, весьма специальный характер; предлагаемые в них методы распознавания существенным образом связаны с особым характеро11 рассматриваемых случаев. й 5.
Изучение формализма исчисления преднкатов 1. Понятие переводимости; производные правила. Таким образом, мы далеки от общего регпения проблемы разрешимости '). Следовательно, в этом отношении в исчислении предикатов мы имеем существенно иное положение, чем в исчислении высказываний. Здесь мы не можем, как в исчислении высказываний, заменить вывод формул применением какой-либо распознающей процедуры; напротив, мы в принципе оказываемся вынужденными остановиться на дедуктивном методе.
Несыотря на это, мы проведем определенную параллель между методами исчисления предикатов и методами исчисления высказываний, отметив целый ряд специальных производных правил. Мы здесь обсудим ряд таких правил, играющих особо важную роль в деле сокращения формальных выводов. Эти правила будут главным образом касаться преобразования выражений, и с помощью этих преобрааований мы будем, в частности, строить для формул исчисления преднкатов определенные нормалъныв формы.
Прежде всего мы должны будем уяснить себе, чтб в данном контексте будет пониматься под преобразованием. В исчислении высказываний преобрааования производятся путем применения определенных правил замены. Прн таком пре- 1) Ск. с. 186. ') Эрбрак к своей работе: Н е г Ь г а и й 1. Эпг1 к ргоЫеше 1опйашепгк1 йе 1а 1о9кйпе ша1Ьбша119пе.— С.й. Эоа.
Эс1. гзгзогге, С1. 1П, 1931, 24— указал ккогообраэкые применения его теоремы. Э) т ) То, что такое общее решение па самок деле невозможно, было кпоследстккк показало Алонзо Черчем в работе". С Ь и г с Ь А. А по1е оп гйе Еп)- эсЬеЫпп9вргоЫеш.— 1. БушЬо11с Ьоз)с, 1936, 1, рр. 40 — 41, 101 — 102.
См. об этом во втором томе Прпложепке П (укаазкке 1 после оглавления т. 11). образовании выражение Я ааменяется выражением В, представляющим ту же самую истннностную функцию. Тем самым ааменимость Я посредством 3 равноаначна тому, что эквивалентность Я В является толсдвственно истинной. В дедуктивной логике высказываний роль тождвстввнной эквивалентности начинает играть выводимая эквивалентность, которая, собственно говоря, совпадает с тождественной эквивалентностью. Чтобы иметь возможность проводить четкое различие между этими понятиями, мы будем называть формулу Я п е р е в о д им о й в В, если эквивалентность Я вЂ” В является выводимой. В исчислении предикатов, рассматриваемом в том виде, как оно получается из наших основных правил, в нашем распоряхгении имеется только понятие выводимой эквивалентности, и поэтому речь здесь может идти только о преобразованиях в смысле иереводимвсти.
Основание нааывать переход от Я к З преобрааованием в случае переводнмости Я в В нам дают следующие факть11 1. Если Я переводима в В, то и В переводима в Я. Если Я переводима в В, а  — в 6, то Я переводима в 6. 2. Если Я переводима в В, то З выводима иа Я и Я выводима из В с помощью наших основных правил. 3. Пусть Я является подформулой формулы (й в смысле правил построения формул исчисления выскааываний, а Й получается из (о в результате подстановки В выесто укааанного вхождения Я. Тогда если Я переводима в В, то (е переводима в Ф. Утверждения 1 и 2 очевидны; утверждение 3 является следствием того, что из эквивалентности Я В можно, во-первьгх, вывести а кроме того, для любого выражения 6 можно вывести 6бгЯ 6дгВ, Ябг6-Вдг6, 6)~Я 6)7В, Я~76-В~6, (6 — Я) (6 -+.В), (Я -~-6) (В-~-6), (6- Я) -(6-В), (Я-6) (В- 6).
Заметим также, что любые две выводимые формулы переводимы друг в друга. 474 исчисление НРедикАТОВ 4 Ы 11зучение ФОРмллизмА исчисления НРедиклтов $75 [РЛ. 1У Действительно, если Я и й) обе выводимы, то выводимы также Я-Р1О и ю-+ Я, а вместе с ними и Я )В и, аначит, Я переводима в кг.
Мы приступаем теперь к перечислению этих правил. Так как речь адесь пойдет о простом применении ранее выведенных формул и правил, то пояснение и обоснование достаточно будет давать с помощью примеров, нз которых можно будет навлечь и общий лгетод. П р а в и л о (е): Пусть нам дана некоторая формула (в качестве исходной или выведенной), содержащая одну или несколько. свободных переменных.
Тогда мы можем каждую иг них связать при помощи какого-либо написанного перед этой формулой квантора всеобщности или существования, причем последовательность кванторов может быть выбрана произвольным образом. (Разумеется, вместо свободных переменных можно будет брать лишь такие связанные переменные, которые раныпе в этой исходной формуле не встречались.) Тан, например, от формулы Я(а, Ь,с) если она не содержит ни х, ни у, ни г, мы можем перейти к Чх13у)1гг Я (х, г, у) следующим образом. Сначала подставим вместо а какую-нибудь не входящую в Я (а, Ь, с) свободную переменную, например с), а затем подставим а вместо Ь; так мы получим Я(д, а, с). Применив правило (у') 1), мы получим 1гхЯ (д, х, с), а отсюда, переименовав переменную х в г и подставив а вместо с, получим 'ггЯ (д, г, а).
Эта формула вместе с формулой 'ггЯ (с(, г, а) — 1- Эх г гЯ (д, г, х), получающейся из формулы (Ь), по схеме заключения дает Зх 'РгЯ (д, г, х). 1) См. с. 446. Переименовав х в у и подставив а вместо д, получаем Зу 1УгЯ (а, г, у), а отсюда по правилу (у') получаем 1Ух 3у ~УгЯ (х, г, у).
В частности, этим методом из тождественных формул исчисления высказываний мы получим, производя подстановки формульных переменных с аргументами и последующее связывание свободных переменных, ряд дальнейших формул. Так, например, иа А~ 7А моягно получить такие формулы, нан 1Ух(А(х) ~( 1А(х)), 1Ух Чу (А (х, у) ~/ 7 А (х, у)), Зх1Уу(А(х, у) )/ 1А(х, у)); А -+. ( ~А -ъ. В) можно получить Зх~уу Эг(А(х, у) — Р( 1А (х, у) — РВ(у, г))). П р а в и л о (е'): Пусть нам дана формула с кванторной' приставкой, состоящей иэ одного или нескольких действующих на всю эту формулу кванторов всеобщности. Тогда мы можем эти кванторы опустить, а связываемые ими переменные заменить произвольными свободными переменными.
(Это правило является частичным обращением предыдущего.) Допустим, что у нас имеется формула Чу 1ггЯ (у, г) и пусть мы хотим получить из нее Я (а, Ь). С этой целью мы сначала подставим вместо переменной а, если она входит в Я (у, г), какую-нибудь новую свободную перемепную, например с; если переменная х входит в Я (у, г), переименуем ее в какую-нибудь еще не встречавшуюся связанную переменную, например в и. В результате из чу ггЯ (у, г) получится некоторая формула 1ту 1УгЯ' (у, г). 1гл.
гг ИСЧИСЛЕНИЕ ПРЕДИКАТОВ 17З 'эг Я' (а, г), и, подставив Ь вместо а,— Я' (д, Ь). Я (Ь, с)-ь5 (Ь, с), или же к то в выражении Я (х) -ь. (З (х, у) -+. 1е (х, у)) Я (а, Ь, с) З (а, Ь, с), ') См. с. 146. 1- д. Рильберт, и. Еериеае Теперь переименуем у в х. Получившаяся формула 1гх т"гЯ'(х, г) вместе с формулой 'эх 77г Я' (х, г) — ь 17г Я (а, г), получающейся подстановкой из формулы (а), по схеме заключения дает Подставим теперь вместо а какую-нибудь новую переменную, например 4 и переименуем г в х. Из получившейся формулы 1э'х Я ' (д, х), воспользовавшись еще раз формулой (а) и применив схему заключения, мы получим Я'(д, ) Теперь нам остается только вновь переименовать и в х и подставить а вместо с, а также а вместо д; тогда мы получим искомую формулу Я (а, Ь).
П р а в и л о (~): Пусть в обеих частях данной импликации или эквивалентности встречаются какие-либо свободные переменные. Тогда каждую иэ этих перельенных мы.кажем в обеих частях связать одним и тем же квантором всеоби1ности или суи1ествования; необходимо только, чтобы порядок кванторов в обеих частях был один и тот же. Так, от импликацни если переменные х и у в нее не входят, мы можем перейти к Ь(Х эгу Я (Х, у) -ь 1ЭХ Уу й) (Х, у) )7х Зу Я (х, у) -ь. Чх Зу 3 (х, у) . Точно так же от эквивалентности в которую не входят ни х, ни у, ни г, мы можем перейти к Зх Зу )7г Я (х, у, г) Зх Зу 17г 5 (х, у, г).
1 51 изуЧЕние ФОРИАлиЗмА исчисления пРедикАТОВ 177 Процедуру перехода мы рассмотрим на примере формулы Я (Ь, с)-ь-5(Ь, с), не содержащей переменных х и у. Выведем иэ нее формулу 'чх Зу Я (х, у) -~ т х ЗуЪ (х, у). Сначала, если в исходной формуле встречается переменная а, мы подставим вместо нее какую-нибудь новую переменную, например д; затем вместо с подставим а.
Из получившейся формулы Я' (Ь, а) -ь- З' (Ь, а) мы по правилу (6) ь) получим ЗхЯ'(Ь,х)- Зхй)'(Ь, х). Переименовав х в у и подставив а вместо Ь, мы получим ЗуЯ' (а, у) -ь. Зуй)' (а, у). Применив еще раз правило (6), мы получим 'тх ЗуЯ'(х, у)-ь.7х Зуй)' (х, у). Если мы теперь снова подставим а вместо е), то придем к искомой формуле.
В случае, когда исходная формула является не импликацией, а эквивалентностью, вместо правила (6) следует применять правило (6'). Применив правило (ь) к эквивалентностям, мы, в частности, получим П р а в и л о (ц): Пусть дана формула с кванторной приставкой, состоящей иэ одного или нескольких кванторов. Тогда в выражении, стоящем за этими квантороми, можно выполнять все те преобразования, которые оказываются допустимыми, когда вместо связываемых эт ми кванторами переменных стоят свободные переменные (и, значит, в частности, все преобразования исчисления высказываний).
Если, например, у нас имеется формула Зх 17у (Я (х) -ь-(й) (х, у) — ~ 6 (х~ у)))~ можно проиавести перестановку посылок, в результате чего мы придем к Зх ~Уу (З (х, у) -э (Я (х) ь- Я (х, у))). 1гл, гч исчисление НРедикАТОВ 178 В самом деле из тождественной формулы (А -«. (В-+. С)) (В-«- (А -+. С)) 1 е1 изучение ФОРмллизмА исчисления пРедикАТОВ 179 можно преобразовать в «уу Я(с, у) бс «1у З(с, у). подстановкой мы получим (Я (с) -ь (З (с, д) — +-6 (с, д))) (3 (с, д) -«(Я (с) -+. 6 (с, а))). Пусть при атом переменные с и д выбраны так, что они не входят в Я (х), З (х, у) и 6(х, у).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
