Полнота разрешения и пункты в искусственном интеллекте

Чтобы завершить нашу тему резолюции, мы попытаемся понять, почему PL-РАЗРЕШЕНИЕ завершено. Для этого мы предлагаем закрытие резолюции из набора статей , который представляет собой набор всех предложений, производных от предложений в или их производных путем многократного применения правила разрешения. Замыкание разрешения — это окончательное значение переменных предложений, вычисленное с помощью PL-РАЗРЕШЕНИЕ. Потому что есть только ограниченное количество отдельных фраз, которые могут быть созданы из символов. которые существуют в S, должно быть конечным. (Обратите внимание, что без фазы факторизации, которая устраняет многочисленные копии литерала, это было бы неверно.) В результате PL-РАЗРЕШЕНИЕ всегда заканчивается.

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

Доказано обратное этой теореме: если замыкание не содержит пустого предложения, то является удовлетворительным. На самом деле мы можем построить модель для который включает в себя соответствующие значения истинности для . Ниже приведена процедура построения: Для от 1 до k, присвойте значение false если пункт в имеет буквальное и все остальные его литералы ложны при задании, указанном для В противном случае, должно быть установлено значение true.

Это задание на . Предположим противное — что присвоение символа в какой-то момент в последовательности вызывает некоторое предложение стать ложным. Для этого все другие литералы в должны быть уже сфальсифицированы заданиями на . Как результат, теперь должен напоминать либо

Определенные оговорки и оговорки Хорна

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

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

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

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

Только базы знаний с определенными предложениями интересны по трем причинам:

1. Каждое определенное предложение может быть выведено с одним положительным литералом в качестве заключения и положительной буквальной конъюнкцией в качестве посылки. Определенная фраза , например, можно представить в виде импликации Фразу проще понять в форме импликации: если агент находится в [1,1] и есть ветер, то [1,1] ветрено. Посылка известна как тело, а заключение известно как голова в форме Рога. Факт — это утверждение, состоящее из одного положительного литерала, например . можно также выразить в форме импликации, но проще просто написать .
2. Методы прямой и обратной цепочки могут использоваться для вывода с использованием предложений Хорна. Оба эти алгоритма естественны в том смысле, что процессы вывода понятны и просты для понимания людьми. Логическое программирование основано на этой форме вывода.
3. Предложения Хорна могут определить следствие за время, пропорциональное размеру базы знаний, что является приятным сюрпризом.