Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 38
Текст из файла (страница 38)
Тогда правило (ь) даст нам формулу Зх ч«у(Я (х)-«. (З(х, у)-+.6 (х, у))) Вх 1гу (З (х, у) -«- (Я (х) — «- 6 (х, у))). Значит, исходная формула действительно переводима в формулу Эх «Ру(З(т, у)-ь(Я (х) — «-6(х, у))). П р а в и л о (9): Пусть какая-либо формула представляет собой конъюнкцию с кванторной приставкой, состоящей иг одного или нескольких кванторов всеобщности. Пусть каждый член данной конъюнкции содержит все связываемые этими кванторами переменные.
Тогда мы можем написать эту кванторную приставку перед каждым из членов конъюнкции в отдельности. То же самее справедливо в отношении дизъюнкции с приставкой из кванторов существования. Указанная операция может быть произведена и в обратном направлении и, следовательно, имеет характер преобразования. В том случае, когда приставка состоит только из одного кван- тора всеобщности или существования, это правило получается непосредственным применением формул (7) и (9) ') в сочетании с правилом переименования связанных переменных. Распространение на случай нескольких кванторов всеобщности или нескольких кванторов существования мы проиллюстрируем на примере формулы вида 'ч х Чу (Я,'(х,"у) бс З (х, у)). Наше правило утверждает, что эта формула переводима Е1формулу «Рх ч«у",Я'(х, у) бг «вх «чу З'(х,(у).
Для доказательства воаьмем какую-нибудь свободную переменную, не входящую в Я (х, у) н З (х, у), например с. Так как мы уже умеем применять наше правило для случая одного квантора всеобщности, то мы получим, что '«гу(Я (с, у) дг З(с, у)) г) См. с. 150 з далее. Отсюда по правилу (е1) следует,что '«г х «чу (Я (х, у) дг З (х, у)) может быть преобразована в «в х («Уу Я (х, у) бс «чу З (х, у)), а эта формула по уже один раз примененному правилу для единичного квантора всеобщности переводима в 1Ух 'Уу Я (х, у) й «Ух Уу З (х, у).
Поэтому формула )(х Уу (Я (х, у) бг З (х, у)) также переводима в эту формулу. Следует обратить внимание на то, что в правиле (9) проявляется сходство между квантором всеобщности и конъюнкцией, а также между квантором существования и дизъюнкцией. В случае комбинации квантора существования с конъюнкцией или квантера всеобщности с дизъюнкцией эти дистрибутивные преобразования допустимыми не являются.
Так, например, выводимая формула «Ух (А (х) '/ 1А (х)) не переводима в «г«х А (х) ~/ Чх 1А (х), что усматривается хотя бы из того, что эта последняя формула ие является даже 2-тождественной. П р а в н л о (е): Пусть какой-либо конъюнкции или дизъюнкции предшествует кванторная приставка, состоящая из одного или нескольких кванторов всеобщности или существования, взятых в произвольном порядке. Пусть относящиеся к этим кванторам переменные так распределены между членами этой конъюнкции или дизъюнкции, что ни одна из них одновре.кенно не встречается в двух различных членах.
Тогда эту приставку можно так распределить между отдельными членами рассматриваемой формулы, что перед каждьм членом будут стоять только те кванторы, для которых соответствующие им переменные входят в рассматриваемый член. Порядок кванторов при этом сохраняется. Такал опера ция носит характер преобразован я и, следовательно, допустима в обратном направлении. В качестве примера рассмотрим формулу вида Зх «в у Зг (Я (х, у) ~/ З ~/ 6 (г)), 1ге г 5) ИЗУЧЕНИЕ ФОРМАЛИЗМА ИСЧИСЛЕНИЯ ПРЕДИКЛТОВ 18$ ИГЛ, 1У Ист1ИСЛЕНИЕ ПРЕДИКЛТОВ )8О где Я (х, у) не содержит переменной г, В не содержит ки х, яи у, ни г, а 6 (г) не содержит переменных х и у. Правило (1) утвержда- ет, что эта формула переводима в Зх )/у Я (х, у) )/ В )/ Зг 6 (г).
Соответствующее преобразование производится следующим обра- зом. Возьмем сначала какие-нибудь две свободные переменные, не входящие в исходную формулу, например Ь и с. Из формулы (8) ') подстановкой и переименованием х в г мы получаем Эг((Я(Ь, с) )/ В) '/6(г)) (Я(Ь,с) )/ В) )/ Згб(г).
По правилам (ь) н (т)) отсюда получается ') Зх Ру Зг (Я (х, у) 1/ В )/ 6 (г)) Зх еу (Я (х, у) )/ В ~/ Зг 6 (г)). Таким образом, наша исходная формула переводима в Зх 'ту (Я (х, у) )/ В ')/ Зг 6 (г)). В атой формуле мы прежде всего можем по правилу (т)) поменять местами члены дизъюнкции, так что получится Зх)ву(В ')/ Згб(г) )/ Я (х, у)). Теперь применим формулу (5) '); из нее подстановкой и переиме- нованием х в у получается 7у ((В )/ Зг 6 (г)) )/ Я (Ь, у)) ((В ')/ Зг 6 (г)) )/ )еу Я (Ь, у)), а отсюда, по правилам (1,) и (т)),— Зх7у(В )/ Згб(г) )/ Я (х, у)) Зх(В)/ Зг6(г) )/ 'еуЯ(х, у)). Возьмем, кроме того, формулу, получающуюся иа формулы (8) подстановкой (и применением правила (ц)): Зх (В ')/ Зг 6 (г) )/ 'Ру Я (х, у)) (В )/ Зг 6 (г) )/ Зх )/у Я (х, у)).
Из обеих этих эквивалентностей получается, что формула Зх Ру (В ')/ Зг 6 (г) )/ Я (х, у)), а тем самым и исходная формула, переводима в формулу В ')/ Зг 6(г) 1/ Зх)/уЯ (х, у), из которой нужная нам формула получается перестановкой чле- нов дизыонкции. 1) См. с. 488. е) Правило (т)) здесь испольеуетси яии Рстраиеиии скобок.
в) См. с. )49. П р а в и л о (х): етдущие друг ва другом кванторы всеобщности, а также идущие друг ва другом кванторы существования, относящиеся к одному и тому же выражению, можно в проиавольном порядке поменять местами. Это правило получается применением формул (13) и (13') 1). Так, например, любая формула )/х Чу угЯ (х, у, г) переводима в 1/г )/у )/хЯ (х, у, г). Действительно, произведя подстановку в формулу (13) и переименовав переменные х и у в у и г в обеих частях эквивалентности, мы получим Чу )Рг А (а, у, г) 1Уг 1Уу А (а, у, г), а отсюдя, но правилу (6'),— )Рх 7у чг А (х, у, г) 1ех 1ег )/у А (х, у, г). С другой стороны, формула (13) переименованием у в г и подста- новкой Ру А (а, у, с) вместо именной формы А (а, с) дает формулу в1х1Уг'еуА(х,у,г) )/г')/х7уА(х,у,г), а нз предыдущей эквивалентности путем подстановки А (Ь, с, а) вместо именной формы А (а, Ь, с) и последующего переименова- ния х, у и г в г, х и у получается 1)/г )/х 7у А (х, у, г) )/г 7у )/х А (х, у, г).
Три полученные эквивалентности совместно друг с другом дают формулу 1ех 'Уу 1Уг А (х, у, г) 1Уг )/у чх А (х, у, г), из которой и получается нужная нам переводнмость. Следует заметить, что, согласно правилу (т)), перестановка следующих друг за другом кванторов всеобщности допустима и в том случае, когда им предшествует квантор существования, так что, например, формула Чи Зх 1Уу чгЯ (х, у, г, и) переводима в ')/и Зх Уг 'УуЯ (х, у, г, и). П р а в и л о (Х): Отрицание формулы с кванторной приставкой может быть получено заменой каждого ив кванторов всеобщно- ') Си.
с. )84 и далее. [гл. в' исчисленин ИРВдикАТОВ 182 1 Ь1 изучение ФОРИАЛИзмА ИСЧИсЛения пРедикАТОВ 133 сти квантором существования, каждого квантора существования— квантором всеобщности, а следующего ва ними выражения — его отрицанием. Так, формула ~ 1Ух Зу Я (х, у) может быть 1треобразована в 3х Уу 1Я (х, у). Действительно, из формулы (2) г) подстановкой мы получаем ЗпхЗуЯ(х,у) Зх 3 ЗуЯ(х,у), затем нз формулы (3) переименованием х в у и подстановкой получаем 13уЯ(а,у) 'Уу 1Я(а,у). Теперь по правилу (6') получается лх 1 Лу Я (х, у) лх ту ~ Я (х, у). Объединив эту формулу с ранее полученной, мы получаем ~'тх Зу Я (х, у) Зх Чу 1 Я (х, у), откуда и вытекает искомая переводимость.
2. Приведение формул к предваренному виду; примеры; описамие разрешимых случаев проблемы разрешимости с помощью предваренной нормальной формы. Перечисленные выше правила преобразования мы теперь применим для получения нормальных форм некоторого специального типа. Именно, мы покажем, что всякую формулу исчисления предикатов можно перевести в такую формулу, у которой все кванторы стоят снаружи, так что она получается из некоторого выражения исчисления высказываний, если его формульные переменные снабдигь аргументами и связать свободные переменные кзанторами всеобщности и существования, поставленными перед всей формулой в целом. Всякую формулу, имеющую такой вид, мы будем называть предваренной формулой. Процедуру перевода любой формулы в предваренную мы изложим на примере формулы 'ух ту А (х, у) -«Чх(В(х) -«ЗуС(х, у)).
Прежде всего, пользуясь правилом (ц), мы при помощи исчисления высказываний устраним обе нмпликации; так мы получим формулу ~Ух ЧуА (х, у) ~/ Ух( )В(х) ~/ ЗуС(х, у)). 1) См. с. 147, Согласно правилу ()), 1Чх Уу А (х, у) мы можем перевести в ЗхЗу ~ А(х, у); далее, по правилу (~), 3В(а) ~/ лу С(а, у) мы можем преобразовать в Эу( чВ(а) ~/ С(а,у)); следовательно, по правилу (Ч), 'ух ( 1В (х) '/ Эу С (х, у)) может быть преобразовано в Ъ'хЗу( ~В(х) ~/ С(х, у)), так что в целом мы получим ЗхЗу 1А(х, у) ~/ ЧхЛу 1(В(х) ~/ С(х, у)).
Теперь применим к члену 'т'х Зу ( 1В (х) ~/ С (х, у)) атой дизыонкции правило переименования, переименовав х и у в и и о; так мы получим формулу ЗхЭу 1А (х, у) ~/ 1виЗР( )В(и) ~/ С'(и, и)), а ее по правилу (~) можно перевести в предваренную формулу Зх Зу Чи Зи ( 1А (х, у) ~/ 3В (и) ~/ С (и, о)). Следует обратить внимание на то„что при применении правила (ь) порядок кванторов в кванторной приставке может быть здесь установлен различными способами. Например, последовательности Зх Уи Зу Эо 'у и Зо Эх Зу тоже являются допустимыми. Если же еще учесть н правило (х) о перестановочности двух соседних кванторов существования, то становится ясным, что единственное условие, налагаемое в этом примере на порядок кванторов, состоит в том, что квантор уи должен предшествовать квантору ло.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
