Пример 3 (Дедуктивные базы данных)
Отметим вначале одно свойство метода резолюций. Пусть сигнатура состоит из двух символов двухместных предикатов P и Q, которые интерпретируются следующим образом: P(x,y) означает, что х– сын y, Q(x,z) означает, что х– внук z. Рассмотрим формулы: F1="x,y,z (P(x,y)&P(y,z) É Q(x,z)), F2="x $yP(x,y), G="x $zQ(x,z), смысл которых достаточно ясен. Используя метод резолюций, покажем, что G есть логическое следствие F1 и F2. Приведем формулы F1,F2 и G к сколемовской нормальной форме, получим дизъюнкты: D1= P(x,y) Ú P(y,z) ÚQ(x,z), D2=P(x,f(x)), D3= Q(a,z). Вывод пустого дизъюнкта получается довольно просто: D4= P(a,y) Ú P(y,z) ((D1 D3,){x=a}), D5= P(f(a),z) ((D2 D4 ),{x=a, y=f(a)}), D6=□ ((D2 D5), {x=f(a),z=f(f(a))}.
Подстановка z=f(f(a)) означает, что дед элемента a есть отец отца элемента a. Таким образом, метод резолюций не только устанавливает факт логического следствия формулы G из формул F1 и F2, но еще и «подсказывает», как по данному х получить z такой, чтобы формула Q(x,z) была истинна. Довольно часто интересующая нас переменная участвует не в одной подстановке, как в этом примере переменная z, а в нескольких. Для того, чтобы отследить все подстановки, в которых может изменить значение переменная, к формуле G добавляют литерал ответа ANS(z) и заканчивают вывод не пустым дизъюнктом, а литералом ответа.
Пример 4 (Планирование действий). В качестве примера использования метода резолюций в задачах планирования действий рассмотрим известную в теории искусственного интеллекта задачу об обезьяне и бананах. В задаче говорится об обезьяне, которая хочет съесть бананы, подвешенные к потолку комнаты. Рост обезьяны недостаточен, чтобы достать бананы. Однако в комнате есть стул, встав на который обезьяна может достать бананы. Какие ей надо совершить действия, чтобы достать бананы? Задачу формализуем следующим образом. Комнату с находящимися в ней обезьяной, стулом и бананами будем называть предметной областью. Конкретное местонахождение в комнате обезьяны, стула и бананов будем называть состоянием предметной области. Рассмотрим два предиката P(x,y,z,s) и R(z). Пусть P(x,y,z,s) означает, что в состоянии s обезьяна находится в точке x, стул – в y, бананы – в z, R(s) означает, что в состоянии s обезьяна взяла бананы.
Возможности обезьяны формализуем следующим образом. Введем три функции, которые принимают значения в множестве состояний: ИДТИ(x,y,s) – состояние, которое получится из s, если обезьяна из точки x перешла в y, НЕСТИ(x,y,s) – состояние, которое получится из s, если обезьяна перенесла стул из точки x в y, БРАТЬ(s) – состояние, которое получится из s, если обезьяна взяла бананы.
Условия задачи запишутся в виде следующих формул: F1= "x,y,z,s (P(x,y,z,s) ÉP(y,y,z, ИДТИ(x,y,s)), F2="x, u, s (P(x,x,u,s) É P(u,u,u, НЕСТИ(x,u,s)) , F3="x (P(x,x,x,s) ÉR(БРАТЬ(s))).
F4=P(a,b,c,s0). Надо показать, что формула G=$sR(s) есть логическое следствие формул F1,F2,F3,F4.
Из множества формул F1,F2,F3,F4,G получим множество дизъюнктов D1–D5 (к дизъюнкту, полученному из G добавлен литерал ответа ANS(s)): D1= P(x,y,z,s) Ú P(y,y,z,ИДТИ(x,y,s)), D2= P(x,x,u,s,) ÚP(u,u,u,НЕСТИ(x,u,s)), D3= P(x,x,x,s) ÚR(БРАТЬ(s)), D4=P(a,b,c,s0), D5= R(s) ÚANS(s).
Последовательность дизъюнктов D1–D5 продолжаем до вывода литерала ответа: D6= P(x,x,x,s) ÚANS(БРАТЬ(s)) (из D3 D5), D7= P(x,x,u,s) ÚANS(БРАТЬ(НЕСТИ(x,u,s))) (из D2 и D6), D8= P(x,y,z,s) ÚANS(БРАТЬ(НЕСТИ((y,z,ИДТИ(x,y,s)))) (из D1 и D7), D9=ANS(БРАТЬ(НЕСТИ(b,c,ИДТИ((a,b,s0)))) (из D4 и D8).
Итак, для того, чтобы обезьяне взять бананы, надо сначала из точки а идти в точку b, затем из точки b нести стул в точку с и в точке с, встав на стул, взять бананы.
Популярное: Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (569)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |