Допущение и условное доказательство

Взять утверждение на пробу, посмотреть, что выйдет, и потом снять

Допущение это временно принятое высказывание: его берут «на пробу», выводят следствия, а затем снимают, фиксируя результат. Так доказывают условные утверждения (условное доказательство) и отрицания (рассуждение от противного). Снятое допущение не остаётся среди посылок, и в этом весь механизм.

forall x: Calgary, гл. 16 «Basic rules for TFL» и гл. 17 «Constructing proofs». Запись по Фитчу, 1950-е · 30 мин · обновлено 06.09.2026

Человек стоит на перроне и думает. «Допустим, я не успею на этот поезд. Тогда следующий только утром. Ночевать в этом городе негде. Значит, опаздывать нельзя». Рассуждение заняло четыре секунды и совершенно обычно: такое проделывают по десять раз на дню.

Присмотримся к первому слову. «Допустим».

Человек не утверждал, что опоздает, и не считал это правдой: он взял утверждение на пробу, чтобы посмотреть, куда оно ведёт. И заметьте, чем всё кончилось. Вывод «опаздывать нельзя» держится сам по себе и не зависит от того, опоздает человек или нет. Допущение было, и его больше нет: оно сработало и ушло. Вот эту машинерию урок и разбирает: она даёт две недостающие половины набора правил, и на ней спотыкается больше людей, чем на всём остальном курсе.

Как доказывают «если… то»

Вспомним, чего нам не хватало в уроке 11: у стрелки было правило удаления и не было правила введения. Спросим прямо: что вообще нужно, чтобы получить право написать «если A, то B»? Ответ подсказывает перрон: надо допустить A и дойти до B. Это правило называется условным доказательством, в записи →I, и работает оно так. Открывают блок: сдвигают строки вправо и отчёркивают вертикальной чертой, а первой строкой блока ставят допущение. Внутри блока рассуждают обычным порядком, всеми известными правилами.

Дойдя до нужного B, блок закрывают, и снаружи блока появляется одна новая строка: A → B. Ссылки у неё две, на первую строку блока и на последнюю: вот что я допустил, вот до чего дошёл. Есть одно ограничение, о котором стоит знать заранее: закрытие берёт последнюю строку блока, а не любую понравившуюся. Если нужная формула стоит в середине блока, её повторяют правилом R и ставят в конец. Вот теперь повтор из урока 11 отработал свой долг.

Разбор по шагам: цепочка стрелок

Задача. Известно: если Аня придёт, придёт Боря. И: если Боря придёт, придёт Вера. Надо получить: если Аня придёт, придёт Вера. Обратите внимание, чего в условии нет: не сказано, что Аня придёт, и заключение этого не требует, ведь оно само условное.

Ключ перевода: пусть P означает «Аня придёт», Q означает «Боря придёт», R означает «Вера придёт». Тогда посылки записываются так. Первая, P → Q, читается: не бывает так, чтобы Аня пришла, а Боря нет. Вторая, Q → R, читается: не бывает так, чтобы Боря пришёл, а Вера нет. Цель записывается как P → R и читается: не бывает так, чтобы Аня пришла, а Вера нет.

1. P → Q (посылка).
2. Q → R (посылка).
3. │ P (допущение).
4. │ Q (→E 1, 3).
5. │ R (→E 2, 4).
6. P → R (→I 3, 5).

Теперь по одной строке, ничего не пропуская. Строки 1 и 2. Посылки. Стоят вне блоков, на нулевой глубине.

Строка 3. Открываем блок и допускаем P. Это не утверждение и не ложь. Это проба: посмотрим, что будет, если Аня придёт.

Строка 4. Правило →E по строкам 1 и 3. Заметьте: строка 1 лежит снаружи блока, а мы ею пользуемся. Это разрешено, и разрешено намеренно.

Блок закрывает выход, а не вход. Внутрь можно тянуть всё, что стоит выше и доступно.

