Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 47
Текст из файла (страница 47)
По виду этих формул можно без труда сообразить, какой вид будут иметь соответствующие эквивалентности для любой фигурирующей вместо переменных а, Ь и с последовательности переменных, например для а, Ь, . Этим эквивалентностям мы дадим номера 10а)) и 10Ь)). Применим к ним следующие специальные преобразования. Возьмем какую-нибудь из формул 10а)) и подставим в нее вместо именной формы А (г) формулу А (г) & г7 А (г). Возникшая таким образом формула теперь может быть существенно упрощена. Мы рассмотрим этот вопрос на имеющемся у нас частном случае формулы 10а)). В левой части этой формулы (после выполнения подстановки) в качестве дизъюнктивного члена будет стоять А (х) & 1 А (х). Однако по правилам исчисления высказываний [в сочетан сп равилом (г[) )) этот дизъюнктивный член может быть опущен. ии В правой части вместо зхА (х) мы получаем выражение ~х (А (х) & Ч А (х)), которое может быть преобразовано в отрицание выводимой фомулы о ои ор- Зх ( 1 А (х) ~/ А (х)), 1) Сы.
с. 177, и потому этот член диаъюнкции можно будет убрать с помощью схемы заключения. Вместо 1А(а), 1А(Ь), ~А(с) в результате подстановки появятся выводимые формулы 7 А (а) ~/ А(а), 7 А(Ь) ~/А(Ь), 1А(с) ~/ А(с), которые также могут быть опущены в конъюнкциях. Далее, в выражениях 'УгхА (х), згхА (х), )/,хА (х) дизъюнктивные члены, содержащие формульную переменную А, в результате подстановки также перейдут в такие члены, которые можно будет удалить, применяя правила исчисления высказываний и правило (7)); поэтому на месте указанных выражений останутся только формулы 'чх уу (х = у), чх чу Чг (х = у ~/ х = г ~/ у = г), 1ух чу чгзи(х=у ~/ х=г ~/ х=и ~/ у=г ~/ у=и ~/ г=и).
Для формул этого типа мы также введем специальные сокращенные обоаначения. Пусть 7х7У(х=У) (ДлЯ 1=2, 3, ...) означает формулу с приставкой из 1 кванторов всеобщности, за которой следует дизъюнкция, состоящая из равенств между всевозможными парами различных переменных, связываемых 7(7 — О г этими кванторами (таких пар будет — ) .
2 ) Указанная формула вполне этим определяется, если отвлечься от обозначений связанных переменных. Будучи истолкована содержательно, она говорит о том, что в индивидной области имеется не более 1 — 1 индивида. После выполнения подстановки и указанных преобразований рассматриваемая нами эквивалентность с использованием нового обозначения приобретает следующий простой внд: 'эх (х = а ~/ х = Ь ~/ х = с)- ( э хгу (х = у) ~/ ((а ~Ь7 ~/ а ~ с ~/ Ь ~ с) & 'зхгу (х = у)) ~/ (а ~ Ь & а ~ с & Ъ ~ с & 7хгу (х = у))). Введем теперь обозначение Зх7У (х Ф'У) РАСШИРЕННЫЙ ФОРМАЛИЗМ 225 224 исчисление,пРеднкАТОВ с РАвенством !Гл.
ч для той формулы, которая получится из Чхгу (х = у), если мы возьмем (по правилу (2,)) ее отрицание. Тогда формула, двойственная по отношению к только что написанной, будет иметь вид Зх (х ~ а 8з х Ф Ь !й х 'Ф е) (ах!у(хф у) 8з((а Ь8за=с8з,'б е) !/ лхзу(х ~ у)) 8 (а=б !/ а=с ~/ Ь=е '!/ Зхзу(х т=у))) Если использовать формулы !!/Хзу(х=у) — «Чхз у(х=у), которые легко могут быть выведены для любого заданного числа 1, то обе полученные нами формулы с помощью преобразований исчисления высказываний могут быть переведены в следующий, более подходящий для содержательного осмысливания вид: 'эх (х = а ~/ х = Ь ~/ х = е) ('з хзу (х = у) 8з (а = Ь ~/ а = е 'з/ Ь = с -з- 'ч хзу (х = у)) 8з (а=б8за=с8зб=е — 'чхзу(х У)))з Эх (х ~ а !й х чь Ь 8з х Ф с) (лх у (х чь у) 8з (а чь Ь \/ а чь е ~/ Ь ть с — !- Зхзу (х чь У)) 8з (а -й Ь А а Ф с 8з Ь Ф е — «Лхзу (х Ф У))) С формальной стороны, в этих эквивалентностях достойна внимания выраженная ими переводимость формулы 'э!х (х = а !/ х = Ь )/ х = е) (или формулы Зх(ХФа8зхчь Ь8зх~с)) в такую формулу, которая получается с помощью свяаок исчисления высказываний из равенств а=Ь, а=с, Ь=е и формул Чхзу (х = У), ухзУ (х = У), ух!У (х = У) (соответственно формул Зхзу (х чь у), Эхзу (х ~ у), Зхзу (х ~ у)) ° Заметим, что в последних иа названных здесь формул свободные переменные а, Ь, с больше уже не встреча!отея.
И вообще, этот способ показывает, каким образом из формул 10а)) и 10Ь)) путем подстановки А (г) 8з 1А (г) вместо именной формы А (г) и упрощающих преобразований, выполняемых в рамках исчисления предикатов и направленных на исключение формульной переменной А, получается переводимость формулы ззх (х = а з/ х = д '!/... ~/ х = г) (соответственно формулы Зх (х ~ а 8з х ~ Ь 8з... 8з х чЬ г) ) в такую формулу, которая при помощи связок исчисления высказываний строится ив равенств между парами свободных переменных и формул чхзу(х=у) Мхзу(х=у), .*., 7Х!+зу(х=у) (соответственно формул. Зхзу(хФУ) Пхзу(хч" У)1 ° °" ах~+!у(ХФУ))з здесь 1 означает число переменных а, Ь,..., г.
Заметим также, что формула Зх!у (х ~ у) с точки зрения содержательного ее истолкования говорит о том, что в индивидной области содержится не менее 1 индивидов. Таким образом, если формула Ух!У (х = у), будучи истолкована содержательно, указывает максимальное число индивидов в рас- сматриваемой индиввдной области, то формула ах!у (х чь у) указывает минимальное их число.
Формулы вида УХГУ (х = у) и Эх!у (х ~ у) мы будем называть общим именем каличеппвеннмх формул. Рассматриваемые преобразования мы вывели из эквивалент- ностей 10а)) и 10Ь)) в результате специально подобранной под- становки вместо формульной переменной. Если же мы рассмотрим подстановку какой-нибудь произвольной формулы Я (г) вместо А (г), то из эквивалентностей 10а)) и 10Ь)) непосредственно полу- чится переводимость формулы 'эх (х = а !/ х = Ь 'з/ ...
~/ х = г ~/ Я (х)) (соответственно формулы Зх (х ~ а 8з х ~ Ь 8з... 8з х чь г 'л Я (х))) в некоторую формулу, получаюшуюся с помощью связок исчисле- ния высказываний, во-первых, иа формул Я(а), Я(Ь), ..., Я(з'), !5 д. гззьгзрт, п. верэаае 226 исчислннин пРБдикАтов с РАэвнством 1гл Р РАСШИРБННЫЙ ФОРМАЛИЗМ 227 во-вторых, из — равенств между всевозможными парами й1 — О свободных переменных а, Ь,..., г и, в-третьих, из формул Аух Я (х), 'Угх Я (х), ..., 71~,х Я (х) (соответственно формул ЗхЯ(х), ЭзхЯ(х), ..., 31 хЯ(х)). Эффект этого преобразования в случае формулы Я (г), не содержащей ни одной из переменных а, Ь,..., г, состоит в том, что в результате перевода эти свободные переменные в области действия какого-либо квантора всеобщности или существования больше уже не встречаются.
В частности, если Я (г) вообще не содержит никаких свободных индивидпых переменных, кроме», то в выражениях )))хЯ (х) ° Ч1+!х Я (х) 3х Я (х), ..., 31+!х Я (х) не будет никаких свободных переменных. 3. Разложение в примарные формулы для формул расширенного одноместного исчисления предикатов. Наличие таких преобразований приводит нас к воэмон<ности построения некоторой нормальной формы для формул расширенного одномесшного исчисления предика»пав, т. е.
того формализма, который получается из одноместного исчисления предикатов в результате дополнительного присоединения знака равенства и свяаанных с ним аксиом. Основываясь на правилах этого исчисления, всякую его формулу можно будет разложить, подобно формулам одноместного исчисления нредикатов, в «примарные формулы» (теперь уже в некотором обобщенном смысле); при этом под рак«огкениег« е примарные )берг«уяы мы будем понимать перевод данной формулы в такую, которая строится с помощью связок исчисления высказываний из составных частей следующего типа: 1.
Формульные переменные без аргументов. 2. Формульные переменные с одной свободной индивидной переменной в качестве аргумента. 3. Равенства между свободными индивидными переменными. 4. Формулы вида »!х З (х) или Зх л (х), где л! (х) обозначает некоторую дизъюнкцию, а Й (х) — конъюнкцию, члены которых являются или формульными перемениымн с аргументом х, или их отрицаниями.
5. Формулы вида !Умхй (х) или Зкхй (х), где % (х) и Й (х) обладают свойствами, указанными в и. 4 6. Количественные формулы, т. е. формулы вида З'хку (х = У) или ЗхмУ (х ~ У). Отличие от обыкновенного одноместного исчисления предикатов проявляется в том, что здесь добавляются пп. 3, 5 и 6, связанные с равенством, Процедура разложения произвольной ааданной формулы расширенного одноместного исчисления предикатов в примарные формулы аналогична процедуре, применяемой в обычном одноместном исчислении предикатов. Если исходная формула никаких связанных переменных не содержит, то она уже имеет необходимый вид.
Таким образом, остается рассмотреть только случай ! когда в формуле имеются связанные переменные. В атом случае мы сначала переведем исходную формулу в какую-либо предваренную. С помощью переименования связанных переменных мы всегда сможем добиться того, чтобы последний из кванторов, стоящих перед формулой, связывал переменную х и, значит, был квантором )7х или 3х. Остальные кванторы, если они имеются, пусть относятся к переменным У,г,...,и. Выражение, стоящее эа квантором»!х или Вх, кроме связанных переменных у, г,..., и может, вообще говоря, содержать еще и свободные переменные. Согласно правилу («)) !), к атому выражению можно применять преобразования исчисления высказываний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
