Логика
Доказательство от противного
В 500 г. до н.э. пифагореец Гиппас доказал, что √2 нельзя представить как отношение целых чисел. Согласно легенде, его за это утопили - доказательство разрушило пифагорейскую веру в рациональность мира. Это было доказательство от противного - и оно изменило математику навсегда.
- **Криптография:** Многие доказательства безопасности используют reductio: «Если алгоритм взломан → можно решить NP-полную задачу → противоречие»
- **Судебная практика:** «Если подсудимый виновен, он был на месте преступления. Но он был в другом городе - противоречие. Значит, невиновен»
- **Дебаты:** «Допустим, ваша позиция верна. Тогда... (вывод абсурдных следствий). Следовательно, позиция ошибочна»
Доказательство от противного
**Доказательство от противного** - один из самых мощных методов доказательства. Идея проста: чтобы доказать утверждение P, **допустим ¬P** и покажем, что это ведёт к **противоречию**. Значит, ¬P невозможно, поэтому P истинно.
**Логическая основа:** (¬P → ⊥) → P. Если отрицание P приводит к противоречию, то P истинно. Это следует из закона исключённого третьего: либо P, либо ¬P - третьего не дано.
Этот метод особенно полезен, когда **прямое доказательство затруднено**. Часто проще показать, что отрицание абсурдно, чем напрямую вывести утверждение.
Чтобы доказать от противного «√2 иррационально», что нужно допустить?
Reductio ad absurdum
**Reductio ad absurdum** (лат. «сведение к абсурду») - классический термин для доказательства от противного. Метод известен с античности: Евклид использовал его для доказательства бесконечности простых чисел.
**Доказательство Евклида:** Предположим, простых чисел конечно много: p₁, p₂, ..., pₙ. Рассмотрим N = p₁×p₂×...×pₙ + 1. N не делится ни на одно pᵢ (остаток 1). Значит, N либо простое, либо делится на простое вне списка. Противоречие!
**Важно:** Противоречие должно быть **логическим** (A ∧ ¬A), а не просто неожиданным или контринтуитивным результатом. «Это странно» - не противоречие. «p чётно И p нечётно» - противоречие.
В доказательстве бесконечности простых чисел, что является противоречием?
Косвенное доказательство
**Косвенное доказательство** - более широкий термин, включающий доказательство от противного и **доказательство контрапозиции**. Вместо A → B доказываем эквивалентное ¬B → ¬A. Иногда это проще.
**Контрапозиция:** A → B ≡ ¬B → ¬A. Пример: «Если идёт дождь, земля мокрая» ≡ «Если земля сухая, дождя нет». Доказательство контрапозиции - легитимный метод.
**Различие:** Доказательство от противного работает с любым утверждением. Контрапозиция - только с импликациями. Оба - легитимные косвенные методы, но контрапозиция не требует противоречия.
Чтобы доказать контрапозицией «Если x² > 100, то x > 10 или x < -10», что нужно доказать?
Введение отрицания
В натуральной дедукции доказательство от противного оформляется через **правило введения отрицания (¬I)**: чтобы доказать ¬A, допускаем A и выводим противоречие. Это «мини-reductio» для отрицаний.
**RAA (Reductio Ad Absurdum)** - правило для доказательства положительных утверждений: допускаем ¬P, выводим ⊥, получаем P. **¬I** - для отрицаний: допускаем P, выводим ⊥, получаем ¬P. Технически RAA = ¬I + двойное отрицание.
**Интуиционистская логика** принимает ¬I, но отвергает RAA (классическое). В ней нельзя вывести P из ¬¬P. Это важно для конструктивной математики и теории типов (Coq, Agda).
Доказательство от противного и доказательство контрапозицией - одно и то же
Контрапозиция - частный случай для импликаций, reductio - общий метод для любых утверждений
Контрапозиция: вместо A→B доказываем ¬B→¬A (прямым методом). Reductio: допускаем ¬P и выводим противоречие. Контрапозиция не требует противоречия - это прямое доказательство эквивалентного утверждения.
Какое правило позволяет из ⊥ в допущении A вывести ¬A?
Ключевые идеи
- **Reductio:** Допустить ¬P, вывести ⊥, заключить P
- **Контрапозиция:** Вместо A→B доказать ¬B→¬A
- **¬I:** Допустить P, вывести ⊥, заключить ¬P
- **Противоречие** - логическое (A ∧ ¬A), не просто неожиданное
- **Применение:** Когда прямое доказательство затруднено
Связанные темы
Доказательство от противного - центральная техника:
- Натуральная дедукция — Reductio и ¬I - правила в системе натуральной дедукции
- Контрапозиция — Альтернативный косвенный метод для импликаций
- Закон исключённого третьего — Классическое reductio опирается на P ∨ ¬P
Вопросы для размышления
- Почему доказательство от противного «неконструктивно» - что это значит на практике?
- Приведите пример утверждения, которое проще доказать от противного, чем напрямую.
- Как бы вы объяснили человеку без математического образования, почему из противоречия следует что угодно?