Гильберт, Аккерман - Основы теоретической логики (947372), страница 27
Текст из файла (страница 27)
99 (1928), (Б е р н е й с н Ш е й н ф н н к е л ь, К проблеме разрешимости математической логики.) Из числа других решенных частных случаев проблемы разрешимости, в которых, впрочем, приходят к цели уже не такими простыми средствами, упо- мянеи еще следующий. Для формул, приставка кото- рых имеет форму (х,)...
(х ) (Еу,) (Еу,) (з,)... (з„). также можно решить вопрос об общезначимости '. И в этом случае решение вопроса об общезначимости вообще может быть сведено к решению вопроса об общезначимости для определенной конечной области индивидуумов. Однако этими типами приставок исчерпываются случаи, когда таким путем удается решить вопросы об общезначимости.
Для всех других приста- вок можно указать формулы, которые общезначимы во всех областях с конечным числю! индивидуумов, однако не общезначимы в области с бесконечно мно- гими индивпдуумами '. Что касается общего решения проблемь! разрешимости, то поиски такового после исследований, которые предпринял Черч, примыкая к работам Геделя, следует рассматривать как безнадежные'. На иютожеСр. Стмс1, К., Хигп Еп!всЬеынпйвргоЫеш сев !ос!зсйеп Рип1гцопепйзШО) ° (оредвзрнт. нзл.
з Егб. Ш!еп, шз1Ь. Коц. ВО. 2 (1982). Ко!шег, Г., ОЬег О!е Ег!ЬПЬзгке!! Осг)епщеп 28Ызимггасае, не1сЬе !и Оег Хогшзноггп знс)ЬепзсЬЬзг)с АЦ- зс!слеп еп!Ьз!!еп. Мзщ, Апп ВО. )аз (19З2). Шаацг, К., Г)п!егвисьипбеп хнш епьиье(бипбвргоыеш Оег нвзшепвзпвсьеп ьош)г. Мзщ.
Апп. ВО. цш (1984).— Оьог Ше Егпшшзгке)1 е)пег К)зеве топ го81зсьсп Гоглге1п. мзпг, Апп. ВО. 11о (1934). Для сзучлп, когда зышеупомянутзя приставка содержит не днз, з толь- ко опнн знзк сущестзоззпня, решенно получено уже раньше Ллчврчоном н Сьолвлом. Ср. Агагплолл, и'., Оьсг Оге Ег!иньзгаеы йеиншег хзшзизигасае. Мз!Ь. Апп. 11928)! 84В!СШ, та„ОЬСГ О!Е Шс СИСЬЕ 1. 8Ш. ЫОГВЬ. ШЗЬ тшвьг.
ВО 10 (1928). члстныгв случай зтаго родо был уже рзс- смотрен в работе, укеззнпой з предыдущем примечании, ' Ср, первую нз упомянутых а предыдущем ирнмечяннн работу К. Ясаа!!г. ' Санге», А., Ал ипвошзЫе ргоЫеп! ог е)мпел1згу пишЬег шеогу. Ашег, 1. мз!ь ВО, 68 (1986). А по!е оп ше еп!всьешипбв- ргаыеш, соггесноп !о л по!е оп !ье еп1всьешипйвргоыегп, ,), 8УгпЬ. ).ос!с. ВО. 1 (1936), узше исси«вские лреоикстов нии этих исследований в рамках данной книги мы не мои!ем останавливаться. Отметим только, что общий разрешающий метод должен был бы состоять в некотором рекурсивном приеме для отдельных формул, который кап!дай формуле относит окончатеяьно значение «истинноо илн «до>кнор.
Но существование такого рекурсивного приема отрицается работой Черча; во всяком случае, необходимые рекурсии не подпадают под установленный Черчем общий тип рекурсии, с помощью которого содержательно несколько неопределенное понятие рекурсии получило известное формальное уточнение. Чтобы изоежать недоразумений, следует отметить, что невозможность найти всеобщий разрешающий метод не означает, что можно указать определенные формулы, неразрешимость вопроса об общезначимости которых можно было бы доказать.
Предположение существования подобного доказательства немедленно приводит к противоречию. Из такого доказательства получилось бы доказательство того, что эта формула не выводима из системы аксиом З 5. Однако, пользуясь предложением полноты З 1О, в такои случае можно бьшо бы доказать выполнилюсть отрицания этой !)юрмул!з.
Но таким образом вопрос об общезначимости был бы решен н притом в отрицательном смысле. Таким образом, во всяком случае задача расширять область тех фориул, для которых решается проблема разрешимости, остается и в дальнейшем ценной и значительной. ГЛАВА гетВертля расширенное исчислпппп предпкятпв б !.
Исчисление прсянкатов второй стуисии К первому расширению узкого исчисления предикатов, или, как его еще налезают, исчисления предикатов первой ступени, мы приходим, учитывая то обстоятельство, что формализм узкого исчисления явно не завершен. Так, мы можем, правда, выразить, что иш<бторая формула для всех значений встречающихся в ией переменных предикатов выражает истинное высказывание, но мы не можем выразить утверждение, противоположное этому.
В самом деле, если мы поставим черту отрицания над всей формулой, то это будет означать, что формула для всех значений переменных предикатов должна выражать ложное высказывание. Однако возможно, что некоторая формула представляет утверждение, про которое нельзя сказать ни что оно истинно для всех значений переменных предикатов, ни что оно ложно для всех значений переменных предикатов.
Например, формула (х) Г (х), конечно, ни для какой области индивидуумов не общезначима; но также не является общезначимой и формула (хх) )г (х). Чтобы выразить, что (х) г (х) не общезначима, мы должны были бы располагать знаком существования для предикатов. Вполне естественным представляется поэтому такое расширение исчисления предикатов первой ступени, при котором мы применяеи знпки общности и существования также в связи с переменнымп высказываниями и пергменными предикатами и различаем свободные и связанные переменные подобного рода.
Понятие логической формулы, сформулированное в З 4, подвергается в такоп случае соответствующему расширению. Мы приходим к исчислению предикатов впюроб ступени. !! С» р** «««осло ос >гэ Рэ "юолм>о мс ос ш лепке пцмащам«« Поясним нссколькими прил>ера>«и получающееся та. ким образом расширение возиом<нсстей вырюксния. Формула (Р) (х) (Р (х) >у Р (х)) высказывэет, что (х) (Р (х) >у Р (х)) пыполнястся для каждого предикат.> Р. Формула (А) (Р') ((х) (А — > Р (х)) - (А — . (х) Р <х))) выражает, что отношение меяп<у высказываниями и предикатами, определенное через (х)(А Р (хИ (А (х) Р (х)), выполняется для любых высказываний и предикатов.
По;сбного же рода случай возникает при силеоличесло<) формулирое>ге принципа полней илдукцки. Содерж >ние зтсго при~пипа можно выразить следующим образом: «Если некоторый предикат выполняется для числа 1, и если при выполнении предиката каким либо числом он выполняется и непосредственно следующим числом, >о этот предикат выполняется каждым числом>. Если мы введем знак Яс>) (х, у) длэ стно>венпч числа к неп>средственно следующему, то этот приннип мы можем выразить формулой: (Р (1) и (х) (у) (Р (х) б> Яец (х, У) — ' Р (у)]) —.. <х) Р (х), постулируя ее в качестве истинной.
Если мы хотим еп;е явно выразить самим способом записи, что эта формул>дол>кна выполня>ьсч для всех предикатов Р, то еле;ует перед фоомулой поставить знак всеобщности (Р). Дальнейший харак>ерный случай представляет собой опуеселечие т»лссесшаа. Отношение то>кдсстш« можно, по определенню, свести к основным логпчсскнм отпгшенияэ>, считал х тождественным с у, если каждыя предикат, выполняющийся для х, выполняется также для у, и обратно. В смысле этого разьяснсния знак тождества =— (х, у) можно понимать как <Гс«опека Ш«эю,,мм ия Л а гм>мело >оэ сокращение длл выр;оковы (Р) (Р(х, Р(1>)). В приведенных случаях у>ютреблсние знака общности хотя и очень естественно, но все же нс неизбежно. Однако сущестнуют случаи, когда употребление знака общности необх диью, если не желать отказспься от важных возможностей выражения.
Если пожелать, например, выразить, что каждый предикат <<(х, у), эквивалентный тон<деству, обладает свойств>м симметрии, то приходится запнапь э>о следующим образе м: (Е) ('(х) (и> (Е (х, у) (Р) (<'(х) Р (у))) —: (х) (у) (И(х, у) Е(у, х))).
Здесь знак общности (Р) нельзя отбросить, не изменяя смысла высказывания. Как уже выше упоь>януто, без знака общнос>п нельзя обойтись н когда об определенном ныражешш нужно сказать, по не для всех значений встречающихся в нем переменных предикэтов оио является истинной формулой. Наприэ>ер, чтобы выразить, что (х) (у) Р (х, у) не является общезначимой формулой, мь: ь>ожем применить формутт (Р) (х) (у) Р(х,у) нли также равнозначную сй (ЕР) (Ех) ('Еу) Р(х, у). Такое >ке положение вещей имеет место длэ многих предло>пений логики, содержащих у>верж.епи > общего характера о высказываниях и пред~катах; эш применимо, напркмер, к предложении>, что ал,> каждого высказывания Х существует высказывание У таком> рода, что нз обеих высказываний по крайней иере одно, но и только одно, истинно (г.
е. к предложеин>о о существовании противоположности для высказывания). В расин>репкой символике опо ш лу юст выражение <Х) <ЕУ) <Х '/ 1' й Х и У), >>* рвсширенчое шчислсиис предтттоо Между тем посредством прежней символики это предложение не могло бы быть передано. Расширение символики дает нам также возможность формулировать символически такие проблемы и их решения, которые раньше требовали обстоятельного содержасельного описания. Я напомню, например, рассуждения, которые мы применили в б 8 главы Е Полученные там результаты можно выразить следующими формулами: (Х) (А,Х й А,Х) А, й А„ (ЕХ) (АсХ й АоХ) А чс Ао Эти формулы дают правило, позволяющее заменить выражение, содержащее кванторы сзля переменных вьсскансвании, эквивалентным выражением, в котором зти кванторы уже не встречиютсл.
Именно, надо по. следовательно разворачивать выражение по переменным, принадлежащим самим внутреннилс кванторам, б , от ра. ва затем всякий раз эти кванторы по правилу исклю. чения, выраженному в наших формулах. Например, нз (Х,) (Х,) (А,Х,Хо й А,Х,Х, й А,Х,Х, й А,Х,Х.) получаем, прежде всего, исключением квантора (Х,) (Х,) ((А,йА,) Х, й(А,йА,) Х,)) и дальше А,йА,йА,йА,, Это правило исключения, которое мы теперь можем сформулировать символически, дает нам возможность решать вопрос об истинности (соответственно ложно. сти) формул, в которых содержатся только переменные высказывания и принадлежащие им квзйт р им кванторы.
Например, в вышеупомянутой формуле (Х) (ЕУ) (ХУйХйу) мы прежде всего развертываем выражение ХУ й Хйу по У. Получим (Х сЕУ) (ХУ й ХУ . Н числспис прсдик тоо кторов стутсси !сь Исключение самого внутреннего квантора дает (Х) (ХХ). Но выражение ХХ являешься общезначимым, поэтому формула (Х)(ЕУ) (ХУйХй У) истинна.
Проблема разрешнмосзн для узкого исчисления преднкатов в обоих ее пониманиях получает теперь свою символическую формулировку. Например, общезначимости (соответственно выполнимости) формулы (Ех) (У) (Р (х, х) ГУ Р (У, У) кос 0 (Х, У)) в некоторой области индивидуумов соответствует в расширенном исчислении справедливость формулы (р)(6)(Ех)(у)(р(х, х) гу Г(у, у) т/6(х, у)!, соответственно формулы: (ЕР) (ЕО) (Ех) (у) (Р (х х) ~/ Г (у, у) гу 6 (х, у)) дгся этой области.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
