Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 44
Текст из файла (страница 44)
В рассматриваемом нами примере формулы 'УхЗуЧзЗВЯ (х, у, з,и) квантору существования Зи ставится в соответствие формульная переменная В с тремя аргументами, квантору всеобщности уз— переменная С с двумя аргументами н квантору существования 3у — переменная Р с одним аргументом. Однако обычно хватает меньшего числа формульных перемен- ных; действительно, не изменяя нашей процедуры в остальном, можно объединить в одно целое последовательность кванторов су- ществования с одним квантором всеобщности, следующим за ними, и такой группе кванторов достаточно будет поставить в соответ- ствие всего лишь одну формульную переменную.
Так, при рассмотрении формулы 'Рх Зу Чз Зи Я (х, у, з, и) можно сэкономить одну формульную переменную, сопоставив последовательности Зу 1(з только одну переменную. Это значит, что в качестве формулы, дедуктивно равной нашей исходной, мы можем взять формулу )7х)7у7з(ЗВЯ (х, у, з, и)-эВ(х,у, з)) & Ух (Зу '7з В (х, у, г) -+-С (х)) — э.'Фх С (х), преобразование которой дает нормальную дизъюнкцию ЗхЗуЗзЗи(Я (х, у, з, и) & ~В(х, у, г)) 1/ ЗхЗуЧз(В(х, у, г) & 7С(х)) 1/ 'ухС(х).
Подобным же образом для формулы ЗхМуЗВЧиЧРЯ (х, у, з, и, Р), в которой не встречаются формульные переменные В и С (с аргу- ментами), мы получим дедуктивно равную ей формулу Чх'уу'Р'зуи(РРЯ(х, у, з, и, и)-+В(х, у, з, и)) & 7(хуу(3гМВВ(х, у, з, и)-~-С(х, у))-1-3х17уС(х, у), )гл. рч исчислкнин прндиклтов 208 ГЛАВА У которая может быть переведена в нормальную дизыонкцию ЭхЭуЭгЭиУо(Я (х, у, г, и, о) А )В(х, у, г, и)) ~ ЭхЭуЭгУи(В(х, у, г, и)д«)С(х, у)) ~/ ЭФ(уС(х, у). Если же стремиться получить не нормальную дизъюнкцию, а сколемовскую нормальную форму, то можно добиться и более существенных сокращений; в этом случае можно оставить нерасчлененной любую последовательность кванторов существования с несколькими следующими аа ней кванторами всеобщности. Так, например, в только что рассмотренном случае формулы ЭхчуЭг'эи1«о«й ',х, у, г, и„о) мы можем оставить нерасчлененной последовательность ЭМи)«о, т.
е. ей достаточно будет поставить в соответствие всего лишь одну формульную переменную. В самом деле, указанная формула дедуктивно равна формуле 'эх'эу(Эг1эиэнЯ (х, у, г, и, о) — ьВ(х, у))-ьЭхчуВ(х, у), а получающаяся из последней преобразованием формула ЭхЭуЭгрйчо(Я (х, у, г, и, о) А'чВ(х, у)) )( ЭхЧуВ(х, у) хотя и не является нормальной дизъюнкцией (из-за наличия двух кванторов всеобщности в первом члене дизъюнкции), но все же ее можно перевести в сколемовскую нормальную форму, а именно в формулу ЭхЭуЭгчи1«опт((Я(х, у, г, и, о) дс 1В(х, у)) ~/ В(х, т)).
Иэ методических соображений следует подчеркнуть, что испо льзование формульных переменных лежит в самом существе тео ремы Сколема. На атом мы пока что закончим формальное рассмотрение исчисления предикатов. За нами остается долг — два обещанных в дальнейшем доказательства: во-первых, доказательство того, что всякая формула одноместного исчисления предикатов, тождественная в конечном, является выводимой, и, во-вторых, доказательство того, что формулы )5, К«), и )ф'), относительно которых мы установили, что они тождественны в конечном, не являются выводимыми.
В связи с упомянутой теоремой об одноместном исчислении предикатов мы обсудим вопрос и о проблеме разрешимости для этого исчисления. Однако прежде полезно будет дополнить формализацию про цесса вывода в двух направлениях, а именно — в отношении поня тия равенства и в отношении использования наряду с предикатными символами знаков для математических функций '). ') См. с. 162 и далее. ») См. с.
235. ИСЧИСЛЕНИЕ ПРЕДИКАТОВ С РАВЕНСТВОМ. ПОЛНОТА ОДНОМЕСТНОГО ИСЧИСЛЕНИИ ПРЕДИКАТОВ й 1. Расширенный формализм 1. Знак равенства; изображение высказываний о количестве; аксиомы равенства и формальные свойства равенства. Равенство, которое мы в речевом обиходе выражаем фразами типа «а представляет собой тот же самый объект, что н Ь», при внешнем рассмотрении имеет вид предиката с двумя субъектами. Но по содержанию оно соответствует чему-то такому, что в известном смысле предшествует определению какого бы то ни было предиката, а именно — возможности различения элементов индивидной области. Во всяком случае, так это выглядит с той точки зрения, которой мы придерживаемся в аксиоматических теориях, а также в теоретико-множественной логике предикатов.
В любой аксиоматической теории основные грамматические конструкции связываются с одной или несколькими системами объектов, внутри которых различение индивидов предполагается имеющимся с самого начала. Такому воззрению соответствует и тот факт, что в этих теориях равенство, как и его антипод — различие, обычно не фигурирует среди основных отношений, подлежащих неявной характеризацни при помощи аксиом (речь идет о таких, например, отношениях, как отношения принадлежности, порядка и конгруэнтности в геометрии), а используется как некоторое понятие содержательной логики. Теперь, чтобы учесть, с одной стороны, лингвистическую форму высказываний о равенстве, а с другой стороны, их особый содержательный характер, мы рассмотрим равенство как некоторый выделенный по отношению к логике основной предикат.
Определенная формализация равенства в нашем распоряжении имеется уже благодаря возможности идентификации переменных. Так, например, формула ~((а, а) выражает тот факт, что отношение ~ не имеет места междуобъектом а и им же самим. Однако этого нам не хватит уже, например, в том случае, если мы захотим воспроизвести предложение «если а не меньше Ь, а Ь не меньше а, то а представляет собой тот же самый объект, что и Ь». )4 Д. Гмльберт, и. Берпае« РАСШИРЕННЫИ ФОРМАЛИЗМ 21) ИСЧИСЛЕНИЕ ПРЕДИКАТОВ С РАВЕНСТВОМ 2)О Мы ведем для равенства специальный предикатный символ. в В качестве этого символа мы возьмем — поскольку у нас нет ричин отличать данное равенство от «равенства» арифметического— обычный знак' равенства (а равно Ь).
а =Ь Прежде всего, к этому символу будет применимо правило подстановки, т. е. выражение а =Ь мы сможем подставлять вместо любой формульнои переменнои г ментами а и Ь. В прочих отношениях роль знака равенства в нашем формализме будет определяться следу щ д у аксиомами равенства: (о,) а=а, (о «) а = Ь -» (А (а) -» А (Ь)), которые в процессе вывода можно будет использовать в качестве Отрицание равенства есть р а з л и ч и е. В дальнейшем мы будем пользоваться обычным знаком различия, применяя его, однако, лишь как сокращение для отрицания равенства г). Таким образом, мы соглашаемся, что Вместо )Ка = Ь) всегда можно будет писать а -ь Ь и наоборот. В тесной свяаи с понятиями равенства и различия находятся укладывающиеся в элементарные рамки представления о количестве, и в результате введения знака равенства мы получаем средства для формального изображения этих представлений. В частности, с помощью знака равенства мы сможем формулировать условия, выражающие ие количество элементов в той индивидной области, к которой относятся связанные иедивидные переменные.
Так, формула, 'Ух)7у (х = У) выражает высказывание о том, что в индивидной области имеется только один элемент. Точно так же.формула чхЧУ)гг(х=у ~/ х=г ~/ у=г) ь) С этны соглашвнкем мы уже встречались в гл. 1; сы, . 2 . , с. 27. выражает (при содержательном ее понимании) тот факт, что в индивидной области имеется самое большее два элемента, а формула лх Эу (х ~ у) говорит о том, что их имеется по меньшей лере два Аналогичным же образом посредством специальной формулы, не содержащей форм ульных переменных н имеющей в качестве единственного предикатного символа знак равенства, может быть выражена любая наперед заданная конечная верхняя и нижняя оценка числа элементов в рассматриваемой индивидной области.
Эти формулы являются более простыми и элементарными,чем те, которые были использованы Фреге и Расселом для логического определения конкретных конечных чисел, т. е. чем формулы, выражающие 1-численность, 2-численность и т. д. одноместных првдикатов г). 1-численность одноместного предиката Р (а) выражается посредством формулы Вх чу (Р (у) х = у) («существует элемент х такой, что Р выполняется для у тогда и только тогда, когда х представляет собой тот же самый элемент, что и у»). 2-численность предиката Р (а) изображается формулой ВхЭУ(хФУАМг(Р(г) г=х)/ г=у)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
