Доказательство от противного: предположи ложность и выведи невозможное
Доказательство от противного предполагает, что утверждение ложно, и выводит невозможное — предположение рушится. Так доказывают иррациональность √2 и бесконечность простых. Инженеры делают это каждый день: допустим, цикл не завершается; допустим, два id совпали — невозможно.
Прилетает баг-репорт: два клиента получили один и тот же номер счёта. Дежурный инженер отвечает одним предложением: «Невозможно — номера счетов берутся из колонки с уникальным индексом, так что будь у двух строк один номер, база отклонила бы вторую вставку». Она предположила, что репорт верен, прошла по гарантиям системы до невозможного и заключила, что репорт должен быть ошибочным. Это доказательство от противного — второй древнейший приём математики, тот, что поверг √2 и короновал простые числа бесконечностью. Конец истории стоит сохранить: репорт был верен. Миграция тремя неделями раньше тихо удалила индекс. Доказательство было корректным — но один из его «известных фактов» фактом уже не был.
После этого урока ты можешь назвать три такта доказательства от противного и объяснить, почему приём законен, применить его к иррациональности √2 и бесконечности простых, определить, когда нужно «от противного», а когда контрапозиция, и назвать режим отказа, порождающий ложные доказательства.
Три такта: предположи ¬C, выведи невозможное, заключи C. Допусти, ради рассуждения, что утверждение ложно. Только корректными шагами приди к тому, что не может быть истинным — к столкновению с известным фактом или с самим предположением. Заключи: предположение привело к невозможному, значит, оно несостоятельно; утверждение выполняется. Двигатель под капотом: корректные шаги никогда не ведут от истины к лжи. Значит, цепочка, упёршаяся в невозможное, имела ложный вход — а если каждый вход, кроме предположения, незыблем, предположение — единственный подозреваемый.
Классика первая: √2 иррационален. Число рационально, если равно p/q (целые, q ≠ 0) в несократимом виде (у p и q нет общего делителя). Утверждение: такой дроби не существует — предположите, что она есть, и допросите её.
Предположим, √2 = p/q в несократимом виде. Возведение в квадрат: p² = 2q², значит p² чётно. Будь p нечётным, p² было бы нечётным (прошлый урок, по контрапозиции), значит p чётно — пишем p = 2k. Подстановка: q² = 2k², значит q тоже чётно. Теперь p и q оба чётны, оба делятся на 2 — хотя дробь взята несократимой. Вот невозможное. Каждый шаг — алгебра или уже доказанный факт, поэтому виновато предположение. √2 иррационален. ∎
Заметьте камео: контрапозиция из первого урока сделала тяжёлую работу внутри этого доказательства. Техники компонуются.
Классика вторая: наибольшего простого не существует. Предположим, простых конечное число, список: p₁, p₂, …, pₙ. Построим N = p₁·p₂·…·pₙ + 1. Деление N на любое простое из списка оставляет остаток 1, значит ни одно простое из списка N не делит. Но N > 1 имеет какой-то простой делитель — которого в списке нет. Список претендовал на полноту; вот простое, которое он упустил. Невозможно. ∎
Важно: доказательство не утверждает, что N само простое. Ему нужен лишь простой делитель вне списка. Конкретно: 2·3·5·7·11·13 + 1 = 30031 = 59·509 — не простое, но делители 59 и 509 — новые простые.
Стена должна вырастать из предположения, а не из ошибки. Приём работает, потому что «предположение — единственный подозреваемый». Одна арифметическая ошибка в середине цепочки тоже породит «невозможное» — и теперь у лжи два возможных источника, а вы обвините не того. Противоречие в конце не сертифицирует цепочку; оно обличает какой-то вход. Только чистая цепочка даёт право указать на предположение. Если доказательство импликации от противного использует только ¬Q (не P) — это контрапозиция в маскировке: переформулируйте как ¬Q→¬P, одно предположение вместо двух.
Завершаемость как рассуждение от противного.
function drainQueue(queue) {
// Утверждение: этот цикл всегда завершается.
while (queue.length > 0) {
queue.pop(); // каждый проход удаляет ровно один элемент
}
}
// Предположим, цикл крутится вечно. Каждый проход строго уменьшает
// queue.length на 1, значит, длина убывала бы вечно. Но длина — целое
// неотрицательное число: вечно убывать оно не может. Невозможно → цикл завершается.И история со счетами: предположим, две строки делят один номер → вторая INSERT нарушила бы уникальный индекс → база отклоняет такие вставки → однако обе строки существуют — невозможно, если индекс существует. Каждый «известный факт» — несущее звено. Когда невозможное случилось в продакшене, правильный вывод — не «репорт ошибочен», а «одна из аксиом тихо умерла».
▸Почему это работает
Почему вина падает на предположение, а не на какое-то другое звено? Аудит: каждое другое звено — либо определение (оно не может быть ложным — оно лишь фиксирует смысл), либо ранее доказанный факт, либо корректный вывод. Ложь не может зародиться ни в одном из них. Единственное утверждение, впущенное без документов, — предположение. В продакшен-системах ничто не незыблемо по-настоящему: индекс можно удалить, часы могут прыгнуть. Когда в живой системе происходит невозможное, правильный вывод — «идите ищите, какая аксиома тихо умерла».
Назовите три такта доказательства от противного (через запятую).
В доказательстве про √2 — что является «невозможным», закрывающим рассуждение?
В доказательстве Евклида о простых — должно ли построенное число N = p₁·p₂·…·pₙ + 1 само быть простым? Ответьте «да» или «нет».
Если доказательство импликации от противного использует только ¬Q (никогда не использует P), что это такое? Ответьте двумя словами.
Инженер доказывает «дублирующихся счетов быть не может» из гарантии уникального индекса. Баг-репорт утверждает, что дубликаты есть. Наиболее вероятное объяснение? Напишите кратко.
Почему в доказательстве про √2 вывод «p и q оба чётны» завершает рассуждение?
Доказательство от противного идёт в три такта: предположи, что утверждение ложно, выведи корректными шагами невозможное, заключи, что утверждение истинно. Двигатель — сама корректность: корректные шаги не переносят истину в ложь, поэтому цепочка, упёршаяся в невозможное, имела ложный вход, и если каждое звено, кроме предположения, незыблемо, подозреваемый один. Две классики показывают ремесло: предположите √2 = p/q в несократимом виде, возведите в квадрат, и чётность заражает p, затем q, пока «нет общего делителя» не рухнет; предположите полный конечный список простых, перемножьте и прибавьте 1 — остаток изготовит простое, упущенное списком, само N простым быть не обязано. Приём блистает там, где лобовая атака тонет: невозможность и единственность, где предположение ложности вручает конкретный объект. Дисциплина: стена должна восходить к предположению — одна ошибка даёт вине второй дом; в продакшене, когда невозможное зримо случилось, идите ищите, какая аксиома тихо умерла. И если ваше доказательство использовало только ¬Q — это контрапозиция в маскировке: переформулируйте.
Практика
Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.
Что-то непонятно?
Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.