Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 117
Текст из файла (страница 117)
Знания и рассуждения 9.3. Предположим, что база знаний содержит только одно высказывание, Зх АвН1дЛАв(х, Еиегеве) . Какие из следующих фактов являются действительными результатами применения правила конкретизации с помощью квантора существования? а) АВН1дЛАв(ЕссетееС,Ессетеее). б) АэНудЛАе(К111саап>аго,ЕуегееС). в) АеНЗдЛАэ(К111тап3ато,Ессетеэт) А АеНЗдЛАв(Велнеубе,Еуегеее) (после двух применений). 9.4. Для каждой приведенной ниже пары атомарных высказываний укажите наиболее общий унификатор, если он существует. а) Р(А,В,В), Р(х,у, я).
б) а(у,0(А,В) ), 0(а(х,х),у). в) 01с)ет(ЕеСЛег(у),у), 01с)ет(ЕаСЛег(х), 1оЛп). г) Клоне(ЕаСЛет(у),у), Клоне(х,х). 9.5. Рассмотрите решетки обобщения, приведенные на рис. 9.). а) Составьте решетку для высказывания Етр1оуе (Мо СЛег ( доЛп ), ЕаГЛег(Н1сЛагс() ) . б) Составьте решетку для высказывания В)ар1оуе(твм,у) (" Компания )ВМ является нанимателем для всех"). Не забудьте включить запрос любого рода, который унифицируется с этим высказыванием. в) Предположим, что функция ясоте индексирует каждое высказывание под каждым узлом в его решетке обобщения.
Объясните, как должна работать функция еессЛ, если некоторые из этих высказываний содержат переменные; воспользуйтесь в качестве примера высказываниями, приведенными в упр. 9 5, а и 9 5, б, а также запросом Есар1оуе ( х, Еа сЛ ет ( х) ) . 9.6. Предположим, что в логическую базу данных помещена часть данных переписи населения США с указанием возраста, города проживания, даты рождения и имени матери каждого лица, с использованием номеров карточек социального страхования в качестве идентифицирующих констант для каждого лица.
Таким образом, например, возраст Джорджа задается выражением Аде (443- б 5-1282, 56 ) . Какая из приведенных ниже схем индексации Я1-Я5 позволяет эффективно находить ответы на каждый из запросов 01-()4 (при условии, что применяется обычный метод обратного логического вывода)? * Схемы индексации. ° 81. Индекс для каждого атомарного терма в каждой позиции. ° 82. Индекс для каждого первого параметра. ° 83 . Индекс для каждого атомарного терма предиката.
° 84. Индекс для каждой комбинации предиката и первого параметра. ° 85. Индекс для каждой комбинации предиката и второго параметра и индекс для каждого первого (нестандартного) параметра. ° Запросы. ° 01. Аде(443-44-4321, х) . ° (32. Вее1с)ее1п (х, Ноле Сел) . Глава 9. Логический вывод в логике первого порядка 437 9.7. 9.8. 9.9. 9.10. 9.11.
9.12. 9.13. ° ДЗ. иосйеп(х, у) . ° 04. Аде(х, 34) л ЯепЗс]еагп(х, ТТпуТоап()йА) . Можно было бы предположить, что стандартизация раз и навсегда отличий всех высказываний в базе знаний позволяет избежать проблемы конфликта переменных при унификации в процессе обратного логического вывода. Покажите, что для некоторых высказываний этот подход не применим. (Подсказки.
Рассмотрите высказывание, одна часть которого унифицируется с другой.) Обьясните, как записать любую конкретную формулировку задачи 3-ЯАТ произвольного размера с использованием единственного определенного выражения первого порядка и не больше 30 базовых фактов. Запишите логические представления для приведенных ниже высказываний, применимые для использования с обобщенным правилом отделения.
а) Лошади, коровы и свиньи — млекопитающие. б) Рожденный лошадью — лошадь. в) Блюберд — лошадь. г) Блюберд — родитель Чарли. д) Отношения "быть рожденным" и "быть родителем" — обратные. е) Каждое млекопитающее имеет родителя. В этом упражнении для получения ответов на вопросы с помощью алгоритма обратного логического вывода используются высказывания, записанные при решении упр. 9.9. а) Нарисуйте дерево доказательства, сформированное исчерпывающим алгоритмом обратного логического вывода для запроса йп ноппе(Ь) (" Существует некоторая лошадь"), в котором выражения согласуются в указанном порядке.
б) Какие особенности этой проблемной области вы обнаружили? в) Какое количество решений для ]з фактически следует из ваших высказываний? г) Можете ли вы предложить способ поиска всех этих решений? (Подсказка. Вам может потребоваться обратиться к [14341.) Одной из известных детских английских загадок является следующая: "Вгогйегз апг] ямегз Ьаче 1 попе, Ьщ Гйа( шап'з Гагйег В гпу Га(йег'з зоп" (Братьев и сестер у меня нет, но отец этого человека — сын моего отца).
С использованием правил из области семейных отношений (глава 8) определите, кто этот человек, о котором говорится в загадке. Вы можете применять любые методы логического вывода, описанные в этой главе. Почему, по вашему мнению, эту загадку трудно отгадать сразу? Проследите за выполнением алгоритма обратного логического вывода, приведенного в листинге 9.3, при его применении лля решения задачи доказательства преступления. Покажите, какую последовательность значений принимает переменная поа1я, и расположите эти значения в виде дерева. Приведенный ниже код Рго!од определяет предикат Р: Р(Х,[Х]У)). Р(Х,(У]2]) : — Р(Х,2). 438 Часть !П. Знания и рассуждения а) Покажите деревья доказательства и решения для запросов Р (А, [1, 2, 3) ) и Р(2,[1,А,З]).
б) Какую стандартную операцию со списками представляет предикат Р? 9.14. Ф В этом упражнении рассматривается применение сортировки в языке Рго[оа. а) Напишите выражения Рго)оа, которые определяют предикат яогсес)(ь), принимающий истинное значение тогда и только тогда, когда список ь отсортирован в возрастающем порядке.
б) Напишите на языке Рго[оа определение предиката рехга(ь, м), который принимает истинное значение тогда и только тогда, когда ь — перестановка м. в) Определите предикат яохс(ь,м) (м — отсортированная версия ь) с использованием предикатов рехаз и яохсесЬ г) Применяйте предикат яохс ко все более длинным и длинным спискам, пока вам это не надоест. Какова временная сложность вашей программы? д) Реализуйте на языке Рго[оа более быстрый алгоритм сортировки, такой как сортировка вставкой ((пзег( зогг) или быстрая сортировка (Чшсйзоп). 9.15. 1Й В этом упражнении рассматривается рекурсивное применение правил переза- писи с использованием логическою программирования.
Правилом перезаписи (или демодулятором, в терминологии программы Оссех) является уравнение с указанным направлением применения. Например, правило перезаписи х+Π— )х указывает, что любое выражение, которое согласуется с х~О, должно заменяться выражением х. Средства применения правил перезаписи составляют центральную часть систем формирования рассуждений с учетом отношения равенства.
Для представления правил перезаписи мы будем использовать предикат еьгхвсе(х, у) . Например, приведенное выше правило перезаписи может быть представлено как генгвсе (хьО, х) . Некоторые термы являются примитивными и не могут подвергаться дальнейшим упрощениям, поэтому мы будем использовать запись рхьан свче ( 0) для указания нато, что Π— примитивный терм. а) Запишите определение предиката явгар11йу(Х,у), который принимает истинное значение, если у — упрощенная версия х, т.е. к каким-либо подвыражениям у больше не применимы какие-либо правила перезаписи. б) Запишите коллекцию правил перезаписи для упрощения выражений, в которых применяются арифметические операторы, и примените ваш алгоритм упрогцения к некоторым примерам выражений. в) Запишите коллекцию правил перезаписи для символического дифференцирования и примените их наряду с определенными вами правилами упрощения для дифференцирования и упрощения выражений, в которых есть арифметические выражения, включая возведение в степень.
9.16. В этом упражнении рассматривается реализация алгоритмов поиска на языке Рго)оа. Предположим, что предикат яиссеяяог(х, у) принимает истинное значение, если состояние у является преемником состояния х, и что предикат доа1 (Х) принимает истинное значение, если Х вЂ” целевое состояние. Запишите определение для предиката яо1уе(Х, Р), который означает, что Р— путь (список состояний), начинающийся отх, оканчивающийся в целевом Глава 9.
Логический вывод в логике первого порядка 439 9.17. 9.18. 9.19. 9.20. 9.21. состоянии и состояший из последовательности допустимых шагов, которые определены предикатом эиссевэох. Вы обнаружите, что простейшим способом решения этой задачи является поиск в глубину. Насколько легко будет ввести эвристическое управление поиском? Как можно воспользоваться методом резолюции для демонстрации того, что некоторое высказывание является общезначимым? Невыполнимым? Из высказывания "Лошади — животные" следует, что "голова лошади — голова животного". Продемонстрируйте, что этот логический вывод является допустимым, выполнив приведенные ниже этапы.
а) Преобразуйте предпосылку и вывод этого высказывания в язык логики первого порядка. Воспользуйтесь тремя предикатами; Веаг)ОЕ()з,х) (который означает, что ")з — голова х"), ногае (х) и Апхта1 (х) . б) Примените отрицание к заключению и преобразуйте предпосылку и отрицаемое заключение в конъюнктивную нормальную форму. в) Воспользуйтесь правилом резолюции, чтобы показать, что заключение следует из предпосылки. Ниже приведены два высказывания на языке логики первого порядка. АЧхЗу ( х>у) ВЗуЧх ( х>у) а) Допустим, что переменные пробегают по всем натуральным числам О, 1, 2, ..., и что предикат> означает "больше или равно". При использовании такой интерпретации переведите высказывания А и В на естественный язык. б) Является ли высказывание А истинным при этой интерпретации? в) Является ли высказывание в истинным при этой интерпретации? г) Является ли В логическим следствием А? д) Является ли А логическим следствием В? е) С использованием правила резолюции попытайтесь доказать, что А следует из В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
