Доказательство от противного в логике. Доказательство от противного — что представляет собой, когда используется
Доказательство от противного – мощный и часто используемый в математике метод. Предположив, что некоторый факт (объект) является истинным (существует), и придя к противоречию, мы заключаем, что факт ложен (объект не существует). Рассмотрим несколько примеров.
Теорема Евклида о бесконечности простых чисел является классическим и самым простым рассуждением от противного:
Не существует самого большого простого числа .
: Пусть это не так, и самое большое простое число существует. Построим число . Оно не делится ни на одно , и больше чем . Мы пришли к противоречию, следовательно, самого большого простого числа (как объекта!) не существует и простых чисел бесконечно много.
Заметим, что не обязательно простое, так как его простой множитель может находится между и , но всё равно будет большим .
Теорема об иррациональностиНе существует натуральных и , таких, что
.
: Пусть это не так. Сократим общие множители у , , и возведём всё в квадрат: . Отсюда следует, что является чётным числом, поэтому тоже чётно и представимо при помощи некоторого натурального , как . Подставляя в исходное соотношение, получаем , а, следовательно, и чётно. Но это противоречит тому, что мы сократили все общие множители, а значит таких и не существует.
Психологическая убедительность обоих доказательств не вызывает сомнений. Тем не менее, необходимо помнить, что получив противоречие, мы не всегда доказываем то, что хотим доказать. Противоречие не обязательно свидетельствует об ошибочности исходной посылки. Его может дать любое из утверждений использовавшихся при доказательстве. Особенно их много в теореме об иррациональности . Однако, они на столько "очевидны", что мы считаем ошибочной именно исходную посылку.
Видно, что схема доказательства приведенных теорем одинаковая. Мы показываем, что некоторый объект не существует, если предположение о его существовании приводит к противоречию.
Проблема Брадобрея . В некоторой деревне все мужчины бреются либо сами, либо у брадобрея. Брадобрей (мужчина) бреет только тех, кто сам не бреется. Сформулируем теорему:
Брадобрей бреет себя сам.
Пусть это не так, и брадобрей себя не бреет. Тогда он должен бриться у брадобрея. Значит брадобрей бреет себя.
Сделав отрицание теоремы, и получив противоречие, мы должны прийти к выводу, что теорема верна. Но совершенно ясно, что это не так, и мы можем построить не только обратное доказательство, но и прямое: "если брадобрей бреется сам, то он не может бриться у брадобрея...". В этом случае вновь получается противоречие.
Приведенное описание деревни со строгими правилами принадлежит Бертрану Расселу, как популярная формулировка проблем, возникающих в попытке определить "множество всех тех множеств, которые не содержат себя в качестве своего элемента". Мы умышленно явный парадокс представили в виде теоремы, чтобы продемонстрировать простой факт:
Получение противоречия в доказательстве от противного может свидетельствовать не об истинности теоремы, а о противоречивости объектов которые участвуют в её формулировке.Другими словами, нельзя сказать: "возьмём множество всех множеств..." и докажем "теорему о том, что..." Сначала необходимо убедиться, что объект, о котором будет идти речь в теореме, существует. В частности, деревня, описанная Расселом, существовать не может. Конечно, возникает вопрос – "а что значит существовать или не существовать, и где не существовать?" Есть объект, определённый выше, и мы можем использовать его при построении новых объектов и теорем о них...
Дело в том, что математическое рассуждение явно или не явно исходит из некоторых аксиом. Именно аксиомы задают свойства объекта. Если в фиксированной системе аксиом поменять хотя бы одну аксиому, может получиться объект с совершенно другими свойствами. Понятно, что произвольно задавать аксиомы нельзя. Они не должны быть противоречивыми , иначе никакого объекта определять не будут. Или, другими словами, – объект определяемый при помощи противоречивых аксиом не существует.
Подробнее мы обсудим элементы формальных аксиоматических систем в следующем разделе, где снова проанализируем проблему брадобрея. Сейчас же рассмотрим ещё одну версию того же парадокса.
Проблема Библиотекаря . Существует Библиотека с книгами. Любая книга внутри своего текста может упомянуть сама себя (например, в списке литературы привести свое название). Соответственно все книги можно разделить на две группы. В первую попадают книги, которые на себя не ссылаются, а во вторую – ссылающиеся на себя книги. Кроме этого, существуют две книги, являющиеся каталогами всех книг Библиотеки. Первый каталог перечисляет все те книги, которые на себя не ссылаются, а второй, наоборот – все ссылающиеся на себя книги:
Сформулируем теперь теорему:
Первый каталог содержитв списке книг себя.
Пусть это не так. Тогда первый каталог содержится во втором (все книги перечислены в обоих каталогах и каталог есть книга). Но во втором каталоге перечисляются только самоссылающиеся книги, и первого каталога там быть не может. Мы пришли к противоречию, следовательно теорема верна.
Если мы остановимся на этом этапе, то получим заведомо неверный вывод. Понятно, что первый каталог на себя ссылаться не может (он является каталогом не самоссылающихся книг). Как и в случае с брадобреем, мы можем провести как обратное доказательство (от противного), так и прямое. И оба раза получить противоречие.
О чём оно говорит? Понятно, что не об истинности или ложности теоремы. Веря в то, что два различных доказательства должны всегда приводить к одному и тому же, мы вынуждены сделать вывод: объект Библиотека , c заданными свойствами, существовать не может .
Любая ссылка на "естественность" или "видимую не противоречивость" исходных определений не достойна математика, так как это уже эмоции. Единственный путь – попытаться уйти от психологических формулировок и доказательств к формальным.
Парадокс лжеца . Вся математика состоит из логических утверждений. При этом логика математики бинарна. Утверждение "" или истинно или ложно. Третьего не дано. Именно эта бинарность придаёт математическому доказательству ту чудесную убедительность, ради которой всё и затевалось. Введем обозначение того, что некое логическое утверждение является истинным:
.На самом деле обозначение излишне, так как записывая в качестве аксиомы или посылки некоторое утверждение , мы предполагаем его истинность. Однако, такое обозначение будет удобно для дальнейшего. Определим высказывание:
где "" – знак логического отрицания, а после двоеточия идёт определение утверждения . Оно является вариантом парадокса лжеца: " – истинно, если не истинно ". Сформулируем следующую теорему:Утверждение L является истинным: L=И.пусть L=Л => True(L)=Л => L=True(L)=И.
(Далее "" означает логический вывод; "И" – истина, "Л" – ложь). В доказательстве от противного, мы пришли к противоречию. Поэтому исходная посылка не верна и, следовательно, теорема верна. Однако понятно, что это не так. Мы можем провести доказательство и в прямом направлении.
лат. reductio ad absurdum) - вид доказательства, при котором справедливость некоторого суждения (тезиса доказательства) осуществляется через опровержение противоречащего ему суждения - антитезиса. Опровержение антитезиса достигается путем установления его несовместимости с заведомо истинным суждением. Часто доказательство от противного опирается на двузначности принцип.
Отличное определение
Неполное определение ↓
ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО
обоснование суждения путем опровержения методом "приведения к нелепости" (reductio ad absurdum) нек-рого другого суждения, – именно того, к-рое является отрицанием обосновываемого (Д. от п. 1-го вида) или того, отрицанием к-рого является обосновываемое (Д. от п. 2-го вида); "приведение к нелепости" состоит в том, что из опровергаемого суждения выводится к.-л. явно ложное заключение (напр., формальнологическое противоречие), что и свидетельствует о ложности этого суждения. Необходимость различения двух видов Д. от п. вытекает из того, что в одном из них (именно, в Д. от п. 1-го вида) имеет место логический переход от двойного отрицания суждения к утверждению этого суждения (т.е. применяется т.н. правило снятия двойного отрицания, разрешающее переход от A к А, см. Двойного отрицания законы), в то время как в другом такого перехода нет. Ход рассуждения в Д. от п. 1-го вида: требуется доказать суждение А; в целях доказательства предполагаем, что суждение А неверно, т.е. что верно его отрицание: ? (не-А), и, опираясь на это предположение, логически выводим к.-л. ложное суждение, напр. противоречие, – осуществляем "приведение к нелепости" суждения А; это свидетельствует о ложности нашего предположения, т.е. доказывает, истинность двойного отрицания: A; применение к A правила снятия двойного отрицания завершает доказательство суждения А. Ход рассуждения в Д. от п. 2-го вида: требуется доказать суждение?; в целях доказательства предполагаем верным суждение А и приводим это предположение к нелепости; на этом основании заключаем, что А ложно, т.е. что верно?. Различение двух видов Д. от п. важно потому, что в так называемой интуиционистской (конструктивной) логике закон снятия двойного отрицания не имеет места, в силу чего не допускаются и Д. от п., существенно связанные с применением этого логического закона. См. также Косвенное доказательство. Лит.: Тарский?., Введение в логику и методологию дедуктивных наук, пер. с англ., М., 1948; Асмус В. Ф., Учение логики о доказательстве и опровержении, [М.], 1954; Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; Черч?., Введение в математич. логику, пер. с англ., [т.] 1, М., 1960.
Часто при доказательстве теорем пользуются методом доказательства от противного . Суть этого метода помогает понять загадка. Попробуйте её разгадать.
Представьте себе страну, в которой приговорённому к казни предлагается выбрать одну из двух одинаковых на вид бумаг: на одной написано «смерть», на другой - «жизнь». Враги оклеветали одного жителя этой страны. И, чтобы у него не осталось никаких шансов спастись, сделали так, что на обороте обоих бумажек, из которых он должен выбрать одну, было написано «смерть». Друзья узнали об этом и сообщили осуждённому. Он попросил никому об этом не рассказывать. Вытащил одну из бумажек. И остался жить. Как ему это удалось?
Ответ. Осуждённый проглотил выбранную им бумажку. Чтобы установить, какой жребий ему выпал, судьи заглянули в оставшуюся бумажку. На ней было написано: «смерть». Это доказывало, что ему повезло, он вытащил бумажку, на которой было написано: «жизнь».
Как в случае, о котором рассказывает загадка, при доказательстве возможны только два случая: можно… или нельзя… Если удастся убедится, что первое невозможно (на бумажке, которая досталась судьям, написано: «смерть»), то сразу можно сделать вывод, что справедлива вторая возможность (на второй бумажке написано: «жизнь»).
Доказательство методом «от противного» осуществляется так.
1) Устанавливают, какие варианты в принципе возможны при решении задачи или доказательстве теоремы. Вариантов может быть два (например, перпендикулярны ли не перпендикулярны рассматриваемые прямые); вариантов ответа может быть три и больше (например, какой получается угол: острый, прямой или тупой).
2) Доказывают. Что не может выполняться ни один из тех вариантов, которые нам необходимо отбросит. (Например, если надо доказать, что прямые перпендикулярные, смотрим, что получается, если рассматривать не перпендикулярные прямые. Как правило, удаётся установить, что в этом случае какой-либо из выводов противоречит тому, что дано в условии, а потому невозможен.
3) На основании того, что все нежелательные выводы отброшены и только один (желательный) остался нерассмотренным, делаем вывод, что именно он верный.
Решим задачу, используя доказательство от противного.
Дано: прямые а и b такие, что любая прямая, которая пересекает а, пересекает и b.
Используя метод доказательства «от противного», доказать, что а ll b.
Доказательство.
Возможны только два случая:
1) прямые а и b параллельны (жизнь);
2) прямые а и b не параллельны (смерть).
Если удастся исключить нежелательный случай, то останется сделать вывод, что имеет место второй из двух возможных. Чтобы отбросить нежелательный случай, давайте подумаем, что произойдёт, если прямые а и b пересекаются:
По условию любая прямая, которая пересекает а, пересекает и b. Поэтому, если удастся найти хотя бы одну прямую, которая пересекает а, но не пересекает b, этот случай надо будет отбросить. Таких прямых можно найти сколько угодно: достаточно провести через любую точку К прямой а, кроме точки М прямую КС, параллельную b:
Поскольку отброшен один из двух возможных случаев, можно сразу сделать вывод, что а ll b.
Остались вопросы? Не знаете, как доказать теорему?
Чтобы получить помощь репетитора – зарегистрируйтесь .
Первый урок – бесплатно!
сайт, при полном или частичном копировании материала ссылка на первоисточник обязательна.
МЕТОД ОТ ПРОТИВНОГО (далее МОП) - научно-прикладной метод, названный по имени выдающегося украинского просветителя, основателя целого ряда научных школ и направлений Василия Козьмича Противного. В.К.Противный родился 29 февраля 1513 г по старому стилю в селе Нижние Лопухи близ Чернигова. Вася с детства был слабым и хлипким мальчиком и постоянно, начиная с детского сада, подвергался насмешкам сверстников, что в дальнейшем предопределило его скверный характер.
В дальнейшем слова "делать все назло окружающим" фактически стали девизом жизни В.К.Противного. Так, назло всем он покинул родные Холмогоры и поступил в МГУ им. Ломоносова (а не в суворовское училище, как хотел его отец), назло всем никогда ни на ком не женился (хотя его бабушка Василиса Противная нашла ему за всю жизнь как минимум 14 невест), назло всем, сославшись на грибной сезон, не стал получать медаль Филдса - высшую награду в области математики.
Суть метода от Противного можно передать следующими пунктами:
1. Делается неверное предположение.
2. Выясняется, что следует из этого предположения на основании известных знаний.
3. Осуществляется заход в тупик.
4. Делается верный вывод о том, что неверное предположение неверно.
Многие ученые, философы, исследователи и даже деятели искусств стали ярыми приверженцами идей украинского просветителя. Например, так впервые в медицинской практике была использована лоботомия, когда была сделана попытка разрешить извечный философский спор о первичности материи или сознания с помощью медицинского эксперимента. Так ученик В.К.Противного Лобачевский создал неевклидову геометрию, так его почитатель Чайковский написал гимн альтернативной любви - вальс "Голубой Дунай", и так далее.
Метод от Противного часто применяется в настоящее время в самых разных областях человеческой жизни. Например, для воспитания художественного вкуса москвичей им с успехом пользуется московский мэр Лужков, устанавливая в городе скульптуры Церетели. Руководство ГУВД, пользуясь этим методом, решило найти убийц известной журналистки Политковской, так как другие методы в виду особой сложности дела результатов не дают. Вооруженные МОП московские милиционеры знают - последовательно выявив всех непричастных, они автоматически выйдут на след убийц.
Вся жизнь и даже смерть В.К.Противного явилась яркой иллюстрацией его метода. Ученый трагически ушел из жизни 29 февраля 1613 г в возрасте 112 лет, повесившись назло своей бабушке Василисе Противной, не давшей Василию Козьмичу попробовать варенье из холодильника. Несмотря на двоякое отношение к В.К.Противному из-за его скверного характера, большинство ученых и исследователей все-таки считают МОП одним из наиболее мощных орудий современной науки в целом и математики в частности.
____________________________________
Василий Козьмич Противный, выдающийся украинский просветитель (1513 - 1613)
Выражаю благодарность
Урок можно начать с рассказа учителя.
Ващенко Н.М., на уроке
В Древней Греции всех ораторов учили геометрии. На дверях школы было написано: «Не знающий геометрии, да не войдет сюда». Почему? Да потому, что геометрия учит доказывать. А речь человека убедительна только тогда, когда он доказывает свои выводы. В своих рассуждениях люди часто пользуются способом доказательства, который называется "от противного".
Приведем примеры таких доказательств.
Пример 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 способом от противного.
