Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 30
Текст из файла (страница 30)
136 исчислнник пгкдиклтов 1гл. гт выражения А (а), А (Ь), ..., А (1). Тогда мы получим А(а) 8сА(Ь) 8с ... &А(1) — 1-А(а), А(а) &А(Ь) & ... &А(1)-э.А(1). Если мы теперь начнем толковать чх А (х) как конъюнкцию, распространенную на все значения переменной х, то в соответствии с только что упомянутыми формулами мы для каждого значения с переменной а должны будем иметь Чх А (х) — ь А (с). Систему (вообще говоря, бесконечную), состоящую из этих формул, мы можем с учетом правила подстановки свести в одну формулу (а) Чх А(х)-ьА(а).
Таким образом, зту формулу для квантора всеобщности мы вводим в качестве аналога формул 11 1), 2) для конъюнкции. Совершенно тем же рассуждением мы получаем в качестве аналога формул П1 1), 2) для дизъюнкции формулу (Ь) А (а) -ь Лх А (х). Теперь осталось найти аналоги для формул 11 3) и 111 3). Сначала мы рассмотрим формулу П 3): (А -ь В) -+-((А -ь С) -+ (А — ь В & С)). Обобщением ее для случая конечного числа членов конъюнкции является формула (А -+. В) — ((А »С) — ь ...
-+ ((А — »К) — ь (А — В& С& ... &К)) ...). Подставим вместо В,С,...,К выражения В(а), В(Ь), ..., В(1), где а, Ь, ...,1 суть значения переменной а. Тогда получится (А -+. В (а)) -+. ((А -+- В (Ь)) — ь ... — ь ((А -ь В (1)) -ь (А -ь В(а) & В(Ь) 8« ... & В(1))) ...). 1 2) СВЯЗАННЫЕ ПВРНМВННЫВ И ПРАВИЛА ДЛЯ КВАНТОРОВ 137 Эту многочленную импликацию, зависящуго от указанных значений а, Ь, ..., 1 переменной а, мы, вообще говоря, не можем распространить на всю область ее значений, так как у нас в распоряжении нет никакого формального выраи<ения, изображающего «бесконечную импликацню» '). Тем не менее мы сможем осуществить переход ко всей нндивидной области, взяв вместо формулы 11 3) соответственным образом выбранное правило, а именно уже упоминавшуюся ранее схему (6): Если мы здесь вместо двучленной конъюнкции снова рассмотрим многочленную, распространенную па значения а, Ь, ..., $ переменной а, то получим схему Я -ь 'л) (а) Я вЂ” (3 (Ь) Я -~ )3 (г) Теперь в атой схеме уже можно будет произвести переход ко всей области аначений переменной а.
Именно, во-первых, в формуле Я -+. (3(а) & й) (Ь) & ... &(3(1) ') Можно было бы думать, что эту трудность удастся устранить посредством объединения всех посылок этой многочлеиной иьсоликацин в одну конъюнкцию. Это удалось бы в том случае, если бы вместо формулы П 3) мы отправлялиоь от формулы (А -ь В) & (А -ь С) -ь (А -э. В & С). Этой формулы, однако, недостаточно для того, чтобы вместе с формуламн П 1) и 2) неявным образом охарактеризовать конъюнкцию, как это видно иэ приведенного в предыдущей главе (иа с.
108) доказательства независнмости. Равным образом, для неявной характеризации распространенной на всю инливидную область конъюнкции было бы недостаточно взять для квантора. всеобщности формулу Чх (А -ь В (х)) -ь (А -ь 1(х В (х)]. исчисление НРедикАТСВ Я -». (В -». )1) Я -». ( — » й) Я -» В(с), Я -» В(Ь), Я вЂ” » ( — Одсй) Я вЂ” » В(1) формулу Я -» (В -» 6 (а)) Я -»- В (а), Я -» ( — »~х5(х)) Я вЂ” В (с), Я -» (В-» 6(а)) Я -» ( — ». 6 (а)) вместо имеющейся в ней конечной коныонкции можно написать формулу )гхй (х).
(Конечно, для того чтобы )гхй (х) оказалось формулой, в В (а) не должна входить переменная х, но этого всегда можно добиться путем предварительных переименований связанных переменных.) Систему посылок этого правила мы тоже смон<вм распространить на всю область значений переменной а, взяв вместо конечного списка формул которая для произвольного значения с переменной а позволяет вывести При этом, конечно, должно выполняться одно существенное условие: переменная а не должна встречаться в формуле Я, потому что в противном случае выражение Я при подстановке вместо переменной а могло бы претерпевать какие-нибудь изменения. По тем же самым причинам и в В (а) переменная а моясет фигурировать только на том месте или ыа тех местах, которые соответствуют выделенному аргументу; это условие выполняется отнюдь не всегда.
Например, воли равенство а=Ь мы записали сокращенно, обозначив его посредством В (Ь), то в В (а) зависимость от а будет касаться лишь правой части этого равенства, хотя переменная а фигурирует и в левой части его. В соответствии со сказанным мы приходим к следующей схеме: Я вЂ” » В(а) (а) Я вЂ” » чхй(х) Однако схема эта может быть применена лишь в том случае, воли формула Я -».
В (а) содержит переменную а только на месте, соответствующем выделенному аргументу (мы для краткости говорим о «месте аргументаэ и 1 21 СВЯЗАННЫЕ ПЕРЕМЕННЫЕ И ПРАВИЛА ДЛЯ КВАНТОРОВ 139 тогда, когда в качестве аргумента указано несколько таких мест), а также если связанная переменная х не входит в В (а). Эта схема соответствует, конечно, не формуле 113) для конъюякции, а схеме (й), которая, как мы установили ранее '), при аксиоматическом введении конъюнкции не может быть полноценным заменителем формулы 113).
Скорее, роль такой замены могла бы играть схема (9'): Если мы снова в этой схеме перейдем от двучленпой конъюнкции к конъюнкции, распространенной на всю область значений пере- менной а, то для знака всеобщности у нас получится следующая схема: причем снова должно выполняться предварительное условие, состоящее в том, что переменная а в формуле доли«на встречаться только на местах, указанных в качестве аргумента, и что связанная переменная х не должна входить в формулу 5 (а). Однако можно показать, что эта схема может быть получена из приведенной выше схемы (а) в качестве производного праги«а '): это означает, что с помощью схемы (а) и применяемых нами правил исчислеыия высказываний мы можем в случае выполнения упомянутых выше условий из формулы получить формулу Я -» (й -» ))'хб (х)).
Для этого ыам достаточно заменить по правилу соединения посылок г) исходную формулу формулой Я дс В -»- 6 (а). г) См. гл. П1, с. 112. е) Более полно о роли, которую играют производные правила, см. на с. 144. г) См. с. 116. «21 связАнные пеРеменные и пРАВилА для НВАнтоРОВ $44 1гл гч ИСЧИСЛЕНИЕ ПРЕДИКАТОВ 44О Теперь схема (сс) даст нам, ввиду сделанных предположений о характере вхождений переменных а и х, формулу Я А  — ~ '«хб (х), а эту последнюю»«он~но будет по правилу рааъединевия посылок снова преобрааовать в Я вЂ” ~ (3 -~ Чхб (х)). Ввиду того, что в основу наших рассмотрений мы уже положили исчисление высказываний (в виде теории нстинностных функций), нам нужно дать неявное описание не самой конъюнкции, а ее аналога — «конъюнкции, распространенной на индивпдную область».
В связи с этим мы обойдемся схемой (а) и не будем вводить вместо нее в качестве исходного правила более сложную схему с двумя посылками в нмпликацин. По аналогии со схемой (а) для квантора всеобщности, для квавтора существования мы сформулируем следующую схему: 3(а) — ~- Я (И ЭхВ (х) — Я применение ее снова будет ограничено требованием относительно того, что переменная а должна встречаться в формуле В (а) -м Я только на местах, указанных в качестве аргумента, и что х не должно входить в 3 (а).
Эта схема соответствует следующей схеме для дизъюнкции: Я вЂ” ~Я В- б которая, как мы установили ранее '), в аксиоматической логике высказываний может играть роль полного ааменителя формулы П1 3). Относительно формул (а), (Ь) и схем (а), (р), к которым мы пришли с помощью эвристических аналогий, моя<но и непосредственно констатировать, что в смысле перевода нашего формализма в содержательный план они соответствуют таким способам умозаключений, которые получаютсн на основе нашего понимания общеутвердительных и частноутвердительных суждений. Формуле (а) содержательно соответствует заключение от общего к частному («с(1С»нш с(е ошп1»): «Если а — некоторый объект и для всех объектов х истинно Я (х), то истинно и Я (а)».
') См. с. П4 — П5. ~Формуле (Ь) соответствует заключение от наличия некоторого свойства у определенного объекта к существованию объекта с этим свойством: «Если с — некоторый объект и истинно Я (а), то существует объект х, для которого истинно Я (х)». 11е так уж непосредственно, но все же легко, из смысла слов «все» и «существует» извлекаются следующие способы умозаключений, содержательно соответствующие схемам (сс) и (р): «Если для всякого объекта с в случае истинности Я истинно В (а), то в случае истинности Я В (х) будет истинным для всех объектов хм «Если для любого объекта а Я истинно, когда истинно 3 (с), то Я истинно, если существует х, для которого истинно В (х)».
Под о б ъ е к т а м и здесь всякий раз понимаются объекты из участвующей в данном рассмотрении индивидной области. Точности ради отметим, что формализация упомянутых четырех способов умозаключений с помощью указанных двух формул и двух схем становится действенной лишь в сочетании с правилом подстановки. 4. Окончательная формулировка правил исчисления предикатов; изображение форм категорических суждений; случай пустой нндивидной области. Теперь мы получили наконец систему правил, с помощью которой, как будет покааано, может быть произведена формализация всех обычных способов умозаключений, касающихся взаимосвязи между всеобщим н частным, а также соотношений между всеобщими н частными су'кдениями.
Описанное таким образом исчисление может быть названо исчислением предик тсв— причем мы допускаем, как это уже делалось и раньше, преднкаты и с несколькими субъектами. Ф о р и у л а м и и с ч и с л е н и я и р е д и к а т о в мы будем называть только такие формулы— в смысле определенного нами понятия ф о р м у л ы,— которые строятся лишь из переменных и логических знаков. Зато мы будем говорить о в ы в о д е с р е д с т в а м и и с ч и с л е н и я п р ед и к а т о в и в том случае, если в формулах вывода будут встречаться предикатные, а может быть, и индивидные символы. В выводе средствами исчисления предикатов, кроме тех формул, которые в исчислении предикатов вообще допускаются в качестве исходных, в атом качестве могут браться еще и некоторые другие формулы (а к с и о м ы).
Про заключительную формулу вывода мы будем тогда говорить, что она выведена из этих аксиом средствамн исчисления преднкатов. Теперь еще раз коротко суммируем правила исчисления предикатов. Про»кде всего, у нас имеется правило подстановки вместо формул»них переменных, содержание которого приобрело точный характер в результате точной формулировки понятия ф о р м у- 1 21 сВяэАнные пеРеменные и пРАВилА для КВАнтоРОВ 143 (гл. РР 142 ИСЧИСЛЕНИЕ ПРЕДИКАТОВ л ы; далее, у нас имеются правило подстановки вместо свободных индивидных переменных и правило переименования связанных переменных 2). В качестве исходных формул разрешается брать тождественные формулы исчисления высказываний. К ним мы добавляем обе основные формулы: (а) 1»хА(х) — 1- А(а) и (Ь) А(а) -» ЗхА(х). В качестве схем, позволнющих получать новые формулы из ранее полученных, у нас имеется, во-первых, наша первоначальная схема заключения а кроме того, две новые схемы: Я вЂ” В (а) » )ухВ (х) В (а) -ь Я Ф) ЗхВ(х) — » Я Обе они могут применяться лишь тогда, когда в первой формуле схемы переменная а встречается лишь на местах, указанных в качестве аргумента, а х не входит в В (а).