Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 100
Текст из файла (страница 100)
Каковы преимушества и недостатки каждого из этих языков, логического и аналогического? 8.2. Рассмотрите базу знаний, содержащую только два высказывания: Р(а) и Р(Ь). Следует ли из этой базы знаний высказывание зх Р(х)? Объясните свой ответ в терминах моделей.
8.3. Является ли допустимым высказывание Эх, у х = у? Объясните, почему. 8.4. Напишите такое логическое высказывание, что каждый мир, в котором оно является истинным, содержит точно один объект. 8.5. Рассмотрите словарь символов, который содержит с константных символов, р„предикатных символов с арностью (с каждый и б, функциональных символов с арностью (с каждый, где ).<(г<л. Допустим, что размер проблемной области ограничен значением (з. Для каждой конкретной комбинации "интерпретация/модель" каждый предикатный или функциональный символ отображается, соответственно, на отношение или функцию с той же арносгью.
Может быть принято предположение, что функции в этой модели допускают, чтобы некоторые входные кортежи не имели значения для этой Глава 8. Логика первого порядка 377 8.6. 8.7. 8.8. 8.9. 8.10. 8.11. функции (т.е. чтобы значение было невидимым объектом). Выведите формулу определения количества возможных комбинаций "интерпретация/модель*' для проблемной области с и злементами. Не учитывайте необходимость устранения избыточных комбинаций. Представьте приведенные ниже высказывания в логике первого порядка, используя совместимый словарь (который вы должны определить). а) Некоторые студенты участвовали в экзамене по французскому языку весной 200! года.
б) Каждый студент, который участвует в экзамене по французскому языку, сдает его. в) Только один студент участвовал в экзаменах по греческому языку весной 200! года. г) Лучшая оценка по греческому всегда выше чем лучшая оценка по французскому. д) Каждый человек, который покупает страховой полис, умен. е) Ни один человек не покупает дорогой страховой полис. ж) Существует агент, который продает страховой полис только людям, когорые не застрахованы. з) Есть некий парикмахер, который бреет всех мужчин в городе, которые не бреются сами.
и) Любой человек, рожденный в Великобритании, каждым из родителей которого является британский гражданин или британский резидент, является британским гражданином по рождению. к) Любой человек, рожденный вне Великобритании, одним из родителей которого является британский гражданин по рождению, является британским гражданином по происхождению. л) Политические деятели могут постоянно вводить некоторых людей в заблуждение, они также могут вводить в заблуждение всех людей некоторое время, но они не могут постоянно вводить в заблуждение всех людей.
Представьте высказывание; "Все немцы говорят на одном и том же языке" в исчислении предикатов. Используйте предикат ~реа?св ! х, 1 !, который означает, что лицо х говорит на языке 1. Какая аксиома необходима, чтобы вывести логически факт ьета1и (лаоса), если даны факты зга1е !.туп! и Яроиве (,туга, Ьаиса )? Напишите общее множество фактов и аксиом, чтобы представить утверждение: "Веллингтон слышал о смерти Наполеона" и правильно ответить на вопрос: "Наполеон слышал о смерти Веллингтона?" Запишите в логике первого порядка факты о мире вампуса, представленные в разделе 7.5 с помощью пропозициональной логики.
Насколько более компактной является новая версия? Составьте аксиомы с описанием предикатов акапйсй11с! (Внук или внучка), стеасскапс)рагепс (прадедушка или прабабушка), всос)зев (Брат), яхвсес (Сестра), !за аул с ег (Дочь), Боп (сын), липс (тетя), гтп с1 е (Дядя), врос!зек1пьаы(Брат мужа или жены), БЗ в с езтпьаы(сестра мужа или жены) и 378 Часть[И. Знания и рассуждения р1 ке ссоие1п (Двоюродный брат или двоюродная сестра). Найдите правильное определение гп-го кузена или кузины в и-м колене и запишите это определение в логике первого порядка.
Теперь запишите основные факты, изображенные в генеалогическом дереве, приведенном на рис. 8.3. С использованием подходящей системы формирования логических рассуждений введите в базу знаний с помощью операции Те11 все записанные вами высказывания, а затем определите с помощью операции Аэ)с, кто является внуками или внучками Элизабет (Е[[ваЬе[Ь), братьями мужа Дианы (Р)апа), а также прадедушкой и прабабушкой Сары (Вагай). Врепсег И КИО Е!тапера И Рпг)гр Магаагег Р)апа И Еааг1еа Аппе И Мат Аппгезг И Вагах Еп вага ЛЛР Фгэ)ат Нану Регег Лага Веагпсе Епаепге Рис.
83. 7йггинггое генеалогическое дерево. Символ е г соединяет супругов, а стрелки указывают на детей 8.12. Запишите высказывание с утверждением, что функция + является коммутативной. Следует ли это высказывание из аксиом Пеано? В случае положительного ответа объясните, почему; в случае отрицательного ответа приведите модель, в которой эти аксиомы являются истинными, а ваше высказывание— ложным. 8.13. Объясните, в чем ошибка в следующем предлагаемом определении предиката принадлежности к множеству, н: гух,в х е (х[е) гух, е х е е => гггу х е (у[в) 8.14.
Используя в качестве примеров аксиомы множества, запишите аксиомы для проблемной области списков, включая все константы, функции и предикаты, упомянутые в данной главе. 8.15. Объясните, в чем ошибка в следующем предлагаемом определении соседних квадратов в мире вампуса: Гух,у Ас)уасепс[ [х,у), [хет,у] ) А Ас13асепг( [х,у], [х,у+1] ) 8.16.
Запишите аксиомы, требуемые для формирования рассуждений о местонахождении вампуса, с использованием константного символа вгцтрце и бинарного предиката гп(и~итров, ъосасдоп) . Не забудьте учесть, что сугцествует только один вампус. 8.17. [Й Дополните словарь, приведенный в разделе 8.4, чтобы определить правила сложения дяя и-битовых двоичных чисел. Затем сформулируйте описание четырехбитового сумматора, показанного на рис. 8.4, и составьте запросы, необходимые для проверки того, что это описание действительно правильно.
379 Глава 8. Логика первого порядка «о )о «з «з Хз «о Гз )з )з )о х, )', Уз Хз )з Уо «з Уз Уз «о гз «з г, Рас. 8.4. Четырехбатаеыа сумматор Цтз 12, Оа О ИЛНР(тз 12 О) ео АКР(зз 12 Ое) м ИОт(О, О) С использованием этого представления определите однобитовый сумматор, приведенный на рис. 8.2, и четырехбитовый сумматор, приведенный на рис.
8.4, и объясните, какими запросами вы бы воспользовались для проверки таких проектов. Какого рода запросы, поддерживаемые представлением, описанным в разделе 8.4, не поддерживаются данным представлением? 8.19. Получите бланк заявки на оформление паспорта для гражданина своей страны, выясните, какие правила определяют права человека на получение паспорта, и переведите эти правила на язык логики первого порядка в соответствии с этапами, описанными в разделе 8.4. 8.18. Представление схемы, приведенное в этой главе, является более подробным, чем это необходимо, если нас интересуют только функциональные возможности этой схемы. В более простой формулировке рассматриваются любые логические элементы или цифровые схемы с и входами и п выходами с использованием предиката, имеющего тьп параметров, такого, что предикат принимает истинное значение тогда и только тогда, когда входы и выходы согласованы.
Например, логические элементы ыОт могут быть описаны с помощью бинарного предиката нот(1, о), для которого известны значения ИОт(0, 1) и ыОт(1, 0) . Композиции логических элементов определяются с помощью конъюнкций пред)окатов логических элементов, в которых наличие разделяемых переменных указывает на прямые соединения. Например, схема голыР может состоять из элементов л)(Р и ыОт: В этой главе будут определены эффективные процедуры получения ответов на вопросы, сформулированные в логике первого порядка.
В главе 7 определено понятие логического вывода и показано, как можно обеспечить непротиворечивый и полный логический вывод для пропозициональной логики. В данной главе эти результаты будут дополнены для получения алгоритмов, позволяющих найти ответ на любой вопрос, сформулированный в логике первого порядка и имеюший ответ. Обладать такой возможностью очень важно, поскольку в логике первого порядка можно сформулировать практически любые знания, приложив для этого достаточные усилия. В разделе 9.1 представлены правила логического вывода для кванторов и показано, как можно свести вывод в логике первого порядка к выводу в пропозициональной логике, хотя и за счет значительных издержек.
В разделе 9.2 описана идея унификации и показано, как эта идея может использоваться для формирования правил логического вывода, которые могут применяться непосредственно к высказываниям в логнке первого порядка. После этого рассматриваются три основных семейства алгоритмов вывода в логике первого порядка: прямой логический вывод и его применение к дедуктивным базам данных и продукционным системам рассматриваются в разделе 9.3; процедуры обратного логического вывода и системы логического программирования разрабатьяваются в разделе 9.4; а системы доказательства теорем на основе резолюции описаны в разделе 9.5.
Вообще говоря, в любом случае следует использовать наиболее эффективный метод, позволяющий охватить все факты и аксиомы, которые должны бь1ть выражены в процессе логического вывода. Но следует учитывать, что формирование рассуждений с помощью полностью общих высказываний логики первого порядка на основе метода резолюции обычно является менее эффективным по сравнению с формированием рассуждений с помощью определенных выражений с использованием прямого или обратного логического вывода. 38! Глава 9. Логический вывод в логике первого порядка 9. 1.
СРАВНЕНИЕ МЕТОДОВ ЛОГИЧЕСКОГО ВЫВОДА В ПРОПОЗИЦИОНАЛЬНОЙ ЛОГИКЕ И ЛОГИКЕ ПЕРВОГО ПОРЯДКА В этом и следуюших разделах будут представлены идеи, лежашие в основе современных систем логического вывода. Начнем описание с некоторых простых правил логического вывода, которые могут применяться к высказываниям с кванторами для получения высказываний без кванторов. Эти правила естественным образом приводят к идее, что логический вывод в логике первого порядка может осушествляться путем преобразования высказываний в логике первого порядка, храняшихся в базе знаний, в высказывания, представленные в пропозицнональной логике, и дальнейшего использования пропозиционального логического вывода, а о том, как выполнять этот вывод, нам уже известно из предыдуших глав.
В следующем разделе указано одно очевидное сокра(цение, которое приводит к созданию методов логического вывода, позволяюших непосредственно манипулировать высказываниями в логике первого порядка. Правила логического вывода для кванторов Начнем с кванторов всеобшности. Предположим, что база знаний содержит следующую стандартную аксиому, которая передает мысль, содержашуюся во многих сказках, что все жадные короли — злые: Чх Ктпд(х) л Сгееду(х) ~ Еъ11(х) В таком случае представляется вполне допустимым вывести из нее любое из следующих высказываний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
