Доказательство от противного — synset
Доказательство от противного – мощный и часто используемый в математике метод. Предположив, что некоторый факт (объект) является истинным (существует), и придя к противоречию, мы заключаем, что факт ложен (объект не существует). Рассмотрим несколько примеров.
Теорема Евклида о бесконечности простых чисел является классическим и самым простым рассуждением от противного:
Не существует самого большого простого числа .
: Пусть это не так, и самое большое простое число существует. Построим число . Оно не делится ни на одно , и больше чем . Мы пришли к противоречию, следовательно, самого большого простого числа (как объекта!) не существует и простых чисел бесконечно много.
Заметим, что не обязательно простое, так как его простой множитель может находится между и , но всё равно будет большим .
Теорема об иррациональностиНе существует натуральных и , таких, что
.
: Пусть это не так. Сократим общие множители у , , и возведём всё в квадрат: . Отсюда следует, что является чётным числом, поэтому тоже чётно и представимо при помощи некоторого натурального , как . Подставляя в исходное соотношение, получаем , а, следовательно, и чётно. Но это противоречит тому, что мы сократили все общие множители, а значит таких и не существует.
Психологическая убедительность обоих доказательств не вызывает сомнений. Тем не менее, необходимо помнить, что получив противоречие, мы не всегда доказываем то, что хотим доказать. Противоречие не обязательно свидетельствует об ошибочности исходной посылки. Его может дать любое из утверждений использовавшихся при доказательстве. Особенно их много в теореме об иррациональности . Однако, они на столько «очевидны», что мы считаем ошибочной именно исходную посылку.
Видно, что схема доказательства приведенных теорем одинаковая. Мы показываем, что некоторый объект не существует, если предположение о его существовании приводит к противоречию.
Проблема Брадобрея. В некоторой деревне все мужчины бреются либо сами, либо у брадобрея. Брадобрей (мужчина) бреет только тех, кто сам не бреется. Сформулируем теорему:
Брадобрей бреет себя сам.
Пусть это не так, и брадобрей себя не бреет. Тогда он должен бриться у брадобрея. Значит брадобрей бреет себя.
Сделав отрицание теоремы, и получив противоречие, мы должны прийти к выводу, что теорема верна. Но совершенно ясно, что это не так, и мы можем построить не только обратное доказательство, но и прямое: «если брадобрей бреется сам, то он не может бриться у брадобрея …». В этом случае вновь получается противоречие.
Приведенное описание деревни со строгими правилами принадлежит Бертрану Расселу, как популярная формулировка проблем, возникающих в попытке определитьПолучение противоречия в доказательстве от противного может свидетельствовать не об истинности теоремы, а о противоречивости объектов которые участвуют в её формулировке.Другими словами, нельзя сказать: «возьмём множество всех множеств …» и докажем «теорему о том, что …» Сначала необходимо убедиться, что объект, о котором будет идти речь в теореме, существует. В частности, деревня, описанная Расселом, существовать не может. Конечно, возникает вопрос – «а что значит существовать или не существовать, и где не существовать?» Есть объект, определённый выше, и мы можем использовать его при построении новых объектов и теорем о них…
Дело в том, что математическое рассуждение явно или не явно исходит из некоторых аксиом. Именно аксиомы задают свойства объекта. Если в фиксированной системе аксиом поменять хотя бы одну аксиому, может получиться объект с совершенно другими свойствами. Понятно, что произвольно задавать аксиомы нельзя. Они не должны быть противоречивыми, иначе никакого объекта определять не будут. Или, другими словами, – объект определяемый при помощи противоречивых аксиом не существует.
Подробнее мы обсудим элементы формальных аксиоматических систем в следующем разделе, где снова проанализируем проблему брадобрея. Сейчас же рассмотрим ещё одну версию того же парадокса.
Проблема Библиотекаря. Существует Библиотека с книгами. Любая книга внутри своего текста может упомянуть сама себя (например, в списке литературы привести свое название). Соответственно все книги можно разделить на две группы. В первую попадают книги, которые на себя не ссылаются, а во вторую – ссылающиеся на себя книги. Кроме этого, существуют две книги, являющиеся каталогами всех книг Библиотеки. Первый каталог перечисляет все те книги, которые на себя не ссылаются, а второй, наоборот – все ссылающиеся на себя книги:
Сформулируем теперь теорему:
Первый каталог содержитв списке книг себя.
Пусть это не так. Тогда первый каталог содержится во втором (все книги перечислены в обоих каталогах и каталог есть книга). Но во втором каталоге перечисляются только самоссылающиеся книги, и первого каталога там быть не может. Мы пришли к противоречию, следовательно теорема верна.
Если мы остановимся на этом этапе, то получим заведомо неверный вывод. Понятно, что первый каталог на себя ссылаться не может (он является каталогом не самоссылающихся книг). Как и в случае с брадобреем, мы можем провести как обратное доказательство (от противного), так и прямое. И оба раза получить противоречие.
О чём оно говорит? Понятно, что не об истинности или ложности теоремы. Веря в то, что два различных доказательства должны всегда приводить к одному и тому же, мы вынуждены сделать вывод: объект Библиотека, c заданными свойствами, существовать не может.
Любая ссылка на «естественность» или «видимую не противоречивость» исходных определений не достойна математика, так как это уже эмоции. Единственный путь – попытаться уйти от психологических формулировок и доказательств к формальным.
Парадокс лжеца. Вся математика состоит из логических утверждений. При этом логика математики бинарна. Утверждение «» или истинно или ложно. Третьего не дано. Именно эта бинарность придаёт математическому доказательству ту чудесную убедительность, ради которой всё и затевалось. Введем обозначение того, что некое логическое утверждение является истинным:
- .
На самом деле обозначение излишне, так как записывая в качестве аксиомы или посылки некоторое утверждение , мы предполагаем его истинность. Однако, такое обозначение будет удобно для дальнейшего. Определим высказывание:
,где «» – знак логического отрицания, а после двоеточия идёт определение утверждения . Оно является вариантом парадокса лжеца: » – истинно, если не истинно «. Сформулируем следующую теорему:
Утверждение L является истинным: L=И.
- пусть L=Л => True(L)=Л => L=True(L)=И.
(Далее «» означает логический вывод; «И» – истина, «Л» – ложь). В доказательстве от противного, мы пришли к противоречию. Поэтому исходная посылка не верна и, следовательно, теорема верна. Однако понятно, что это не так. Мы можем провести доказательство и в прямом направлении:
- пусть L=И => True(L)=И => L= True(L)=Л
и снова прийти к противоречию. Таким образом, мы не способны ни доказать ни опровергнуть теорему и ходим по замкнутому кругу.
Причина этого, как и раньше, состоит в том, что объект используемый при формулировке теоремы противоречив и, следовательно, не может существовать. Второй вопрос, почему объект , построенный столь «конструктивным» образом, не существует? Вокруг парадокса лжеца ломают копья со времен древних греков. Самое простое объяснение состоит в том, что при определении используется бесконечная рекурсия. Объект определяется сам через себя и при этом, говоря языком программирования, нет точки остановки этой рекурсии. Например, компьютер не смог бы оперировать с таким определением и просто «завис» бы. Это же рискует сделать и человек пытающийся глубоко вдуматься в . Поэтому, такое построение (определение) объекта просто некорректно.
Истинность и доказуемость — о конструктивной математике, Канторе и Гёделе
synset.com
Доказательство от противного — это… Что такое Доказательство от противного?
 | В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 13 мая 2011. |
