18. Исчисление предикатов. Логическое следствие

Понятие логического следствия, введенное в § 2.4 для исчисления высказываний, распространяется и на исчисление предикатов. Теперь нам придется иметь дело не только с символами, обозначающими высказывания, но и с предикатными символами, а приписывание значений происходит несколько более сложно. В исчислении предикатов начинает играть роль еще один фактор — возможность свободного вхождения какой-либо переменной. Например, в арифметической теореме исходное допущение может иметь форму «пусть х есть целое число больше 0» или «предположим, что х делится на 3». Исследование того, как такое х «рассматривается» в доказательстве, обнаруживает, что х считается постоянной, т. е. одним и тем же предметом на протяжении всего доказательства. Однако вне контекста доказательства это х — переменная. (Например, доказав некоторый результат, относящийся к х, которое делится на 3, мы считаем, что имеем право применять этот результат ко всем таким числам.) Читателю хорошо известны такие названия, как «параметр» и «произвольная постоянная» для символов, используемых подобным образом.

Так мы приходим к основному определению: формула В есть логическое следствие формул А1, А2, ..., АM (в исчислении предикатов), что символизируется записью

А1, А2, ..., Аm |=В,

Если для каждого поля D и для каждого приписывания формулам А в D формула В получает значение Т каждый раз, как каждое А получает значение Т. Далее, если переменная х входит как свободная в какую-либо формулу А, то при каждом приписывании формулам А для всех свободных вхождений х в поле D выбирается одно и то же значение, т. е., выбирая приписывание формулам А, такое х рассматривают как постоянную.

Формулировка и доказательство теоремы 2.6 и ее следствия без всяких изменений относятся к рассматриваемому случаю. Таким образом, этими результатами мы уже располагаем. В частности, для того чтобы заключить, что А1, А2, ..., Аm |=В, достаточно доказать, что |= А1А2 ..., Аm→В. Поскольку теорема 2.7 также распространяется на исчисление предикатов, можно представить доказательство того, что формула В есть логическое следствие формул А1, А2, ..., Аm в форме конечной последовательности шагов, последним из которых будет В. Для исчисления предикатов можно ввести дополнительные правила, кроме основных правил p и t, служащих вычислении высказываний оправданием появления в доказательстве формулы Е. Самыми основными из этих правил являются следующие два:

Правило us (универсальной конкретизации). Существует формула (х)А(х), предшествующая формуле Е, такая, что Е есть А(у), результат подстановки в формулу А(х) переменной у вместо х, причем подстановки эти ограничиваются требованием, чтобы ни одно из получающихся в результате вхождений у не было связанным.

Правило ug (универсального обобщения). Е имеет форму (х)А(х), где А(х) является предшествующей формулой, такой, что х есть переменная, не имеющая свободных вхождений ни в одной из посылок.

Положение вещей в вопросе о доказательстве логического следствия в исчислении предикатов оказывается, таким образом, следующим. Мы утверждаем, что А1, А2, ..., Аm |=В, если мы можем образовать цепочку формул

E1, E2, ..., Er (=В),

Такую, что наличие в ней каждого Е можно оправдать на основании одного из правил р, t, us или ug. В самом деле, как и в § 2.4, можно доказать, что если наличие в цепочке каждого Е можно оправдать таким способом, то

А1, А2, ..., Аm |=(любое Е в последовательности).

Прежнее доказательство сохраняет силу (причем достаточно использовать расширенную форму теоремы 2.7) для случая, когда наличие в цепочке какого-либо Е оправдывается правилами р или t. Те случаи, когда используются правила us или ug, охватываются применением теорем 2.10 (I) и 2.11 (I). Подробное доказательство предоставляется читателю в качестве упражнения.

Мы теперь в состоянии построить формальные выводы для простых рассуждений в том стиле, какой применялся в § 2.4.

Примеры

1. Рассмотрим следующее рассуждение.

«Ни один человек не является четвероногим. Все женщины — люди. Следовательно, ни одна женщина не является четвероногой». Пользуясь методами перевода, данными в § 2.6, запишем это рассуждение в символической форме:

(x)(Hx→~Qx)

(x)(Wx→~Qx)

Вывод строится следующим образом.

{1} (1) (x)(Hx→~Qx) p

{2} (2) (x)(Wx→Hx) p

{2} (3) Wy→Ну 2us

{1} (4) Hy→~Qy 1us

{1,2} (5) Wy→~Qy 3,4t

{1,2} (6) (x)(Wx→~Qx) 5ug

3. Если читатель согласился с правильностью вывода в предыдущем примере, то он, собственно, принял новые правила вывода, помогающие строить рассуждение. Введем еще два производных правила, играющих ту же роль. Правила эти представляют собой формальные аналоги двух обычных, хорошо известных явлений в математике. Если мы уверены в том, что «(Х)Р(х)» истинно, то мы считаем себя вправе «выбрать» такое у, что Р(у). Тогда у есть неизвестная, но определенная величина, такая, что Р(у). Наоборот, если дано, что существует у такое, что Р(у), то мы, не колеблясь, выводим, что «(Х)Р(x)» истинно. В исчислении предикатов правило, позволяющее перейти от (Х)Р(х) к Р(у), называется правилом es (правило экзистенциальной конкретизации). Правило, позволяющее перейти от Р(у) к (Х)Р(х), называется правилом eg (правило экзистенциального обобщения). Эти правила представляют собой такие же аналоги квантора существования, как правила us, ug — аналоги квантора общности. Мы не будем ни обосновывать эти правила, ни даже рассматривать ограничения, которые необходимо соблюдать при пользовании ими. В приводимом ниже простом примере мы будем пользоваться строчной греческой буквой для обозначения предмета, участвующего в «выборе», сопровождающем случай применения правила es.

