Метод от противного в логике
Метод от противного — это приём доказательства, при котором временно предполагают ложность требуемого утверждения и показывают, что это приводит к противоречию. Значит, исходное утверждение должно быть истинным.
Схема метода
Сначала формулируют требуемое логическое высказывание \(P\). Затем рассматривают противоположное предположение \(\neg P\) и последовательно преобразуют его вместе с условием задачи. Если получается одновременно истинное и ложное значение, например \(A=1\) и \(A=0\), или выражение \(0=1\), найдено противоречие.
Здесь \(\bot\) обозначает противоречие. В классической логике используется также закон двойного отрицания: из ложности \(\neg P\) следует истинность \(P\).
Докажем, что число \(n\), делящееся на 2, не может быть нечётным. Предположим обратное: \(n\) одновременно чётное и нечётное. Тогда существуют целые \(k\) и \(m\), для которых \(n=2k\) и \(n=2m+1\). Получаем \(2k=2m+1\), но левая часть чётная, а правая нечётная. Это противоречие, значит, исходное утверждение дұрыс.
Метод от противного не проверяет все варианты. Метод перебора рассматривает каждый допустимый случай отдельно, а здесь достаточно найти противоречие в одном предположении \(\neg P\). В логических задачах такой приём может применяться и при преобразовании выражений к нормальным формам.
Что нужно предположить в начале доказательства утверждения \(P\) методом от противного?
Главное
- Чтобы доказать \(P\), предположите \(\neg P\).
- Выведите из этого предположения противоречие \(\bot\).
- Сделайте вывод: \(\neg P\) ложно, поэтому \(P\) истинно.