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