Интуиционистская логика: доказательство и законы

Интуиционистская логика изучает выводы, сохраняющие конструктивный смысл доказательства. Чтобы утверждать «существует объект», недостаточно получить противоречие из предположения, что объекта нет: нужно предъявить объект и доказать его свойство. Чтобы доказать «А или Б», нужно указать ветвь и обосновать её. Поэтому некоторые привычные классические схемы здесь не принимаются как общие законы.
Это не логика догадок или личных ощущений. Её правила точны, а доказательства проверяемы. Выберите вопрос в форме, чтобы разобрать конкретную связку или сравнить два способа вывода.
От конструкций к логике
Истоки направления связаны с математическим интуиционизмом Лёйтзена Брауэра: математический объект должен быть задан допустимым построением. Аренд Гейтинг формализовал логику, выражающую допустимые в таком подходе рассуждения. Важно различать философию Брауэра, отдельные системы конструктивной математики и саму интуиционистскую логику: последнюю можно изучать формально, не принимая всю философскую программу.
Для сравнения, в интерпретации формул логики предикатов смысл формулы рассматривают через модель, область и значения символов. Здесь первый вопрос иной: какие данные составляют доказательство составного утверждения? Формальные модели тоже существуют, и ниже одна из них покажет предел классического правила. Слово «интуиционизм» встречается и в другом контексте: этический интуитивизм обсуждает основания морального знания, а не правила математического вывода. Общий термин не делает эти теории одной и той же позицией.
Что считается доказательством связок
Объяснение Брауэра - Гейтинга - Колмогорова, или BHK, связывает логические операции с конструкциями. Пусть и - утверждения. Тогда:
- Для нужны доказательства обоих утверждений.
- Для нужно выбрать одну ветвь и доказать её.
- Для нужна конструкция, превращающая любое доказательство в доказательство .
- Для , то есть , нужна конструкция, которая из предполагаемого доказательства получает противоречие .
- Для нужен свидетель и доказательство ; для - общий способ получить доказательство для каждого допустимого .
Например, доказательство импликации «если число делится на четыре, то оно чётное» задаёт общий переход: запись числа как произведения четырёх на целое преобразуется в запись как произведения двух на целое. Проверка нескольких чисел здесь не заменит общий переход. Аналогично доказательство дизъюнкции передаёт не только уверенность, что одна из ветвей верна, но и указание, какая именно ветвь доказана. Это требование относится к построенному доказательству, а не к обязательному перебору всех возможных утверждений.
Знак обозначает невозможное утверждение; из него в обычной интуиционистской логике можно вывести любое утверждение. О самих обозначениях подробнее рассказывает статья о кванторах всеобщности и существования. Например, свидетель для «существует чётное натуральное число больше двух» - число четыре, вместе с проверкой его свойств. Фраза «такое число не может не существовать» сама по себе ещё не предъявляет свидетель.
Почему исключённое третье не является общим законом
В классической логике схема доказуема для любого . В конструктивном чтении для доказательства этой дизъюнкции нужно иметь доказательство либо преобразование любого доказательства в противоречие. Универсального способа выбрать одну из ветвей для произвольного утверждения логика не предоставляет. В работе «О ненадёжности логических принципов» Брауэр ставил под вопрос перенос таких принципов с конечных проверок на бесконечные области.
Это не означает доказательства противоположного, : такая общая схема тоже не выводится. Если конкретное утверждение разрешимо, исключённое третье для него доказуемо. Например, для заданного натурального числа можно проверить делители и установить, простое оно или нет. Проблема возникает при превращении такого метода для конкретного случая в безусловное правило для любой формулы, в том числе об открытой бесконечной области.
Двухузловая модель Крипке
В семантическом анализе Крипке формулы рассматриваются относительно упорядоченных состояний. Представим два состояния, или узла: . Переход вправо означает допустимое расширение информации; установленные утверждения сохраняются. Пусть атомарное выполнено в , но не выполнено в . Для отрицания в узле необходимо, чтобы не выполнялось ни в одном доступном расширении, включая сам узел.
В нет по построению. Нет там и : доступный узел уже выполняет . Дизъюнкция выполняется в узле, когда в нём выполняется хотя бы одна её ветвь, поэтому в не выполняется. В она выполняется благодаря . Это контрмодель к общезначимости схемы: одного корректного примера достаточно, чтобы показать, что схема не выводится из правил, сохраняющих истинность во всех таких моделях.

