Рассуждении от противного

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

Приведенная схема может быть записана на языке формул:

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

Это правило и обосновывает возможность использования метода от противного.

Заметим, что посылку правила можно записать и так: ~Р —> (С л 1Q.

Таким образом, вместо того чтобы доказывать предложение Р, можно доказать предложение ~Р —>(С д! С). На первый взгляд кажется, что доказательство предложения Р мы заменяем на доказательство более сложного по структуре предложения. Однако второе утверждение бывает доказать проще. Разберемся, в чем здесь дело.

Дело в том, что при доказательстве Р в качестве исходных предложений (из которых можно выводить первые следствия) выступают лишь ранее доказанные теоремы или аксиомы. При доказательстве же импликации ~Р —> (С л! С) мы имеем право использовать предложение 1Р, из которого можно выводить следствия.

Пример 5.4.1. Докажем теорему Р: «Касательная к окружности перпендикулярна радиусу, проведенному в точку касания».

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

что если расстояние от центра окружности до прямой меньше радиуса, то эта прямая имеет две общие точки с окружностью.

Теперь докажем сформулированную теорему. Предположим противное. Пусть касательная к некоторой окружности с центром в точке О не перпендикулярна ее радиусу, проведенному в точку касания М (предложение 1Р). Проведем радиус окружности в точку М и опустим перпендикуляр из точку О на касательную. Длина перпендикуляра, то есть расстояние от центра окружности касательной, будет меньше длины радиуса ОМ. Значит, прямая пересекает окружность в двух точках (предложение С).

Из определения касательной вытекает, что касательная пересекает окружность в одной точке. Отсюда следует предложение: «Неверно, что касательная пересекает окружность в двух точках» (1C).

В этом случае говорят кратко: «Пришли в противоречие с определением касательной». Теорема доказана. •.

При построении отрицания к теореме мы, возможно неосознанно, сформулировали теорему, выделив в ней условие и заключение: «Если прямая является касательной к окружности, то она перпендикулярна радиусу, проведенному в точку касания». Так как предложение имеет вид импликации Л-«/?, то отрицание к нему выражается формулой АлВ.

Когда теорема имеет вид то в качестве условия выступает только предложение А. После того как мы построим отрицание к теореме, получим уже два предложения А и 1Z?, из которых можно выводить следствия.

В качестве предложения С, с которым ищется противоречие, может выступать любое предложение. Например, С и 1с оба могут быть выведены при доказательстве теоремы. Часто в качестве С выбирают ранее доказанную теорему (так как С истинно, то его можно вывести в любом доказательстве). В этом случае из предположения требуется вывести отрицание ~|С.

Пример 5.4.2. Докажем, что уравнение 2^х = 6 не имеет рациональных корней. Другими словами, число log₂ 6 иррациональное.

Методом от противного докажем, что уравнение не имеет положительных решений. То, что уравнение не имеет неположительных решений, следует из свойств степеней: при, т<0 степень 2^х не превосходит 1.

Итак, требуется доказать утверждение Р = «Уравнение 2^Л = 6 нс имеет положительных рациональных корней».

Построим отрицание 1р = «Уравнение имеет хотя бы один положительный рациональный корень». Выведем отсюда следствия.

Представим существующий по предположению рациональный корень уравнения 2^х = 6 в виде несократимой дроби —, где п и т — натуральные.

т

п

числа. Тогда 2^т =6, откуда по свойствам степеней 2″ = 6^т. Разложим левую и правую части на простые множители, получим 2″ = 2^т • 3″ '. Получаем, что одно и то же натуральное число имеет два различных разложения на простые множители, что противоречит известной теореме.

Здесь в качестве предложения С выступает теорема, сформулированная в примере 4.2.9. Доказательство этой теоремы дается в курсе теории чисел. Итак, с одной стороны, верно С, с другой стороны, мы вывели его отрицание, так как нашли натуральное число, большее 1, которое имеет два различных разложения на простые множители. Полученное противоречие и доказывает исходную теорему. •.

При доказательстве от противного также случается, что из отрицания к импликации выводят ~л. Значит, с одной стороны, верно А (как условие), с другой стороны, выведено ~А. В этом случае говорят, что пришли в противоречие с условием теоремы (в качестве С здесь выступает условие А). Заметим, что если из 1# вывести 1А, то отсюда сразу можно заключить, что из А следует В по правилу контрапозиции. Поэтому применение правила контрапозиции — это тоже своего рода рассуждения от противного.

Пример 5.4.3. Докажем утверждение: «Если число нечетное, то оно не делится на 4». Оно имеет вид импликации А—>В.

Можно рассуждать так. «Предположим противное. Пусть число нечетное и делится на 4 (предложение Ал]В). Обозначим это число буквой д;. Так как х четное, то х=4п, где п — целое. Тогда х = 2(2п) = 2 т, где т=2п — целое. Итак, х — четное число (предложение ~U). Пришли в противоречие с условием А. Следовательно, исходное предложение доказано».

Однако для доказательства утверждения можно просто применить правило контрапозиции, переформулировав исходное предложение в виде: «Если число делится на 4, то оно четное». Полученное предложение выводится прямым путем: предполагается, что число делится на 4, откуда следует, что оно является четным (см. пример 5.1.9). •.

Замечание. Доказать импликацию А—>В означает доказать, что она истинна при всех значениях переменных, от которых зависят А и В. Пусть А и В зависят от переменной х. Так как отрицание к формуле V* (А (х)—>В (х))

