УПРАЖНЕНИЯ

7.1. Опишите мир вампуса в соответствии со свойствами проблемной среды, перечисленными в главе 2.
7.2. Предположим, что агент достиг пункта, показанного на рис. 7.3, я, получив такие результаты восприятия: в квадрате [1,1] — ничего, в квадрате [2,1] — ветерок, а в квадрате [1,2] — неприятный запах. В настоящий момент агента интересует содержимое квадратов [1,3], [2,2] и [3,1]. Каждый из них может содержать яму, и самое большее в одном из них может находиться вампус. На основе примера, приведенного на рис. 7.4, сконструируйте множество возможных миров. (Должно быть найдено 32 таких возможных мира.) Отметьте миры, в которых существующая база знаний является истинной, а также те, в которых истинным является каждое из следующих высказываний:
ОС2 = "В квадрате [2,2] нет ямы"
ос3 = "В квадрате [1,3] есть вампус"
На основании этого покажите, что KB И а2икв И ос3.
7.3. Рассмотрите задачу определения того, является ли некоторое высказывание
пропозициональной логики истинным в данной модели.
а) Напишите рекурсивный алгоритм PL-True? (s,т), который возвращает true тогда и только тогда, когда высказывание s является истинным в модели т (где т присваивает истинностное значение каждому символу в s). Этот алгоритм должен заканчивать свою работу за время, линейно зависящее от размера высказывания. (Еще один вариант состоит в том, чтобы воспользоваться версией этой функции из оперативного репозитария кода.)
б) Приведите три примера высказываний, в отношении которых можно опреде-
лить, являются ли они истинными или ложными, в частичной модели, в ко-
торой не заданы истинностные значения для некоторых из символов.
в) Покажите, что в общем случае истинностное значение высказывания (если
оно имеется) невозможно эффективно определить в частичной модели.
г) Доработайте свой алгоритм PL-True? так, чтобы он иногда позволял су-
дить об истинностном значении по частичным моделям, сохраняя вместе
с тем свою рекурсивную структуру и линейную зависимость времени
прогона от размера высказывания. Приведите три примера высказыва-
ний, истинность которых в частичной модели не обнаруживается вашим
алгоритмом.
д) Проведите исследование того, позволяет ли этот модифицированный
алгоритм повысить эффективность алгоритма TT-Entails?.
7.4. Докажите каждое из приведенных ниже утверждений.
а) Высказывание а является допустимым тогда и только тогда, когда
True \= а.
б) Для любого высказывания а истинно, что False \= а.
в) Истинно, что а N (3 тогда и только тогда, когда высказывание (а => (3)
допустимо.
г) Истинно, что а = (3 тогда и только тогда, когда высказывание (а (3)
допустимо.
д) Истинно, что а \= (3 тогда и только тогда, когда высказывание
(а л -, (3) недостижимо.
7.5. Рассмотрите словарь, состоящий только из четырех высказываний, А, в, С и D.
Сколько существует моделей для каждого из следующих высказываний?
а) (А л В) v (В л С)
б) A v В
в) А В <=> С
7.6. В этой главе мы определили четыре различных бинарных логических связки.
а) Имеются ли какие-либо другие логические связки, которые могут ока-
заться полезными?
б) Сколько может быть определено разных бинарных связок?
в) Почему некоторые из них не очень полезны?
7.7. Используя любой предпочитаемый вами метод, проверьте каждую из эквива-лентностей, приведенных в листинге 7.4.
7.8. Определите, является ли каждое из приведенных ниже высказываний действительным, невыполнимым или ни тем ни другим. Проверьте полученные вами результаты с помощью истинностных таблиц или правил эквивалентности, приведенных в листинге 7.4.
а) Smoke => Smoke
б) Smoke => Fire
в) (Smoke => Fire) => (-nSmoke => -iFire)
г) Smoke v Fire v —iFire
д) {{Smoke л Heat) => Fire) <=> ((Smoke => Fire) v (Heat =>
Fire) )
е) (Smoke => Fire) => ((Smoke л Heat) => Fire)
ж) Big v Dumb v (Big => Dumb)
з) (Big A Dumb) v -Dumb
7.9. {Адаптировано из [78].) Можете ли вы доказать на основании приведенных
ниже рассуждений, что единорог — мифическое существо? А что насчет того,
что это волшебное существо? Существо, вооруженное рогом?
Если единорог — мифическое существо, то он бессмертен, а если не мифическое, то он — смертное млекопитающее. Если единорог либо бессмертен, либо является млекопитающим, то он вооружен рогом. Единорог является волшебным существом, если он вооружен рогом.
7.10. Любое высказывание пропозициональной логики логически эквивалентно утверждению, что любой возможный мир, в котором это высказывание было бы ложным, не имеет места. На основании этого наблюдения докажите, что любое высказывание может быть записано в конъюнктивной нормальной форме.
7.11. Minesweeper (минный тральщик) — широко известная компьютерная игра, которая тесно связана с миром вампуса. Мир минного тральщика представляет собой прямоугольную решетку из N квадратов с М разбросанными по ним невидимыми минами. Агент может проверить любой квадрат; если он проверяет заминированный квадрат, его ждет немедленная смерть. В игре Minesweeper наличие мин раскрывается путем показа в каждом проверенном квадрате количества мин в квадратах, соседних по горизонтали, вертикали или диагонали. Цель игры состоит в том, чтобы проверить каждый незаминиро-ванный квадрат.
а) Допустим, что высказывание xitj является истинным тогда и только тогда, когда в квадрате находится мина. Составьте утверждение, согласно которому в квадратах, соседних по отношению к квадрату [1,1],
имеется точно две мины, в виде высказывания, включающего определенную логическую комбинацию высказываний Xi# j.
б) Обобщите ваше утверждение, составленное при выполнении упр. 7.11, а,
и объясните, как следует формировать высказывание CNF с утверждением, что к из п соседних квадратов содержат мины.
в) Точно объясните, как агент может использовать алгоритм DPLL для дока-
зательства того, что данный квадрат содержит (или не содержит мину),
игнорируя глобальное ограничение, согласно которому всего имеется
точно м мин.
г) Предположим, что глобальное ограничение конструируется с помощью
метода, созданного вами при выполнении упр. 7.11, б. Как зависит количество выражений в этом ограничении от Ми iV? Предложите способ осуществления такой модификации алгоритма DPLL, чтобы в нем не требовалось явно представлять это глобальное ограничение.
д) Становятся ли недействительными какие-либо выводы, полученные при
создании метода, о котором речь идет в задании 7.11, в, если учитывается
это глобальное ограничение?
е) Приведите примеры конфигураций проверочных значений, которые по-
рождают такие далеко идущие зависимости, что содержимое любого не-
проверенного квадрата может предоставить информацию о содержимом
какого-то далеко отстоящего от него квадрата. {Подсказка. Рассмотрите
доску с размерами ivxl.)
7.12. В данном упражнении рассматривается связь между выражениями и импликативными высказываниями.
а) Покажите, что выражение (-пРх v ... v -,pm v Q) логически эквивалентно импликативному высказыванию (Рг л ... л Рт) ?=> Q.
б) Покажите, что каждое выражение (независимо от количества положительных литералов) может быть записано в форме (Р2 л ... л PJ =>
((?! v ... v Qn), где Ри Q— пропозициональные символы. База знаний,
состоящая из таких высказываний, находится в импликативной нормальной
форме, или в форме Ковальского.
в) Составьте полное правило резолюции для высказываний в импликативной нормальной форме.
7.13. В этом упражнении речь идет о проектировании агента для мира вампуса на
основе логической схемы.
а) Запишите уравнение, аналогичное уравнению 7.4, для высказывания
Arrow, которое должно быть истинным, если у агента все еще есть стре-
ла. Составьте соответствующую логическую схему.
б) Повторите задание 7.13, а для высказывания FacingRight (агент смот-
рит вправо), используя в качестве образца уравнение 7.5.
в) Создайте версии уравнений 7.7 и 7.8 для поиска вампуса и начертите ло-
гическую схему.
7.14. Обсудите понятие оптимального поведения в мире вампуса. Покажите, что
приведенное в этой главе определение алгоритма PL-Wumpus-Agent не явля-
ется оптимальным, и предложите способы его усовершенствования.
7.15. ш Дополните алгоритм PL-Wumpus-Agent таким образом, чтобы он обеспечивал отслеживание всех относящихся к делу фактов с помощью только базы
знаний.
7.16. Сколько времени потребуется, чтобы доказать высказывание ХВ N ас помощью алгоритма DPLL, если а — литерал, который уже содержится в базе знаний кв? Объясните полученные результаты.
7.17. Проследите за поведением алгоритма DPLL при обработке приведенной на рис. 7.7 базы знаний в попытке доказать высказывание Q и сравните это поведение с тем, которое демонстрируется алгоритмом прямого логического вывода.







Материалы

Яндекс.Метрика