Применение метода резолюций для ответов на вопросы
Предположим, что у нас есть предикат F(x,y), означающий, что x - отец y, и истинна следующая формула
F(john,harry) Ù F(john,sid) Ù F(sid,liz).
Таким образом, у нас есть три дизъюнкта. Они не содержат переменных или импликаций, а просто представляют базисные факты.
Введем еще три предиката M(x), S(x,y) и B(x,y), означающие соответственно, что x - мужчина, что он единокровен с y, что он брат y. Мы можем записать следующие аксиомы о семейных отношениях.
"x,y (F(x,y) Þ M(x))
"x,y,w (F(x,y) Ù F(x,w) Þ S(y,w))
"x,y (S(x,y) Ù M(x) Þ B(x,y))
Они утверждают следующее: 1) все отцы - мужчины; 2) если у детей один отец, то они единокровны; 3) брат - это единокровный мужчина.
Пусть мы задали вопрос $z B(z,harry)? Чтобы найти ответ с помощью метода резолюции, мы записываем отрицание вопроса "z ØB(z,harry). Затем приводим аксиомы к нормальной форме и записываем каждый дизъюнкт в отдельной строке (так как каждый дизъюнкт истинен сам по себе):
| ØF(x,y) Ú M(x) | (1) | ||
| ØF(x,y) Ú ØF(x,w) Ú S(y,w) | (2) | ||
| ØS(x,y) Ú ØM(x) Ú B(x,y) | (3) | ||
| F(john,harry) | (4) | ||
| F(john,sid) | (5) | ||
| F(sid,liz) | (6) | ||
| ØB(z,harry) | (7) |
Мы не пишем внешних кванторов всеобщности, так как подразумевается, что каждая переменная связана таким квантором.
Для применения резолюции необходимо найти для данной пары дизъюнктов такую подстановку термов вместо переменных, чтобы после нее некоторый литерал одного из дизъюнктов стал отличаться от некоторого литерала другого дизъюнкта лишь отрицанием. Мы можем делать подстановки, так как все переменные связаны кванторами всеобщности. Если, например, мы подставим john вместо x и sid вместо y, то получим следующее:
ØF(john,sid) Ú ØF(john,w) Ú S(sid,w).
Мы можем применить правило резолюции к этому дизъюнкту и (5), что дает новый дизъюнкт:
| ØF(john,w) Ú S(sid,w)
из (5) и (2) {x->john,y->sid} | (8) |
Продолжая, получим
|
S(sid,harry) из (4) и (8) {w->harry} |
(9) |
|
M(sid) из (6) и (1) {x->sid,y->liz} |
(10) |
|
ØS(sid,y) Ú B(sid,y) из (10) и (3) {x->sid} |
(11) |
|
B(sid,harry) из (9) и (11) {y->harry} |
(12) |
|
пустой дизъюнкт из (12) и (7) {z->sid} |
2. ВВЕДЕНИЕ В ЯЗЫК ПРОЛОГ
"… инструменты, которые мы пытаемся использовать, а также язык (язык программирования в том числе) или обозначения, применяемые нами для выражения или записи наших мыслей, являются главными факторами, определяющими нашу способность хоть что-то думать или выражать!"
Из лекции лауреата премии Тьюринга за 1972 год Э. Дейкстры.