Строка 5. Снова →E, по строкам 2 и 4. Дошли до R, ради чего блок и открывался.

Строка 6. Закрываем блок правилом →I. Ссылки: строка 3 показывает, что допустили, строка 5 показывает, до чего дошли. Получаем P → R.

Строка 6 стоит уже вне блока: она не опирается на допущение и держится на одних посылках 1 и 2. Скажем это ещё раз, потому что здесь и происходит главное: мы доказали «если Аня, то Вера», ни разу не утверждая, что Аня придёт.

Что значит «снять допущение»

Это место надо пройти медленно: оно короткое и решает всё. Внутри блока строка 5 (R) держится на трёх вещах: на посылках 1, 2 и на допущении 3. Сама по себе, без допущения, она не стоит: Вера придёт только при условии, что придёт Аня.

Строка 6 устроена иначе: она говорит не «Вера придёт», а «если Аня, то Вера». Условие никуда не делось, оно переехало внутрь формулы, и вот в этом весь фокус. Допущение не исчезает, оно переезжает в левую часть стрелки.

Было: R при условии P. Стало: P → R без всяких условий. Аналогия: допущение работает как строительные леса. Их ставят, чтобы возвести стену, а потом убирают, и стена стоит сама.

Где аналогия ломается. От лесов не остаётся ничего, а от допущения остаётся след, и след этот виден: буква P в левой части стрелки. Ничто не исчезает бесследно, оно просто меняет место. Отсюда и ответ на естественное недоумение. «Разве можно доказывать из того, чего не знаешь?» Можно, потому что доказано не B, а «если A, то B»: это утверждение слабее, зато оно от A не зависит.

Почему закрытый блок закрыт

Правило звучит сурово: после закрытия блока строки внутри него недоступны навсегда. Сослаться на строку 4 или 5 из нашего вывода больше нельзя: они бледнеют и выбывают. Это кажется расточительством: строки же честно получены, зачем их выбрасывать? Затем, что без этого запрета система доказывала бы что угодно, и катастрофу мы сейчас покажем целиком. Она занимает четыре строки.

1. │ P (допущение).
2. │ P (R 1).
3. P → P (→I 1, 2).
4. P (R 1). ← так нельзя.

Первые три строки безупречны: мы допустили P, повторили его и закрыли блок, получили P → P. Читается эта строка: не бывает так, чтобы P, а P нет. Чистая правда при любом P. А теперь представьте, что строка 1 осталась доступной: тогда строкой 4 её можно просто повторить. И вот результат: P доказано без единой посылки. Любое P. Хоть «Луна сделана из сыра».

Система, которая доказывает всё, не доказывает ничего, поэтому запрет и стоит. Правило доступности формулируется одной фразой. Строка доступна, если все блоки, внутри которых она лежит, ещё открыты. Отсюда и односторонность блока: изнутри наружу смотреть можно (посылки 1 и 2 нам пригодились), а снаружи внутрь смотреть нельзя.

Знак ⊥ и правила при нём

Вернёмся на перрон: там было место, которое мы проскочили. «Ночевать негде. А ночевать где-то надо». Две вещи, которые вместе невозможны. Человек в этот момент не выводит ничего нового. Он ставит отметку: приехали, дальше по этому пути идти некуда.

Для такой отметки в логике есть знак: ⊥, читается «абсурд» или «противоречие». Важно понять, чем ⊥ не является: это не «какое-то ложное высказывание», это знак того, что набор строк перед нами невозможен целиком. Ставят его правилом ¬E: есть строка A, есть строка ¬A, значит можно написать ⊥. Порядок ссылок здесь безразличен. Требование к правилу привычное, оно состоит в буквальности: под отрицанием должна стоять в точности та же формула, а не похожая.

Второе правило при ⊥ выглядит вызывающе. ⊥E: есть строка ⊥, значит можно написать что угодно. Это то самое «из противоречия следует всё» из урока 9, теперь одним ходом вместо двух. В уроке 11 мы добирались туда через ослабление и дизъюнктивный силлогизм, а правило ⊥E делает то же самое напрямую. Поломкой это не является: раз случая, где все строки истинны, не существует, то и случая с истинными строками и ложным заключением тоже нет. Правильность определена именно так.

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

