Гильберт, Аккерман - Основы теоретической логики (947372), страница 28

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 28)

При ингерпретации лосических формул мы всегда можем положить в основу формулы, не содержащие вообще никаких свободных переменных. Действительно, в каждой формуле со свободнымн переменными можно устранить последние, поставив впереди формулы соответствующие знаки общности. Поэтому в исчислении второй ступени не может быть и речи об общезначимости нли выполнимости формул в прежнем смысле. Все же при помощи одной только символики смысл формул еще не устанавливается однозначно, так как мы еще не знаем, какая область индивидуумов должна быть положена в основу. Например, формула (Е Г) (Ех) (Еу) (г (х) й Е (У)) еырансает ложное высказывание, если область нндивидуумов состоит только яз одного элемента; во всех же остальных сл>чаях она представляет истйнное высказывание, Рес>иинснн>с и>киске нс срейикннтк ка >от Иск лс не и 'с>> клт к к нркй лтуисни Под твэссдестсе>>ныли фвр,иулилси исчисления иы беден теперь понимать формулы.

которые при произвольном выборе аоластн индивидуумов предсгавлякп истинные высказывания. Если угодно, можно гавсрить также сб общезначимых формулах, причем, однако, общезначимость о.гносится только к сблас>ям индивидуумов. Соответсгвеншч можно называть выполнимыми >е формулы, для которых вообще существу>от области индивидуумов, но отношению к когорыи эти формулы выражают истинное высказывание. Обгпезпочнмссть некоторой формулы и здесь всегда равнозначна с невыполнимостью формулы.

снабженной чертой отрипания. К тождественньщ формулам относятся все тождественные формулы узкого исчисления предикатов, а также н другие. Если знак .=-!х, у) предо>авляет, как и ранее, сокращение для (Е)(Р(х) Е(у)), т, е. для предиката тождес ва, .то формулы (х) =..(х, х); (х)(у) (= — (х, у) †> = (у, х)) являются тождествепнымн. Дальнейшими примерами являются (ЕГ) (Ех) Г (х); (Е) (Е6) (х) (у) (!' (х.

у) >у 6 (х, у)), К выполнимым форе>улан прьп>адлежат все формулы, которые получаются нз пьпюлпимых формул узкого исчисления преднкатов, если поставить впереди соответствующие знаки существования для предикатав; однако этими фн>рмулами не исчерпывается совокупность выполнимых фаре>ул.

Например„ (Р) ((Ех) Е (х) — (х) Р (х)) .аюке является выполнимой формулой. Естественным следующии вопрссоп был бы: нельзя лн и здесь, подобно тому. как:гго сделано в исчислении предикатсв нерпой ступени, указать систему логических основных формул, из которой все другие тождественные формуль> получались бы и резулшате Последовательных действий пп ппредслсншлл> правилам. Заметим >ут же, ч>о петлей систв.иы охси>м для твмс дсстсенних флриул исчисле >ия предикотее второй ступени нс суи)еств) ет. Б лес того, как п1 казал К. Гедель, для любой системе> основных формул и правил пывада можно указать тоясдествеааые фориулы, которые не могут быть выведены'. Все же для большинства возникающих задач можно считать достаточной следуюшу>о систему. Прежде всего мы берем все основные формулы и правила вывода узко~о исчисления предикатсв, причем в отношении правил выводе пушно иметь в виду, чта понятие формулы теперь расширено.

