Система натурального вывода: правила и примеры

Система натурального вывода - способ строить формальные доказательства из посылок с помощью правил для логических связок. Её особенность - работа с временными допущениями: можно предположить , вывести при этом условии , а затем заключить и снять допущение. Важна не только последняя формула, но и то, от каких условий она зависит. Выберите задачу в форме ниже, чтобы разобрать шаги и границы подвывода; далее построим доказательство вручную.
Из чего состоит натуральный вывод
Пусть , и обозначают высказывания. Запись читают так: формула выводима из набора посылок по выбранным правилам. Знак относится к самому доказательству, а стрелка - связка внутри формулы. Поэтому и записывают разные вещи, хотя они связаны правилом введения импликации.
Доказательство можно изобразить деревом или последовательностью пронумерованных строк. В построчной записи рядом с формулой указывают правило и номера строк, на которые оно опирается. Вложенный участок выделяют вертикальной чертой или рамкой: это подвывод, начинающийся с допущения. В нём доступны внешние посылки и строки текущей области; после закрытия области её внутренние строки нельзя просто использовать как независимые факты.
На видео маркер проходит по строкам от посылок к заключению и возвращается к началу. Обратите внимание, что строки 3–5 составляют один подвывод: последняя строка уже утверждает условную связь, а не отдельно .
Отдельный шаг вида «, , значит » известен как модус поненс. Натуральный вывод объединяет такие шаги с правилами построения новых формул и управления допущениями.
Введение и устранение связок
Правила обычно делят на два семейства. Введение показывает, при каких условиях можно получить формулу с данной главной связкой; устранение - какие выводы разрешено сделать из уже полученной формулы. В разных учебниках обозначения могут различаться: здесь означает введение, а - устранение.
Для конъюнкции нужны две части: из и по выводят . Обратно, из по можно получить каждую часть по отдельности. Это два применения правила, если нужны обе строки. Например, из «сервер доступен и база отвечает» следует «сервер доступен»; обратное заключение без второй посылки не обосновано.
Для импликации устранение применяют к и , получая . Введение устроено иначе: внутри подвывода временно предполагают , получают , закрывают область и записывают . Допущение при этом снимается, но остальные открытые допущения, использованные в подвыводе, сохраняются.
Для дизъюнкции достаточно доказать одну из частей, чтобы ввести всю формулу. Устранение требует разбора случаев: из , подвывода и отдельного подвывода получают , снимая соответствующие допущения. Один случай не покрывает обе возможности. Разбор по случаям - отдельная конструкция, а не выбор более удобной ветви.
Пример: цепочка из двух импликаций
Докажем из посылок и . Это утверждение о составе доказательства, а не о том, истинно ли само по себе. Пусть означает «тест запущен», - «собран отчёт», - «команда получила результат». Посылки задают две условные связи; их фактическую истинность в конкретном проекте нужно устанавливать отдельно.

