Доказать методы от противного примеры из жизни. Логика и доказательство. Доказательство: прямое, обратное, от противного. Метод математической индукции

Ложен, мы тем самым обосновываем истинность противоположного ему положения - тезиса. Напр., врач, убеждая пациента в том, что тот не болен гриппом, может рассуждать следующим образом: «Если бы вы действительно были больны гриппом, то у вас была бы повышена температура, был заложен нос и т.д. Но ничего этого нет. Следовательно, нет и гриппа». Доказательство некоторого положения от противного - это истинности данного положения, опирающееся на демонстрацию ложности «противного» (противоречащего) положения и исключенного третьего.
Общая Д. от п. описывается следующим образом. Нужно доказать некоторое А. В процессе доказательства сначала формулируется противоположное ему высказывание не-А и предполагается, что истинно: допустим, что А ложно, тогда должно быть истинно не-А. Затем из этого якобы истинного антитезиса выводятся следствия - до тех пор, пока либо не получится , либо такое , которое явным образом противоречит известному истинному высказыванию. Если показано, что не-А ложно, то тем самым обоснована истинность тезиса А (см. ДОКАЗАТЕЛЬСТВО).

Философия: Энциклопедический словарь. - М.: Гардарики . Под редакцией А.А. Ивина . 2004 .

(лат. reduc-tio ad absurdum) , вид доказательства, при кром «доказывание» некоторого суждения (тезиса доказательства) осуществляется через противоречащего ему суждения - антитезиса. Опровержение антитезиса при этом достигается установлением факта его несовместимости с к.-л. заведомо истинным суждением. Этой форме Д. от п. соответствует след. схема доказательства: если В истинно и из А следует ложность В, то А - ложно. Другая, более общая Д. от п. - это путём опровержения (обоснования ложности) антитезиса по правилу: допустив А, вывели , следовательно - не-А. Здесь А может быть как утвердительным, так и отрицательным суждением. В последнем случае Д. от п. опирается на и закон двойного отрицания. Помимо указанных выше, существует «парадоксальная» форма Д. от п., применявшаяся уже в «Началах» Евклида: А можно считать доказанным, если удастся показать, что А следует даже из допущения ложности А.

Философский энциклопедический словарь. - М.: Советская энциклопедия . Гл. редакция: Л. Ф. Ильичёв, П. Н. Федосеев, С. М. Ковалёв, В. Г. Панов . 1983 .

ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО

Лит.: Тарский Α., Введение в логику и методологию дедуктивных наук, пер. с англ., М., 1948; Асмус В. Ф., Учение логики о доказательстве и опровержении, [М.], 1954; Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; Чёрч Α., Введение в математич. логику, пер. с англ., [т.] 1, М., 1960.

Философская Энциклопедия. В 5-х т. - М.: Советская энциклопедия . Под редакцией Ф. В. Константинова . 1960-1970 .

Смотреть что такое "ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО" в других словарях:

- (proof by contradiction) Доказательство, при котором признание исходной предпосылки неверной ведет к противоречию. То есть предположение об ошибочности исходной посылки позволяет одновременно и доказать какое либо утверждение, и опровергнуть его; … Экономический словарь

Один из видов косвенного доказательства … Большой Энциклопедический словарь

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете … Википедия

Один из видов косвенного доказательства. * * * ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО, один из видов косвенного доказательства (см. КОСВЕННОЕ ДОКАЗАТЕЛЬСТВО) … Энциклопедический словарь

Доказательство от противного - (лат. reduction ad absurdum) вид доказательства, при котором справедливость некоторого суждения (тезиса доказательства) осуществляется через опровержение противоречащего ему суждения антитезиса. Опровержение антитезиса достигается путем… … Исследовательская деятельность. Словарь

ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО - (лат. reductio ad absurdum) вид доказательства, при котором справедливость некоторого суждения (тезиса доказательства) осуществляется через опровержение противоречащего ему суждения антитезиса. Опровержение антитезиса достигается путем… … Профессиональное образование. Словарь

См.: Косвенное доказательство … Словарь терминов логики

