Глава 9. Конструктивные и неконструктивные выводы

(«Бастилия была взята 14 июля 1789 года», «Волга впадает в Каспийское море», «Луна —спутник Земли»).

Объяснение различия между классическим и конструктивным пониманием логических операций удобнее всего начать с операции постановки квантора существования, т.к.

M

F

указан — иначе говоря, мы не обязаны уметь привести пример элемента, обладающего данным свойством. При конструктивном понимании, напротив, предложение 3xF(x) считается обоснованным лишь в том

M

F

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

Другой пример: из общих свойств многочленов — точнее, из общих свойств непрерывных функций — следует, что всякое уравнение вида f (x) = 0, где f (x)—многочлен нечетной степени с действительными коэффициентами, имеет хотя бы один действительный корень; в частности, это верно для уравнения 4x5 — x4 + 7x3 — 5x2 — 3x — 2 = 0. Но такое доказательство существования корня данного уравнения

неконструктивно: оно не позволяет нам указать никакого конкретного корня. Если же мы заметим, что левая часть нашего уравнения обращается в нуль при подстановке вместо переменной x числа 1, мы тем самым получим конструктивное доказательство.

Перейдем теперь к дизъюнкции.

Пусть, например, в ходе расследования некоторого преступления неопровержимо установлено, что в момент его совершения на месте преступления находились два человека — назовем их А и Б, —и больше никого там не было. Тогда можно считать обоснованной дизъюнкцию утверждений «Преступление совершил А» и «Преступление совершил Б», однако это обоснование неконструктивно. А если для того, чтобы занять какую-то должность, требуется, в числе прочего, владение немецким или французским языком, и отборочная комиссия, проэкзаменовав каждого из нескольких кандидатов по одному из этих языков, установила, что он им владеет, то дизъюнкция «Данный кандидат владеет немецким или французским языком» является для каждого из них конструктивно обоснованной.

Рассмотрим, далее, операцию постановки квантора общности. При классическом понимании предложение VxF(x), где F(x) — (одноместный) предикат, определенный на некотором множестве M, считается обоснованным, если мы любым способом смогли убедиться, что все эле-

MF быть косвенным: например, нам удалось привести к нелепости гипотезу,

MF конструктивном же понимании это предложение считается обоснованным лишь тогда, когда у нас имеется регулярный способ (алгоритм),

aM

F( a)

обоснование также должно быть конструктивным).

Например, упомянутое выше обоснование утверждения: «Всякое уравнение вида f(x) = 0, где f(x)—многочлен нечетной степени с действительными коэффициентами, имеет хотя бы один действительный корень», вытекающее из общих свойств непрерывных функций, не является конструктивым; но утверждение «Всякое уравнение вида ax = b, где a, b — действительные числа и а = 0, имеет действительный корень», легко обосновать конструктивно: алгоритм, позволяющий конструктивно обосновать соответствующее утверждение для любого конкретного уравнения такого вида —иначе говоря, найти корень этого

ba

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

Обратившись теперь к конъюнкции, мы сразу увидим, что, поскольку она связана с квантором общности так же, как дизъюнкция с квантором существования (если множество, на котором определен предикат F, СОСТОИТ из двух элементов a и b, то VxF(x) означает то же, что F(a) & F(b)), при классическом понимании конъюнкция должна считаться обоснованной, если мы каким-либо способом (возможно, косвенным) убедимся, что истинны оба ее члена, а при конструктивном — лишь тогда, когда каждый из них мы умеем обосновать.

Импликация при классическом понимании считается обоснованной, если мы каким угодно способом убедимся, что в случае истинности ее посылки заключение также истинно, а при конструктивном — лишь

тогда, когда у нас имеется регулярный способ (алгоритм), позволяющий по любому обоснованию посылки построить обоснование заключения.

Для примера рассмотрим следующее доказательство утверждения: «Две прямые, соответственно перпендикулярные к двум пересекающимся прямым, также пересекаются» (приведенное в учебнике геометрии А.П.Киселева).

Е

Пусть FE и FG (см. чертеж) — пересекающиеся прямые, а прямые АВ и CD им перпендикулярны. Тогда, если допустить противное, т. е. что АВ и CD параллельны, то прямая FG, будучи перпендикулярна к одной из

