Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 46

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

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

е., в подробной записи, к выводу формул А (а) & 7х (х ~ а — »- А (х)) « "эх А (х), 7х (х ~ а-+ А (х))-1 Чх "ч'у (х чь у-«А (х) 1/ А (у)), ~х А (х) -«)/х (х ~ а — «А (х)), )/хну(х~у-«А(х) 1/ А (р))-«чх(х~ а-«А(х)) )/ А(а). Из этих формул две последние легко могут быть получены средствамн исчисления предикатов. Действительно, третья формула получается в результате подстановки из следующей, легко выводимой формулы:( 1/х А (х) -»- Ух (В (х) -«А (х)), а четвертая применением правила («) ') и тождественной формулы (А -« В) ~/ С (А -» В 1/ С) (в сочетании с правилом (7)) »)) может быть преобразована в формулу )7х)7у (х ~ у — «А (х) )/ А (у)) -»- 'эх (х Ф а-«А (х) )/ А (а) ), которая получается подстановкой из выводимой формулы )/хчуВ(х, у)-«)/хВ(х, а). Что касается вывода первых двух формул, то он протекает с существенным использованием формул для равенства. Первая из них с помощью формулы ба',,) переводится в формулу эх (х = а -» А (х)) & эх (х ~ а -«А (х)) -« '«х А (х), которая получается в результате подстановки иэ выводимой в исчислении предикатов формулы 1/х(В(х) — «А(х)) &7х( 1В(х)-«А(х))«7хА(х).

Вторая формула 'эх (х ~= а -» А (х)) -«7х 17р (х ~ у -» А (х) )/ А (у)) может быть выведена по правилам исчисления предикатов из формулы (Ь~ а — «А (Ь)) &(счьа-».А (с))-«(ЬЧА с-«А (Ь) 1/ А (с)), а вывод этой формулы можно средствами исчисления выска- зываний свести к выводу формулы Ь~с — «Ьчьа )/ с~а. Но эта последняя получается подстановкой из формулы 5)).

Из формул 7а)) и 7Ь)) мы можем получить еще две замечательные формулы. Если в формуле 7а)) переименовать переменную у в з, а х в р и затем применить правило (б') для квантора существования ») См. с. 179. «) См. с. 177. мз ИСЧИСЛЕНИЕ ПРЕДИКАТОВ С РАВЕНСТВОМ 1гл. ч в сочетании с правилом (~), то получится формула Зх 7у (у чь х -«А (у) (ЧуА(у) ~/(Зх ~А(х)8~'УуУЗ(учьз-«А(у) ~/А(г)))).

В правой части этой эквивалентности мы можем снова переименовать у в хи з в у; кроме того, Зх ~ А (х) мы мол~ем преобразовать в ~ Ух А (х). Полученную таким образом формулу мы можем, применяя уже использованные ранее обозначения В и З, представить в виде Зх ~у (у Ф х -«А (у)) (В ~/ ( 1В Й 'Э)).

По правилам исчисления высказываний, В ~/ ( ~ВАЗ) можно заменить формулой В ~/ З. Далее, мы установили, что формулы являются выводимыми формулами. Следовательно, выводима и формула  — «З, а потому В ~/ З переводима в З. Тем самым мы получаем формулу ЗхМу(у~ х — «А (у)) ° З, т. е. 8а)) Зх уу (у Ф х — А (у)) - ух уу (х чь у — «А (х) ~/ А (у)). Тем же самым способом, каким мы перешли от 7а)) к 7Ь)), мы, исходя из 8а)), получим формулу 8Ь)) УхЗу(у~ хйА(у)) ЗхЗу(х~уЬА(х)АА(у)).

Значение этих формул заключается в том, что с их помощью могут быть переведены друг в друга различные представления условий, налагаемых на количество элементов в индивидной области. В самом деле, обе части эквивалентности 8а)) соответствуют высказыванию о том, что имеется не более одного индивида со свойством ~ А, а обе части 8Ь)) — высказыванию о том, что имеется не менее двух индивидов со свойством А. Совершенно аналогичные преобразования могут быть произведены и для большего числа индивидов. Схема формул, представляющих собой обобщения формул 8а)) и 8Ь)) на случай боль- РАСШИРЕННЫИ ФОРМАЛИЗМ 219 щего числа индивидов, выглядит следующим образом: 9а)) ЗхЗу ...