- (лат. reductio ad absurdum) вид Доказательства, при котором «доказывание» некоторого суждения (тезиса доказательства) осуществляется через опровержение противоречащего ему суждения антитезиса. Опровержение антитезиса при этом достигается… … Большая советская энциклопедия

лат. reductio ad absurdum) - вид доказательства, при котором справедливость некоторого суждения (тезиса доказательства) осуществляется через опровержение противоречащего ему суждения - антитезиса. Опровержение антитезиса достигается путем установления его несовместимости с заведомо истинным суждением. Часто доказательство от противного опирается на двузначности принцип.

Отличное определение

Неполное определение ↓

ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО

обоснование суждения путем опровержения методом "приведения к нелепости" (reductio ad absurdum) нек-рого другого суждения, – именно того, к-рое является отрицанием обосновываемого (Д. от п. 1-го вида) или того, отрицанием к-рого является обосновываемое (Д. от п. 2-го вида); "приведение к нелепости" состоит в том, что из опровергаемого суждения выводится к.-л. явно ложное заключение (напр., формальнологическое противоречие), что и свидетельствует о ложности этого суждения. Необходимость различения двух видов Д. от п. вытекает из того, что в одном из них (именно, в Д. от п. 1-го вида) имеет место логический переход от двойного отрицания суждения к утверждению этого суждения (т.е. применяется т.н. правило снятия двойного отрицания, разрешающее переход от A к А, см. Двойного отрицания законы), в то время как в другом такого перехода нет. Ход рассуждения в Д. от п. 1-го вида: требуется доказать суждение А; в целях доказательства предполагаем, что суждение А неверно, т.е. что верно его отрицание: ? (не-А), и, опираясь на это предположение, логически выводим к.-л. ложное суждение, напр. противоречие, – осуществляем "приведение к нелепости" суждения А; это свидетельствует о ложности нашего предположения, т.е. доказывает, истинность двойного отрицания: A; применение к A правила снятия двойного отрицания завершает доказательство суждения А. Ход рассуждения в Д. от п. 2-го вида: требуется доказать суждение?; в целях доказательства предполагаем верным суждение А и приводим это предположение к нелепости; на этом основании заключаем, что А ложно, т.е. что верно?. Различение двух видов Д. от п. важно потому, что в так называемой интуиционистской (конструктивной) логике закон снятия двойного отрицания не имеет места, в силу чего не допускаются и Д. от п., существенно связанные с применением этого логического закона. См. также Косвенное доказательство. Лит.: Тарский?., Введение в логику и методологию дедуктивных наук, пер. с англ., М., 1948; Асмус В. Ф., Учение логики о доказательстве и опровержении, [М.], 1954; Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; Черч?., Введение в математич. логику, пер. с англ., [т.] 1, М., 1960.

