Решение от противного. Что такое метод доказательства «от противного

Часто при доказательстве теорем пользуются методом доказательства от противного . Суть этого метода помогает понять загадка. Попробуйте её разгадать.

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

Ответ. Осуждённый проглотил выбранную им бумажку. Чтобы установить, какой жребий ему выпал, судьи заглянули в оставшуюся бумажку. На ней было написано: «смерть». Это доказывало, что ему повезло, он вытащил бумажку, на которой было написано: «жизнь».

Как в случае, о котором рассказывает загадка, при доказательстве возможны только два случая: можно… или нельзя… Если удастся убедится, что первое невозможно (на бумажке, которая досталась судьям, написано: «смерть»), то сразу можно сделать вывод, что справедлива вторая возможность (на второй бумажке написано: «жизнь»).

Доказательство методом «от противного» осуществляется так.

1) Устанавливают, какие варианты в принципе возможны при решении задачи или доказательстве теоремы. Вариантов может быть два (например, перпендикулярны ли не перпендикулярны рассматриваемые прямые); вариантов ответа может быть три и больше (например, какой получается угол: острый, прямой или тупой).

2) Доказывают. Что не может выполняться ни один из тех вариантов, которые нам необходимо отбросит. (Например, если надо доказать, что прямые перпендикулярные, смотрим, что получается, если рассматривать не перпендикулярные прямые. Как правило, удаётся установить, что в этом случае какой-либо из выводов противоречит тому, что дано в условии, а потому невозможен.

3) На основании того, что все нежелательные выводы отброшены и только один (желательный) остался нерассмотренным, делаем вывод, что именно он верный.

Решим задачу, используя доказательство от противного.

Дано: прямые а и b такие, что любая прямая, которая пересекает а, пересекает и b.

Используя метод доказательства «от противного», доказать, что а ll b.

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

Возможны только два случая:

1) прямые а и b параллельны (жизнь);

2) прямые а и b не параллельны (смерть).

Если удастся исключить нежелательный случай, то останется сделать вывод, что имеет место второй из двух возможных. Чтобы отбросить нежелательный случай, давайте подумаем, что произойдёт, если прямые а и b пересекаются:

По условию любая прямая, которая пересекает а, пересекает и b. Поэтому, если удастся найти хотя бы одну прямую, которая пересекает а, но не пересекает b, этот случай надо будет отбросить. Таких прямых можно найти сколько угодно: достаточно провести через любую точку К прямой а, кроме точки М прямую КС, параллельную b:

Поскольку отброшен один из двух возможных случаев, можно сразу сделать вывод, что а ll b.

Остались вопросы? Не знаете, как доказать теорему?
Чтобы получить помощь репетитора – .
Первый урок – бесплатно!

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

Что такое метод доказательства «от противного»?

Суть метода доказательства от противного заключается в два этапах. Первое в доказательстве СУЩЕСТВОВАНИЯ самого доказательства и второе в доказательстве ЕДИНСТВЕННОСТИ доказания. Коряво описал, но хотел сказать следующее. При доказательстве теорем таким методом нужно показать, что существует решение данной задачи или теоремы, а затем доказать, что это решение будет единственное. Это не единственный метод применяемый в доказательстве теорем, но как математический и логический инструмент небезынтересный.

Метод доказательства от противного используется не только в математике, хотя там и получил довольно широкое распространение в качестве инструмента доказательства отдельных задач и теорем.

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

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

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

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

Данный закон основывается на законе двойного отрицания если не верно А, то А верно.

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

Стандартный прием, например, в математике. Нужно доказать утверждение А. А это трудно. Тогда берут прямо противоположное утверждение В, и доказывают, что оно неверно. Отсюда следует, что А - истинно. То же и в жизни. Простой пример: некто говорит: Мистер Х - вор. Его оппонент: Но как это доказать? Первый: Предположим, что он - честный человек. Второй: Да это же курам насмех!. Первый: Вот мы и доказали, что Х - вор :)))

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предполагаем, что высказывание А истинно и показываем справедливость В. Такой способ доказательства исключает ситуацию, когда 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. В чем разница между доказательством прямым рассуждением, обратным, от противного?
2. Что означает математическая индукция? Объясните принцип математической индукции.

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

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. Докажите, что за несколько ходов можно добиться того, что все клетки окажутся белыми тогда и только тогда, когда любая горизонталь и любая вертикаль содержит чётное число чёрных клеток.

Урок можно начать с рассказа учителя.

Ващенко Н.М., на уроке

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

Приведем примеры таких доказательств.

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

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

Пример 2. Врач после осмотра больного ребенка говорит:

«У ребенка нет кори. Если бы у него была корь, то тогда была бы сыпь на теле, но сыпи нет».

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

Задается вопрос: «В чем же сущность способа доказательства от противного?»- и вывешивается таблица (табл. 5).

Способом от противного можно решить уже известные до этого задачи.

1. Дано: а||b, прямые с и а пересекаются. Докажите: прямые с и b пересекаются.

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

1) Предположим, что b||с.

2) Тогда получается, что через точку О (точка пересечения прямых а и с) проходят две различные прямые а и b, которые параллельны прямой b.

3) Это противоречит аксиоме параллельных прямых.

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

2. Дано: A, В, С - точки прямой а, АВ = 5 см, АС = 2 см, ВС = 7 см. Докажите:

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

1) Предположим, что точка С лежит между точками А и В.

2) Тогда по аксиоме измерения отрезков АВ = АС + СВА

3) Это противоречит условию: АВ = АС + СВ, так как АВ = 5 см, АС+ С5 = 9 см.

Вывод: точка С не лежит между точками А и В.

3. Дано: АВ - полупрямая, С АВ, АС < АВ. Докажите:

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

1) Предположим, что точка В лежит между точками А и С.

2) Тогда по аксиоме измерения отрезков АВ + ВС = АС, т. е. AB

3) Это противоречит условию задачи: АС<АВ.

Вывод: точка В не лежит между точками А и С.

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

Карточка имеет вид:

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

Из предположения следует, что (на основании ……

Получаем противоречие с.

Значит, наше предположение неверно, а верно то, что требовалось доказать, т.е.

Задание на дом:

п. «Доказательство от противного» § 2 до слов: «Поясним это...».

1. Докажите, что если MN = 8 м, МК = 5 м, NK- 10 м, то точки М, N и К не лежат на одной прямой.

2. Докажите, что если <(ab) = 100°, <(be) - 120°, то луч с не проходит между сторонами угла (ab).

3. Докажите теорему 1.1 способом от противного.