Доведення від супротивного

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Доведення від супротивного (зведення до абсурду, лат. Reductio ad absurdum) — один із поширених методів доведення тверджень в математичній логіці. Доведення від супротивного - вид доведення, при якому доведення деякого твердження відбувається через спростування заперечення цього твердження - антитезису. Метод ґрунтується на правильності формули ((A\Rightarrow B) \land \neg B) \Rightarrow \neg A в численні висловлень та законі подвійного заперечення.

Припускаємо, що A є істинним твердженням, і доводимо, що, по-перше, з A виводиться B, а по-друге, що з A виводиться ¬B, що неможливо; отже, A хибне, тобто істинне ¬A.

Ґодфрі Гарольд Гарді назвав доказ від супротивного, кращою зброєю для математиків.

Схема доведення[ред.ред. код]

Доведення твердження A проводиться наступним чином. Спочатку приймають припущення, що твердженняA невірне, а потім доводять, що при такому припущенні було б вірним деяке твердження B, яке завчасно невірне. Отримане протиріччя показує, що початкове твердження було невірним, і тому вірним є твердження \urcorner\urcorner A, яке по закону подвійного заперечення дорівнює твердженню A.

В інтуїтивній логіці закон виключно третього не діє, тому такі доведення в ній не приймаються.

Приклад[ред.ред. код]

Доведення ірраціональності числа \sqrt{2}.[ред.ред. код]

Припустимо супротивне: \sqrt{2} раціональне, тобто представляється у вигляді нескоротного дробу \frac{m}{n}, де m - ціле число, а n - натуральне. Піднесемо отриману рівність в квадрат:

\sqrt{2} = \frac{m}{n} \Rightarrow  2 = \frac{m^2}{n^2}, звідки m^2 = 2 n^2.

Звідси витікає, що m^2 парне, значить, парне і m; звідси m^2 ділиться на 4, а значить, n^2 і n теж парні. Отримане твердження суперечить нескоротності дробу \frac{m}{n}. Значить початкове твердження було вірним (\sqrt{2} - ірраціональне число).

Довжина гіпотенузи[ред.ред. код]

Метод від супротивного також використовується, щоб показати, що для будь-якого невиродженого прямокутного трикутника, довжина гіпотенузи менше, ніж сума довжин двох інших. Доказ спирається на теорему Піфагора. Припустимо c є довжиною гіпотенузи і a і b довжини ребер, твердження в тому, що a+b>c.

Заперечимо це твердження припустивши, що a+b≤c. Піднесемо обидві частини нерівності в квадрат(a + b)2 ≤ c2. Маємо a2 + 2ab + b2 ≤ c2. Трикутник є невиродженим, якщо кожне ребро має додатню довжину, тому можна вважати, що a і b більше 0. Таким чином a2 + b2 < a2 + 2ab + b2 ≤ c2. Транзитивне відношення може бути зведене до a2 + b2 < c2. Як відомо з теореми Піфагора, що a2 + b2 = c2. Це призводить до протиріччя, так як нерівність строга і рівності є взаємовиключними.

Не існує найменшого раціонального числа[ред.ред. код]

Розглянемо твердження, P: "немає найменшого раціонального числа більше 0". Доводячи від супротивного припустимо зворотне, ¬P: що є найменше раціональне число, скажімо, r.

Тепер r/2 є раціональним числом більше 0 і менше, ніж r. Але це суперечить нашому початковому припущенню: ¬P, що r було найменшим раціональним числом. Таким чином, ми можемо зробити висновок, що початкове положення, P, має бути правдою - "немає найменшого раціонального числа більше 0".

Інші приклади[ред.ред. код]

Лікар, переконуючи пацієнта в тому, що той не хворий на грип, може розмірковувати наступним чином: "Якби ви дійсно були хворі грипом, то у вас би була підвищена температура, була б нежить і т. д. Але нічого з цього немає. Відповідно, пацієнт не хворий на грип.

В математичній логіці[ред.ред. код]

В математичній логіці метод від супротивного представляється так:

Якщо S \cup \{ P \} \vdash \mathbb{F} тоді S  \vdash \neg P. Або, якщо S \cup \{ \neg P \} \vdash \mathbb{F} тоді S  \vdash P.

У наведеному вище тексті P це припущення, яке ми хочемо довести, і S являє собою набір операторів, наприклад, аксіоми теорії в якій ми працюємо, або більш ранні теореми на яких ми можемо побудувати доведення. Ми розглядаємо P, або заперечення Р, на додаток до S; якщо це призводить до логічного протиріччя F, то можна зробити висновок, що припущення в S призводять до заперечення Р або самої Р відповідно.

Зверніть увагу, що теоретико-множинне об'єднання, в деяких контекстах тісно пов'язані з логічною диз'юнкцією (або).

Див. також[ред.ред. код]

Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.