CD

АВ F АВ

различных перпендикуляра FE и FG, что невозможно.

Это вполне корректное доказательство условного утверждения (импликации) «Если прямые FE и FG пересекаются, а прямые АВ и CD

АВ CD

казательство неконструктивно: оно не дает никакого способа, который позволял бы, если указана точка пересечения FE и FG, указать точку АВ CD

Возьмем теперь арифметическое утверждение: «Если целое число делится на 6, то оно делится на 3». Вот его подробное доказательство. Пусть целое число n делится на 6, т. е. может быть представлено в виде произведения числа 6 на некоторое целое число к. Тогда, поскольку 6 = 3 • 2, число n представляется также в виде произведения числа 3 на некоторое целое число, —а именно, на 2к, — а это и значит, что n делится на 3. Это доказательство конструктивно, т.к. дает алгоритм,

n

nn на З».

Что же касается отрицания, то здесь различие между классическим и конструктивным пониманием отсутствует: отрицательное предложение «Утверждение A неверно» с любой точки зрения естественно считать обоснованным в том случае, когда опровергнуто «положительное» A

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

Прежде всего, сразу видно, что с ним не согласуется закон исключенного третьего. В самом деле, в силу этого закона истинна всякая дизъюнкция вида A У -A, где A — произвольное предложение; но при конструктивном понимании мы имеем право считать такую дизъюнк-

A

либо -A —иначе говоря, либо умеем доказать предложение A, либо умеем его опровергнуть.

Все остальные правила при конструктивном понимании логических операций сохраняют силу. Более точно это означает следующее: если

M

мощью правил, перечисленных в пункте 3 главы 8, но без применения

M

конструктивно обоснованы, то формулу у также можно считать конструктивно обоснованной.

Постараемся убедиться, что это действительно так. Начнем с простейшего случая, когда у выводится из M за один шаг — иначе говоря, с помощью «одноэтажного» дерева вывода. Итак, пусть весь вывод у из M состоит из одного шага, т. е. одного применения некоторого правила. Правило это должно быть безусловным, т. к. условное правило может применяться только в «сложном» выводе, когда что-то из чего-то уже было выведено раньше. Поэтому у нас есть следующие возможности:

M

а формула у есть а & р. Но конструктивное понимание конъюнкции как раз в том и состоит, что из конструктивной обоснованности ее членов вытекает конструктивная обоснованность ее самой.

M

а & р, а формула у есть а или р.

M

или р, а формула у есть а V р. Но конструктивное понимание дизъюнкции

состоит именно в том, что ее конструктивная обоснованность вытекает из конструктивной обоснованности одного ее члена.

г) Применяемое правило есть У И. Тогда M состоит из двух формул а и а ^ р, а формула у есть р. Но конструктивная обоснованность импликации означает наличие регулярного способа по всякому конструктивному обоснованию ее посылки построить конструктивное обоснование заключения. Поэтому, если мы располагаем конструктивными обоснованиями формул а и а ^ р, то мы сумеем конструктивно обосновать и формулу р.

M

-их, а формула у есть Л. Поэтому доказываемое условное утверждение «Если

M

же можно считать конструктивно обоснованной» справедливо тривиальным

-

быть обоснованы (ни конструктивно, ни классически).

е) Аналогичным образом можно рассуждать, если применяемое правило

M

невозможно обосновать.

ж) Если применяемое правило есть ТВ, то формула а входит в множест-

M

M

ного» дерева вывода (как в примерах 1, 2, 6, 7, 8, 9, 10 из предыдущей главы).

M

листьев. Если при этом на последнем шаге, т. е. на «нижнем этаже» дерева, применяется какое-либо из безусловных правил (как в примерах 1, 2, 6), то формула у, стоящая под самой нижней чертой, получается с помощью этого правила из формул, стоящих непосредственно над ней, а каждая из этих формул конструктивно обоснована, потому что она либо является корнем

M

сама входит в M (гак формула р ^ у в примере 2). А отсюда мы можем заключить, рассуждая точно так же, как в случае «одноэтажного» дерева, что и стоящую под чертой формулу у можно считать конструктивно обоснованной.