К основной формуле е) мы можем присоединить любо~ число основных формул вида (Р) с)((Е) н т)((6). При этом М (Р) есть дк>рл>ула, которая содержит свободный переменный предикат Е и не содержит 0; п((6> — формула, которая получлется из й((Е;,, если по пр>вилу из) подставить 6 вместо Е в бюрмулу сй(Г). Можно также присоединить в качестве основных любое число фор>еел вида т( (6) — н (ЕР) и (Е). К этому грисоединяются еще основные ф.рмулы, которые тесно связаны с аксиой>ой выбора теории иножеств.

Первая из этих формул ость е) (ЕР) ((х) [ Еу! 6 (х, у) — к','Еу> (Р (х,у', й 6;.Х,У;) сс (х) (у) (с) [сЕ(х, у) й Р(х, с) — > = — (У, з)П. Смысл этой форе>улы зтключаетсч в следующем. Предикат 0(х, у) тем х, для которых вообще сгществ ет у со свойством 6(х, у), приводит в соответствие некоторые значения у. Ноева основная формул.> высказывает, что для каждого х можно выбрать адно ' свен к., Оьег ганне> ипепскспе>оьаге зшсе аес рс>пс>р>е мосье>пенсе ипа неспкпшег зуме>пе. ма.

месь. рауенс. пе. зо 0931). 1Ео Ысчпсаепие преспатпвв втарва ппрпенп 1ЕЭ Раппвршсте псвисвепие преэпватав нз приведенных ему в соответствие значений таким образом, что соответствие будет однозначным. Р выражает такое однозначное соответствие. Пусть, далее, т (х, Р(, )) †форму, содержащая свободное предметное переменное х и свободный переменный предикат Р с л пустыми местами. Пусть 2((х, 6(х, ...)) означает формулу, которая получается из % (х, Р(...)) в результате замены, по правилу и3), каждой части Р (о„ав, ..., а„) нашего выражения на О (х, оп о,..

. о„), перинам О обозначает переменную с я+1 пустыми местами. Тогда мы можем принять в качестве основной и формулу Ь) (х)(ЕР]сд(х, Р(...)) — в(ЕО)(х) й (х, 6(х,...)). Истинность этой формулы мы можем усмотреть следующим образом. Если для каждого х существует Р такое, что выполняется 2((х, Р(...)), то' мы можем дяя каждого х выбрать одно из этих Р, которое мы обозначим р . Если мы теперь определим О так, что выполняется (х)(у,)(у,)...

(у„) (6(х, у„...,'у„) Е"(у„..., у„)), то получим О вида, постулированного основной формулой Ь). Правила вывода остаются теми же самыми, что и правила узкого исчнсленшс предикатов; только теперь правила Т !), у2),З) следует так расширить, чтобы они относияись также н к переиенным предикатам. Из этой системы получается (на чем мы здесь не будем подробно останавливаться), что резуяьтаты, которые мы прежде вывели для узкого исчисления предикатов, могут быть, в соответствии со смыслом, распространены и на новые формулы. Например, предложение о предваренной нормальной форме, принцип двойственности, предложение об образовании противоположности для формулы остаются и теперь истинными. Точно так же каждой формуле узкого исчисления предикагов, которая содержит индивиду- альные переменные, можно привести в соответствие класс формул, в которых содержатся переменные предикаты.

Например, тому факту, что (х) (Р(х) — + 6(х)) — в «Ех) Р(х) — а(Ех) 6(х)) Кюрмула (34)) была выводимой формулой, теперь соответствует выводимость каждой формулы вида (Р)(й(Р)- Ю(Р))- «ЕЕ)!й(Е)- (ЕР) В(Р)). Для вынода достаточно только повторитьп с соответствующим видоизменением, доказательство формулы (34). То же самое относится и ко всем другим формулам узкого исчисления предикатов.

Под прсбпенсй разрешимости второй ступени мы понимаем проблему: для данной формулы исчисления, решить вопрос, представляет ли она тождественную формулу илп нет. При более строгой формулировке следовало бы решить, для каких областей индивидуумов формула выражает истинное высказывание и для каких нет. Так как проблема разрешимости второй ступени включает в себя такую же проблему первой ступени, то не приходится и думать об общем решении проблемы разрешспсости второй ступени. Единственный важный частный результат заключается в том (если не говорить о случаях, которые относятся к области узкого исчисления нредикатов и были там решены), что решение удалось провести полностью для области формул, которые содержат только адповсесшяьсе предикаты.

Доказательство этого приведено в работах Левенгеймо, Околела и Ермака, упомянуть1х уже в б )2 предыдущей главы. при этом респение проблемы разрешимости получено в от рогом смысле. Что касается подробного изложения разрешающего алгоритма, мы укажем на особенно ясно построенную работу Бемана. Здесь же ограни. чимся краткой характеристикой использованного метода. Решение проблемы разрешимости в области одноместных предикатов основано на решении про. блемы исключения для этой области. Под проблемой $70 рагюиренн и иэшг»»ни» ерша,» г»» Ишиг»ение ар»диасам»»м»р»и стул»ли !7! нсклкченпя мы попвмаем вооба;е следуюн ее. Пусть дана формула 2! (Г, 6„, ..., О„„х„..., х ), которая, кремс сгобэдных переменных предикатон Р, 0„...,6,„ и кроме св бодяых индивидуальных переменных х„ х,, х, содержит еде, быть ивкет, связанные пнднвидуальныс перемснныс, но пе содержит связанных переменных прели!гатов. Мы спэа»ннвасм.

нельзя ли указать формулу»В (О„..., О„„х„..., х,), также не содержащую связанных переменных предикатов, такую что (Р) 2! (Е, 6„,, Ом, х„., х») 5(Оо ...,6,„, хо ..., х!) илн, что означает то >ке самое: (ЕЕ) Ф (Е,Оп...,6,„, т„..., х!) 'ю (6„..., 6„, х„., х,) является тождественной формулой второй ступени. Если зто имеет место, то в каждой фор»гуле иожно составншо часть: (Е] З»! (Р, 6„, о„„х, х»). соответственно (ЕЕ) а (Г, 61... О„„х„. х,). заменять на 6 (0„...,0„, х„..., х,), соответственно на ю(6„..., О„„х„...,х,). Та!сим образом, мы можем переменный предика! Е исключить из подобного рода формулы. Отношение этого к проблеме рззрсшимссти вполне понятно. Если я име!о формулу исчисления предикатсв, для которой мпс нужно найти решение, то я, прежде всего, уничтожаю саободныс псремснные преднкаты, номе цая в начале формулы соответствуюн;ие знаки об-!ности, н могу затем, если предположить проблему исключения решенной, исключить переменные преднкаты один за другии, начиная с внутреннего, так что н качестве окончательного результата я получаю либо значение»истинно» нли»ложно», либо же наложенное на область индивидууишв числ=вое усл вие.

Редудиров .нне формул путем исключения станет понятнее на примере формуты (Г) г(Ех) Г(х) о' (ЕО) [(х)(0(х) ти(х)) В(х) 0(х))). Преждс всего иы замечаем, что формула (ЕЕ) (х) (А О ) !уЕ(х) й В (х)' у Ет(х)) (х) (Л (х)»у В (х)), со!)ержаа;ая один из основных результат!в, относя- п»нхся к исключению, является тождественной фор- мулой, так как левую часть этой эквивалентности можно преобразовать в (ЕЕ) (х) ((Р (х) = А (х)) й (Е(х) — » В (х))). Используя эту ![ормулу, мы можем в нашей исходной фориуле исключить переменный прсдикат 6.

И»»евно, мы можем составную часть фориулы, образующую область действия для (ЕО), (х)(6(х) Ё(х))й(х) 6(х) [формула (29), гл. 1, 4 2; формула 30, гл. !И, [ б[, заменить на (. )(6(..) ~/Р(х) Й 0(х) тГ Г(х) й О(х)) или же на (х)(6(х) й Р(х) ту 6',х)) и дальше на (х) [(Е(х) б Р(х)) т/6(х) й Е (х)г/6(х)[. С!шласно вышеупомянутой основной формуле иск!печения, имеем (ЕО) (х) [(Е(х) а Р(х))тгО(.) Л Р(х)НО(. и(х) [(Г (х) й Г(х)) ту Е (х)]. йы)гажснис (х) [(Е (х) В !.

(х)) (г Е (х)[ 1тз В>соснов ореоосотое >т оредосотее лг Росторекное и е слепое орсо>>есме в последней формуле можно заменить на (х)Р(х). Таким образом, наша исходная формула (Р) [(Ех) Р (х) >/ (Е6) [(х) (6 (х) Р (х)) В (х) 6 (х)]) после исключения переменного предиката 6 переходит в (Р) ((Ех) Р(х) )/(х) Р(хД. Из агой формулы, у которой область действия кван- тора 1Р) имеет форму >д 'ьс 9(, непосредственно видно, что наша исходная формула является тождественной.

Характеристики

Список файлов книги