ЗОЪ'й(й~х8 йФу ... Айчьи-«А(й)) Г/хт/у... 'УхУй(х~уйх~зй ... 8 и~ й — « А(х) ~/ А(у) ~/ ° .. ~/ А(й)), 9Ь)) УхУу ... ЪЪЗй(й~хйй~уй ... Ай~и ВА(й)) ЗхЗу ... ЗРЗй(х~у %х~зй ... Аи~ й8~ А(х) 8 А(у) А .. АА(и)). Здесь в левых частях эквивалентностей вместо одной фигурирующей в формулах 8а)) и 8Ь)) переменной х, которая в 8а)) связывалась квантором существования, а в 8Ь)) — квантором всеобщности, появились переменные У~ ° которые в 9а)) связаны кванторами существования, а в 9Ь))— кванторами всеобщности и на которые распространяется коньюнкция В правых частях этих эквивалентностей вместо двух фигурирую- щих в формулах 8а)) и 8Ь)) нврвменных х и у стоят переменные х,у...и,й, ! связанные в 9а)) кванторами всеобщности, а в 9Ь)) — кванторами существования; на эти переменные в 9а)) распространяется дизьюнкция А(х) ~/А(у) ~/...

~/А(и) ~/А(й), В 9Ь)) — конъюнкция А (х) Ь А (у) Ь... Ь А (и) А А (й), и в 9а)) и 9Ь)) конъюнкция х~у Ах~г8~... А и ~ й распространяется на пары, состоящие из двух различных между собой переменных х, у,..., и, й. Кроме того, в формулах 9а)) импликации можно превратить в дизъюнкцни; тогда мы получим формулы Зх Зу ... Зи Фо (й = х ~/ й = у 1/ ... ~/ й = и ~/ А (й)) Чх7у ...7РЬй(х= у ~/ х=а ~/ ... ~/ и=й 1/ А (х) ~/ А(у) ~/ ... ~/ А(й)), которые двойственны соответствующим формулам 9Ь)).

1гл, т ИСЧИСЛЕНИЕ ПРЕДИКАТОВ С РАВЕНСТВОМ 220 РАСШИРЕННЫЙ ФОРМАЛИЗМ 221 Для правых частей этих эквивалентностей мы введем сокращенное обозначение. Пусть ш — число переменных, образующих набор х, у,..., в. Посредством 3щхЯ (х) мы будем обозначать выражение Зх... 3 и (х ~ у & х ~ з & ... & и ~ ш & Я (х) & Я'(у) &... & Я (1с)), а посредством ЧщхЯ (х) — выражение 1/х ...Ъю(х=у Чх=с Ч ... )/и=юг Я(х) 1/ ЧЯ(ш)). Эти обозначения имеют смысл для ш = 2, 3, ... Содержательно формула ЗщхЯ (х) выражает тот факт, что имеется по меньшей мере ш различных индивидов, для которых выполняется Я (х), а УщхЯ (х) говорит о том, что Я (х) не выполняется самое большее для ш — 1 индивида, т.

е. Я (х) выполняется для всех индивидов, за исклю- чением не более чем ш — 1 из них. Пользуясь правилом (Х) для образования отрицания '), можно получить следующие эквивалентности: [)/щхА(х) — Зщх 1 А(х), 13щхА(х) 1Ущх 1А(х) (ш= 2, 3, ...). Далее, для любого конкретного числа ш легко вывести формулы УщхА (х) — ~ 1/щ+,хА (х), 3 щ,хА (х) -+.

3щ хА (х), а такн<е формулы 'Ух Ах -+ ]/,х А (х), Ззх А (х) -э Зх А (х). 1) См. с. 181. Справедливость всех этих формул легко также усмотреть с точки зрения их содержательного смысла. С помощью введенных сокращений формулы 9а)) и 9Ь)) запи- сываются следующим образом: ЗхЗу ... Зи Фи (ю = х )/ ... '1/ и~ = и 1/ А (ш)) 71+ хА (х), 'чх у у ... з и Зиэ (й чь х &... & ш ~ и & А (ил)) 31,хА (х), где 1 представляет собой число переменных х, у,..., и. Мы не будем заниматься здесь выводом формул 9а)) и 9Ь)), так как это было бы кропотливым делом, не дающим ничего прин- ципиально нового. Способом, подобным тому, которым формулы 8а)) и 8Ь)) были обобщены до формул 9а)) и 9Ь)), могут быть обобщены и форму- лы 7а)) и 7Ь)).