Доказательство «от противного» (лат. Contradictio in contrarium) в математике — один из самых часто используемых методов доказательства утверждений. Этот способ доказательства основывается на истинности формулы в классической логике и законе двойного отрицания.
Схема доказательства
Доказательство утверждения проводится следующим образом. Сначала принимают предположение, что утверждение неверно, а затем доказывают, что при таком предположении было бы верно некоторое утверждение , которое заведомо неверно. Полученное противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение , которое по закону двойного отрицания равносильно утверждению .
В интуиционистской логике закон исключённого третьего не действует, поэтому такие доказательства в ней не принимаются.
Пример
Доказательство иррациональности числа .
Допустим противное: рационален, то есть представляется в виде несократимой дроби , где и — целые числа. Возведём предполагаемое равенство в квадрат:
- .
Отсюда следует, что чётно, значит, чётно и ; следовательно, делится на 4, а значит, и тоже чётны. Полученное утверждение противоречит несократимости дроби . Значит, исходное предположение было неверным, и — иррациональное число.
См. также
dic.academic.ru
Доказательство от противного — Википедия
Материал из Википедии — свободной энциклопедии
Доказательство «от противного» (лат. contradictio in contrarium) в математике — вид доказательства, при котором «доказывание» некоторого суждения (тезиса доказательства) осуществляется через опровержение отрицания этого суждения — антитезиса. Этот способ доказательства основывается на истинности закона двойного отрицания в классической логике.
Схема доказательства
Доказательство утверждения A{\displaystyle A} проводится следующим образом. Сначала принимают предположение, что утверждение A{\displaystyle A} неверно, а затем доказывают, что при таком предположении было бы верно некоторое утверждение B{\displaystyle B}, которое заведомо неверно.
Из определения импликации следует, что, если B{\displaystyle B} ложно, то формула ¬A⇒B{\displaystyle \neg A\Rightarrow B} истинна тогда и только тогда, когда ¬A{\displaystyle \neg A} ложно, следовательно утверждение A{\displaystyle A} истинно.
Полученное противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение ¬¬A{\displaystyle \neg \neg A}, которое по закону двойного отрицания равносильно утверждению A{\displaystyle A}.
В интуиционистской логике закон исключённого третьего не действует, поэтому такие доказательства в ней не принимаются.
Пример
- Доказательство иррациональности числа 2{\displaystyle {\sqrt {2}}}.
Допустим противное: число
wiki2.red
Предложения со словосочетанием ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО
Доказательство от противного — великая вещь! Седьмое занятие посвящено доказательству от противного. Есть и ещё одна вариация на ту же тему. Можно сказать, доказательство от противного. Получалось настоящее, принятое в науке доказательство от противного. Так бывает в жизни, это называется доказательство от противного.
Привет! Меня зовут Лампобот, я компьютерная программа, которая помогает делать
Карту слов. Я отлично
умею считать, но пока плохо понимаю, как устроен ваш мир. Помоги мне разобраться!
Спасибо! Я обязательно научусь отличать широко распространённые слова от узкоспециальных.
Насколько понятно значение слова осанистый (прилагательное):
Кристально
понятно
Понятно
в общих чертах
Могу только
догадываться
Понятия не имею,
что это
Другое
Пропустить
kartaslov.ru
Доказательство от противного — это… Что такое Доказательство от противного?
- Доказательство от противного
- вид Доказательства, при котором «доказывание» некоторого суждения (тезиса доказательства) осуществляется через опровержение противоречащего ему суждения — антитезиса. Опровержение антитезиса при этом достигается установлением факта его несовместимости с каким-либо заведомо истинным суждением. Этой форме Д. от п. соответствует следующая схема доказательства: если В истинно и из А следует ложность В, то А — ложно. Другая, более общая форма Д. от п. — это доказательство путём опровержения (обоснования ложности) антитезиса по правилу: допустив А, мы вывели противоречие, следовательно — не-А. Здесь А может быть как утвердительным, так и отрицательным суждением, а вывод противоречия может пониматься либо как вывод утверждения о тождестве заведомо различных предметов, либо как вывод пары суждений В, не-В, либо как вывод конъюнкции этой пары, либо как вывод эквивалентности этой пары. Этим различным случаям соответствуют различные интерпретации понятий Д. от п. и «противоречие». Приём Д. от п. особенно важен в математике: многие отрицательные суждения математики не могут быть доказаны другим путём, кроме приведения к противоречию. Помимо указанных выше, существует иная — «парадоксальная» — форма Д. от п., применявшаяся уже в «Началах» Евклида: суждение А можно считать доказанным, если удастся показать, что А следует даже из допущения ложности А.
М. М. Новосёлов.
Большая советская энциклопедия. — М.: Советская энциклопедия. 1969—1978.
- Доказательство
- Докембрий
Смотреть что такое «Доказательство от противного» в других словарях:
ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО — косвенное доказательство, при котором истинность тезиса обосновывается не прямо с помощью аргументов, а посредством антитезиса положения, противоречащего тезису. Показывая, что антитезис ложен, мы тем самым обосновываем истинность… … Философская энциклопедия
ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО — (proof by contradiction) Доказательство, при котором признание исходной предпосылки неверной ведет к противоречию. То есть предположение об ошибочности исходной посылки позволяет одновременно и доказать какое либо утверждение, и опровергнуть его; … Экономический словарь
ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО — один из видов косвенного доказательства … Большой Энциклопедический словарь
Доказательство от противного — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете … Википедия
доказательство от противного — один из видов косвенного доказательства. * * * ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО, один из видов косвенного доказательства (см. КОСВЕННОЕ ДОКАЗАТЕЛЬСТВО) … Энциклопедический словарь
Доказательство от противного — (лат. reduction ad absurdum) вид доказательства, при котором справедливость некоторого суждения (тезиса доказательства) осуществляется через опровержение противоречащего ему суждения антитезиса. Опровержение антитезиса достигается путем… … Исследовательская деятельность. Словарь
ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО — (лат. reductio ad absurdum) вид доказательства, при котором справедливость некоторого суждения (тезиса доказательства) осуществляется через опровержение противоречащего ему суждения антитезиса. Опровержение антитезиса достигается путем… … Профессиональное образование. Словарь
доказательство от противного — см.: Косвенное доказательство … Словарь терминов логики
ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО — один из видов косвенного доказательства … Естествознание. Энциклопедический словарь
Доказательство от противного — см. Абсурд1 … Философский словарь Спонвиля
dic.academic.ru
Доказательство от противного — Википедия. Что такое Доказательство от противного
Доказательство «от противного» (лат. contradictio in contrarium) в математике — вид доказательства, при котором «доказывание» некоторого суждения (тезиса доказательства) осуществляется через опровержение отрицания этого суждения — антитезиса. Этот способ доказательства основывается на истинности закона двойного отрицания в классической логике.
Схема доказательства
Доказательство утверждения A{\displaystyle A} проводится следующим образом. Сначала принимают предположение, что утверждение A{\displaystyle A} неверно, а затем доказывают, что при таком предположении было бы верно некоторое утверждение B{\displaystyle B}, которое заведомо неверно.
Из определения импликации следует, что, если B{\displaystyle B} ложно, то формула ¬A⇒B{\displaystyle \neg A\Rightarrow B} истинна тогда и только тогда, когда ¬A{\displaystyle \neg A} ложно, следовательно утверждение A{\displaystyle A} истинно.
Полученное противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение ¬¬A{\displaystyle \neg \neg A}, которое по закону двойного отрицания равносильно утверждению A{\displaystyle A}.
В интуиционистской логике закон исключённого третьего не действует, поэтому такие доказательства в ней не принимаются.
Пример
- Доказательство иррациональности числа 2{\displaystyle {\sqrt {2}}}.
Допустим противное: число 2{\displaystyle {\sqrt {2}}} рационально, то есть представляется в виде несократимой дроби mn{\displaystyle {\frac {m}{n}}}, где m{\displaystyle m} — целое число, а n{\displaystyle n} — натуральное. Возведём предполагаемое равенство в квадрат:
- 2=mn{\displaystyle {\sqrt {2}}={\frac {m}{n}}} ⇒{\displaystyle \Rightarrow } 2=m2n2{\displaystyle 2={\frac {m^{2}}{n^{2}}}}, откуда m2=2n2{\displaystyle m^{2}=2n^{2}}.
Отсюда следует, что m2{\displaystyle m^{2}} чётно, значит, чётно и m{\displaystyle m}; следовательно, m2{\displaystyle m^{2}} делится на 4, а значит, n2{\displaystyle n^{2}} и n{\displaystyle n} тоже чётны. Полученное утверждение противоречит несократимости дроби mn{\displaystyle {\frac {m}{n}}}. Значит, исходное предположение было неверным, и 2{\displaystyle {\sqrt {2}}} — иррациональное число.
- Другие примеры
Врач, убеждая пациента в том, что тот не болен гриппом, может рассуждать следующим образом: «Если бы вы действительно были больны гриппом, то у вас была бы повышена температура, был заложен нос и т. д. Но ничего этого нет. Следовательно, нет и гриппа».
См. также
wiki.sc
ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО — это… Что такое ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО?
- ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО
- ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО
(proof by contradiction) Доказательство, при котором признание исходной предпосылки неверной ведет к противоречию. То есть предположение об ошибочности исходной посылки позволяет одновременно и доказать какое-либо утверждение, и опровергнуть его; следовательно, исходное допущение о неправильности предпосылки не могло быть верным. К примеру, рассмотрим предположение, что √2 не является рациональным числом (rational number). Допустим противоположное: что √2 – это рациональное число х/у. Если х и у четные, разделим то и другое на 2 и будем продолжать делить, пока не получим некое рациональное число х/у, где по крайней мере одно из чисел нечетное. Квадрат любого четного числа является четным, а квадрат любого нечетного – нечетным. При х2=2у2, х должен быть четным. Пусть x=2z. Тогда 4z2=2y2, y2=2z2 и y должен быть четным. Однако, по крайней мере одно из чисел, х или у, было по построению нечетным. Из этого видно, что предположение о том, что √2 – это рациональное число, ведет к противоречию, поэтому √2 не может быть рациональным числом.
Экономика. Толковый словарь. — М.: «ИНФРА-М», Издательство «Весь Мир». Дж. Блэк. Общая редакция: д.э.н. Осадчая И.М.. 2000.
Экономический словарь. 2000.
- ДОКАЗАТЕЛЬСТВО МЕТОДОМ ИНДУКЦИИ
- ДОКЛАД БЕВЕРИДЖА
Смотреть что такое «ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО» в других словарях:
ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО — косвенное доказательство, при котором истинность тезиса обосновывается не прямо с помощью аргументов, а посредством антитезиса положения, противоречащего тезису. Показывая, что антитезис ложен, мы тем самым обосновываем истинность… … Философская энциклопедия
ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО — один из видов косвенного доказательства … Большой Энциклопедический словарь
Доказательство от противного — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете … Википедия
доказательство от противного — один из видов косвенного доказательства. * * * ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО, один из видов косвенного доказательства (см. КОСВЕННОЕ ДОКАЗАТЕЛЬСТВО) … Энциклопедический словарь
Доказательство от противного — (лат. reduction ad absurdum) вид доказательства, при котором справедливость некоторого суждения (тезиса доказательства) осуществляется через опровержение противоречащего ему суждения антитезиса. Опровержение антитезиса достигается путем… … Исследовательская деятельность. Словарь
ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО — (лат. reductio ad absurdum) вид доказательства, при котором справедливость некоторого суждения (тезиса доказательства) осуществляется через опровержение противоречащего ему суждения антитезиса. Опровержение антитезиса достигается путем… … Профессиональное образование. Словарь
доказательство от противного — см.: Косвенное доказательство … Словарь терминов логики
Доказательство от противного — (лат. reductio ad absurdum) вид Доказательства, при котором «доказывание» некоторого суждения (тезиса доказательства) осуществляется через опровержение противоречащего ему суждения антитезиса. Опровержение антитезиса при этом достигается… … Большая советская энциклопедия
ДОКАЗАТЕЛЬСТВО ОТ ПРОТИВНОГО — один из видов косвенного доказательства … Естествознание. Энциклопедический словарь
Доказательство от противного — см. Абсурд1 … Философский словарь Спонвиля
dic.academic.ru