Теперь второе правило введения, которого нам не хватало, а именно правило для отрицания. Спросим так же прямо: что нужно, чтобы получить право написать ¬A? Ответ симметричен условному доказательству: надо допустить A и упереться в ⊥. Правило называется ¬I: открывают блок, допускают A, доводят дело до ⊥, закрывают блок, и снаружи появляется ¬A. Смысл прозрачен: если из A при наших посылках выходит невозможное, то A при наших посылках невозможно.

У правила есть зеркальный ход, и он-то и называется доказательством от противного: допускают ¬A, доходят до ⊥ и заключают A. Обратите внимание на разницу: в первом случае мы доказываем отрицание, а во втором снимаем отрицание, то есть получаем утверждение из невозможности его отрицания.

Второй ход законен в классической логике и стоит того, чтобы отметить его отдельно: он не следует из первого автоматически, это решение о том, как устроена система. Есть логики, где так делать нельзя: в интуиционистской логике из «¬A невозможно» получить A не разрешается, там доказательством считают построение, а не отсутствие препятствий. Урок 23 показывает цену такого выбора целиком.

Разбор по шагам: доказываем modus tollens

Задача. Известно: если Аня придёт, придёт Боря. И известно: Боря не пришёл. Надо получить: Аня не пришла. Ключ прежний: P означает «Аня придёт», Q означает «Боря придёт». Посылки: P → Q и ¬Q, где второе читается «неверно, что Боря пришёл». Цель: ¬P, неверно, что Аня пришла.

1. P → Q (посылка).
2. ¬Q (посылка).
3. │ P (допущение).
4. │ Q (→E 1, 3).
5. │ ⊥ (¬E 4, 2).
6. ¬P (¬I 3, 5).

Разберём построчно. Строки 1 и 2. Посылки.

Строка 3. Допускаем P на пробу. Цель у нас с отрицанием снаружи, значит допускать надо то же самое без отрицания.

Строка 4. Правило →E по строкам 1 и 3. Стрелка снаружи блока плюс допущение внутри дают Q.

Строка 5. Правило ¬E по строкам 4 и 2. На строке 4 стоит Q, на строке 2 стоит ¬Q. Есть формула, есть её отрицание, значит ⊥.

Строка 6. Закрываем блок правилом ¬I. Допустили P, дошли до ⊥, значит ¬P.

Посмотрите, что мы сейчас доказали в общем виде: из A → B и ¬B выводится ¬A. Это modus tollens, и он теперь наш. В тренажёре он есть отдельной кнопкой, МТ, и делает всё это одним шагом вместо трёх. Такие правила называют производными. Они не добавляют системе силы, ведь всё, что выводится с ними, выводилось и без них. Они добавляют скорости. Отсюда практический совет: полезно один раз построить производное правило руками, а потом всю жизнь пользоваться кнопкой.

Блок внутри блока

Блоки вкладываются друг в друга, и это не редкость, а норма. Разберём самый маленький случай, вывод вообще без посылок. Цель: P → (Q → P). Читается это так: если P, то верно, что при Q будет P. Фраза звучит запутанно, а смысл её прост: если P уже верно, то оно останется верным при любом добавочном условии.

1. │ P (допущение).
2. │ │ Q (допущение).
3. │ │ P (R 1).
4. │ Q → P (→I 2, 3).
5. P → (Q → P) (→I 1, 4).

Строка 1. В цели стоит стрелка, значит начинаем с допущения её левой части.

Строка 2. Внутри осталась цель Q → P, снова стрелка. Открываем второй блок и допускаем Q.

Строка 3. Нужна P. Она уже есть на строке 1, во внешнем блоке, и она доступна: этот блок ещё открыт. Но закрытие берёт последнюю строку блока, а последней сейчас стоит Q, поэтому P повторяем правилом R. Вот ради чего повтор и держат в системе.