Если в том же случае «двухэтажного» дерева на «нижнем этаже» применяется условное правило, то имеются три возможности:

з) Это правило есть ВИ (как в примерах 8 и 10).

M

M

обоснования а можно получить конструктивное обоснование р. А это как раз и значит, что конструктивно обоснована импликация a ^ р, которая служит корнем нашего двухэтажного дерева.

и) Правило, применяемое на «нижнем этаже», есть ВО (как в примере 9). Тогда над чертой в «нижнем этаже» стоит формула Л, являющаяся корнем

одноэтажного дерева вывода, один из зеленых листьев которого есть a, a остальные входят в M. Отсюда следует (см. сноску 9 в предыдущей главе), что для всякого набора значений переменных, для которого все формулы

M

была бы принять значение И—что, очевидно, невозможно. Поэтому всякий

M

а принимает значение Л. А это значит, что если мы сумеем обосновать все

M

формулы как раз и является обоснованием формулы -іа, которая служит корнем нашего двухэтажного дерева.

к) Правило, применяемое на «нижнем этаже», есть УД (как в примере 7). Тогда над чертой в «нижнем этаже» дважды записана формула у, и она же записана под чертой. Одна из двух «верхних» у является корнем одноэтажного дерева вывода, один из зеленых листьев которого есть а, а остальные входят M

M

да следует, что при условии конструктивной обоснованности всех формул,

M

основания р можно получить конструктивное обоснование у. Следовательно, его при том же условии можно получить и из конструктивного обоснования дизъюнкции aVp, которая тоже записана над чертой. (В примере 7 множество M пусто, роль у играет pVa, роль а играет сама а, роль р — сама р.)

Далее мы можем точно так же рассуждать в случае трехэтажного дерева вывода (как в примерах 3, 4, 11, 12, 14 из предыдущей главы), с тем лишь различием, что теперь над самой нижней чертой имеется хотя бы одно двухэтажное дерево, — а для двухэтажных деревьев нужный факт уже установлен. Затем таким же образом можно рассмотреть случай четырехэтажного дерева, и т. д.

3. Выводы, в которых не используется закон исключенного третьего—т. е. те, которые согласуются с конструктивным пониманием логических операций, — называются конструктивными выводами. Все выводы, проведенные в предыдущей главе, были конструктивными. Рассмотрим теперь пример неконструктивного вывода. (Все неконструктивные примеры мы будем отмечать звездочками.)

Пример 1*. ——a h а.

—1(5)

-УО

[<х](5)

л

-ТВ

дс

а V -іа

-ИТ

-уд

Вернемся теперь к одной из основных равносильностей логики предложений, рассмотренных в гл. 6,— равносильности Hi, которую мы назвали там «правилом снятия двойного отрицания». Мы показали сейчас, что ее левую часть можно вывести в исчислении естественного вывода из правой. Ранее (глава 8, пример 9) мы видели, что верно и обратное — ее правую часть можно вывести из левой. При переходе от равносильности к двум выводимое! ям естественно назвать правилом снятия двойного отрицания ту из них, которая установлена только что, а другой скорее подойдет название правила постановки двойного отрицания; впредь мы так и будем их называть.

Неконструктивный характер правила снятия двойного отрицания легче всего уяснить себе на примере случая, когда а есть утверждение о существовании объекта с теми или иными свойствами. При конструктивном понимании такое утверждение считается обоснованным .лишь тогда, когда указан конкретный пример объекта с нужными свойствами; а его двойное отрицание означает только то, что опровергнуто утверждение о несуществовании такого объекта,—но такое опровержение не обязательно дает возможность построить пример. (В то же время построение примера само по себе служит опровержением утверждения о несуществовании нужного объекта; в этом и состоит смысл конструктивности правила постановки двойного отрицания.)

На правиле снятия двойного отрицания основано доказательство от

А

мы принимаем гипотезу, что оно неверно — иначе говоря, что истинно его отрицание, —и пытаемся привести эту гипотезу к нелепости, т. е. вы-вести из нее два противоположных друг другу утверждения — скажем, ВВ

правилом введения отрицания, что гипотеза неверна, т.е. что спра-

