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

Д

(1)

не верна, то есть существует такой объект х, что условие Р(х) истинно, а заключение Q(x) - ложно. Если из этих предположений путем логических рассуждений приходят к противоречивому утверждению, то делают вывод о том, что исходное предположение не верно, и верна теорема (1). Покажем, что такой подход дает доказательство ис­тинности теоремы (1).

Действительно, предположение о том, что теорема (1) не справедлива, означает истинность формулы

Противоречивое утверждение, которое получается из допущенного предположения, есть конъюнкция С& , где С — некоторое высказывание. Таким образом, схема доказательства от противного сводится к доказательству истинности формулы

Легко видеть, что эта формула равносильна фор­муле (1).

Действительно,