равносильно формуле Зд; (Л (х)л|Я (л;)), то при выводе следствий из предположения выбирают существующий объект л: (он может быть обозначен и другой буквой), для которого верны А и ~В, и рассуждают, понимая под х именно этот объект. Поэтому в примере 5.4.3 формулировку предположения можно уточнить: «Пусть существует нечетное число, делящееся на 4».

Рассмотрим случай, когда доказываемое предложение Р утверждает существование объекта, обладающего некоторым свойством А (Р = Злг А (х)). Для доказательства Р можно предположить, что Р неверно: «Ни один объект д: не обладает свойством А», и вывести отсюда два предложения С и 1C.

Пример 5.4.4. Пусть имеются 5 ящиков, в которые произвольным образом раскладываются 16 предметов. Докажем, что найдется хотя бы один ящик, в котором будет находиться нс менее четырех предметов.

Предположим противное. Построим отрицание к доказываемому предложению: «В каждом ящике лежит менее четырех предметов». Значит, в любом из 5 ящиков находится максимум 3 предмета. Поэтому всего имеем максимум 15 предметов.

Из условия следует, что число разложенных предметов больше 15 (это предложение С). А из рассуждений получилось, что число предметов не превосходит 15 (это предложение 1C). Имеем противоречие. •.

Методом от противного можно доказать утверждение из примера 5.2.2. Кратко рассмотрим схему такого доказательства.

Требуется доказать предложение Р = «Существует число, записанное одними единицами, которое делится на 23». Предполагаем, что ни одно из чисел, записанных одними единицами, не делится на 23 (предложение 1Р).

Рассмотрим последовательность чисел 1; 11; 111; …; 11…1, каждое из.

которых разделим на 23 с остатком. Так как среди данных чисел нет кратных 23 (следует из предположения), то возможны следующие остатки: 1,2, …, 22. Значит, среди 23 чисел по крайней мере два числа имеют одинаковый остаток. Поэтому разность этих чисел делится на 23. Но разность есть число вида 11… 10… О, которое равно 11… I • 10', поэтому число 11… 1 делится на 23. Итак, нашлось число, записанное одними единицами, которое делится на 23 (предложение Р). Получаем противоречие.

В приведенном выше рассуждении в качестве С выступило исходное предложение Р (или 1Р). Тем самым вместо прямого доказательства предложения Р была доказана истинность импликации ~Р—>Р.

Иногда методом от противного доказывают теоремы единственности. Пусть требуется доказать, что свойством А обладает не более чем один объект: V. rVy [(А (х)лА (у)) —> (х=у)].

Рассуждения можно провести примерно так. Предполагают, что свойством А обладают объекты х и у, при этом х*у. Далее выводят следствия и получают противоречие.

Однако часто подобные рассуждения без существенных изменений можно провести без предположения о том, что х и у различны, то есть предполагать противное нс обязательно. Лучше взять произвольные объекты х иy_t такие, что А{х) и А (у), и показать, что они равны (см. пример 5.2.4).

Рассмотрим еще одну ситуацию. Пусть требуется доказать предложение В. При этом известно, что если В неверно, то верно некоторое предложение А (то сеть верна импликация 1В—>А). Поэтому можно из А вывести противоречие; это и будет означать, что предложение В верно.

Очень часто в доказательствах используется утверждение о том, что среди двух или более предложений хотя бы одно истинно. Так как формула АуВ равносильна 1#->Л, то для доказательства В достаточно из А вывести противоречие, то есть показать, что А неверно. Здесь используется так называемое правило исключения случая:

Эти рассуждения нетрудно обобщить, взяв вместо одного исключаемого случая А два или более.

Пусть известно, что выполняется хотя бы одно из трех утверждений Л, А₂ или В, то есть верна дизъюнкция A_tvA₂vB (другими словами, верна импликация 1 В —> (A]V А₂)). Если будет доказано, что из каждого предложения А и А₂ вытекает противоречие, то есть предложения А и А₂ ложны, то отсюда можно будет заключить, что предложение В верно. Мы применили следующее правило исключения случаев:

Пример 5.4.5. Решим уравнение 3*+ 4^х = 25.

Очевидно, что х=2 является корнем уравнения. Докажем, что других корней нет. Надо показать следующее: если число является корнем данного уравнения, то это число равно 2. Применим метод исключения случаев.

Пусть а — корень данного уравнения. Тогда 3^Й+4^Й = 25. Возможны только три случая: а<2, а>2, а=2.

Если а<2, то по свойствам степеней 3^й < З² и 4^й < 4². Значит, 3^й + 4″ < 25. Противоречие.

Если а>2, то 3^й > З² и 4^й > 4². Поэтому 3^й + 4^й > 25. Противоречие.

Следовательно, число а равно 2.

Итак, х=2 — единственный корень уравнения 3^х + 4^х = 25.

При доказательстве было использовано предыдущее правило вывода. Здесь А, = (а<2), А₂ = (а>2), В = (а=2). В качестве С мы взяли предположение: «а есть корень уравнения 3^х + 4^Л = 25». Вначале было доказано предложение А —> (С д1С), затем А₂ —> (С a]Q. Отсюда сделали вывод о том, что верно В.

Доказательство, конечно, можно оформить, сразу предположив противное. Тогда рассуждения можно было начать так: «Предположим, что существует корень уравнения, не равный 2. Обозначим его буквой а. Тогда а<2 или а>2…». •.