А

А

доказательство от противного сложнее, чем приведение к нелепости, и в отличие от него неконструктивно. Приведением к нелепости мы .лишь опровергаем некоторую гипотезу, а от противного доказывается «положительное» утверждение.

В математических рассуждениях доказательства от противного используются весьма часто; примером может служить приведенное выше

доказательство утверждения: «Две прямые, соответственно перпендикулярные к двум пересекающимся прямым, также пересекаются». Но и вне математики нередко приходится иметь дело с этим приемом доказательства. Например, все имеющиеся доказательства подлинности «Слова о полку Игореве» суть доказательства от противного; то же можно сказать едва ли не обо всех мыслимых доказательствах утверждения, что «Илиада» и «Одиссея»—произведения одного автора (независимо от степени их убедительности). Читатель легко сможет найти и другие подобные примеры.

Следует, впрочем, иметь в виду, что в современных учебниках ма-тематики о «доказательстве от противного» нередко говорят и в тех случаях, когда в действительности используется всего лишь приведение к нелепости. Это бывает в случаях, когда доказывается отрицательное утверждение. Таково, например, доказательство упоминавшегося выше утверждения, что из одной точки нельзя провести больше одного перпендикуляра к одной и той же прямой.

Вопрос. В течение многих веков в качестве пособия для изучения греческого языка использовался сборник писем, приписывавшихся жившему в VI в. до н. э. Фалариду, тирану сицилийского города Акраганта. В 1696 г. английский филолог Р. Бентли (Richard Bent ley. 1662—1742) доказал неподлинность этих писем, приведя ряд аргументов, одним из которых было упоминание в них городов, основанных в более позднее время. Что представляет собой этот аргумент — доказательство от противного или приведение к нелепости?

[« vp](6) уд

2 -а _ М ур 4 -Р И(5) уо

Л

Л

ВО

6-

л

n(a vp)

i(a. VP)

(v)

М(3)

v

gvp

JL

ЗІ

-хх& —р

7 —а

