УПРАЖНЕНИЯ
9.1. Докажите на основании главных логических принципов, что процедура конкретизации с помощью квантора всеобщности является непротиворечивой и что процедура конкретизации с помощью квантора существования позволяет получить базу знаний, эквивалентную с точки зрения логического вывода.
9.2. Представляется вполне обоснованным утверждение, что из отдельного факта Likes (Jerry, IceCream) можно вывести высказывание Зх Likes (х, IceCream). Запишите общее правило логического вывода, правило введения квантора существования, позволяющее узаконить такой логический вывод. Тщательно сформулируйте условия, которым должны удовлетворять переменные и термы, участвующие в этом выводе.
9.3. Предположим, что база знаний содержит только одно высказывание,
Зх AsHighAs{x, Everest). Какие из следующих фактов являются действи-
тельными результатами применения правила конкретизации с помощью
квантора существования?
а) AsHi ghAs (Everes t, Everes t).
б) AsHighAs(Kilimanjaro, Everest).
в) AsHi ghAs (Ki 1 imanjaro, Everes t) л AsHi ghAs {BenNevi s, Everes t)
(после двух применений).
9.4. Для каждой приведенной ниже пары атомарных высказываний укажите
наиболее общий унификатор, если он существует.
а) Р{А, В, В), Р(х,у, z).
б) Q(y,G(A,B)),Q(G(x,x) ,у).
в) Older {Father (у) , у), Older {Father (х) , John).
г) Knows {Father (у) , у), Knows (х, х).
9.5. Рассмотрите решетки обобщения, приведенные на рис. 9.1.
а) Составьте решетку для высказывания Employs {Mother {John) ,
Father{Richard)).
б) Составьте решетку для высказывания Employs {IBM, у) ("Компания
IBM является нанимателем для всех"). Не забудьте включить запрос лю-
бого рода, который унифицируется с этим высказыванием.
в) Предположим, что функция Store индексирует каждое высказывание под
каждым узлом в его решетке обобщения. Объясните, как должна работать
функция Fetch, если некоторые из этих высказываний содержат перемен-
ные; воспользуйтесь в качестве примера высказываниями, приведенными в
упр. 9.5, а и 9.5,5, атакже запросом Employs (х. Father (х) ).
9.6. Предположим, что в логическую базу данных помещена часть данных перепи-
си населения США с указанием возраста, города проживания, даты рождения
и имени матери каждого лица, с использованием номеров карточек социаль-
ного страхования в качестве идентифицирующих констант для каждого лица.
Таким образом, например, возраст Джорджа задается выражением Age(443-
65-1282,56). Какая из приведенных ниже схем индексации S1-S5 позволя-
ет эффективно находить ответы на каждый из запросов Q1-Q4 (при условии,
что применяется обычный метод обратного логического вывода)?
• Схемы индексации.
• S1. Индекс для каждого атомарного терма в каждой позиции.
• S2. Индекс для каждого первого параметра.
• S3 . Индекс для каждого атомарного терма предиката.
• S4. Индекс для каждой комбинации предиката и первого параметра.
• S5. Индекс для каждой комбинации предиката и второго параметра и индекс для каждого первого (нестандартного) параметра.
• Запросы.
• Q1. Аде(443-44-4321,х).
• Q2. Residesln{x,Houston).
• Q3. Mother {х, у).
• Q4.Age(x,34) л Residesln(x, TinyTownUSA).
9.7. Можно было бы предположить, что стандартизация раз и навсегда отличий всех высказываний в базе знаний позволяет избежать проблемы конфликта переменных при унификации в процессе обратного логического вывода. Покажите, что для некоторых высказываний этот подход не применим. {Подсказка. Рассмотрите высказывание, одна часть которого унифицируется с другой.)
9.8. Объясните, как записать любую конкретную формулировку задачи 3-SAT произвольного размера с использованием единственного определенного выражения первого порядка и не больше 30 базовых фактов.
9.9. Запишите логические представления для приведенных ниже высказываний, применимые для использования с обобщенным правилом отделения.
а) Лошади, коровы и свиньи — млекопитающие.
б) Рожденный лошадью — лошадь.
в) Блюбёрд — лошадь.
г) Блюбёрд — родитель Чарли.
д) Отношения "быть рожденным" и "быть родителем" — обратные.
е) Каждое млекопитающее имеет родителя.
9.10. В этом упражнении для получения ответов на вопросы с помощью алгоритма
обратного логического вывода используются высказывания, записанные при
решении упр. 9.9.
а) Нарисуйте дерево доказательства, сформированное исчерпывающим ал-
горитмом обратного логического вывода для запроса 3h Horse(h)
("Существует некоторая лошадь"), в котором выражения согласуются в
указанном порядке.
б) Какие особенности этой проблемной области вы обнаружили?
в) Какое количество решений для h фактически следует из ваших высказы-
ваний?
г) Можете ли вы предложить способ поиска всех этих решений? (Подсказка.
Вам может потребоваться обратиться к [1434].)
9.11. Одной из известных детских английских загадок является следующая: "Brothers and sisters have I none, but that man's father is my father's son" (Братьев и сестер у меня нет, но отец этого человека — сын моего отца). С использованием правил из области семейных отношений (глава 8) определите, кто этот человек, о котором говорится в загадке. Вы можете применять любые методы логического вывода, описанные в этой главе. Почему, по вашему мнению, эту загадку трудно отгадать сразу?
9.12. Проследите за выполнением алгоритма обратного логического вывода, приведенного в листинге 9.3, при его применении для решения задачи доказательства преступления. Покажите, какую последовательность значений принимает переменная goals, и расположите эти значения в виде дерева.
9.13. Приведенный ниже код Prolog определяет предикат р:
Р(Х,[X|Y]).
P(X, [Y|Z]) :- P(X,Z).
а) Покажите деревья доказательства и решения для запросов Р(А, [1,2,3])и
Р(2, [1,А,3]).
б) Какую стандартную операцию со списками представляет предикат Р?
9.14. Si) В этом упражнении рассматривается применение сортировки в языке Prolog.
а) Напишите выражения Prolog, которые определяют предикат sorted (L),
принимающий истинное значение тогда и только тогда, когда список L
отсортирован в возрастающем порядке.
б) Напишите на языке Prolog определение предиката perm (L, М), который
принимает истинное значение тогда и только тогда, когда L -— переста-
новка м.
в) Определите предикат sort (L,M) (М— отсортированная версия L) с ис-
пользованием предикатов perm и sorted.
г) Применяйте предикат sort ко все более длинным и длинным спискам,
пока вам это не надоест. Какова временная сложность вашей программы?
д) Реализуйте на языке Prolog более быстрый алгоритм сортировки, такой
как сортировка вставкой (insert sort) или быстрая сортировка (quicksort).
9.15. Si) В этом упражнении рассматривается рекурсивное применение правил переза-
писи с использованием логического программирования. Правилом перезаписи
(или демодулятором, в терминологии программы Otter) является уравнение с
указанным направлением применения. Например, правило перезаписи х+0—>х
указывает, что любое выражение, которое согласуется с х+0, должно заменяться
выражением х. Средства применения правил перезаписи составляют центральную
часть систем формирования рассуждений с учетом отношения равенства. Для
представления правил перезаписи мы будем использовать предикат
rewrite (X, Y). Например, приведенное выше правило перезаписи может быть
представлено как rewrite (Х+0, X). Некоторые термы являются примитивными
и не могут подвергаться дальнейшим упрощениям, поэтому мы будем использо-
вать запись primitive (0) для указания на то, что 0 — примитивный терм.
а) Запишите определение предиката simplify (X,Y), который принимает
истинное значение, если Y — упрощенная версия X, т.е. к каким-либо подвыражениям Y больше не применимы какие-либо правила перезаписи.
б) Запишите коллекцию правил перезаписи для упрощения выражений,
в которых применяются арифметические операторы, и примените ваш
алгоритм упрощения к некоторым примерам выражений.
в) Запишите коллекцию правил перезаписи для символического дифферен-
цирования и примените их наряду с определенными вами правилами уп-
рощения для дифференцирования и упрощения выражений, в которых
есть арифметические выражения, включая возведение в степень.
9.16. В этом упражнении рассматривается реализация алгоритмов поиска на языке
Prolog. Предположим, что предикат successor (X, Y) принимает истинное
значение, если состояние Y является преемником состояния X, и что предикат
goal (X) принимает истинное значение, если X— целевое состояние. Запи-
шите определение для предиката solve(Х,Р), который означает, что Р —
путь (список состояний), начинающийся отХ, оканчивающийся в целевом
состоянии и состоящий из последовательности допустимых шагов, которые определены предикатом successor. Вы обнаружите, что простейшим способом решения этой задачи является поиск в глубину. Насколько легко будет ввести эвристическое управление поиском?
9.17. Как можно воспользоваться методом резолюции для дeмoнcfрации того, что некоторое высказывание является общезначимым? Невыполнимым?
9.18. Из высказывания "Лошади — животные" следует, что "голова лошади — голова животного". Продемонстрируйте, что этот логический вывод является допустимым, выполнив приведенные ниже этапы.
а) Преобразуйте предпосылку и вывод этого высказывания в язык логики
первого порядка. Воспользуйтесь тремя предикатами: HeadOf (h, х)
(который означает, что "п — голова х"), Horse (х) и Animal (х).
б) Примените отрицание к заключению и преобразуйте предпосылку и от-
рицаемое заключение в конъюнктивную нормальную форму.
в) Воспользуйтесь правилом резолюции, чтобы показать, что заключение
следует из предпосылки.
9.19. Ниже приведены два высказывания на языке логики первого порядка.
A. Vx Зу ( х > у )
B. Зу Vx ( х > у )
а) Допустим, что переменные пробегают по всем натуральным числам
0,1,2,...,°°и что предикат > означает "больше или равно". При исполь-
зовании такой интерпретации переведите высказывания А и в на естест-
венный язык.
б) Является ли высказывание А истинным при этой интерпретации?
в) Является ли высказывание В истинным при этой интерпретации?
г) Является ли в логическим следствием А?
д) Является ли А логическим следствием в?
е) С использованием правила резолюции попытайтесь доказать, что А сле-
дует из В. Сделайте эту попытку, даже если вы считаете, что А не следует
логически из В; продолжайте свои усилия до тех пор, пока доказательство
не оборвется и вы не сможете продолжать дальше (поскольку оно оборва-
лось). Покажите унифицирующую подстановку для каждого этапа резо-
люции. Если доказательство окончилось неудачей, точно объясните, где,
как и почему оно оборвалось.
ж) А теперь попытайтесь доказать, что в следует из А.
9.20. Метод резолюции способен вырабатывать неконструктивные доказательства для запросов с переменными, поэтому приходится вводить специальные механизмы для извлечения только определенных ответов. Объясните, почему такая проблема не возникает при использовании баз знаний, содержащих только определенные выражения.
9.21. В этой главе было указано, что метод резолюции не может использоваться для формирования всех логических следствий из некоторого множества высказываний. Позволяет ли какой-то другой алгоритм решить эту задачу?