Порядок узлов важен: модель не утверждает, что каждое состояние обязательно превратится в следующее в реальном времени. Стрелка задаёт отношение доступности, позволяющее проверить условия выполнения формул. В нашем примере возможного расширения достаточно, чтобы исключить выполнение отрицания в исходном узле. Поэтому не нужно ждать, пока кто-то фактически найдёт доказательство: речь идёт о свойствах специально построенной математической модели.
Отсутствие выполнения в узле не следует путать с выполнением отрицания. Модель описывает отношения между формулами и состояниями, а не вводит особое третье истинностное значение.
Двойное отрицание и доказательство от противного
Переход допустим. Действительно, имея доказательство и предполагая , мы применяем отрицание к доказательству и получаем противоречие. Значит, предположение опровергнуто.
Обратный переход в общем случае не выводится. В приведённой модели выполняется уже в : ни в , ни в не выполняется . Однако в не выполняется. Поэтому та же двухузловая конструкция отделяет двойное отрицание от самого утверждения.
При этом рассуждение от противного не запрещено целиком. Чтобы доказать , можно предположить и вывести противоречие. Но если предположить и получить противоречие, непосредственно получается лишь ; для перехода к требуется дополнительное основание, например разрешимость конкретного . Это полезное различие при проверке каждого шага доказательства. Например, если отдельно построен алгоритм, который для данного выбирает доказательство или доказательство , то из можно получить : в ветви отрицания возникает противоречие, а в другой ветви нужное доказательство уже есть. Без такого алгоритма этот аргумент не работает для произвольной формулы.
От доказательства к программе
Соответствие Карри - Ховарда связывает доказательства с программами, а утверждения с типами. В этой аналогии доказательство похоже на функцию, принимающую значение типа и возвращающую значение типа . Доказательство конъюнкции похоже на пару значений, а доказательство дизъюнкции - на значение с меткой выбранного варианта.
Для существования вместе с доказательством свойства передаётся свидетель. Это объясняет практический интерес к конструктивным системам и проверке программ: из достаточно явного доказательства можно извлечь вычислительное содержание. Но соответствие не превращает любое математическое доказательство автоматически в эффективную программу: важны конкретная система типов, её правила и способ извлечения.
В обычном программировании также полезно различать спецификацию и реализацию. Утверждение, что ответ не может отсутствовать, ещё не показывает алгоритм его нахождения. А алгоритм Кнута - Морриса - Пратта демонстрирует другую сторону: явная процедура не просто обещает найти совпадение, но задаёт последовательность действий. Сложность и корректность такой процедуры нужно доказывать отдельно. В частности, корректность связывает выход алгоритма с условием задачи, а оценка сложности говорит о требуемых ресурсах. Даже когда свидетель найден конструктивно, эти два вопроса остаются разными. Это помогает не смешивать доказуемость существования решения, возможность его вычислить и стоимость вычисления.
Частые ошибки
- Считать отрицание отсутствием знания. требует вывода противоречия из ; незнание доказательства ещё не даёт такого вывода.
- Считать исключённое третье опровергнутым для всех формул. Общая схема не доказывается, но для разрешимых конкретных утверждений она доступна.
- Запрещать любой вывод от противного. Доказательство отрицания через противоречие остаётся допустимым; спорным является общий переход от двойного отрицания к утверждению.
- Приравнивать логику к философии интуиции. Формальные правила можно изучать независимо от бытового значения слова и от принятия всех взглядов Брауэра.
FAQ
Интуиционистская логика слабее классической?
В смысле множества теорем стандартная интуиционистская логика выводит меньше классических схем. При добавлении исключённого третьего получается классическая логика. «Слабее» здесь означает отношение формальных систем, а не оценку их полезности.
Можно ли использовать таблицы истинности?
Обычные двухзначные таблицы проверяют классическую общезначимость и не отделяют все классические законы от интуиционистских. Для этого подходят, например, модели Крипке или алгебры Гейтинга.
Нужен ли конкретный числовой пример для любого существования?
Нужен свидетель соответствующего типа и доказательство свойства. Это может быть число, функция или другой объект; допустимость построения зависит от выбранной конструктивной теории.
Коротко
Интуиционистская логика сохраняет конструктивное содержание вывода: дизъюнкция требует выбранной ветви, существование - свидетеля, импликация - преобразования доказательств. Поэтому исключённое третье и снятие двойного отрицания не являются общими правилами, хотя работают в отдельных разрешимых случаях. Модель Крипке показывает это различие формально, а связь с типами объясняет интерес к логике в информатике.
Читайте также

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

Абсолютное и избыточное давление: формулы и вакуум
Абсолютное и избыточное давление, разрежение и вакуум: как выбрать начало отсчёта, перевести показания манометра и решить задачи с примерами в килопаскалях.

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

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

Адиабатический процесс: уравнение Пуассона и расчёт
Уравнение Пуассона для адиабатического процесса: вывод через первое начало термодинамики, связь давления, объёма и температуры, пример и границы применения.

Адресация: прямая, косвенная и непосредственная
Разбираем прямую, косвенную и непосредственную адресацию операндов на одном примере памяти: как найти значение, посчитать чтения и не перепутать адрес с данными.