В толковом словаре математических терминов дано определение доказательству от противного теоремы, противоположной обратной теореме. «Доказательство от противного – метод доказательства теоремы (предложения), состоящий в том, что доказывают не саму теорему, а ей равносильную (эквивалентную), противоположную обратной (обратную противоположной) теорему. Доказательство от противного используют всякий раз, когда прямую теорему доказать трудно, а противоположную обратной легче. При доказательстве от противного заключение теоремы заменяется её отрицанием, и путём рассуждения приходят к отрицанию условия, т.е. к противоречию, к противному (противоположному тому, что дано; это приведение к абсурду и доказывает теорему».

Доказательство от противного очень часто применяется в математике. Доказательство от противного основано на законе исключённого третьего, заключающегося в том, что из двух высказываний (утверждений) А и А (отрицание А) одно из них истинно, а другое ложно». /Толковый словарь математических терминов: Пособие для учителей/О. В. Мантуров [и др.]; под ред. В. А. Диткина.- М.: Просвещение, 1965.- 539 с.: ил.-C.112/.

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

Заслуживает особого внимания и характеристика отношения друг к другу прямой и обратной ей теорем. «Обратная теорема для данной теоремы (или к данной теореме) — теорема, в которой условием является заключение, а заключением – условие данной теоремы. Данная теорема по отношению к обратной теореме называется прямой теоремой (исходной). В то же время обратная теорема к обратной теореме будет данной теоремой; поэтому прямая и обратная теоремы называются взаимно обратными. Если прямая (данная) теорема верна, то обратная теорема не всегда верна. Например, если четырёхугольник – ромб, то его диагонали взаимно перпендикулярны (прямая теорема). Если в четырёхугольнике диагонали взаимно перпендикулярны, то четырёхугольник есть ромб – это неверно, т. е. обратная теорема неверна». /Толковый словарь математических терминов: Пособие для учителей/О. В. Мантуров [и др.]; под ред. В. А. Диткина.- М.: Просвещение, 1965.- 539 с.: ил.-C.261 /.

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

Допустим, что на примете имеется прямая теорема, которую доказать обычным математическим методом можно, но трудно. Сформулируем её в общем виде в краткой форме так: из А следует Е . Символ А имеет значение данного условия теоремы, принятого без доказательства. Символ Е имеет значение заключения теоремы, которое требуется доказать.

Доказывать прямую теорему будем от противного, логическим методом. Логическим методом доказывается теорема, которая имеет не математическое условие, а логическое условие. Его можно получить, если математическое условие теоремы из А следует Е , дополнить прямо противоположным условием из А не следует Е .

В результате получилось логическое противоречивое условие новой теоремы, заключающее в себе две части: из А следует Е и из А не следует Е . Полученное условие новой теоремы соответствует логическому закону исключённого третьего и соответствует доказательству теоремы методом от противного.

Согласно закону, одна часть противоречивого условия является ложной, другая его часть является истинной, а третье – исключено. Доказательство от противного имеет совей задачей и целью установить, именно какая часть из двух частей условия теоремы является ложной. Как только будет определена ложная часть условия, так будет установлено, что другая часть является истинной частью, а третье — исключено.

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

Дано: из А следует Е и из А не следует Е .

Доказать: из А следует Е .

Доказательство : Логическое условие теоремы заключает в себе противоречие, которое требует своего разрешения. Противоречие условия должно найти своё разрешение в доказательстве и его результате. Результат оказывается ложным при безупречном и безошибочном рассуждении. Причиной ложного заключения при логически правильном рассуждении может быть только противоречивое условие: из А следует Е и из А не следует Е .

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

Следовательно, прямую теорему методом от противного доказать невозможно.

Теперь эту же прямую теорему докажем обычным математическим методом.

Дано: А .

Доказать: из А следует Е .

Доказательство.

1. Из А следует Б

2. Из Б следует В (по ранее доказанной теореме)).

3. Из В следует Г (по ранее доказанной теореме).

4. Из Г следует Д (по ранее доказанной теореме).

5. Из Д следует Е (по ранее доказанной теореме).

На основании закона транзитивности, из А следует Е . Прямая теорема доказана обычным методом.

Пусть доказанная прямая теорема имеет правильную обратную теорему: из Е следует А .

Докажем её обычным математическим методом. Доказательство обратной теоремы можно выразить в символической форме в виде алгоритма математических операций.

Дано: Е

Доказать: из Е следует А .

Доказательство.

!. Из Е следует Д

1. Из Д следует Г (по ранее доказанной обратной теореме).

2. Из Г следует В (по ранее доказанной обратной теореме).

3. Из В не следует Б (обратная теорема неверна). Поэтому и из Б не следует А .

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

Чтобы её доказать методом от противного, требуется заменить её математическое условие логическим противоречивым условием, заключающим в себе по смыслу две части – ложную и истинную.

Обратная теорема утверждает: из Е не следует А . Её условие Е , из которое следует заключение А , является результатом доказательства прямой теоремы обычным математическим методом. Это условие необходимо сохранить и дополнить утверждением из Е следует А . В результате дополнения получается противоречивое условие новой обратной теоремы: из Е следует А и из Е не следует А . Исходя из этого логически противоречивого условия, обратную теорему можно доказать посредством правильного логического рассуждения только, и только, логическим методом от противного. В доказательстве от противного любые математические действия и операции подчинены логическим и поэтому в счёт не идут.

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

