Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 79
Текст из файла (страница 79)
Итак, литерал (, является либо истинным, либо ложным, поэтому справедливо одно или второе из этих заключений, а именно это утверждается в правиле резолюции. Еше более привлекательным свойством правила резолюции является то, что оно образует основу для семейства полных процедур логического вывода, е- .дзюбой полный алгоритм поиска, в котором применяется только правило резолюции, позволяет вывести любое заключение, копюрое следует из любой базы знаний в пропозициональной логике.
Тем не менее необходимо сделать одно предупреждение: правило резолюции является полным только в узком смысле этого понятия. Если известно, что высказывание А истинно, правило резолюции нельзя использовать для автоматического формирования следствия А ы В. Однако в этом случае правилом резолюции можно воспользоваться для поиска ответа на вопрос, является ли истинным высказывание А ы В. ЭтО СВОйетВО ПраВИЛа рЕЗОЛЮцИИ НаЗЫВаЕтСя 'т.
ПОЛНОтОй ОПрОВЕржЕНИя (ге(ц1а1)оп согпр!е1епезз) и означает, что правило резолюции может всегда использоваться либо для подтверждения, либо для опровержения какого-то высказывания, но его нельзя применять для перебора всех истинных высказываний. В следуюших двух подразделах описано, как может использоваться правило резолюции для осуШествления логического вывода. Конъюнктивная нормальная форма Как было описано выше, правило резолюции применяется только к дизъюнкциям литералов, поэтому на первый взгляд оно распространяется только на базы знаний и запросы, состоящие из таких дизъюнкций.
На каком же основании мы утверждаем, что это правило может служить основой процедуры полного логического вывода для всей пропозициональной логики? Ответ на этот вопрос состоит в том, что оэ- каждое высказывание пропозициональнои логики логически эквивалентно коньюнкции дизьюнкции литералов. Любое высказывание, представленное как конъюнкция дизъюнкций литералов, называется высказыванием, находящимся в г)г коньюнктивиой нормальной форме, или С)ч)Е (Сов)ппс((че )ч(оппа) Ропп). Кроме того, ниже будет показано, что целесообразно определить также ограниченное семейство высказываний в конъюнктивной нормальной форме, называемое высказываниями в форме 'т. й-С)ч(Е.
Высказывание в форме )(-СНЕ имеет точно )с литералов в расчете на каждое выражение: (1~ч...чгм)л...н(г„,ч...чг,,) Как оказалось, любое высказывание может быть преобразовано в высказывание в форме З-Сг)Р, которое имеет эквивалентное множество моделей. Вместо доказательства этих утверждений (см. упр.
7.10) опишем простую процедуру преобразования. Проиллюстрируем эту процедуру, преобразовав высказывание Вм или В„, с=» (Вмг м В,,,), в форму С)ч(Г. Ниже описаны соответствующие этапы. Глава 7. Логические агенты 309 1. Устранить связку е», заменив высказывание а ее )3 высказыванием (а =о )3) л ()3 =о а): ( В,г '— г ( Рг,г ч Рг,г) ) л ( ( Рг г ч Рг г) =г Вг г) 2. Устранить связку .=г, заменив высказывание а =о )3 высказыванием -а г)3: (-~ Вг.г ч Р. г ч Рг.г) л ( (Р,, ч Р,,)ч В,,) 3. Конъюнктивная нормальная форма требует, чтобы связка — появлялась только перед литералами, поэтому, как принято называть эту операцию, "введем связку ~ внутрь выражения", повторяя операцию применения следующих эквивалентностей из листинга 7.4: (устранение двойного отрицания) (правило де Моргана) (правило де Моргана) (-,а) на ~(ал()) е ( ау ()) (ач()) е ( ал В данном примере требуется применение только одного, последнего правила: (.
Вг,г ч Р; г ч Рг г) л (( Рг г л Рг,г) ч Вг,г) 4. В результате получено высказывание, содержащее вложенные связки л и ч, которые применяются к литералам. Используем закон дистрибутивности, приведенный в листинге 7.4, распределяя связки ч по связкам л везде, гле это возможно. Вг, ч Рг,г ч Рг,г) л ( Р,г ч Вг,г) л ( Рг,г " Вг, ) Теперь первоначальное высказывание представлено в форме СХЕ, как коньюнкция трех выражений.
Это высказывание стало более сложным для чтения, но зато его можно использовать в качестве входных данных для процедуры резолюции. ° перестают вырабатываться какие-либо новые выражения, которые могли быть добавлены к существующим, и в этом случае из базы знаний кв не следует высказывание а; ° два противоположных друг другу выражения устраняются, в результате чего создается пустое выражение; в этом случае из базы знаний кВ следует высказывание а. Алгоритм резолюции Процедуры логического вывода, основанные на правиле резолюции, действуют с использованием принципа доказательства путем установления противоречия, который описывался в конце раздела 7.4.
Таким образом, чтобы показать, что кн М а, мы покажем, что высказывание (КВ л а) является невыполнимым. Это можно сделать, доказав, что имеет место противоречие. Алгоритм резолюции приведен в листинге7.5. Вначале высказывание (КВ л ~а) преобразуется в форму С)4Г. Затем к результирующим выражениям применяется правило резолюции. В каждой паре выражений, содержащих взаимно противоположные литералы, происходит удаление этих противоположных друг другу литералов Лля получения нового выражения, которое добавляется к множеству существующих выражений, если в этом множестве еще нет такого выражения. Указанный процесс продолжается до тех пор, пока не происходит одно из следующих двух событий: Часть 1П. Знания и рассуждения Листинг 7.5.
Простой алгоритм резолюция для пропознцнональней легякн. Функция РЬ- цево1че возвращает множество всех возможных выражений, полученных путем устранения противоположных друг другу литералов нз двух высказываний, которые поступают ня ее вход тппсезоп Рь-иеяо1исьоп(кВ, а) геепгпв значение егие или га1яе 1присв: КВ, база знаний — высказывание в пропозиииональной логике а, запрос — высказывание в пропозиииональной логике с)аияея +- множество выражений, полученное после преобразования высказывания КВ л а в форму СНР пем ь- () 1оор до тот васи С,, С, 1п о1аияея до геяо1уепгя ь- Ръ-иеяо1уе(С,, С)) И множество геяо1уепея содержит пустое выражение Е)теп гееигп егие пем ь- пеи ьу геяо1уепея йл пеи с о1аияея еьеп гесигп Га1яе о1аияея ь- о1аияея ьу пеы Пустое выражение (дизъюнкция без дизъюнктов) эквивалентно высказыванию Ра1яе, поскольку дизъюнкция является истинной, только если истинен по меньшей мере один из ее дизъюнктов. Еше один способ убедиться в том, что пустое выражение служит свидетельством противоречия, состоит в том, что, вернувшись к описанному выше процессу логического вывода, можно заметить, по пустое выражение возникает только после устранения двух взаимно противоположных единичных выражений, таких как Р и — Р.
Эту процедуру резолюции можно применить для формирования очень простого логического вывода в мире вампуса. Когда агент находится в квадрате (1, 1), он не чувствует ветерка, поэтому в соседних квадратах не может быть ям. Соответствующая база знаний является следующей: КВ = Кг л К4 - -(Вьь ~ (Р;2 у Рьг)) а -~ В;ь и требуется доказать высказывание а, которое, скажем, имеет вид — Р,, После преобразования высказывания (кв л ~ а) в форму С) )Г получим выражения, показанные в верхнем ряду на рис. 7.6.
В нижнем ряду на этом рисунке показаны все выражения, полученные путем устранения противоположных друг другу литералов из всех пар выражений, приведенных в верхнем ряду. Затем после устранения литерала Р, „противоположного литералу — Р, „будет получено пустое выражение, показанное в виде небольшого квадрата. Анализ результатов, приведенных на рис. 7.6, позволяет обнаружить, что многие этапы резолюции были бессмысленными.
Например, выражение в,, и ~вы, У Р,, ЗКВИВапситнО ВЫражЕНИЮ Тгие у Р... которое эквивалентно тгие. Логический вывод, согласно которому выражение тгие является истинным, не очень полезен. Поэтому любое выражение, в котором присутствуют два взаимно дополнительных литерала, может быть отброшено. Полнота резолюции Чтобы завершить обсуждение правила резолюции в этом разделе, покажем, почему алгоритм РЬ-пезо1ис1оп является полным. Для этого целесообразно ввести Глава 7. Логические агенты понятие Ъ.революционного замыкания яС( Я) множества выражений З, представляющего собой множество всех выражений, которые могут быть получены путем повторного применения правила резолюции к выражениям из множества Б или к их производным.
революционным замыканием является множество выражений, которое вычисляется алгоритмом Рг;цево1псхоп в качестве окончательного значения переменной с1аывея. Можно легко показать, что множество Е(С(Я должно быть конечным, поскольку количество различных выражений, которые могут быть сформированы из символов Р,, ..., Р„, присутствующих в Я, является конечным. (Следует отметить, что это утверждение не было бы истинным, если бы не применялся этап факторизации, в котором уничтожаются дополнительные копии литералов.) Поэтому алгоритм РЕ-Нево1пейоп всегда оканчивает свою работу. Риг. 76.
геаспв блик-схемы, пакизываююей працесс применении функции Рд-аево1исхап длл фармиравинил ираеигага лаггтеекагп выводи в мире вампуеа. Здесь показано, чта из первых четырех вырижений, приведенных в верхнем ряду, следует выражение Рк г Теорема полноты для правила резолюции в пропозициональной логике называется 'л. основной теоремой резолюции.
Если множество выражений является невыполнимым, то революционное замыкание этих выражений содержит пустое выражение. Докажем эту теорему, показав, что справедливо противоположное ей утверждение: если замыкание згс( я не содержит пустое выражение, то множество я выполнимо. В действительности для множества З можно создать модель с подходящими истинностными значениями для Р„..., Р,. Процедура создания такой модели описана ниже.
Для х от 1 до уа ° если в множестве ЛС(Я имеется выражение, содержащее литерал Рп такое, что все другие его литералы являются ложными при данном присваивании, выбранном для Р„..., Р„;, то присвоить литералу Р, значение Еа1ае; ° в противном случае присвоить литералу Р, значение схие.
Остается показать, что это присваивание значений литералам Р„..., Р, представляет собой модель множества выражений З, при условии, что множество ПС( Я является замкнутым согласно правилу резолюции и не содержит пустого выражения. Доказательство этого утверждения оставляем читателю в качестве упражнения. Прямой и обратный логический вывод Благодаря такой полноте алгоритм резолюции становится очень важным методом логического вывода. Однако во многих практических ситуациях вся мощь правила З)г Часть Н!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
