EssayAI
Блог
Блог
Естественные науки

Метод резолюций: правило и пример доказательства

8 ноября 2026Время чтения: 8 минут
#метод резолюций#математическая логика#дизъюнкт#унификация#автоматическое доказательство
Метод резолюций: правило и пример доказательства

Метод резолюций - способ проверять логические следствия, последовательно объединяя специальные формы высказываний. Он особенно удобен для автоматического доказательства: вместо множества разных правил используется одно основное правило вывода. Чтобы доказать утверждение, его отрицание добавляют к посылкам и ищут противоречие. В интерактивном примере ниже можно проследить оба шага от исходных дизъюнктов до пустого дизъюнкта.

Из чего состоит правило

Пусть PP и QQ - высказывания. Литерал - это атомарное высказывание либо его отрицание: например, PP и ¬P\neg P. Дизъюнкт - дизъюнкция литералов, то есть их соединение через «или»: ¬P∨Q\neg P\lor Q. Отдельный литерал тоже считается дизъюнктом.

Правило резолюции берёт два дизъюнкта с противоположными литералами. Выбираем одну такую пару, удаляем её и соединяем оставшиеся литералы через «или». Полученный дизъюнкт называется резольвентой:

A∨PB∨¬PA∨B.\frac{A\lor P\qquad B\lor\neg P}{A\lor B}.

Здесь AA и BB обозначают остальные части дизъюнктов; одна из них может отсутствовать. Например, из P∨RP\lor R и ¬P∨Q\neg P\lor Q получается R∨QR\lor Q. Порядок литералов несущественен, а повторения можно убрать: Q∨QQ\lor Q равносильно QQ.

Почему это законно? Если PP ложно, первый дизъюнкт вынуждает AA быть истинным. Если PP истинно, второй вынуждает быть истинным BB. В обоих случаях верно A∨BA\lor B. Таким образом, резольвента логически следует из своих родителей, хотя сама по себе обычно не равносильна их совокупности. Общие операции над формулами разобраны в статье об исчислении высказываний.

Сначала из P и ¬P ∨ Q получается Q, затем Q и ¬Q дают пустой дизъюнкт; повтор показывает, как результат первого шага становится посылкой второго.

Зачем добавлять отрицание цели

Допустим, нужно установить, следует ли заключение GG из посылок SS. Вместо прямого поиска GG метод проверяет совместность SS вместе с ¬G\neg G. Если общих моделей у них нет, то не существует ситуации, где все посылки истинны, а заключение ложно. Значит, S⊨GS\models G.

Символ ⊨\models означает семантическое следование: речь обо всех допустимых интерпретациях, а не об одном удачном примере. Идея доказательства от противного здесь выражается в механической форме: допущение противоположного приводит к невозможному набору требований. Это близко к рассуждениям по методу аналитических таблиц, хотя сами процедуры устроены по-разному.

Пустой дизъюнкт обозначают □\Box или ∅\varnothing. В нём нет ни одного литерала, который мог бы сделать дизъюнкцию истинной, поэтому он ложен при любой оценке. Его вывод доказывает несовместность исходного набора. Если противоречие уже содержалось в самих посылках, оно не подтверждает их содержательную правдоподобность: в классической логике из несовместных посылок следует любое заключение.

Как подготовить формулы к выводу

Для логики высказываний исходный набор приводят к конъюнктивной нормальной форме (КНФ): это конъюнкция дизъюнктов. Каждый дизъюнкт затем записывают отдельной строкой. Типичный порядок действий таков:

  1. Добавить к посылкам отрицание проверяемого заключения.
  2. Устранить импликации: A→BA\to B заменить на ¬A∨B\neg A\lor B.
  3. Перенести отрицания к атомам по законам де Моргана и убрать двойные отрицания.
  4. Раскрыть скобки распределением дизъюнкции относительно конъюнкции и выделить отдельные дизъюнкты.
  5. Применять резолюцию, сохраняя для каждого результата родителей и выбранную пару.

Например, ¬(P∧Q)\neg(P\land Q) превращается в ¬P∨¬Q\neg P\lor\neg Q, а P∨(Q∧R)P\lor(Q\land R) - в (P∨Q)∧(P∨R)(P\lor Q)\land(P\lor R). Важно не перепутать направления распределения: просто удалить скобки нельзя. Приведение может увеличить формулу; в практических SAT-процедурах используют и другие преобразования, сохраняющие выполнимость с добавлением переменных.

Пример: из двух посылок следует заключение

Проверим рассуждение: «Если выполнено PP, то выполнено QQ; PP истинно; следовательно, QQ». Отрицаем цель и добавляем ¬Q\neg Q. После замены импликации получаем три исходных дизъюнкта:

C1=P,C2=¬P∨Q,C3=¬Q.C_1=P,\qquad C_2=\neg P\lor Q,\qquad C_3=\neg Q.

Первый шаг применяет правило к C1C_1 и C2C_2 по паре PP, ¬P\neg P: остаётся C4=QC_4=Q. Второй шаг берёт C4C_4 и C3C_3 по паре QQ, ¬Q\neg Q: остаётся C5=□C_5=\Box. В первом результате один литерал, во втором - ноль. Именно эти значения видны в интерактиве.