Доказываем посредством правильного логического рассуждения и обнаруживаем, что его результатом является ложное, абсурдное заключение. Причиной ложного логического заключения является противоречивое логическое условие теоремы, заключающее в себе две части – ложную и истинную. Ложной частью может быть только утверждение из Е не следует А , в котором Е было принято без доказательства. Именно этим оно отличается от Е утверждения из Е следует А , которое доказано доказательством прямой теоремы.

Следовательно, истинным является утверждение: из Е следует А , что и требовалось доказать.

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

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

Другими словами, Герхард Фрей предположил, что уравнение большой теоремы Ферма x n + y n = z n , где n > 2 , имеет решения в целых положительных числах. Этими же решения являются, по предположению Фрея, решениями его уравнения
y 2 + x (x — a n) (y + b n) = 0 , которое задаётся его эллиптической кривой.

Эндрю Уайлс принял эту замечательную находку Фрея и с её помощью посредством математического метода доказал, что этой находки, то есть эллиптической кривой Фрея, не существует. Поэтому не существует уравнения и его решений, которые задаются несуществующей эллиптической кривой, Поэтому Уайлсу следовало бы принять вывод о том, что не существует уравнения большой теоремы Ферма и самой теоремы Ферма. Однако им принимается более скромное заключение том, что уравнение большой теоремы Ферма не имеет решений в целых положительных числах.

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

В большой теореме Ферма утверждается, что уравнение, x n + y n = z n , где n > 2

Согласно логическому методу доказательства от противного, это утверждение сохраняется, принимается как данное без доказательства, и затем дополняется противоположным по смыслу утверждением: уравнение x n + y n = z n , где n > 2 , имеет решения в целых положительных числах.

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

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

Однако в ходе логически правильного рассуждения не было обнаружено ни одного признака, по которому можно было бы установить, какое именно утверждение является ложным. Им может быть утверждение: уравнение x n + y n = z n , где n > 2 , имеет решений в целых положительных числах. На этом же основании им может быть утверждение: уравнение x n + y n = z n , где n > 2 , не имеет решений в целых положительных числах.

В итоге рассуждения вывод может быть только один: большую теорему Ферма методом от противного доказать невозможно .

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

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

Методом от противного невозможно доказать ни того, что уравнение большой теоремы Ферма не имеет решений, ни того, что оно имеет решения. Ошибка Уайлса не математическая, а логическая — использование доказательства от противного там, где его использование не имеет смысла и большой теоремы Ферма не доказывает.

Не доказывается большая теорема Ферма и с помощью обычного математического метода, если в ней дано : уравнение x n + y n = z n , где n > 2 , не имеет решений в целых положительных числах, и если в ней требуется доказать : уравнение x n + y n = z n , где n > 2 , не имеет решений в целых положительных числах. В такой форме имеется не теорема, а тавтология, лишённая смысла.

МЕТОД ОТ ПРОТИВНОГО (далее МОП) - научно-прикладной метод, названный по имени выдающегося украинского просветителя, основателя целого ряда научных школ и направлений Василия Козьмича Противного. В.К.Противный родился 29 февраля 1513 г по старому стилю в селе Нижние Лопухи близ Чернигова. Вася с детства был слабым и хлипким мальчиком и постоянно, начиная с детского сада, подвергался насмешкам сверстников, что в дальнейшем предопределило его скверный характер.

В дальнейшем слова "делать все назло окружающим" фактически стали девизом жизни В.К.Противного. Так, назло всем он покинул родные Холмогоры и поступил в МГУ им. Ломоносова (а не в суворовское училище, как хотел его отец), назло всем никогда ни на ком не женился (хотя его бабушка Василиса Противная нашла ему за всю жизнь как минимум 14 невест), назло всем, сославшись на грибной сезон, не стал получать медаль Филдса - высшую награду в области математики.

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