[а&р1(6)

[—Р 1(7)

—1(7)

[а&р1(3)

Л

Л

n(ot&3)

Ча&З)

пaV—

Содержательный смысл этих выводов понятен. Например, выводя — (а & р) из —а V —р, мы рассматриваем два случая: —а и —р, и в каждом из них приводим к противоречию (т. е. к нелепости) гипотезу а & р.

Обратный вывод (доказательство выводимости примера 5) мы также

—

разбора которых необходим закон исключенного третьего. В случае р

мы введем еще одну промежуточную гипотезу а, которую уже имеющи- —( & )

—

—а V —р. В случае —р вывод дизъюнкции —а V — очевиден. Формальный вывод выглядит так:

[—Р 1(7)

-¦aV—р

М(3) [Р1(7)

naV —

Итак, «три четверти» законов Де Моргана удается доказать конструктивно. Неконструктивность последней «четверти» означает, что

&

ет, что мы умеем опровергнуть один из ее членов. Проиллюстрируем это следующим примером. Обозначим через а предложение «Всякое четное

число, большее двух, можно представить в виде суммы двух простых чисел» и через р предложение «Существует четное число, большее двух, которое нельзя представить в виде суммы двух простых чисел». Предложение а — это знаменитая гипотеза Гольдбаха—Эйлера, возникшая в 1742 г. в ходе переписки между двумя математиками, Леонардом Эйлером и Христианом Гольдбахом, и до сих пор, несмотря на простоту формулировки, не доказанная и не опровергнутая. Поскольку предложение -&

зом. Но опровержение одного из ее членов было бы доказательством другого, то есть решением задачи, вот уже два с половиной столетия не поддающейся настойчивым усилиям математиков!

5. Следующие шесть выводимостей отвечают основным равносиль- ностям группы III из гл. 8:

Пример 6. -avp h а ^ р.

Пример 7*. а ^ р I—'avp.

Пример 8*. -(а& -р) h а ^ р.

Пример 9. а ^ р і—i(a& -р).

Пример 10. а ^ р I 'Р ^-а (закон контрапозиции).

Пример 11*. -р a h a ^ р (обратный закон контрапозиции).

Деревьев вывода для этих примеров мы не будем выписывать; ограничимся указаниями, по которым нетрудно их построить. В примере 6

-v

правилом ВИ), а это легко сделать разбором случаев. В примере 7

правая часть очевидным образом выводится из левой с добавлением -

-( &- ) - &- -( &- )

а I 1-р. Выводимость примера 9 легко доказать приведением к нелепости. В примере 10 достаточно вывести -а из а ^ р и -р, а это можно

сделать, приведя к нелепости гипотезу а. В точности так же из -р ^ -а --

цания и введением импликации, получаем выводимость примера 11.

Неконструктивность примера 7 означает, что если у нас есть регулярный способ по всякому обоснованию посылки импликации построить обоснование ее заключения, отсюда еще не следует, что мы умеем опровергнуть посылку или обосновать заключение. Если мы, например, обозначим через а предложение «"Илиада" и "Одиссея" — произведения

одного автора», а через |3 — конъюнкцию предложений «"Илиада" — произведение одного автора (а не нескольких или многих)» и «"Одиссея" — произведение одного автора», то из а тривиальным образом следует J3, хотя ни опровергнуть а, ни обосновать J3 мы не умеем.

С другой стороны, если мы доказали, что а и отрицание |3 не могут одновременно быть истинными, это еще не дает нам способа по всякому конструктивному обоснованию а строить конструктивное обоснование Р; в этом смысл неконструктивности примера 8. Примером может служить приведенное выше доказательство утверждения: «Две прямые, соответственно перпендикулярные к двум пересекающимся прямым, также пересекаются». Фактически там было доказано, что не могут одновременно быть истинными предложение а = «Прямые FE и FG пересекаются, а прямые AB и CD им перпендикулярны» и отрицание предложения р = «Прямые AB и CD пересекаются»; но отсюда не получается никакого способа, который позволял бы, если указана точка пересечения FE и FG, указать точку пересечения AB и CD.

Наконец, смысл неконструктивности примера 11 состоит в том, что если мы располагаем способом по всякому опровержению предложения р строить опровержение предложения а, это еще не дает способа по всякому конструктивному обоснованию а строить конструктивное обоснование р. Пример: поскольку в «Задонщине» — древнерусской повести о Куликовской битве 1380 г.—можно обнаружить явные следы влияния «Слова о полку Игореве», из всякого опровержения подлинности «Слова» немедленно получалось бы опровержение подлинности «Задонщины». Но нет, разумеется, никакого способа, позволявшего бы предъявить древнюю рукопись «Слова» всякий раз, когда предъявлена древняя рукопись «Задонщины».

Задача. Покажите, что в конструктивном варианте исчисления естественного вывода имеют место следующие выводимости:

(а) ———а I >а («правило снятия тройного отрицания»);

(б) I 1—(а V —а) [Указание. Привести к нелепости формулу —(а V —а),

воспользовавшись выводимостью примера 3];

—— I

Попробуйте дать содержательное истолкование этих фактов.

6. Если в системе правил исчисления естественного вывода заменить правило ИТ правилом снятия двойного отрицания, то в полученном исчислении

можно вывести закон исключенного третьего в качестве производного правила. Для этого, очевидно, достаточно вывести в первоначальном исчислении без использования ИТ формулу ——(а V—), а это сделать нетрудно (ср. пункт (б) только что сформулированной задачи). Мы можем сказать, таким образом, что правило снятия двойного отрицания равносильно закону исключенного третьего. Можно показать также, что в том же смысле ему равносильны выводимости примеров 7, 8 и 11. В самом деле: из выводимости

примера 7 получается ot ^ ot I іа V а, но а ^ а — доказуемая формула (см. в

предыдущей главе пример 8), а из —а V а выводится а V —а (см. там же пример 7); из выводимости примера 8 получается —(——а & —а) I —а ^ а, а отсюда легко получить правило снятия двойного отрицания, т. к. —(——а & —а) — доказуемая формула (в чем читатель легко убедится сам); из выводтмости

примера 11 также получится правило снятия двойного отрицания, если заме——

равносильна так называемому ослабленному закону исключенного третьего: —а V ——а.

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