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