Многие ученые, философы, исследователи и даже деятели искусств стали ярыми приверженцами идей украинского просветителя. Например, так впервые в медицинской практике была использована лоботомия, когда была сделана попытка разрешить извечный философский спор о первичности материи или сознания с помощью медицинского эксперимента. Так ученик В.К.Противного Лобачевский создал неевклидову геометрию, так его почитатель Чайковский написал гимн альтернативной любви - вальс "Голубой Дунай", и так далее.

Метод от Противного часто применяется в настоящее время в самых разных областях человеческой жизни. Например, для воспитания художественного вкуса москвичей им с успехом пользуется московский мэр Лужков, устанавливая в городе скульптуры Церетели. Руководство ГУВД, пользуясь этим методом, решило найти убийц известной журналистки Политковской, так как другие методы в виду особой сложности дела результатов не дают. Вооруженные МОП московские милиционеры знают - последовательно выявив всех непричастных, они автоматически выйдут на след убийц.

Вся жизнь и даже смерть В.К.Противного явилась яркой иллюстрацией его метода. Ученый трагически ушел из жизни 29 февраля 1613 г в возрасте 112 лет, повесившись назло своей бабушке Василисе Противной, не давшей Василию Козьмичу попробовать варенье из холодильника. Несмотря на двоякое отношение к В.К.Противному из-за его скверного характера, большинство ученых и исследователей все-таки считают МОП одним из наиболее мощных орудий современной науки в целом и математики в частности.
____________________________________

Василий Козьмич Противный, выдающийся украинский просветитель (1513 - 1613)

Выражаю благодарность

Практическое занятие № 2

Тема: Логика и доказательство. Доказательство: прямое, обратное, от противного. Метод математической индукции.

Занятие рассчитано на 2 академ. часа.

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

Теоретический материал

Методы доказательств

При доказательстве теорем применяется логическая аргументация. Доказательства в информатике  неотъемлемая часть проверки корректности алгоритмов. Необходимость доказательства возникает, когда нам нужно установить истинность высказывания вида (А  В). Существует несколько стандартных типов доказательств, включающих следующие:

Прямое рассуждение (доказательство).

Предполагаем, что высказывание А истинно и показываем справедливость В. Такой способ доказательства исключает ситуацию, когда A истинно, a B  ложно, поскольку именно в этом и только в этом случае импликация (А  В) принимает ложное значение (см. табл).

Таким образом, прямое доказательство идет от рассмотрения аргументов к доказательству тезиса, т. е. истинность тезиса непосредственно обосновывается аргументами. Схема этого доказательства такая: из данных аргументов (а, b, с, ...) необходимо следует доказываемый тезис q.

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

Примеры:

1. Учитель на уроке при прямом доказательстве тезиса “Народ  творец истории”, показывает; во-первых , что народ является создателем материальных благ, во-вторых , обосновывает огромную роль народных масс в политике, разъясняет, как в современную эпоху народ ведет активную борьбу за мир и демократию, в-третьих , раскрывает его большую роль в создании духовной культуры.

2. На уроках химии прямое доказательство о горючести сахара может быть представлено в форме категорического силлогизма: Все углеводы - горючи. Сахар - углевод. Сахар горюч.

В современном журнале мод “Бурда” тезис “Зависть - корень всех зол” обосновывается с помощью прямого доказательства следующими аргументами: “Зависть не только отравляет людям повседневную жизнь, но может привести и к более серьезным последствиям, поэтому наряду с ревностью, злобой и ненавистью, несомненно, относится к самым плохим чертам характера. Подкравшись незаметно, зависть ранит больно и глубоко. Человек завидует благополучию других, мучается от сознания того, что кому-то больше повезло”".

2. Обратное рассуждение (доказательство ) . Предполагаем, что высказывание В ложно и показываем ошибочность А. То есть, фактически, прямым способом проверяем истинность импликации ((не В)  (не А)), что согласно таблицы, логически эквивалентно истинности исходного утверждения (А  В).

3. Метод «от противного».

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

Примеров доказательства “от противного” очень много в школьном курсе математики. Так, пример, доказывается теорема о том, что из точки, лежащей вне прямой, на эту прямую можно опустить лишь один перпендикуляр. Методом “от противного” доказывается и следующая теорема: “Если две прямые перпендикулярны к одной и той же плоскости, то они параллельны”. Доказательство этой теоремы пpямо начинается словами: “Предположим противное, т. е. что прямые АВ и CD не параллельны”.

