Математика · объяснение и практика

Почему доказательство через противоположное условие сохраняет утверждение

Как доказать импликацию через отрицание заключения, почему контрапозиция сохраняет смысл и чем она отличается от простого обратного утверждения.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

В маршруте Условия и доказательные связи · 10 тем

Главная мысль

Высказывания P⇒Q и ¬Q⇒¬P равносильны. Для доказательства можно предположить отсутствие Q и вывести отсутствие P,сохранив область и точные отрицания обоих условий.

Исключаем тот же запрещённый случай

Импликация P⇒Q запрещает сочетание «P истинно, Q ложно». Контрапозиция ¬Q⇒¬P запрещает то же сочетание: нельзя иметь отсутствие Q при сохранённом P. Поэтому меняются местами условия и отрицается каждое из них. Простое обратное Q⇒P устроено иначе и в общем случае не следует из исходной импликации.

Метод полезен, когда отрицание заключения даёт простую форму объекта. Например, для целого числа удобно предположить делимость на три и сразу записать n=3k. Это может быть короче, чем извлекать сведения из сложного выражения с n. Выбор способа доказательства определяется структурой условий, а не обязательством всегда начинать с P.

Пример

Докажем: если n²+2 делится на три, то n не делится на три. Предположим наоборот к заключению: n=3k. Тогда n²+2=9k²+2 имеет остаток 2 и не делится на три.

Получена контрапозиция: делимость n на три исключает делимость n²+2. Следовательно, исходное условие влечёт неделимость n на три.

Отрицания нужно строить точно

Если заключение содержит «не меньше»,его отрицание означает «меньше»,а не «не больше». Для составного условия применяются правила отрицания союзов и кванторов. Ошибка на границе или замена «хотя бы одного» на «каждого» превращает доказательство в рассуждение о другой импликации, даже если оно само по себе безошибочно.

В утверждении о двух целых числах «разная чётность» отрицается одинаковой чётностью. Последнее охватывает два случая: оба чётные или оба нечётные. Если проверить только один случай, контрапозиция останется недоказанной. Метод не устраняет необходимость полного покрытия вариантов, а лишь иногда делает их проще для перечисления.

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

При контрапозиции предполагают ¬Q и прямо доказывают ¬P. При доказательстве исходной импликации от противного можно предположить одновременно P и ¬Q и получить противоречие. Методы близки, но имеют разную организацию. В записи полезно явно назвать принятое предположение, чтобы не использовать желаемый вывод как уже доказанный факт.

После доказательства вернитесь к исходной фразе и проверьте, что объект и область не изменились. Контрапозиция не требует доказать обратное утверждение или проверить все примеры отдельно. Её сила состоит в общей логической равносильности, а не в количестве удачно подобранных чисел. Один контрпример к исходной импликации одновременно опроверг бы и её контрапозицию.

От чтения к действию

А теперь — вы

Какая фраза является контрапозицией: «Если a+b нечётно, то a и b разной чётности» для целых a,b?

Частые вопросы

Нужно ли доказывать равносильность заново в каждой задаче?

Нет. Это общий закон классической логики. В конкретной задаче проверяют, что выбранные отрицания действительно соответствуют P и Q.

Обратное утверждение тоже может быть истинным?

Да, но это отдельный факт. Его истинность не делает его контрапозицией: контрапозиция обязательно содержит отрицания обоих условий.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться