Intel_Nils (526801), страница 45
Текст из файла (страница 45)
п. формул, описывающее результирующее состояние. Правила преобразования можно задать в виде списка п. п. формул, которые должны быть изъяты, и списка п. п. формул, которые следует добавить; прн этом предполагается, что те и. и. формулы, которые не были изъяты, остаются н в новом описании состояния. На таком языке наши четыре оператора можно определить следующим образом; ') Нате Ьнпнпнз (нметь бананы). — Прим. нерее. ') Быть в определенном месте.
— Прим. иерее. 226 Гл. 7. Применения иечиеления предикатав к ретиению задач подойти (и) П. и. формула применимости: ОМВОХ Преобразования изъять: АТ (обезьяна, Я) добавить: АТ (обезьяна, и). Здесь символ 1) стоит вместо любого терма.
Правильно построенная формула АТ (обезьяна, Э) должна быть изъята независимо от значения Э. Так как «подойта (и)» представляет собой операторную схему, то ее применение даст схему описания состояния, содержащую переменную и. Приписывая этой переменной конкретное (константное) значение н, получаем конкретное описание состояния. передвинуть (ч) П. и. формула применимости: ОМВОХ Л (Зх) (АТ (обезьяна,'х) Л АТ (ящик, х)) Преобразования изъять: АТ (обезьяна, 3) АТ (ящик, 3) АТ (обезьяна, ч) АТ (ящик, ч) добавить: взобраться П. и. формула применимости: ОМВОХ Л Ях)(АТ (обе зьЯна, х) Л АТ (ящик, х)) ПРеобразования изъять: добавить: ОИВОХ Ог(ВОХ схватить П.
п. формула применимости: Преобразования изъять: добавить: Оо(ВОХ Л АТ (ящик, с) НВ НВ. При формулировке правил изъятий и добавлений, определяющих преобразование п. п. формул, осуществляемое операторами, нужно проследить за тем, чтобы изъятые п. п. формулы не следовали из неизъятых п. и. формул, ибо в противном случае эти изъятые п.
п. формулы могли бы опять оказаться выведенными. Теперь поиск целевого состояния может протекать на основе стандартного процесса применения применимых операторов Хб. Осиольвование иснисленин арединагов ира реисениа вада« Иг к начальному состоянию Яо и к результирующим состояниям, до тех пор пока не будет получено описание состояния, содержашее целевой преднкат НВ. Поскольку мы пользуемся операторными схемами, мы построим сейчас граф схем описаний состояний (идентичный графу рис.
2ЗО). Первым шагом нашего процесса поиска (перебора) будет выяснение того, следует ли НВ нз Яо. Формально эту проверку можно осуществить, строя отрицание п..п. формулы, которую нужно доказать, и используя затем методы поиска доказательства на основе резольвенции для вывода противоречия. Так как очевидно, что никакого противоречия из (Яа)() НВ вывести нельзя (невозможны никакие резольвенции), то мы заключаем, что результат проверки выполнения условия достижения цели отрицателен. Следующий шаг в простейшем процессе перебора в пространстве состояний — выяснение, какой из операторов применим.
Здесь опять можно использовать методы доказательства теорем на основе резольвенции. Для каждого оператора можно было бы попытаться доказать, что его п. п. формула применимости следует из Яо. Тогда мы быстро обнаружили бы, что оператор' «схватить» неприменим. Правильно построенные формулы применимости для операторов «взобраться» и «передвинуть» совпадают.
Отрицание этой общей п. п. формулы применимости (в форме предложения) имеет вид ОХВОХ~/ АТ (обезьяна, х)~/ АТ(ящик, х). Попытка вывести его противоречие с Яо здесь также окончится неудачей, так что операторы «взобраться» и «передвннуть» также неприменимы к Яо. Наконец, нам удастся доказать, что оператор подойти применим к Ба. Используя правило преобразования для оператора «подойти (и)», приходим к следующей схеме описания состояний: ОХВОХ АТ (ящик, Ь) АТ (обезьяна, и) НВ Теперь процесс повторяется. Сначала мы выясняем, сушествует ли частный случай схемы Зь из которого следует целевая п. п.
формула НВ. Очевидно, что иет. Далее мы находим операторы, которые можно применить к частным случаям схемы Яь Например, при проверке применимости оператора «передвинуть (ч)» мы хотим узнать, существует ли частный случай схемы Яь из которого следует п. п. формула Ой)ВОХЛ (:-)х) АТ(обезьяна, х) ЛАТ(яшик, х). Мы видим, что подстановка в 8~ вместо и величины Ь дает частный случай, к которому оператор «передвннуть» применим. Обозначим этот частный 228 Гв, 7.
Ггримененан иечиевенин нредикатав к решению вадач случай через о(. Обязательно нужно проследить за тем, чтобы и было заменено на Ь во всех случаях вхождения и в Зь (В нашем случае имеется ровно одно вхождение, но их могло бы быть и больше.) Поскольку к о( применим оператор «передвинуть», к о1 применим также н оператор «взобраться», но оператор «схватить» неприменим ни к одному частному случаю схемы оь К любому частному случаю схемы 31 применим, конечно, также и оператор «подойти», но его применение не изменяет схему опиСания состояния. Теперь, если применить оператор «передвинуть (и)» к о1, то получится схема описания состояния ОЫВОХ АТ (ящик, ч) АТ (обезьяна, ч) НВ Другая схема получится, если применить к о1 оператор «взобраться». Этот процесс продолжается до тех пор, пока не будет удовлетворен целевой предикат.
В результате создается граф, совпадающий по форме с графом рис. 2.10. После этого нетрудно извлечь решающую последовательность операторов (с соответствующим образом выбранными конкретными значениями схемных переменных). Учитывая различия и пользуясь ключевыми операторами, как в гл.
4, можно было бы также использовать для решения этой задачи подход, основанный на сведении задачи к совокупности подзадач. Тогда в качестве условий цели для подзадач, образованных в результате попытки применить ключевые операторы, выступили бы п. п. формулы применимости этих операторов. Пользуясь решением, представленным на рис. 4.14, читатель .мог бы получить некоторый опыт работы с методом решения, основанным на сведении задачи к совокупности подзадач и ориентированным на исчисление предикатов. 77.
ОДНА ФОРМАЛИЗАЦИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧ В ПРОСТРАНСТВЕ СОСТОЯНИИ В предыдущем разделе состояния описывались с помощью множеств п. п. формул, а дочерние описания состояний получались в результате применения операторных правил изъятии и добавления п. п. формул. Так как преобразования, связанные с операторами, отображают одни множества п. п. формул в другие множества п. п. формул, то они были похожи на правила логического вывода. На самом деле они не были настоя. щнми правилами вывода, так как дочерние п. п.
формулы не 7.7 Одна 4ормаяиэиция дяя решения »ада« 229 следовали логически из родительских п. п. формул. Преобразования, связанные с операторами, изменяли описания состояний, и совершались независимо от системы логического вывода в исчислении предикатов. При небольшой переформулировке удается включить описание действий операторов в рамки формализма исчисления предикатов. Чтобы это сделать, добавим в каждый предикат терм состояныя, указывающий состояние, к которому предикат применим, тогда в нашем предыдущем примере начальное состояние Яе описывалось бы с помощью множества п. п.
формчл ( ОЫВОХ(з,), АТ(ящик, Ь, за), АТ(обезьяна, а, зе), НВ(зе)). Здесь терном состояния является зв В такой формулировке операторы рассматриваются как функции, отображающие одно состояние в другое. Так, значением оператора «схватить (з)» будет новое состояние, возникающее в результате применения оператора «схватить» к состоянию з. Основной эффект применения оператора «схватить» можно описать с помощью п. п. формулы (чз)(ОМВОХ(з) Л АТ (ящих, с, з) ФНВ (схватить (з))), означающий «для всех з, если обезьяна находится на ящике, а ящик расположен в точке с в состоянии з, то в состоянии, возникающем в результате применения оператора «схватить» к состоянию з, обезьяна будет иметь бананыж Прн таком способе описания операторные описания — это просто дополнительные «аксиомы», которые можно объединить с п.
п. формулами, описывающими начальное состояние Я,. Если наша цель состоит в создании состояния з, удовлетворяющего некоторой целевой п. п. формуле )«'(з), то эту задачу можно решить формально, найдя сначала доказательство для предположения (Вз) Я7(з), а затем использовав процесс извлечения ответа для получения решения. Ответное утверждение будет содержать выражение для целевого состояния в форме композиции операторных функций. Для иллюстрации этого подхода воспользуемся упрощенной формой задачи об обезьяне и бананах. Предположим, что у нас только три оператора — «схватить», «взобраться», «передвинуть», — н условия их применимости несколько отличаются от прежних.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