Математическая индукция

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

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

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

Принцип математической индукции  это следующая теорема:

Пусть мы имеем бесконечную последовательность утверждений P 1 , P 2 , ..., P n занумерованных натуральными числами, причём: утверждение P 1  истинно; если некоторое утверждение P k  истинно, то следующее утверждение P k +1 тоже истинно.

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

Другими словами принцип математической индукции можно сформулировать так: если в очереди первой стоит женщина, и за каждой женщиной стоит женщина, то все в очереди женщины.

Способ рассуждений, основанный на принципе математической индукции называется методом математической индукции. Для решения задач методом математической индукции необходимо:

1) сформулировать утверждение задачи в виде последовательности утверждений P 1 , P 2 , ..., P n , ... ;

2) доказать, что утверждение P 1 истинно (этот этап называется базой индукции); 3) доказать, что если утверждение P n истинно при некотором n= k, то оно истинно и при n = k + 1 (этот этап называется шагом индукции).

Ввиду недостоверности заключения индукция не может служить методом доказательства. Но она является мощным эвристическим методом , т. е. методом открытия новых истин.

Индукция может привести к ложному заключению. Так, например, вычисляя значения выражения n 2 +n+17 при n = 1,2,3, ..., 15, мы получаем неизменно простые числа, и это наводит на мысль, что значение этого выражения при любом натуральном n есть простое число. Иначе говоря, на основании пятнадцати частных посылок получено общее заключение, относящееся к бесконечному множеству частных случаев, и это заключение оказывается ложным, так как уже при n = 16 получаем составное число 16 2 +16+17=172.

В истории математики были случаи, когда известные математики ошибались в своих индуктивных выводах. Например, П. Ферма предположил, что все числа вида 22 n + 1 простые, исходя из того, что при n = 1,2,3,4 они являются таковыми, но Л. Эйлер нашел, что уже при n = 5 число 232+ 1 не является простым (оно делится на 641). Однако возможность получения с помощью индукции ложного заключения не является основанием для отрицания роли индукции в школьном обучении математике.

Методические указания

Пример 1: Покажите прямым способом рассуждений, что произведение ху двух нечетных целых чисел х и у всегда нечетно.

Решение. Любое нечетное число, и в частности х, можно записать в виде х = 2 m + 1, где m  Z . Аналогично, у = 2 n + 1, n  Z .

Значит, произведение ху = (2 m + 1)(2 n + 1) = 4mn + 2m + 2n + 1 = 2(2 mn + m + n ) + 1 тоже является нечетным числом.

Пример 2: Пусть n  N . Покажите, используя обратный способ доказательства, что если n 2 нечетно, то и n нечетно.

Решение. Отрицанием высказывания о нечетности числа n 2 служит утверждение « n 2 четно», а высказывание о четности n является отрицанием утверждения «число n нечетно». Таким образом, нужно показать прямым способом рассуждений, что четность числа n влечет четность его квадрата n 2 .

Так как n четно, то n =2 m для какого-то целого числа m . Следовательно, n 2 = 4 m 2 = 2(2 m 2 ) четное число.

Пример 3: Методом «от противного» покажите, что решение уравнения х 2 = 2 является иррациональным числом, т. е. не может быть записано в виде дроби с целыми числителем и знаменателем.

Решение. Здесь нам следует допустить, что решение х уравнения х 2 = 2 рационально, т. е. записывается в виде дроби х = с целыми m и n , причем n  0. Предположив это, нам необходимо получить противоречие либо с предположением, либо с каким-то ранее доказанным фактом.

Как известно, рациональное число неоднозначно записывается

в виде дроби. Например, х = == и т.д. Однако можно считать, что m и n не имеют общих делителей. В этом случае неоднозначность записи пропадает.

