Доказательство от противного

Материал из Википедии — свободной энциклопедии

Доказательство «от противного» в математике — один из самых часто используемых методов доказательства утверждений. Этот способ доказательства основывается на истинности формулы $((A\Rightarrow B) \land \neg B) \Rightarrow \neg A$ в классической логике и законе двойного отрицания.

Доказательство утверждения $A$ проводится следующим образом. Сначала принимают предположение, что утверждение $A$ неверно, а затем доказывают, что при таком предположении было бы верно некоторое утверждение $B$ , которое заведомо неверно. Полученное противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение $\neg\neg A$ , которое по закону двойного отрицания равносильно утверждению $A$ .

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

[править] Пример

Доказательство иррациональности числа $\sqrt{2}$ .

Допустим противное: $\sqrt{2}$ рационален, то есть представляется в виде несократимой дроби $\frac{m}{n}$ , где $m$ и $n$ — целые числа. Возведём предполагаемое равенство в квадрат:

$\sqrt{2} = \frac{m}{n} \Rightarrow 2 = \frac{m^2}{n^2} \Rightarrow m^2 = 2n^2$ .

Отсюда следует, что $m 2$ чётно, значит, чётно и $m$ ; следовательно, $m 2$ делится на 4, а значит, $n 2$ и $n$ тоже чётны. Полученное утверждение противоречит несократимости дроби $\frac{m}{n}$ . Значит, исходное предположение было неверным, и $\sqrt{2}$ — иррациональное число.