«Каждый член комитета богат и республиканец. Некоторые члены комитета — старики. Следовательно, существуют старики—республиканцы».

{1} (1) (X)(Cx→Wx Rx) (Зх) P

{2} (2) (X)(Cx Ox) P

{2} (3) Ca Оа 2Es

{1} (4) Ca→Wa Ra 1us

{2} (5) Са 3t

{1,2} (6) Wa Ra 4,5t

[137]

{2} (7) Oa 3t

{1, 2} (8) Ra 6t

{1, 2} (9) Oa Ra 7,8t

{1, 2} (10) (X)(Ox Rx) 9eg

4. В выводе, соответствующем приведенному ниже рассуждению, используются все описанные нами правила.

«Некоторые республиканцы любят всех демократов. Ни один республиканец не любит ни одного социалиста. Следовательно, ни один демократ не является социалистом».

Причина введения х в строку 3 вывода заключается в следующем. В силу формы заключения (х)(Dx→~Sx) приводится условное доказательство. Таким образом, в строке 3 в качестве посылки вводится Dx. Поскольку вхождение х здесь свободное, мы отмечаем его наличие (как и в последующих строках, зависящих от этой посылки), чтобы помочь избежать неправильного употребления правила ug.

{1} (1) (X)(Rx (Y)(Dy→Lxy)) P

{2} (2) (х)(Rx→(у) (Sy→ ~ Lxy)) P

{3} (3) Dx X, P

{1} (4) Ra (Y)(Dy→Lay) 1Es

{1} (5) (у) (Dy→Lay) 4T

{1} (6) Dx→Lax 5us

{1, 3} (7) Lax x, 3, 6,t

{2} (8) Ra→(y) (Sy→ ~ Lay) 2us

{1} (9) Ra 4t

{1, 2} (10) (y)(Sy→ ~ Lay) 8, 9t

{1, 2} (11) Sx→ ~ Lax 10us

{1, 2, 3} (12) ~ SX x, 7, 11T

{1, 2} (13) Dx→ ~ Sx 3,12cp

{1, 2} (14) (X) (Dx→ ~ Sx) 13ug

Предыдущие примеры сообщают правдоподобие утверждению, что исчисление предикатов представляет собой адекватный способ формализации весьма разнообразных рассуждений. Читателю может показаться неудобным, что такие простые рассуждения, как рассмотренные выше, требуют таких длинных выводов, но мы можем заверить его, что подробное изложение исчисления предикатов включало бы в себя еще новые производные правила, позволяющие сильно упростить выводы. В конечном

Итоге мы приходим к понятию «неформального доказательства». В математике это приводит к выводам в привычной разговорной манере: упоминания о правилах вывода и тавтологиях опускаются, и внимание обращается только на математические (т. е. не логические) аксиомы и ранее доказанные используемые теоремы. (Подробнее об этом говорится в следующей главе.) Главная выгода, получаемая от неформальных доказательств, возникающих из развития формальных выводов, заключается в том, что создается система, в рамках которой можно объективно, механическим путем решить, в случае разногласий, представляет ли собой спорное доказательство действительно доказательство.

Упражнения

Построить выводы, соответствующие следующим рассуждениям:

1. Ни один первокурсник не любит второкурсников. Все, живущие в Даскомбе, — второкурсники. Следовательно, ни один первокурсник не любит никого из живущих в Даскомбе (Fx, Lxy, Sx, Dx).

2. Арт — мальчик, у которого нет автомобиля. Джейн любит только мальчиков, имеющих автомобили. Следовательно, Джейн не любит Арта (Вх, Ox, Lxy, а, i).

3. Ни один республиканец или демократ не является социалистом. Норман Томас — социалист. Следовательно, он не республиканец (Rx, Dx, Sx, t).

4. Всякое рациональное число есть действительное число. Существует рациональное число. Следовательно, существует действительное число.

5. Все рациональные числа являются действительными числами. Некоторые рациональные числа—целые числа. Следовательно, некоторые действительные числа — целые числа (Qx, Rx, Zx).

6. Все первокурсники встречаются со всеми второкурсниками. Ни один первокурсник не встречается ни с одним студентом предпоследнего курса. Существуют второкурсники. Следовательно, ни один второкурсник не является студентом предпоследнего курса.

7. Ни один торговец наркотиками не является наркоманом. Некоторые наркоманы привлекались к ответственности. Следовательно, некоторые люди, привлекавшиеся к ответственности, не являются торговцами наркотиками.

8. Некоторые первокурсники любят всех второкурсников. Ни один первокурсник не любит никого из студентов предпоследнего курса. Следовательно, ни один второкурсник не является студентом предпоследнего курса (Fx, Lxy, Sx, Jx).

9. Некоторым нравится Элвис. Некоторые не любят никого, кому нравится Элвис. Следовательно, некоторых любят не все (Рх, Ex, Lxy).

< Предыдущая		Следующая >