- - первая посылка.
- - вторая посылка.
- - временное допущение для подвывода.
- - устранение импликации по строкам 1 и 3.
- - устранение импликации по строкам 2 и 4.
- - введение импликации по подвыводу 3–5; допущение строки 3 снято.
В строке 5 формула зависит от и обеих посылок. После строки 6 зависимость от временного больше не открыта: заключение зависит от двух исходных посылок. Мы не доказали ни запуск теста, ни получение результата без условия. Если в вашем курсе требуют отдельную строку для закрытия рамки, добавьте её согласно принятому формату: логическое содержание рассуждения не меняется.
Как следить за областью допущения
Представьте рамку как локальный контекст. Внутри неё можно использовать посылки снаружи, а также новые строки, выведенные внутри. После закрытия наружу выходит формула, разрешённая правилом, например ; саму строку из закрытой области ссылкой использовать нельзя. Иначе условное утверждение незаметно превратится в безусловное.
Подвыводы могут быть вложенными. Допустим, внутри допущения открыли ещё одно допущение и получили . Закрыв внутреннюю область, получают , всё ещё зависящее от . Затем можно закрыть внешнюю область и вывести . При проверке отмечайте, какое именно допущение снимает каждое применение правила: похожие буквы в разных рамках могут обозначать разные вхождения.
Похожую дисциплину полезно соблюдать и при доказательстве от противного. Например, модус толленс использует условную связь и отрицание её следствия; он не разрешает без основания отрицать исходное условие. При этом набор правил отрицания зависит от выбранной версии логики.
Отрицание, кванторы и выбор системы
В одном распространённом варианте отрицание вводят через противоречие: если из временного допущения получено , то после снятия этого допущения можно записать . Символ обозначает противоречие, например результат применения правила к и . Отрицание снимает зависимость именно от временного , а не автоматически от всех прочих посылок.
Классический и интуиционистский натуральный вывод имеют много общих правил, но не совпадают. Например, переход от к допустим в классической системе; в интуиционистской он не является общим правилом. Поэтому до решения проверьте, какая система и какие сокращения разрешены в задании. Подробнее о структуре правил и вариантах систем рассказывает Stanford Encyclopedia of Philosophy.
В логике предикатов добавляются кванторы. Из можно получить для допустимого терма . Для введения недостаточно доказать свойство случайного конкретного объекта: объект в доказательстве должен быть достаточно произвольным и удовлетворять ограничениям правила, в частности не зависеть от специальных открытых допущений. Точные условия проверяют по формулировке своей системы. Аналогично при устранении требуется аккуратно выбирать новое имя для свидетеля, а не делать вывод о произвольном объекте.
Как проверить готовое доказательство
Начните с цели и её главной связки: для цели удобно попробовать допущение и подцель ; для нужны две подцели. Затем пройдите доказательство сверху вниз. У каждой строки спросите, существует ли указанное правило, доступны ли перечисленные строки и совпадают ли формулы с его схемой. Отдельно отметьте открытые допущения на последней строке.
На практике удобно чередовать два направления поиска. От цели двигайтесь назад: определите, какие строки позволили бы применить нужное правило. От посылок двигайтесь вперёд: посмотрите, какие доступные формулы можно безопасно извлечь. В нашем примере цель имеет вид импликации, поэтому открываем подвывод с ; затем первая посылка даёт , а вторая - . Когда направления встретились, проверьте запись уже в прямом порядке, не оставляя предположений о невыведенных строках. Такой поиск помогает найти доказательство, но не является отдельным правилом: в готовом решении каждый переход должен иметь своё обоснование. Если поиск зашёл в тупик, проверьте другой порядок применения правил или попытайтесь построить контрпример.
Проверка истинности тоже полезна: если найдена оценка, при которой все посылки истинны, а заключение ложно, корректного вывода в обычной классической системе не будет. Например, из нельзя получить : при ложном и истинном первая импликация истинна, а вторая ложна. Контрпример показывает ошибку в предполагаемом следовании; сам по себе он не заменяет построение вывода, когда следование верно.
Формальные доказательства применяют и в программировании. В системах проверки доказательств импликацию можно понимать через функцию, преобразующую свидетельство в свидетельство ; введению и устранению соответствуют построение и применение функции. Этот взгляд изложен в документации Theorem Proving in Lean. Для сравнения с общим способом организации теории полезен аксиоматический метод, а для перехода от гипотез к проверке наблюдений - гипотетико-дедуктивный метод.
Частые ошибки
- Выносить строку из закрытой рамки. Наружу переносится только результат, разрешённый правилом; зависимость от допущения учитывается в заключении.
- Переставлять условие и следствие. Из не следует ; проверьте возможную оценку формул.
- Указывать одно плечо разбора случаев. Для устранения нужно получить общий результат из каждого случая.
- Снимать все допущения сразу. Введение импликации снимает указанное допущение; другие открытые зависимости сохраняются.
- Применять классическое правило без проверки системы. Снятие двойного отрицания не является общим правилом интуиционистского вывода.
FAQ
Зачем временно предполагать то, что ещё не доказано?
Чтобы доказать условное утверждение: если из допущения получено , правило позволяет заключить , сняв указанное допущение. Само при этом не утверждается безусловно.
Чем посылка отличается от допущения?
Посылка входит в исходный набор задачи и остаётся зависимостью результата. Временное допущение открывает подвывод и может быть снято подходящим правилом; до этого строки внутри зависят от него.
Можно ли выводить формулы без посылок?
Да. Например, временно допустив и сразу используя его как результат подвывода, получают . После снятия допущения открытых посылок не остаётся.
Коротко
Натуральный вывод строит доказательство из посылок, правил для связок и временных допущений. Чтобы проверить результат, нужно сверить каждый шаг с правилом, границы подвыводов и оставшиеся зависимости. В примере из и получается : допущение снимается, но две исходные посылки сохраняются.
Читайте также

Исчисление предикатов: язык, формулы и правила вывода
Исчисление предикатов описывает свойства объектов и отношения между ними. Разбираем устройство формул, пошаговый пример доказательства и поиск контрмодели.

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

Контекстно-свободная грамматика: правила и примеры
Контекстно-свободная грамматика простыми словами: терминалы и нетерминалы, вывод слова, дерево разбора, неоднозначность и применение при анализе синтаксиса.

Метод резолюций: правило и пример доказательства
Метод резолюций в логике: как получить резольвенту, привести формулы к КНФ и доказать следствие через пустой дизъюнкт. Пошаговый пример и особенности унификации.

Регулярная грамматика: правила, примеры и автомат
Регулярная грамматика простыми словами: как устроены праволинейные правила, как вывести слово, построить конечный автомат и проверить границы модели на примерах.

Закон контрапозиции: формула и примеры
Закон контрапозиции в логике: как преобразовать импликацию, проверить равносильность по таблице истинности и применить её в доказательствах и программировании.