Доведення від супротивного (зведення до абсурду, лат. Reductio ad absurdum) — один із поширених методів доведення тверджень в математичній логіці. Доведення від супротивного — вид доведення, при якому доведення деякого твердження відбувається через спростування заперечення цього твердження — антитезису. Метод ґрунтується на правильності формули ( ( A ⇒ ⇒ --> B ) ∧ ∧ --> ¬ ¬ --> B ) ⇒ ⇒ --> ¬ ¬ --> A {\displaystyle ((A\Rightarrow B)\land \neg B)\Rightarrow \neg A} в численні висловлень та законі подвійного заперечення. Це приклад слабшого логічного спростування — доведення до абсурду.
Припускаємо, що A є істинним твердженням, і доводимо, що, по-перше, з A виводиться B, а по-друге, що з A виводиться ¬B, що неможливо; отже, A хибне, тобто істинне ¬A.
Ґодфрі Гарольд Гарді назвав доведення від супротивного, найкращою зброєю для математиків.
Доведення твердження A {\displaystyle A} проводиться наступним чином. Спочатку приймають припущення, що твердження A {\displaystyle A} невірне, а потім доводять, що при такому припущенні було б вірним деяке твердження B {\displaystyle B} , яке завчасно невірне. Отримане протиріччя показує, що початкове твердження було невірним, і тому вірним є твердження ⌝ ⌝ --> ⌝ ⌝ --> A {\displaystyle \urcorner \urcorner A} , яке по закону подвійного заперечення дорівнює твердженню A {\displaystyle A} .
В інтуїтивній логіці закон виключно третього не діє, тому такі доведення в ній не приймаються.
Припустимо супротивне: 2 {\displaystyle {\sqrt {2}}} раціональне, тобто представляється у вигляді нескоротного дробу m n {\displaystyle {\frac {m}{n}}} , де m {\displaystyle m} — ціле число, а n {\displaystyle n} — натуральне. Піднесемо отриману рівність в квадрат:
2 = m n {\displaystyle {\sqrt {2}}={\frac {m}{n}}} ⇒ ⇒ --> {\displaystyle \Rightarrow } 2 = m 2 n 2 {\displaystyle 2={\frac {m^{2}}{n^{2}}}} , звідки m 2 = 2 n 2 {\displaystyle m^{2}=2n^{2}} .
Звідси витікає, що m 2 {\displaystyle m^{2}} парне, значить, парне і m {\displaystyle m} ; звідси m 2 {\displaystyle m^{2}} ділиться на 4, а значить, n 2 {\displaystyle n^{2}} і n {\displaystyle n} теж парні. Отримане твердження суперечить нескоротності дробу m n {\displaystyle {\frac {m}{n}}} . Значить початкове твердження було вірним ( 2 {\displaystyle {\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 ∪ ∪ --> { P } ⊢ ⊢ --> F {\displaystyle S\cup \{P\}\vdash \mathbb {F} } тоді S ⊢ ⊢ --> ¬ ¬ --> P . {\displaystyle S\vdash \neg P.} Або, якщо S ∪ ∪ --> { ¬ ¬ --> P } ⊢ ⊢ --> F {\displaystyle S\cup \{\neg P\}\vdash \mathbb {F} } тоді S ⊢ ⊢ --> P . {\displaystyle S\vdash P.}
У наведеному вище тексті P це припущення, яке ми хочемо довести, і S являє собою набір операторів, наприклад, аксіоми теорії в якій ми працюємо, або більш ранні теореми на яких ми можемо побудувати доведення. Ми розглядаємо P, або заперечення Р, на додаток до S; якщо це призводить до логічного протиріччя F, то можна зробити висновок, що припущення в S призводять до заперечення Р або самої Р відповідно.
Зверніть увагу, що теоретико-множинне об'єднання, в деяких контекстах тісно пов'язані з логічною диз'юнкцією (або).
Lokasi Pengunjung: 18.117.103.57