Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 131
Текст из файла (страница 131)
Глава 10. Представление знаний 485 дизъюнкту для каждого определенного выражения, головой которого является этот предикат~ '. Как правило, такое дополнение создается, как описано ниже. 1. Собрать все выражения с одним и тем же названием предиката (Р) и с одной и той же арностью (и).
2. Преобразовать каждое выражение в 'ж нормальную форму Кларка, например, заменить выражение Р(С,,..., С.) < — Вппу где с, — термины, выражением Р(иг, .", сь) с — Эыг .. ы [иг, „ть] = [ст, ..., с 1 л вос[Р где цтг — вновь введенные переменные, а ы, — переменные, которые присут- ствуют в первоначальном выражении.
При этом следует использовать одно И тО жЕ МНОжЕСтВО 1 т ДЛЯ КажДОГО ВЫРажЕНИЯ. ЭтО ПРИВОДИТ К ПОЛУЧЕНИЮ та- кого множества выражении: Р(ит, 3, ть) < — Вг Р(иг, ], ик) Š— Вь 3. Скомбинировать их вместе в одно большое дизъюнктивное выражение: Р(ю, ..., и„) < — Вг и ... и Вь 4. Сформировать завершение, заменяя оператор е — оператором эквивалентности: ик) ео Вг о ... "' В» Пример дополнения Кларка для базы знаний, включаюшей и базовые факты, и правила, приведен в табл.
10.2. Чтобы ввести в действие предположение об уникальности имен, достаточно сформировать дополнение Кларка для отношения равенства, где единственными известными фактами являются СЯ=СЯ, 101=101 и т.д. Оставляем эту задачу читателю в качестве упражнения. Таблица 10.2. Дополнение Кларка для множества хорновских выражений. В первоначалы<ой хориовской программе (слева) четыре курса перечислены явно, а также содержатся утверждения, что проводятся курсы по математике с целочисленными номерамн от 101 до 130, а для кажлого курса св по компьютерным наукам в серии 100 (для студентов) имеется соответствующий курс в серии 200 (для аспирантов).
В дополнении Кларка (справа) указано, что других курсов больше нет. С помощью этого дополнения и предположения об уникальности имен (а также очевидного определения предиката тпеояоя) можно получить желаемое заключение, что имеется точно 36 курсов: 30 курсов по матеиатике н б курсов по компьютерным наукам Хорновские выражения Дополнение Кларка " Следует отметить, что зти выражения также представляют собой одну из разновидностей аксиом состояния-преемника, приведенных в разделе 10.3 Спияяо(СЯ,101) Спитое ( СЕ, 102 ) Соияяе(СЯ,106) Соияяе(ЕЕ,101) Спияяе(ее,т) е- тпседея(1) Соияяе(с(,п) ся (г),п] = [СЯ,101] [с),п) = [СЕ,1021 [с),п] = [СЯ,1061 [с),п] = [ЕЕ,101] ч Зз [с),п] = [ЕЕ,11 л Гпеоиея(1) 486 Часть П!.
Знания и рассуждения Окончание табл. 10.2 Хорновекие выражения л 101 < Х л л < 130 Ооикле1ОЯ,лн.1001 ч=. Ооикие1ОЯ,т1 л 100 < т л т с 200 дополнение Кларка л 101 < 3 л л < 130 ьл 1с1, и! = !ой, лн-1001 л Ооикее ( Ой, т! л 100 < т л и с 200 Отрицание как недостижение цели и устойчивая семантика модели Как было показано в главах 7 и 9, базы знаний в форме хорновских выражений имеют желаемые вычислительные свойства. Однако во многих приложениях довольно сложно выполнить выдвигаемое при этом требование, чтобы каждый литерал в теле выражения был положительным. Например, может потребоваться сформулировать утверждение: "На прогулку можно выходить, если нет дождя", не будучи вынужденным изобретать такие предикаты, как ргосиазцхпд. В этом разделе рассматривается дополнение к хорновским выражениям в форме явного отрицания, которое Предположение о замкнутом мире позволяет найти минимальную модель отношения.
Это означает, что в данном примере можно найти модель отношения Ооигэе с наименьшим количеством элементов. Минимальная модель отношения Ооихэе, соответствующая уравнению 10.2, имеет четыре элемента; при меньшем количестве элементов возникало бы противоречие. Для хорновских баз знаний всегда имеется уникальная минимальная модель.
Следует отметить, что с учетом предположения об уникальности имен это утверждение распространяется также и на отношение равенства, поскольку каждый терм равен только самому себе. Как ни парадоксально, это означает также, что минимальные модели являются одновременно и максимальными, в том смысле, что включают максимально возможное количество объектов. Было бы допустимо взять любую хорновскую программу, сформировать дополнение Кларка и передать полученный результат в программу автоматического доказательства теорем для выполнения логического вывода. Но обычно является более эффективным использование механизма логического вывода специального назначения, такого как Рго)08, поскольку в этом механизме логического вывода уже учитываются предположения о замкнутом мире и уникальности имен.
Те, кому приходится использовать предположение о замкнутом мире, должны соблюдать осторожность при выборе способа формируемых рассуждений. Например, при использовании базы данных с результатами переписи населения было бы резонно принимать предположение о замкнутом мире при формировании рассуждений о текущем населении городов, но было бы неправильно делать вывод, что в будушем не родится ни один ребенок, лишь на основании того, что база данных не содержит записей, касаюшихся будущих дней рождения. Благодаря С'ччА база данных становится полной в том смысле, что позволяет дать либо положительный, либо отрицательный ответ на каждый атомарный запрос; если же какие-то факты не заданы в этой базе данных изначально (например, о будущих рождениях), то СччА не может применяться. Более сложная система представления знаний может дать пользователю возможность указывать правила, по которым следует применять предположение о замкнутом мире.
487 Глава 1О. Представление знаний основано на идее использования ок отрицания как недостижения цели. Эта идея состоит в том, что истинность отрицательного литерала пес Р может быть "доказана" просто на основании того, что попытка доказательства Р окончилась неудачей. Вэтом заключается одна из форм рассуждений по умолчанию, тесно связанная с предположением о замкнутом мире: предполагается, что нечто является ложным, если нельзя доказать, что оно истинно. Для того чтобы можно было отличить отрицание как недостижение цели от логического оператора "- ", для обозначения первого используется оператор "поп".
В языке Рго!оя допускается применять оператор пос в теле выражения. Например, рассмотрим следующую программу Рго)оя: 1РЕдпдке Е- Рг1ке п пес ЯСЯтдгдие. ЯСЯгдгдке < — Рг1ие п пое 1РЕдгдке. ЯС$1оопего11ег е- ЯСЯтдгдке. Розке. (10.4) Первое правило указывает, что если в компьютере имеется жесткий диск, не являющийся диском бСб1, то это должен быть диск !ОЕ. Согласно второму правилу, если это — не диск 1РЕ, то он должен быть диском ЯСБ!. В третьем правиле утверждается, что из наличия в компьютере диска БСб! следует наличие в нем контроллера бСб!, а четвертое утверждает, что в компьютере обязательно должен быть жесткий диск. Эта программа имеет следующие две минимальные модели: М~ = (Рокке, ЕРЕдгЮе) Мг = (Ргдке, ЯСЯгдгдке, $с$1оопсгО11ег) Очевидно, что минимальные модели не позволяют выразить намеченную семантику программ с отрицанием как недостижением цели.
Рассмотрим следующую программу: (10.5) е е- поп Р. Эта программа имеет две минимальные модели, ( Р) и ((7). С точки зрения логики первого порядка в этом есть смысл, поскольку выражение Р с= О эквивалентно Е ч О. НО С ТОЧКИ ЗрЕНИя яЗЫКа РГО1Оя ЭтО СОМНИТЕЛЬНО: ЕСЛИ тЕрМ д НИ раЗу НЕ ПО- является в этой программе слева от стрелки, то как же он может стать следствием? Альтернативный подход состоит в использовании идеи 'а.
стабильной модели, которая представляет собой такую минимальную модель, что каждый атом в модели имеет 'а. обоснование: правило, голова которого является атомом, а каждый литерал в теле выполняется. Формально модель м определяется как стабильная модель про- ГраММЫ Н, ЕСЛИ и — уНИКаЛЬНая МИНИМаЛЬНая МОДЕЛЬ ох СОКраШЕНИЯ Н ПО ОтНОШЕ- нию к м. Сокращение программы и определяется путем предварительного удаления из н любого правила, которое имеет в теле литерал пос д, где д имеется в модели, а затем удаления всех отрицательных литералов в оставшихся правилах.
Поскольку после этого сокращение программы и становится списком хорновских выражений, оно должно иметь уникальную минимальную модель. Сокращением программы Р е — пос О по отношению к (Р) является Р, и это сокращение имеет минимальную модель (е). Поэтому (Р) — стабильная модель. Сокращение по отношению к ( О) представляет собой пустую программу, и это сокращение имеет минимальную модель ( ) . Поэтому ( О) — это нестабильная модель, 488 Часть !П.
Знания и рассуждения поскольку ц не имеет обоснования в уравнении 10.5. В качестве еше одного примера можно привести сокращение уравнения 10.4 по отношению к дгы как показано ниже. зввег1че < — вгцпе. вс51сапг гп11ег е- Бсвгдгдче. Пг1ъе. Эта программа имеет минимальную модель дгы поэтому и, — стабильная модель. 'ж Программирование множества ответов — это разновидность логического программирования с отрицанием как недостижением цели, которая функционирует на основе преобразования логической программы в базовую форму с последующим поиском стабильных моделей (называемых также 'ъ.
множествами ответов) с использованием методов проверки пропозициональной модели. Таким образом, программирование множества ответов разработано на основе и системы Рго!ой, и быстродействующих алгоритмов автоматического доказательства выполнимости пропозициональных высказываний, таких как уга1)сядт. И действительно, программирование множества ответов было успешно применено для решения задач планирования, по такому же принципу, как применялись программы автоматического доказательства выполнимости пропозициональных высказываний. Преимушеством планировщиков на основе множества ответов над другими планировщиками является их большая гибкость: операторы и ограничения планирования могут быть выражены в виде логических программ и не привязаны к жесткому формату конкретной формальной структуры планирования. Недостаток методов планирования на основе множества ответов является таким же, как и в других пропозициональных методах: если количество обьектов в универсуме очень велико, то может возникать экспоненциальное замедление.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
