УПРАЖНЕНИЯ
8.1. Логическая база знаний представляет мир с использованием множества выска-
зываний без явной структуры. Аналогическое представление, с другой сторо-
ны, имеет физическую структуру, которая непосредственно соответствует
структуре представляемого объекта. Возьмите дорожную карту своей страны в
качестве образца аналогического представления фактов о стране. Двухмерная
структура карты соответствует двухмерной поверхности данного региона.
а) Приведите пять примеров символов на языке карты.
б) Явным высказыванием называется высказывание, фактически формули-
руемое разработчиком представления. Неявным высказыванием называет-
ся высказывание, которое следует из явных высказываний в соответствии
со свойствами аналогического представления. Приведите по три примера
неявных и явных высказываний на языке карты.
в) Приведите три примера сведений о физической структуре территории
вашей страны, которые не могут быть представлены на языке карты.
г) Приведите два примера фактов, которые гораздо легче выразить на языке
карты, чем на языке логики первого порядка.
д) Приведите еще два примера полезных аналогических представлений. Ка-
ковы преимущества и недостатки каждого из этих языков, логического и
аналогического?
8.2. Рассмотрите базу знаний, содержащую только два высказывания: Р(а) и Р(Ь). Следует ли из этой базы знаний высказывание Vx Р(х) ? Объясните свой ответ в терминах моделей.
8.3. Является ли допустимым высказывание Зх, у х = у? Объясните, почему.
8.4. Напишите такое логическое высказывание, что каждый мир, в котором оно является истинным, содержит точно один объект.
8.5. Рассмотрите словарь символов, который содержит с константных символов, рк предикатных символов с арностью к каждый и fk функциональных символов с арностью к каждый, где 1<к<А. Допустим, что размер проблемной области ограничен значением D. Для каждой конкретной комбинации "интерпретация/модель" каждый предикатный или функциональный символ отображается, соответственно, на отношение или функцию с той же арностью. Может быть принято предположение, что функции в этой модели допускают, чтобы некоторые входные кортежи не имели значения для этой функции (т.е. чтобы значение было невидимым объектом). Выведите формулу определения количества возможных комбинаций "интерпретация/модель" для проблемной области с D элементами. Не учитывайте необходимость устранения избыточных комбинаций.
8.6. Представьте приведенные ниже высказывания в логике первого порядка, ис-
пользуя совместимый словарь (который вы должны определить).
а) Некоторые студенты участвовали в экзамене по французскому языку вес-
ной 2001 года.
б) Каждый студент, который участвует в экзамене по французскому языку,
сдает его.
в) Только один студент участвовал в экзаменах по греческому языку весной
2001 года.
г) Лучшая оценка по греческому всегда выше чем лучшая оценка по фран-
цузскому.
д) Каждый человек, который покупает страховой полис, умен.
е) Ни один человек не покупает дорогой страховой полис.
ж) Существует агент, который продает страховой полис только людям, кото-
рые не застрахованы.
з) Есть некий парикмахер, который бреет всех мужчин в городе, которые не
бреются сами.
и) Любой человек, рожденный в Великобритании, каждым из родителей ко-
торого является британский гражданин или британский резидент, явля-
ется британским гражданином по рождению.
к) Любой человек, рожденный вне Великобритании, одним из родителей которого является британский гражданин по рождению, является британским гражданином по происхождению.
л) Политические деятели могут постоянно вводить некоторых людей в заблуждение, они также могут вводить в заблуждение всех людей некоторое время, но они не могут постоянно вводить в заблуждение всех людей.
8.7. Представьте высказывание: "Все немцы говорят на одном и том же языке" в исчислении предикатов. Используйте предикат Speaks (х, 1), который означает, что лицо х говорит на языке 2.
8.8. Какая аксиома необходима, чтобы вывести логически факт Female(Laura), если даны факты Male (Jim) и Spouse {Jim, Laura) ?
8.9. Напишите общее множество фактов и аксиом, чтобы представить утверждение: "Веллингтон слышал о смерти Наполеона" и правильно ответить на вопрос: "Наполеон слышал о смерти Веллингтона?"
8.10. Запишите в логике первого порядка факты о мире вампуса, представленные в разделе 7.5 с помощью пропозициональной логики. Насколько более компактной является новая версия?
8.11. Составьте аксиомы с описанием предикатов Grandchild (Внук или внучка), GreatGrandparent (Прадедушка или прабабушка), Brother (Брат), Sister (Сестра), Daughter (Дочь), Son (Сын), Aunt (Тетя), Uncle (Дядя), Brother1лЬ<а(Брат мужа или жены), SisterlnLaw(Сестра мужа или жены) и
FirstCousin (Двоюродный брат или двоюродная сестра). Найдите правильное определение m-го кузена или кузины в n-м колене и запишите это определение в логике первого порядка.
Теперь запишите основные факты, изображенные в генеалогическом дереве, приведенном на рис. 8.3. С использованием подходящей системы формирования логических рассуждений введите в базу знаний с помощью операции Tell все записанные вами высказывания, а затем определите с помощью операции Ask, кто является внуками или внучками Элизабет (Elizabeth), братьями мужа Дианы (Diana), а также прадедушкой и прабабушкой Сары (Sarah).
8.12. Запишите высказывание с утверждением, что функция + является коммутативной. Следует ли это высказывание из аксиом Пеано? В случае положительного ответа объясните, почему; в случае отрицательного ответа приведите модель, в которой эти аксиомы являются истинными, а ваше высказывание — ложным.
8.13. Объясните, в чем ошибка в следующем предлагаемом определении предиката принадлежности к множеству, е :
Vx, s х Е {х \ s]
Vx, s х е s => Vy x G {y|s}
8.14. Используя в качестве примеров аксиомы множества, запишите аксиомы для проблемной области списков, включая все константы, функции и предикаты, упомянутые в данной главе.
8.15. Объясните, в чем ошибка в следующем предлагаемом определении соседних квадратов в мире вампуса:
Vx, у Adjacent ( [х,у] , [х+1 ,у] ) л Adjacent ( [х, у] , [х, у+1 ] )
8.16. Запишите аксиомы, требуемые для формирования рассуждений о местонахождении вампуса, с использованием константного символа Wumpus и бинарного предиката In (Wumpus, Location). Не забудьте учесть, что существует только один вампус.
8.17. (ё) Дополните словарь, приведенный в разделе 8.4, чтобы определить правила сложения для n-битовых двоичных чисел. Затем сформулируйте описание четырехбитового сумматора, показанного на рис. 8.4, и составьте запросы, необходимые для проверки того, что это описание действительно правильно.
8.16.
8.18. Представление схемы, приведенное в этой главе, является более подробным,
чем это необходимо, если нас интересуют только функциональные возможно-
сти этой схемы. В более простой формулировке рассматриваются любые логи-
ческие элементы или цифровые схемы с т входами и п выходами с использо-
ванием предиката, имеющего т+п параметров, такого, что предикат принима-
ет истинное значение тогда и только тогда, когда входы и выходы
согласованы. Например, логические элементы NOT могут быть описаны с по-
мощью бинарного предиката NOT(i,o), для которого известны значения
NOT (0,1) и NOT (1,0). Композиции логических элементов определяются с
помощью конъюнкций предикатов логических элементов, в которых наличие
разделяемых переменных указывает на прямые соединения. Например, схема
NAND может состоять из элементов AND и NOT:
Vii,i2,oa,o NAND (ii, i2, о) <=$ AND (ii, i2 , oa) л NOT(oa,o)
С использованием этого представления определите однобитовый сумматор, приведенный на рис. 8.2, и четырехбитовый сумматор, приведенный на рис. 8.4, и объясните, какими запросами вы бы воспользовались для проверки таких проектов. Какого рода запросы, поддерживаемые представлением, описанным в разделе 8.4, не поддерживаются данным представлением?
8.19. Получите бланк заявки на оформление паспорта для гражданина своей стра-
ны, выясните, какие правила определяют права человека на получение пас-
порта, и переведите эти правила на язык логики первого порядка в соответст-
вии с этапами, описанными в разделе 8.4.