Гильберт, Аккерман - Основы теоретической логики (947372), страница 25
Текст из файла (страница 25)
Далее, выполнима формула (х) 7 (х, х) й (х) (Еу) Е (х, у). Для ее выполнения достагочно взять в качестве области индивидуумов целые числа, а вместо Е(х, у) подставить преднкат х < у Невыполнима, например, формула (Ех) (у) (Р (х, х) й 7(х, у)), ибо ее отрицание (х) (Еу) (рш(х, х) 'чс Р (х, у)) есть тождествессная формула. Действительно, для со 148 угк«г исчисление прево«апов ПО»а.ылг р««ргтилисио каждого х существует у гребуемого рода, ибо мы можем взять у равным самому х. Проблеме разрешимости можно также дазь еше более строгую форлулировзсу. Некоторая формула, вообще выполнимая, не должна еще в силу этого быть выполнимой в каждой области индивидууиов. Например, форь«ула (Ех) (Еу) (Г(х) д«Р(у)), конечно, выполнима.
Достаточно только взять в качестве обласги индиан-уумов область, состоящую из Он 1, а в качестве поде»ановки для Р— преднкат «х=О». Существуют тогда х и у такие, что х=О и уч»О, именно О и 1. Однако эта формула невыполнима в области индивидуумов, состоящей из одного единственного элемента, так как предикат не л«ожет одновременно для одной и той же вещи выполняться и не выполняться.
Точио так же противоположная вышеупомянутой формула (х)(у) (Е (х) »у Р (у)) общезначима, если существует только один предмет в области инлиаидуумов; в против»юм же случае — нет. Если для формулы в некотсрьй области ни,ивидуумов имеет место выпглнимосзь или общезначимость, то то же самое имеет место и в каждой другой области нндиви-,уумов с тем же количественным (карли. нальным) числом их, как это легко получается с помощью взаимно-однозначного отображения областей друг на друга. Поэтому за исключением формул обще- значимых (соответственно выполнимых) в любой области индивидуумон, а также формул, ни для какай области не обладающих этим свойством, постулирование общезначимосгли (соотсетственно выполнимости) некоторой логиЧеск»й формулы яв)шется эквивалентнын высказызаншо о числе индивидуумов. Проблему разрешимссти можно считать решенной в самом в»ираком смысле, если имеется ме«ол, который для каж;ой данной формулы дает возможнощь решить вопрос: для каких обласп:ей индивидуумов она общезначима (соответственно выпошшма) и олл каких нет? с(то касается оси«шенин груг к другу обеих формулировок проблемы разрешимости, то уже в З 1О было получено на этот счет одно замечательное предложение.
Если некоторая формула обизезночима в счетнобесконсчной области, то оиа общезначима вообще и, следовательно, является тожсестеенной формулой, Сформулированное для выполнимости, шо предложение «ласило бы: Если некоторая формула вообще вмполннма, то выполнилосгпь имеет лести и в счетно-бесконечной области индивидуумов. В качестве (прав «а, значительно более тривиального) дополнения этого пре-ложенан мы имеем далее: Если некоп«орал фор.кула выполнила в кикой-нибудь области индивидуумов, то она вьнюлнил«а также в каждой области с большил«числом индивидуумов. Именно, определение предикатов, выполняющих формулу в некоторой области (1), легко можно так расширить, что выполнимость будет иметь песта и в области индиан "уумсв (1'), которая содержит (1) в качестве своей части.
)(ля мого мы выоираем из области (1) какой-либо злемегп а и распространяем определение предика«св на область (1'), рассматривая все элементы из (!'), котсрые не при«Ш"леэкат к (1), как тождественные с о. Например, если иы имеем предикат Ф с п пустыми местами, выполняющийся в области (!), то соответствующий предикат»р определяется в (1') следующим образо»»: для всех х„х„..., х„из (1') имев~ место: 'У(х„х„..., х„) — Ф(б„р„..., 1„). При этом г, тождественно с х, в том случае, когда х, принадлежит к (1); в противном случае оно равно а. Из способа, каким определены предикаты, получается затем — на чем ь«ы здесь не буде»» в деталях останавливаться — выполнимость в области (р Ь !ь! Поселено рвзраоочзпвк узкое оживление превнввтвв Для случая, когда область индивидуумов содержит опреде.енше конечное число индивидуумов, вопрос об общезначимсюти (соответстсенно выполнимости) всегда может быть решен.
В самом деле, .в этом случае знаки общности мо- !уг быть.заьгенены конечными конъюнкцнлми выска- зываний, а знаки существования †конечны дизъюнк- цинми высказываний, и вопрос об общезначимости (соответственно выполнимости) формулы в данной конечной области сводится к вопросу об общезначн- лшсти (соответственно выполнимости) некоторой фор- мулы исчисления нысназываний. Следующий пример сделает это более ясным. Пусть нужно исследовать вопрос о выполнимости формулы (Ех) (у) (р(х, х)й Р(х,у)) в области, состоящей нз двух элементов. Если мы обозначим элементы этой области через 0 и 1, то каж- дая формула вида (ех) "т((х) в этой области будет равнозначна с б((О) '.' сй(1), а каждая формула вида (х) б((х) — с М(0) 46(1). Поэтому нашу формулу можно заменить сначала формулой: (у) (е (о, о] й е (о, уй !х (у] (р П, Н й р' И, у)] и затем формулой: ( Г (О, 0) й Р (О, 0 ) й Е (О, 0) й 7 (О, )П !у (Р (1 Н й РП, О] й Е(1, 1]й Е(1,1]), После это~о вопрос сводится к такой замене Р(0, 0), Р(0, 1) и т.
д. нстиннымн и ложными высказывани- ями, при которой выражение в целом получило бы значение !истинною Другими словами, выполнимость формулы в области с двумя элементами сводится к выполнимосги формулы исчисления высказываний: (АЙЛйдйй] !/(Сй0йСйС]. Из последних предло>кении вытекает следующее: Гели для данной формулы удается показ!ты, что опо вообще может быть выполнена тогда и только тогда, когг)а имеет место выполнимость в некоторой области с определенным конечным числом А индивидуумов, то проблема выполнимости решена для всех областей ин!]ивадуумов. Ибо прежде всего мои!но установить, имеется лн выполнимость в области с й индивидуумами.
Если зто не имеет места, то формула пе выполнима ни в какой области. Если же ее можно выполнить в этой обла- сти, то это можно сделать и во всех областях с ббль- тим числом индивидуумов. Наи остается в таком случае исследовать еще только выполнимость в обла- стях с 1, 2,..., /с — 1 элементами, которую также мож- но установить. Отмегим тут же, что таким ооразом нельзя до- стичь общего решения проблемы разрешимости.Имен- но, существуют формулы, которые не выполнимы ни в какой конечной области индивидуу,чов, но выполни- мы в области с бесконечным числом элементов. К числу таких формул принадлежит, например: (х) (Еу) Е (х, у) бс (х] Е (х,х] гс (х) (у) (е] К Р (х, у) бс г" (у, з) — + Р (х, е)).
Эта формула выполняется, например, в области нату- ралывых чисел преднкатом х ( у. Напротив, допу- щение выполнимости в области с конечным числом индивндуумов сразу >ке приводит к прстиворечи!о. Допустим, что Ф вЂ” выполняющий предикат. В силу истинности (х) (Еу) Ф(х,у) в таком случае существо- вала бы сколь угодно продолжаемая цепь элементов а„ а„,а„ ... такая, что всегда имеет месса Ф (аь а,„). Но в силу предположенной конечности области инди- видуумов, при этом существооалн бы 1 и й (й'лИ такие, что а! и ак означают один и тот же элемент.
Из (х) (у] (е) (Ф!х,у) ее Ф(у, с) — +Ф(х, з)) мы получили бы тогда Ф (ап а;), между тем кан должно быть (х) Ф(х, х), Узкое исчислемие предакапзов 163 Проблеме Казрешамоста В то время как проблема разрешимости в исчислении высказываний легко решалась, например, путем использования конъюнктиансй или дизъюнктивной нормальной формы (ср. гл. 1, 9 б, а также гл. 1,3 8), проблема разрешимости в исчислении предикатов представляет собой очень трудную и в целом отнюдь не решенную проблему. Определенные причины, на которых мы подробнее остановимсл ниже, заставляют даже считать беанадежными попытки ее полного решения.
Но ввиду центрального зваченпл проблемы большой интерес представляют попытки дать решение хотя бы,,ля возможно более широких классов формул. Излдгаем важнейшие результаты, полученные в этом направлении. Во всех дальнейших рассмотрениях мы считаем, что все формулы, которыми мы оперируем, не содержат уже никаких свободных нредиетных переменных. Прежде чем пписгупить к рассмотрению частных случаев решения проблемы разрешимости, остановимся на некоторых предло енилх общего характера, кото. рые находятсл связи с проблев!ой разрешимости.
Некоторые нз этих предложений мы отметили узке в б 8! шпенна, предлолсения о лредварснлой нормальной (борз!с и нормальной гдормс Сколема. Они имеют то преимущество, что при рассмотрениях вопросов общезначимости или выполнимости формул последние можно представить в специальной нормированной или редуцированной форме без ущерба для общности рассиотрений. Поэтому говорят также о предлоаиелиях редукции. Например. предложение Сколема утпержрает (если мы сформулируем его здесь для 'выполнимости), что для каждой данной формулы исчисления предикатов можно указагь другую с приставкой в форме (х,).
( )(Еу,) . (Еу.), которая относительно выполнимости равнозначна первой. Мы можем поэтому при решении проблемы яыполнимости ограничиться формулами, приставки которых имеют указанную форму. Дальнейшие предложения этого рода относятся или тшоке к редуцированию формул к таковым с определенными приставками, или к редуцнрованию числа аргумен!ав у иче!ощихся предикатных переменных и т. д. Из многочисленных результатов в этом направлении мы упав!пнем только следу!ощие. Для каждой формулы можно указать равнозначную ей в отношении выполнимости, в которой встречаются талька одноместные и двуместные предикатные переменные'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