Эквивалентности, представляющие собой это обобщение, дадут нам некоторое преобразование формул вида 7х(х~а &х~Ь& ... &хчьг-~А(х)), и Зх (х чь а & х Ф Ь & .. & х Ф г & А (х)) (здесь вместо выражения х ~ а, Фигурирующего в формулах 7а)) и 7Ь)), появляется конъюнкция, состоящая из нескольких выражений такого рода, а вместо одной свободной переменной а появляется несколько таких переменных а, Ь, ..., г). Мы приведем соответствующие формулы для случая трех свободныт переменных а, Ь и с. После введенных сокращений формула, аналогичная формуле 7а)), будет иметь вид Чх(хчьа&х-ьЬ& хчьс-эА (х)) ('ух А (х) ~/ [( 1 А (а) ~/ 1 А (Ь) ~/ [ А (с))'& Узх А (х)] ~/ [(( 1А(а) & [А(Ь) &а~Ь) )/ (1 А (а) & 1 А (с) & а чь с) 1/ ( 1 А (Ь) & 1 А (с) & Ь ~ с)) & т эхА (х) ] 1/ [ [ А (а) 8с 1 А (Ь) & 1 А (с) & а =,й Ь & а Ф с & Ь Ф с & 'уьхА (х)Ц, а формула, аналогичная формуле 7Ь)), запишется в виде Зх (х чь а & х -ь Ь 8 х ВВ с & А (х))— (3 А (х) & [[А (а) ~/ А (Ъ) ~/ А (с) -з- З,т А (х)] & [(А(а) & А (Ь) & а Ф Ъ) 1/ (А(а) & А (с) & ачьс) 1/ (А (Ь) & А (с) & Ь чь с) -+- Зэт А (х)) & [А (а) 8с А (Ь) & А (с) & а Ф Ь & а ЧЬ с & Ь Ф с -~ Зьх А (х)]).

Если импликации, встречающиеся в этих формулах, выразить через конъюнкцию и отрицание, а затем применить правило исчисление НРедикАтов с РАвенством игл. ч' РАСШИРЕННЫЙ ФОРМАЛИЗМ взятия отрицания, то получатся следующие эквивалентности: Чх(х=а ~/ х=Ь \/ х=с ~/ А (х)) (ЧхА(х) ~/ [( 1 А (а) ~/ 7 А(Ь) ~/ 1 А(с)) &'УгхА(х)) ~/ [(( 7 А(а)& $ А(Ь) &а~Ь) ~/(ЧА(а) & $ А(с) &а~с) ~/ ( $ А(Ь) & 7 А(с) & Ьчьс)) &'уагА(х)! ~/ [ $ А (а) & Ч А (Ь) & $ А (с) & а ~ Ь & а ~ с & Ь чь с & )/гх А (х) Ц, Зх (х ~ а & х Ф Ь & х ~ с & А (х)) (йхА(х) & [( 1А(а) & 7 А(Ь) & 7 А(с)) ~/ ВгхА(х)) & [(( 1 А (а) ~/ 1 А(Ь) ~/ а=Ъ) &(1 А(а) ~/ 1А(с) ~/ аэ с) & ( Ч А (Ь) ~/ 1 А (с) ~/ Ь = с)) ~/ Зэг А (х)) & [ЧА(а) ~/ 3 А(Ь) ~/ $ А(с) ~/ а=Ы/ а=с ~/ Ь=с ~/ ЧгхА(х))) Легко убедиться, что обе эти формулы двойственны друг другу.

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

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