Строка 4. Закрываем внутренний блок: допустили Q, дошли до P, получаем Q → P.

Строка 5. Закрываем внешний: допустили P, дошли до Q → P, получаем P → (Q → P).

Вывод построен из ничего: посылок не было ни одной, а строка 5 стоит на нулевой глубине и держится на одних правилах. Такие формулы истинны при любых значениях букв, а знак для этого случая появился в уроке 10: слева от ⊢ пусто.

Тренажёр: что нажимать

Ниже стоит построитель вывода. Он проверяет каждый шаг и объясняет отказ, поэтому спорить с ним бесполезно и полезно. Строки выделяют щелчком, это и есть ссылки, а сколько их нужно, задаёт выбранное правило.

Порядок ссылок важен для трёх правил. Для →E и МТ первой называют строку со стрелкой, для ДС первой называют строку с «или». Кнопка «Допущение» открывает блок: в поле вписывают формулу допущения и нажимают её вместо «Применить правило». Кнопка «Закрыть →I» даёт стрелку от допущения к последней строке блока, а кнопка «Закрыть ¬I» требует, чтобы последней строкой было ⊥.

Бледные строки недоступны: они внутри закрытого блока, щёлкать по ним нельзя, и это не поломка, а правило доступности. Задача засчитана, когда цель стоит последней строкой и на нулевой глубине. Формула внутри открытого блока целью не считается: допущение ещё не снято. Ещё одно ограничение стоит знать заранее: закрыть блок сразу после допущения нельзя, внутри должен быть хотя бы один шаг.

Задач семь, по нарастающей. Первые три решаются правилами урока 11: там нужны →E, разбор и сборка «и», дизъюнктивный силлогизм. Четвёртая и пятая относятся к этому уроку: одна на ¬I, другая на →I. Шестая даёт вложенные блоки, тот самый вывод из ничего, который мы только что разобрали. Седьмая длиннее всех и в первый заход не берётся: это половина закона де Моргана, и урок 13 разбирает её по строкам. Совет один: прежде чем нажимать, выпишите на бумаге, какая связка стоит в цели снаружи. От этого зависит, с чего начинать, и почти всегда ответ такой: с допущения.

Что дальше

Набор правил на этом закрыт, и закрыт он с двумя оговорками, которые урок 11 уже называл. Введение и удаление теперь есть у «и», у «или», у стрелки и у отрицания. Но «или» здесь убирают дизъюнктивным силлогизмом, а не разбором случаев, как в учебниках, и двойная стрелка своих правил не получила: её раскрывают через две обычные. Набор рабочий, а не полный, и на семь задач тренажёра его хватает. Остаётся то, чего никакое объяснение не даёт, а именно умение находить вывод, когда его никто не показал. Урок 13 разбирает один длинный вывод целиком: не готовый, а вместе с поиском, где будут два тупика, из которых пришлось выбираться, и приёмы, которые вывели.

Вопросы для самопроверки

Что читать

• Тренажёр «Построитель вывода» на этой странице: Семь задач по нарастающей. Первые три на правила урока 11, четвёртая и пятая на допущения, шестая на вложенные блоки, седьмая ждёт урока 13. Кнопку подсказки стоит нажимать не раньше, чем через пять минут честной попытки.
• forall x: Calgary, гл. 16 «Basic rules for TFL» и гл. 17 «Constructing proofs»: Смотреть стоит на решённые выводы, а не на формулировки правил: разбор чужого доказательства строчка за строчкой учит быстрее. Глава 17 вдобавок даёт стратегию поиска (то, чем занят урок 13).
• Статья «Intuitionistic Logic» в Stanford Encyclopedia of Philosophy: Про системы, где допускать ¬A и заключать A из полученного ⊥ не разрешено. Читать после курса, а сейчас достаточно знать, что этот ход представляет собой решение о системе, а не свойство мышления.