Метод резолюций - это мощный инструмент логического вывода, позволяющий проверять противоречивость или выводимость формул в исчислении предикатов. Он был предложен в 1965 году Джоном Робинсоном и с тех пор широко применяется в информатике и искусственном интеллекте.
Основные понятия метода резолюций
Метод резолюций основан на преобразовании формул в конъюнктивную нормальную форму и применении правила резолюций. Рассмотрим основные определения.
Дизъюнкт - дизъюнкция литералов (атомарных формул или их отрицаний).
Резольвента - результат применения правила резолюций к двум дизъюнктам.
Пустой дизъюнкт - дизъюнкт, не содержащий литералов.
Исторически метод резолюций восходит к работам Жака Эрбрана 1930-х годов. В 1965 году Джон Робинсон формализовал это правило вывода и доказал его полноту.
Метод резолюций применяется для автоматического доказательства теорем, в системах искусственного интеллекта, для проверки непротиворечивости баз знаний.
Правило резолюций в логике высказываний
В логике высказываний правило резолюций формулируется следующим образом:
Если есть дизъюнкты вида C ∨ A и ¬C ∨ B, то из них можно получить резольвенту A ∨ B.
Например, из дизъюнктов p ∨ q и ¬p ∨ r получаем резольвенту q ∨ r.
Для доказательства выводимости формулы F из множества формул Γ применяем следующий алгоритм:
- Переводим все формулы в КНФ и получаем множество дизъюнктов S.
- К S добавляем отрицание формулы F.
- Последовательно применяем правило резолюций, пока не получим пустой дизъюнкт.
Если пустой дизъюнкт получен, значит F логически следует из Γ.
Подстановки и унификация в логике 1-го порядка
В логике 1-го порядка помимо правила резолюций используется унификация - нахождение подстановки термов, приводящей дизъюнкты к одинаковому виду.
Подстановка - замена переменных на термы в дизъюнкте.
Унификатор - подстановка, приводящая дизъюнкты к одному виду.
Например, подстановка {x/a} примененная к дизъюнктам P(x) ∨ Q(y) и ¬P(a) ∨ R(b) дает унифицированные дизъюнкты P(a) ∨ Q(y) и ¬P(a) ∨ R(b).
Доказана теорема о существовании универсального унификатора - такой подстановки, которая унифицирует дизъюнкты при любой другой подстановке.
Унификация позволяет эффективно применять правило резолюций в логике 1-го порядка.
Теорема Мальцева о компактности
Теорема Мальцева утверждает, что если каждое конечное подмножество множества формул S выполнимо, то выполнимо и все множество S.
Это важное свойство позволяет переносить результат о выполнимости конечных частей теории на бесконечную теорию целиком. Например, из выполнимости всех конечных аксиом теории множеств следует выполнимость всей теории множеств.
Теорема Мальцева широко используется в математической логике для доказательства свойств бесконечных теорий.
Применение метода резолюций на Прологе
Язык программирования Пролог хорошо приспособлен для реализации метода резолюций.
Программа на Прологе состоит из фактов и правил вида "A если B". Это по сути дизъюнкты вида A ∨ ¬B.
Интерпретатор Пролога автоматически применяет метод резолюций к заданным фактам и правилам для проверки истинности заключения.
Например, можно записать программу:
q :- p. p.
И интерпретатор Пролога докажет истинность высказывания q, применив один шаг резолюции.
Таким образом, Пролог хорошо подходит для проверки выводимости с помощью метода резолюций.
Пример программы на Прологе с использованием метода резолюций
Рассмотрим более развернутый пример программы на Прологе, демонстрирующий проверку истинности заключения методом резолюций.
высокий(Вася). высокий(Коля). играетВБаскетбол(X) :- высокий(X). вывод(баскетболист(Вася)).
Здесь заданы два факта о том, что Вася и Коля высокие. Далее правило, что если человек высокий, то он играет в баскетбол. И наконец, вывод, который нужно проверить.
Интерпретатор Пролога применит резолюцию к факту "высокий(Вася)" и правилу "играетВБаскетбол(X) :- высокий(X)", чтобы получить новый факт "играетВБаскетбол(Вася)". А затем проверит истинность заключения "баскетболист(Вася)" на основе этого факта.
Метод резолюций для решения логических задач
Метод резолюций может быть использован для решения различных логических задач, например, задач на рассуждение.
Для этого условие задачи преобразуется в набор дизъюнктов, а заключение, которое нужно проверить - в отрицание искомого утверждения.
Затем методом резолюций пытаемся вывести пустой дизъюнкт. Если это удается сделать - значит, заключение следует из условия.
Оптимизация метода резолюций
Существуют различные способы оптимизации метода резолюций:
- Использование эвристик для выбора порядка применения резолюций.
- Ограничение глубины вывода.
- Предварительная обработка для упрощения дизъюнктов.
Эти методы позволяют сократить количество шагов вывода и ускорить процесс доказательства.
Приложения метода резолюций в ИИ
Важнейшим приложением метода резолюций являются системы автоматического доказательства теорем и логического программирования.
Метод резолюций лежит в основе языка Пролог. Он применяется в интеллектуальных для verificati
Метод резолюций лежит в основе языка Пролог. Он применяется в интеллектуальных помощниках, экспертных системах, для верификации программ, в системах распознавания образов и многих других приложениях ИИ.
Эффективная реализация метода резолюций позволяет автоматизировать логический вывод в этих системах.
Пример применения метода резолюций в системе распознавания образов
Рассмотрим применение метода резолюций в системе распознавания рукописных цифр.
Изображение цифры представляется как набор признаков - наличие линий определенной формы в разных частях изображения. Эти признаки записываются в виде логических высказываний.
Например, для цифры 1 характерны:
- Наличие вертикальной линии слева.
- Наличие горизонтальной линии сверху.
- Отсутствие замкнутых контуров.
А для цифры 8:
- Наличие двух замкнутых контуров.
- Пересечение контуров.
Эти признаки преобразуются в дизъюнкты. Далее методом резолюций проверяется, какие классы цифр (наборы признаков) согласуются с наблюдаемыми признаками на изображении.
Применение метода резолюций в интеллектуальных помощниках
Метод резолюций используется в диалоговых системах и интеллектуальных помощниках для логического вывода.
Пользовательский запрос преобразуется в набор дизъюнктов. Эти дизъюнкты комбинируются с фактами из базы знаний системы с помощью резолюций.
Таким образом, система может делать новые логические выводы из имеющихся фактов, чтобы ответить на запрос пользователя.
Применение метода резолюций для верификации программ
Метод резолюций может быть использован для проверки правильности программ.
Утверждения о поведении программы формализуются как набор дизъюнктов. Затем с помощью резолюций проверяется, не приводит ли программа к нарушению этих спецификаций.
Такой подход позволяет доказать частичную или полную корректность программы в рамках заданных требований.
Недостатки метода резолюций
При всех достоинствах, у метода резолюций есть и недостатки:
- Экспоненциальная сложность в худшем случае.
- Не оптимален - дает избыточные выводы.
- Требует предварительной обработки исходных данных.
Поэтому ведутся работы по улучшению этого метода с помощью эвристик и ограничений.
