Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 102
Текст из файла (страница 102)
Вообще говоря, если существует некоторая подстановка О, позволяющая сделать предпосылку импликации идентичной высказываниям, которые уже находятся в базе знаний, то можно утверждать об истинности заключения этой импликации после применения О. В данном случае такой цели достигает подстановка (х/ юо?ш) . Фактически можно обеспечить выполнение на этом этапе вывода еще больше работы.
Предположим, что нам известно не то, что жаден Джон — Океес?у(то)?п), а что жадными являются все: Чу есеес)у(у) (9.2) Но и в таком случае нам все равно хотелось бы иметь возможность получить заключение, что Джон зол — К?г11 (,то??п), поскольку нам известно, что Джон — ко- Глава 9. Логический вывод в логике первого порядка 385 роль (это дано) и Джон жаден (так как жадными являются все). Для того чтобы такой метод мог работать, нам нужно найти подстановку как для переменных в высказывании с импликацией, так и для переменных в высказываниях, которые должны быть согласованы. В данном случае в результате применения подстановки (хl го)зп, у/ Уо)зп) к прелпосылкам импликации кбпд(х) и Сгеес(у(х) и к высказываниям из базы знаний кбпд(Юо)зп) и бгеес)у(у) эти высказывания становятся идентичными.
Таким образом, теперь можно вывести заключение импликации. Такой процесс логического вывода может быть представлен с помошью единственного правила логического вывода, которое будет именоваться 'гв обобшенным правилом отделения (хтепега!(ход Мобцз Ропепз): для атомарных высказываний р„ р, ' и гт, если сУшествует подстановка О, такая, что БцЬБ Ь (О, р„' ) = БцЬБ Е (О, р, ), то для всех З имеет место следуюшее: Р' 2 ° ° р, ( 1 л 2 л ...
л ЯиЬэе(О,д) В этом правиле имеется и+1 предпосылка; п атомарных высказываний р, ' и одна импликация. Заключение становится результатом применения подстановки 0 к следствию сг. В данном примере имеет место следующее: р1' — это Кхпд( Толп) р1 — это кхпд(х) р2' — это Сгеес)у(у) р1 — это о геес(у(х) 0 — это (х/Болл,у/депп) и — это Еь11(х) БиЬэс(0, д) — это ет11(додо) Можно легко показать, что обобгценное правило отделения — непротиворечивое правило логического вывода. Прежде всего отметим, что для любого высказывания р (в отношении которого предполагается, что на его переменные распространяется квантор всеобщности) и для любой подстановки 0 справедливо следующее правило; р и ЯпЬэс(0,р) Это правило выполняется по тем же причинам, по которым выполняется правило конкретизации высказывания с квантором всеобшности.
Оно выполняется, в частности, в любой подстановке О, которая удовлетворяет условиям обобшенного правила отделения. Поэтому из р, ', ..., р„' можно вывести следуюшее: БпЬБЕ (О,р ) ... л Бппэс (О,р ) а из импликации р, л ... л р„=> <у — следующее: ЯиЬэе(О,р1) л ... л Базе(0,р ) ~ ЯиЬэс(О,д) Теперь подстановка О в обобшенном правиле отделения определена так, что ЯиЬЯС (О,Р,' ) = ЯиЬБЕ(О,Рз) ДЛЯ ВСЕХ 1, ПОЭТОМУ ПЕРВОЕ ИЗ ЭТИХ ДВУХ ВЫСКаЗЫ- ваний точно совпадает с предпосылкой второго высказывания.
Таким образом, выражение БиЬЯЬ (О, гу) следует из правила отделения. Как принято выражаться в логике, обобщенное правило отделения представляет собой Ъ. поднятую версию правила отделения — оно поднимает правило отделения из пропозициональной логики в логику первого порядка. В оставшейся части этой главы будет показано, что могут быть разработаны поднятые версии алгоритмов прямого логического вывода, обратного логического вывода и резолюции, представленных в главе 7. Основным преиму)цеством применения поднятых правил логиче- 38б Часть ПЕ Знания и рассуждения ского вывода по сравнению с пропозиционализацией является то, что в них предусмотрены только те подстановки, которые требуются для обеспечения дальнейшего выполнения конкретных логических выводов.
Единственное соображение, которое может вызвать недоумение у читателя, состоит в том, что в определенном смысле обобшенное правило вывода является менее обшим, чем исходное правило отделения (с. 303): правило отделения допускает применение в левой части импликации любого отдельно взятого высказывания а, а обобшенное правило отделения требует, чтобы это высказывание имело специальный формат.
Но оно является обобщенным в том смысле, что допускает применение любого количества выражений р, ' . Унификация Применение поднятых правил логического вывода связано с необходимостью поиска подстановок, в результате которых различные логические выражения становятся идентичными. Этот процесс называется сь унификацией и является ключевым компонентом любых алгоритмов вывода в логике первого порядка.
Алгоритм ()ой Еу принимает на входе два высказывания и возвращает для них Ж унификатор, если таковой существует: ПпЬГу(р,с)) = 9 где яойае(9,р) = ЬаЬае(9,ст) Рассмотрим несколько примеров того, как должен действовать алгоритм цпйбу. Предположим, что имеется запрос кпоье (лойп, х) — кого знает Джон? Некоторые ответы на этот запрос можно найти, отыскивая все высказывания в базе знаний, которые унифицируются с высказыванием Кпоьэ (тойп, х) .
Ниже приведены результаты унификации с четырьмя различными высказываниями, которые могут находиться в базе знаний. цпьсу (Кпама (тайп, х), Кпама (Оойп, Капе) ) = (х!папе) ПоьГу(кпама(аойп, х), Кпама (у, В111) ) = (х/Е111, у/Тайп) опьгу (кпоха (аолп, х), каоыа (у, иосйег(у) ) ) = (у/аойа, х/еосйег(оойп) ) ПптГу(Кпама(пайп,х), Кпама(х,Е11гаЬесй)) = Еа11 Последняя попытка унификации оканчивается неудачей (Га11), поскольку переменная х не может одновременно принимать значения тойп и е11гаЬесй. Теперь вспомним, что высказывание кпоыэ(х,е11гаЬегй) означает "Все знают Элизабет*', поэтому мы обязаны иметь возможность вывести логически, что Джон знает Элизабет. Проблема возникает только потому, что в этих двух высказываниях, как оказалось, используется одно и то же имя переменной, х. Возникновения этой проблемы можно избежать, 'ъ.
стаидартизируя отличие (мапдагдцйп8 араг() одного из этих двух унифицируемых высказываний; под этой операцией подразумевается переименование переменных в высказываниях для предотврашения коллизий имен. Например, переменную х в высказывании кпсс(х, е11гаЬесй) можно переименовать в г„(новое имя переменной), не меняя смысл этою высказывания. После этого унификация выполняется успешно: Ппь Еу(Кпама (Еойп, х), Кпоьа (гм, Е11гаЬесй) ) = (х/Е11гаЬеей, гп/Еойа) С дополнительными сведениями о том, с чем связана необходимость в стандартизации отличия, можно ознакомиться в упр.
9.7. 387 Глава 9. Логический вывод в логике первого порядка Возникает еще одна сложность: выше было сказано, что алгоритм ггп1бу должен возвращать такую подстановку (или унификатор), в результате которой два параметра становятся одинаковыми.
Но количество таких унификаторов может быть больше единицы. Например, вызов алгоритма цпббу(Кпоьгз (Гойю, х), Кпомз(у, г) ) может возвратить (у/гойи,х/г) или (у/ тойп,х/ /ойп, г/ толп). Первый унификатор позволяет получить в качестве результата унификации выражение кпоыз ( толп, г), а второй дает кпо??з(толп,,лойп) . Но второй результат может быть получен из первого с помощью дополнительной подстановки ( з/,тойп); в таком случае принято считать, что первый унификатор является более общим по сравнению со вторым, поскольку налагает меньше ограничений на значения переменных.
Как оказалось, для любой унифицируемой пары выражений существует единственный ск наиболее общий унификатор (Моз( Пепе?а! !)шйег — МЫ)), который является уникальным вплоть до переименования переменных. В данном случае таковым является (у/ гойю, х/з). Алгоритм вычисления наиболее общих унификаторов приведен в листинге 9.!.
Процесс его работы очень прост: рекурсивно исследовать два выражения одновременно, "бок о бок", наряду с этим формируя унификатор, но создавать ситуацию неудачного завершения, если две соответствующие точки в полученных таким образом структурах не совпадают. При этом существует один дорогостоящий этап: если переменная согласуется со сложным термом, необходимо провести проверку того, встречается ли сама эта переменная внутри терма; в случае положительного ответа на данный вопрос согласование оканчивается неудачей, поскольку невозможно сформировать какой-либо совместимый унификатор. Из-за этой так называемой Ж проверки вхождения (оссиг сйесй) сложность всего алгоритма становится квадратично зависимой от размера унифицируемых выражений.
В некоторых системах, включая все систелгы логического программирования, просто исключается такая проверка вхождения и поэтому в результате иногда формируются противоречивые логические выводы, а в других системах используются более развитые алгоритмы со сложностью, линейно зависящей от времени. Листинг 9.1. Алгоритм унификация. Алгоритм действует путем позлемептпого сравнеяия структур входных высказываний. В ходе этого формируется подстановка О, которая также является параметром функции ппьяу н попользуется для проверки того, что дальнейшие сравнения совместимы со связываниями, которые были определены раппе. В составном выражении, таком как г(л, в), функция ор выбцрает функциональный символ г, а функция ъгда выбирает список параметров (л, в) Еипогаоп ппгбу(х, у, О) гееигпа подстановка, позволяющая сделать х и у идентичными ьприеа: х, переменная, константа, список или составной терм у, переменная, константа, список или составной терм О, подстановка, подготовленная до сик пор (наобязательный параметр, по умолчанию применяется пустой терм) ья О = Га11иге Е)леп геепгп Еа11иге е1ее бб х = у ЕЬеп гевигп О е1ве 1г ЧагьаЫе? (х) еиеп гевигп Цпгбу-Чаг(х, у, О) е1ее 1б чагьаые? (у) еьеп гееигп цпггу-чав(у, х, О) е1ее лб Сошроипс)? (х) апб Сотроипс)? (у) енеп 388 Часть 111.
Знания и рассуждения гесигп ])пвеу(Агдв [х], Агдв [у], Ппьбу(ср[х], бр[у], О) ) е1ве ЕЕ Ьдвеэ(х) апй Ь1веэ(у) Е)ьеп гесигп ппЕЕу(иенс [х), иенс [у], ппьбу(Р1гвс [х], Р1гвс [у], 0) ) е1ве гееигп Еа11оге Еипсг1оп Ппдгу-чаг(маг, х, О) гегигпв подстановка Еприсв: каг, переменная х, любое выражение О, подстановка, подготовленная до снх пор ЕЕ (каг!ка1) Е О Епеп гесигп Плугу(ка1, х, О) е1ве 1Е (х1ка1) т О еиеп гееигп пптбу(каг, уа1, 0) е1ве 1Е Оссцг-оиесхэ(каг, х) Епеп гесигп Еа11цге е1ве гееигп добавление (каг/х) к подстановке О Хранение и выборка В основе функций Те11 и Ав)с, применяемых дпя ввода информации и передачи запросов в базу знаний, лежат более примитивные функции Итоге и расс]з.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