Три исходных дизъюнкта дают Q и затем пустой дизъюнкт за два шага резолюции
Три исходных дизъюнкта дают Q и затем пустой дизъюнкт за два шага резолюции

Запись вывода позволяет проверить каждое звено независимо: C4=res⁡(C1,C2)C_4=\operatorname{res}(C_1,C_2), C5=res⁡(C4,C3)C_5=\operatorname{res}(C_4,C_3). Раз пустой дизъюнкт получен, исходные посылки вместе с отрицанием цели несовместны, а потому заключение QQ следует из посылок. Это тот же вывод, который в простой форме называют modus ponens; здесь он представлен как опровержение отрицания результата.

Как выбирать следующий шаг

Из одного набора часто можно получить несколько резольвент, поэтому порядок поиска важен. В примере выше удобно сначала соединить два коротких дизъюнкта по переменной PP: полученный одиночный литерал сразу сопоставляется с ¬Q\neg Q. Но это не единственный допустимый путь. Если сначала разрешить ¬P∨Q\neg P\lor Q и ¬Q\neg Q по переменной QQ, получится ¬P\neg P. Затем PP и ¬P\neg P также дадут пустой дизъюнкт. Оба вывода правильны и требуют двух шагов.

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

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

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

Унификация в логике предикатов

В логике предикатов противоположные литералы могут выглядеть по-разному из-за переменных. Унификация ищет подстановку, после которой атомы совпадут. Пусть есть дизъюнкты ¬Человек(x)∨Смертен(x)\neg Человек(x)\lor Смертен(x) и Человек(Сократ)Человек(Сократ). Подстановка x:=Сократx:=Сократ делает выбранные атомы одинаковыми и позволяет вывести Смертен(Сократ)Смертен(Сократ). Здесь переменная не является названием конкретного человека до применения подстановки.

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

Работу по формализации принципа резолюции и унификации для машинного доказательства предложил Джон Алан Робинсон в статье 1965 года. Это исторический первоисточник метода; на практике системы используют различные стратегии выбора пар, чтобы сократить поиск.

Что гарантирует метод и где он применяется

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

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

Резолюционные идеи применяются в автоматическом доказательстве теорем, проверке спецификаций и логическом программировании. Не всякий современный решатель буквально перебирает все пары: стратегии и дополнительные механизмы сильно влияют на эффективность. Связанный вопрос о трудности логических задач рассматривается в статье о классах P и NP.

Частые ошибки

  • Удалять сразу несколько противоположных пар. За один обычный шаг выбирают одну пару. Из P∨QP\lor Q и ¬P∨¬Q\neg P\lor\neg Q нельзя сразу получить пустой дизъюнкт: исходный набор выполним.
  • Считать резольвенту равносильной обоим родителям. Она является их следствием, но теряет часть информации.
  • Не отрицать цель. Тогда противоречие относится к другому набору и не доказывает нужное следование.
  • Считать отсутствие найденного вывода доказательством выполнимости. Это верно лишь после завершения подходящей полной процедуры, а не после произвольного числа попыток.
  • Путать пустой дизъюнкт с пустым набором дизъюнктов. Первый всегда ложен; пустая конъюнкция ограничений, напротив, истинна.

FAQ

Любые ли два дизъюнкта можно разрешить?

Нет. В них должна быть пара противоположных литералов; в случае предикатов атомы должны также унифицироваться. Если подходящих пар несколько, выбор пары меняет результат шага.

Что делать, если получилась тавтология?

Дизъюнкт вида P∨¬P∨RP\lor\neg P\lor R истинен при любой оценке. Для поиска противоречия его обычно можно отбросить: он не ограничивает множество моделей.

Доказывает ли пустой дизъюнкт истинность цели без условий?

Нет. Он доказывает, что цель следует из выбранных посылок. Чтобы утверждать цель без оговорок, отдельно нужны основания принять сами посылки.

Коротко

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

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Исчисление предикатов: язык, формулы и правила вывода

Исчисление предикатов: язык, формулы и правила вывода

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

8 ноября 20268 минут
Метод аналитических таблиц: правила и примеры

Метод аналитических таблиц: правила и примеры

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

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

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

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

8 ноября 20269 минут
Стандартизация: цели и принципы простыми словами

Стандартизация: цели и принципы простыми словами

Стандартизация: цели и принципы простыми словами. Зачем нужны стандарты, что такое унификация и ряды предпочтительных чисел, чем ГОСТ отличается от СТО и какие правила лежат в основе стандартов.

11 июня 20267 минут
Унификация и агрегатирование в стандартизации: суть, формулы

Унификация и агрегатирование в стандартизации: суть, формулы

Унификация и агрегатирование в стандартизации простыми словами: чем эти методы отличаются, как считать коэффициент применяемости и коэффициент агрегатирования и где чаще всего ошибаются студенты.

11 июня 20268 минут
Коллизионный и материально-правовой метод в МЧП

Коллизионный и материально-правовой метод в МЧП

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

7 ноября 20268 минут