Итак, предполагаем дополнительно, что дробь х = несократима (m и n не имеют общих делителей). По условию число х удовлетворяет уравнению х 2 = 2. Значит, () 2 = 2, откуда m 2 = 2 n 2 .

Из последнего равенства следует, что число m 2 четно. Следовательно, m тоже четно и может быть представлено в виде m = 2р для какого-то целого числа р. Подставив эту информацию в равенство m 2 = 2 n 2 , мы получим, что 4р 2 = 2 n 2 , т. е. n 2 = 2р 2 .

Но тогда n тоже является четным числом. Таким образом, мы показали, что как m , так и n  четные числа. Поэтому они обладают общим делителем 2. Если же теперь вспомнить, что мы предполагали отсутствие общего делителя у числителя и знаменателя дроби, то увидим явное противоречие.

Найденное противоречие приводит нас к однозначному выводу: решение уравнения х 2 = 2 не может быть рациональным числом, т. е. оно иррационально.

Пример 4: Докажем по индукции следующее равенство (которое, конечно, допускает и другие доказательства):

1 + 2 + 3 + ... + n = n(n + 1)/2.

База. При n = 1 равенство превращается в тождество 1 = 1·(1 + 1)/2.

Шаг. Пусть равенство выполнено при n = k: 1 + 2 + 3 + ... + k = k(k + 1)/2.

Прибавим к обеим частям этого равенства k + 1. В левой части мы получим сумму 1+2+3+...+k+(k+1), а в правой - k(k+1)/2+(k+1)=(k(k+1)+2(k+1))/2=((k+2)(k+1))/2.

Итак, 1 + 2 + 3 + ... + k + (k + 1) = (k + 1)(k + 2)/2, а это и есть требуемое равенство при n = k + 1, где n означает произвольное натуральное число.

Контрольные вопросы

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

Индивидуальные задания

1. Используя методы доказательства:

1) Прямым рассуждением докажите истинность высказывания: n и m четные числа  n + m число четное.

2) Дайте обратное доказательство высказывания: n 2 четное число  n четное.

3) Методом «от противного» докажите, что n + m нечетное число  одно из слагаемых является четным, а другое нечетным.

2. Докажите каждое из высказываний методом математической индукции.

1) 1 + 5 + 9 +…+(4 n - 3) = n (2 n  1) для всех натуральных чисел n .

2) 1 2 +2 2 +…+ n 2 = n (n +1)(2 n +1)/6 для всех натуральных чисел n .

3) д ля всех натуральных чисел n .

4) Число n 3  n делится на 3 при всех натуральных значениях числа n .

5) 1*1! + 2* 2!+…+- n * n ! = (n + 1)!  1 для всех натуральных чисел n .

(Символ n ! читается как « n факториал» и обозначает произведение всех натуральных чисел от 1 до n включительно: n ! = l *2*3*** (n  l )* n .)

Дополнительные задания:

1. Найдите ошибку в следующем «доказательстве» того, что все лошади одной масти.

Будем доказывать индукцией по n следующее утверждение: «В любом табуне из n это лошадей, все они одной масти». База (n = 1) очевидна: в этом случае все лошади - одна лошадь, она очевидно одной масти. Ш: пусть в любом табуне из k лошадей все лошади имеют одну масть. Рассмотрим табун из k + 1 лошади. Выберем в нём двух лошадей a и b и рассмотрим оставшиеся k 1 лошадь. Составим табун из этих оставшихся лошадей, добавив к ним a. В нём k лошадей, поэтому, по предположению индукции, все они одной масти. Значит, лошадь a имеет ту же масть, что и оставшиеся лошади. Аналогично доказывается, что ту же масть имеет лошадь b. Значит, все k + 1 лошадь имеют одинаковую масть. Утверждение доказано.

2. На бесконечном клетчатом листе бумаги 100 клеток закрашены в чёрный цвет, а все остальные в белый. За один ход разрешается перекрашивать в противоположный цвет любые четыре клетки, образующие квадрат 2x2. Докажите, что за несколько ходов можно добиться того, что все клетки окажутся белыми тогда и только тогда, когда любая горизонталь и любая вертикаль содержит чётное число чёрных клеток.