§ 3. Различные сгюсобы формулировки и доказательства предложений

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

и

Рассмотрим их поочередно.

Утверждение, «если — четные числа, то число четно», о котором шла речь в § 5 гл. I, является утверждением типа «если А, то В». Утверждение такого рода может быть выражено многими различными способами. Вот некоторые из них:

Различные формулировки отношения «если А, то В»:

1. Если верно А, то верно В.

2. Если выполняется А, то выполняется В.

3. А влечет В.

4. В вытекает из А.

5. В следует из А.

6. А является достаточным условием для В.

7. В является необходимым условием для А.

8. В верно всякий раз, когда верно А.

9. В верно, если верно А.

10. А верно только тогда, когда верно В.

11. Невозможно, чтобы одновременно А было верно, а В — ложно.

12. Если В ложно, то А тоже ложно.

В этом списке содержатся лишь наиболее употребительные формы. Он, конечно, неполон, поскольку в действительности можно привести сколько угодно много различных форм рассматриваемого утверждения. Некоторые из выражений, как, например, 6 и 7, не используются в этой книге и приведены здесь лишь ради полноты. Кроме 12, все перечисленные выражения могут рассматриваться как определения терминов типа «влечет», «необходимое условие», «достаточное условие», и «только тогда».

Например, 10 определяет использование в математике выражения «только тогда». Заменив символы А и В на утверждения относительно , о которых говорилось выше, мы заключаем, что следующие предложения обозначают одно и то же:

«Если целые числа тип четны, то целое число тоже четно».

«Целые числа тип четны только тогда, когда целое число четно».

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

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

Для этого нам нужно доказать, что 1 влечет 12 и, обратно, 12 влечет 1. Допустим сначала справедливость 1 и рассмотрим утверждение 12:

Возможно ли, что это заключение ложно и что на самом деле должно быть «А верно»? В таком случае мы из 1 вывели бы, что В верно, но это противоречит предпосылке в 12.

Следовательно, заключение «А ложно» правильно.

Обратно, пусть справедливо 12. Докажем, что тогда имеет место 1:

Правильно ли такое заключение, не должно ли стоять в нем «В ложно»? Если бы это было так, то из 12 мы бы вывели, что А ложно в противоречие с предпосылкой 1. Следовательно, заключение «В верно» является правильным.

Формы 11 и 12 позволяют подойти к пониманию природы косвенного доказательства. Предположим, что мы желаем установить справедливость утверждения «если А, то В». Прямое доказательство заключается в следующем: утверждение Л предполагается верным, и из него выводится утверждение В. Рассматривая мы видим, что можно также дать доказательство, допуская одновременную верность А и ложность В и выводя из этих предпосылок противоречие. Этот метод называется методом доказательства от противного; он является одним из способов косвенного доказательства. Доказательство от противного можно отличить по допущениям, с которых начинается рассуждение: они содержат предположения сложности доказываемого утверждения. Косвенные доказательства можно отличить также по фразе, завершающей доказательство, которая обычно звучит примерно так: «...таким образом, мы пришли к противоречию, что и доказывает теорему».

Еще одна общая схема косвенного доказательства подсказывается формой 12. Именно для доказательства справедливости утверждения «если А, то В» мы можем предположить ложность В и вывести отсюда ложность А.

Вот три типа доказательства, о которых мы здесь говорили:

предполагается А, выводится В (прямое доказательство);

предполагается А и «не В» (т. е. истинность А и ложность откуда выводится противоречие (вариант косвенного доказательства — доказательство от противного);

предполагается ложность В (истинность «не В»), откуда и выводится ложность А (другой вариант косвенного доказательства).

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

Рассмотрим, далее, второй вид математических предложений, отмеченный в начале этого параграфа;

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

Подобно тому, как это было сделано выше, здесь можно указать различныеэквивалентныеформы выражения «если А, то В, и обратно»:

В влечет А, и обратно;

А есть необходимое и достаточное условие для В;

В есть необходимое и достаточное условие для А;

утверждения А и В эквивалентны.

Все эти утверждения выражают в точности одно и то же.

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

1) предполагается А выводится В;

2) предполагается В, выводится А.

Распространена также следующая схема:

1) предполагается А, выводится В;

2) А предполагается ложным, выводится, что В ложно.

В сложных доказательствах эти схемы часто комбинируются. Доказательство утверждения «если А, то F» может быть проведенопосредством доказательства цепочки утверждений: «если А, то В», «если В, то С», «если С, то D», «если Д то В», «если В, то F». Здесь каждое утверждение влечет следующее. Далее, если одним из указанных выше методов может быть установлено не только любое из этих утверждений, но также и обратное к нему, то будет справедлива также следующая цепочка умозаключений: «если F, то то В», «если В, то D», «если Д то С», «если С, то В», «если В, то А». Таким образом, обратное к исходному утверждение «если F, то А» тоже справедливо. Именно это имеется в виду, когда говорится, что «обратное утверждение может быть доказано с помощью обращения каждого из сделанных шагов».

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

Упражнения

1. Доказать, что утверждение «если четно, то четны» ложно.

2. Какие из следующих утверждений верны и какие ложны? Несократимая дробь может быть представлена в виде конечной десятичной дроби:

а) тогда и только тогда, когда b не делится ни на какое простое число, отличное от 2;

б) если b не делится ни на какое простое число, отличное от 2;

в) только тогда, когда b не делится ни на какое простое число, отличное от 2;

г) тогда и только тогда, когда b не делится на 3;

д) если b не делится на 3;

е) только тогда, когда b не делится на 3.

3. Какие из следующих утверждений верны и какие ложны? Рациональное число может быть представлено в виде конечной десятичной дроби:

а) тогда и только тогда, когда b не имеет других простых делителей, кроме 2 и 5;

б) если b не имеет других простых делителей, кроме 2 и 5;

в) только тогда, когда b не имеет других простых делителей, кроме 2 и 5.

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

4. В одной недавно вышедшей книге по алгебре фигурирует в качестве аксиомы следующее утверждение: только тогда, когда или Переформулировать это утверждение в виде «если А, то В».

5. а) Доказать, что если (бета) — рациональное исло, то число тоже рационально; б) доказывает ли это, что если иррационально, то иррационально?