В третьем столбце таблицы записаны
Предполагается, что
X(smart(X)=¬stupid(X)) и
Y(wealthy(Y)=¬poor(Y)). В третьем столбце таблицы записаны дизъюнкты.
Таблица 3.2. Интересная жизньУтверждения и заключениеПредикатыПредложения(дизъюнкты)
1. Все небедные и умные люди счастливы
X(¬poor(X) smart(X)
happy(X))
|
poor(X) ¬smart(X) & happy(X)
|
2. Человек, читающий книги, - неглуп
Y (read(Y) smart(Y))
|
¬read(Y) & smart(Y)
|
3. Джон умеет читать и является состоятельным человеком
read(John) ¬poor(John)
|
3a read(John) 3b ¬poor(John)
|
4. Счастливые люди живут интересной жизнью
Z (happy(Z)exciting(Z))
|
¬happy(Z)&exciting(Z)
|
5. Заключение: Существует ли человек, живущий интересной жизнью?
W(exciting(W))
|
exciting(W)
|
6. Отрицание заключения
¬W(exciting(W))
|
¬exciting(W)
|
Отрицание заключения имеет вид (строка 6): ¬
W(exciting(W))
Одно из возможных доказательств (их более одного) дает следующую последовательность резольвент:
¬happy(Z)резольвента 6 и 4
poor(X) ¬smart(X)резольвента 7 и 1
poor(Y) ¬read(Y)резольвента 8 и 2
¬read(John)резольвента 9 и 3b
NILрезольвента 10 и 3a
Символ NIL означает, что база данных выражений содержит противоречие и поэтому наше предположение, что не существует человек, живущий интересной жизнью, неверно.
В методе резолюции порядок комбинации дизъюнктивных выражений не устанавливался. Значит, для больших задач будет наблюдаться экспоненциальный рост числа возможных комбинаций. Поэтому в процедурах резолюции большое значение имеют также эвристики поиска и различные стратегии. Одна из самых простых и понятных стратегий - стратегия предпочтения единичного выражения, которая гарантирует, что резольвента будет меньше, чем наибольшее родительское выражение. Ведь в итоге мы должны получить выражение, не содержащее литералов вообще.
Среди других стратегий (поиск в ширину (breadth-first), стратегия "множества поддержки", стратегия линейной входной формы) стратегия "множества поддержки" показывает отличные результаты при поиске в больших пространствах дизъюнктивных выражений [2].
Содержание Назад Вперед