Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 77
Текст из файла (страница 77)
7.2 воспроизведен в более точной форме процесс формирования рассуждений, который проиллюстрирован на рис. 7.4. Общий алгоритм определения логи- Глава 7. Логические агенты 301 ческого следствия в пропозициональной логике приведен в листинге 7.3. Как и в алгоритме Вас)сбгас)схцд-ЯЕаГС)З, ПРиведенном на с. 131, функция ТТ-Епга11з? осушестцляет рекурсивный перебор конечного пространства вариантов присваивания значений переменным. Этот алгоритм является непротиворечивым, поскольку он непосредственно реализует определение логического следствия, и полным, поскольку может применяться для любой базы знаний кв и любого высказывания с( и всегда заканчивает свою работу, при условии, что количество моделей, подлежаших проверке, является конечным.
Листинг 7.3. Алгоритм перебора нстннностней таблицы для получения нренознцненальных логических следствий. Тт обозначает нстнннестную твблнну, функция рь-тгие? возвращает истиннее значение, если некоторое высказывание является истинным в рамках некоторой модели. Переменнвв тоде1 представляет частично заданную модель — нрнсванввнне только некоторым переменным. Вызов функции ехеепа(Р, егие,тоде1) возвращает новую частично заданную модель, в которой высказывание Р имеет значение егие еипсеаоп тт-епса11з?(кВ, а) гееигпв значение егие или еа1зе 1привв: КВ, база знаний — высказывание в пропозициональной логике а, запрос — высказывание в пропозициональной логике зутЬо1з <†список пропозициональных символов в КВ и П гевигп ТТ-Спеси-А11(КВ, П, зутЬо1з, ()) еипсеьоп тт-спеси-А11(кВ, а, зутьо1з, тоде1) гееигпв значение егце или Еа1зе 1Е Етрпу?(зутЬо1з) Еиеп 1Й РЬ-Тгие?(КВ, тоде1) Евеп гевигп РЬ-Тгие?(П, тпде1) е1ве гееиги егие е1ве ао Р +- Рагзь(вутЬо1з); генг ь- пенс(зутЬо1з) гееигп тт-снеек-А11(кв, а, гезг, ехпепд(Р, ггце, тоде1) апа ТТ-СЬесх-А11(КВ, Ы, гезг, Ехеепд(Р, Еа1зе, тоде1) Безусловно, выражение "является конечным" не всегда означает то же, что и выражение "является небольшим".
Если КВ и а содержат в целом п символов, то количество моделей равно 2". Таким образом, временная сложность этого алгоритма составляет 0(2") . (Пространственная сложность составляет только 0(п), поскольку перебор вариантов присваивания происходит по принципу поиска в глубину.) Ниже будут показаны алгоритмы, которые являются гораздо более эффективными на практике. К сожалению, с)Р каждый известный алгоритм логического вывода для пропозициопальпой логики в худшем случае имеет сложность, зкспопепциальпо зависяи(ую от размера ввода.
Мы не можем рассчитывать на то, что наши алгоритмы будут действовать лучше, поскольку задача получения пропозиционального логического следствия является ко-)к(Р-полной (см. приложение А). Эквивалентность, допустимость н выполнимость Прежце чем перейти к изложению подробных сведений об алгоритмах логического вывода, необходимо рассмотреть некоторые дополнительные понятия, ка- Збг Часть П!.
Знания и рассуждения саюшиеся логического следствия. Как и само понятие следствия, эти понятия относятся ко всем формам логики, но их лучше всего показать на примере какого-то конкретного варианта логики, например пропозициональной логики. Первым понятием является тк логическая эквивалентность: два высказывания, а и !3, являются логически эквивалентными, если они истинны в одном и том же множестве моделей. Это утверждение записывается как а оз (3. Например, можно легко ПОКаЗатЬ (С ПОМОШЬЮ ИСтИННОСтНЫХ табЛИц), Чта ВЫСКаЗЫВаНИя Р л О И О л Р логически эквивалентны; другие эквивалентности приведены в листинге 7.4.
Они играют в логике практически такую же роль, какую арифметические равенства играют в обычной математике. Альтернативное определение эквивалентности является следуюшим: для любых двух высказываний а и (3 а и В тогда н только тогда, когдаа и В но 'н а (Вше раз напоминаем, что 1 означает логическое следствие.) Листинг 7.4. Стандартные логические эквивалентности.
Снивояы а, (3 н у обозначают произволь- ные высказывания нранознннональнай логики коммутативность связки л коммутативность связки ассоциативность связки л ассоциативность свяЗки у устранение двойного отрицания контрапозиция устранение импликации устранение двухсторонней импликации правило де Моргана правило де Моргана дистрибутивнооть связки л по дистрибутивнооть связки и по л Вторым понятием, которое нам потребуется, является св допустимость. Высказывание допустимо, если оно истинно во всех моделях. Например, высказывание Р у Р является допустимым. Допустимые высказывания известны также под названием 'ск тавтологий — они обязательно истинны и поэтому избыточны. Поскольку высказывание тдце является истинным во всех моделях, то любое допустимое высказывание логически эквивалентно тз це.
Для чего могут применяться допустимые высказывания? Из определения логического следствия можно вывести сь теорему дедукции, которая была известна еше в древней Греции; мт Дея любых высказываний а и В, а н (3, если и только если высказывание (а ~ (3) является допустимым. (В упр. 7.4 предлагается доказать эту теорему.) Алгоритм логического вывода, приведенный в листинге 7.3, может рассматриваться как проверка допустимости высказывания (кв ~ а) .
И наоборот, каждое допустимое высказывание в форме импликации описывает приемлемый вариант логического вывода. Последним понятием, которое нам потребуется, является Ъ. выполнимость. Некоторое высказывание выполнимо тогда и только тогда, когда оно истинно в неко- (О л (а у 13) ((ало) лу) ((а и (3) ч у) а) (а ~ (3) (а => В) (а~ В) (а л 13) (а х р) (а л (В ч у)) (а и ((3 л у)) и ((3ла) и ((3 у а) и (ал (Влу)) и (ач ((3 чу)) и а — (3 => а) и ( амб) — ((а =-> (3) л (В =-> а) ) ( ах В) и ( ал (3) и ((а л В) ч (а л у)) и ((амб) л (аму)) зоз Глава 7.
Логические агенты торой модели. Например, приведенная выше база знаний, (л, л лз л лз л д4 л лз], выполнима, поскольку существует даже не одна, а три модели, в которых она истинна (см. табл. 7.2). Если некоторое высказывание а является истинным в модели зи, то для обозначения этого применяется выражение, что "зп ск выполняет а", или что "т является моделью а". Выполнимость можно проверить, перебирая все возможные модели до тех пор, пока не будет найдена хотя бы одна из них, которая выполняет данное высказывание.
Первой задачей в пропозициональной логике, для которой было доказано, что она является )к)Р-полной, была задача определения выполнимости высказываний. Многие задачи в компьютерных науках в действительно представляют собой задачи определения выполнимости. Например, во всех задачах удовлетворения ограничений, приведенных в главе 5, по сути требовалось найти ответ на вопрос о том, выполнимы ли данные ограничения при некотором присваивании. Кроме того, с помощью соответствующих преобразований по методу проверки выполнимости можно решать и задачи поиска. Безусловно, что понятия допустимости и выполнимости связаны друг с другом: высказывание а является допустимым тогда и только тогда, когда высказывание — а невыполнимо, и наоборот, высказывание а является выполнимым тогда и только тогда, когда высказывание ~а недопустимо.
На этом основании может быть также получен следующий полезный результат: све Выскозывиние а ~ О истинно, если и только если высказывание (а л )З) невыполнимо. Доказательство истинности высказывания )) на основании истинности высказывания а путем проверки невыполнимости выражения (а л В) точно соответствует стандартному математическому методу доказательства путем 'ск приведения к абсурду (буквально, "доведение до абсурда" — гее)цсг)о ас) аЬзцгс)цщ). Его также называют доказательством путем ск опровержения, или доказательством с помощью выявления противоречия. В этом методе доказательства принимается предположение, что высказывание )З ложно, и демонстрируется, что такое предположение приводит к противоречию с известными аксиомами а.
Подобное противоречие точно соответствует тому, что подразумевается под утверждением, что выражение ) а л В) невыполнимо. 7.5. ШАБЛОНЫ ФОРМИРОВАНИЯ РАССУЖДЕНИЙ В ПРОПОЗИЦИОНАЛЬНОЙ ЛОГИКЕ В данном разделе рассматриваются стандартные шаблоны логического вывода, которые могут применяться для формирования цепочек заключений, ведущих к желаемой цели. Эти шаблоны логического вывода называются ',ъ правилами логического вывода. Наиболее широко известное правило называется сь правилом отделения (Модцз Ропепз — модус поненс) и записывается следующим образом: а =~ В, а Эта запись означает, что если даны любые высказывания в форме а ~ )З и а, то из них можно вывести высказывание р. Например, если дано ( млприял)зеас) л 304 Часть П1.
Знания и рассуждения (в)ширияА11ие) =ь Б)гоос и (я)итрияА)геас( л ьгитрияА11ие), то можно вывести высказывание В)гоос. Еще одним полезным правилом логического вывода является 'в. правило удаления связки иИ", в котором утверждается, что из конъюнкции можно вывести любой из ее конъюнктов: алй а Например, из высказывания ((вгитрияА)геас( л )ГитрияА11ие) можно вывести высказывание ~итрияА11ие. Рассматривая возможные истинностные значения а и [1, можно легко показать, что правило отделения и правило удаления связки "И" являются непротиворечивыми не только применительно к данным примерам, но и ко всем возможным высказываниям. Это означает, что данные правила могут использоваться во всех конкретных случаях, в которых они могут потребоваться, вырабатывая непротиворечивые логические выводы без необходимости перебирать все модели.
В качестве правил логического вывода можно также применять все логические эквивалентности, приведенные в листинге 7.4. Например, из эквивалентности двухсторонней импликации и двух импликаций можно получить следующие два правила логического вывода (первое из них называется правилом удаления двухсторонней импликанииу (и =г [1) л (б =г а) Но не все правила логического вывода действуют в обоих направлениях, как это. Например, нельзя применить правило отделения в противоположном направлении, чтобы получить высказывания а .=> р и а из высказывания 11.
Рассмотрим, как можно использовать эти правила логического вывода и эквивалентности в мире вампуса. Начнем с базы знаний, содержащей высказывания Вг — В„ и покажем, как доказать высказывание Р, „т.е. утверждение, что в квадрате [1, 2] нет ямы. Вначале применим правило удаления двухсторонней импликации к высказыванию В„чтобы получить следующее: Лв; (Виг => (Рг,г ч Рг г)) л ((Р;,г ч Рг г) ~ Вг г) Затем применим к высказыванию Вв правило удаления связки "И" и получим: лг: ((Ргг ч Ргг) => В;, ) Из логической эквивалентности отрицаний следует: кв: ( В;,г =г ° (Риг ч Рг,г) ) Теперь можно применить правило отделения к высказыванию нв и к высказыванию Вв с данными восприятия (т.е, — В, г), чтобы получить следующее: Лв: (Рг г ч Рг г) Наконец, применим правило де Моргана, позволяющее получить такое заключение: Лгв: -гРг,г л -гРг,г Это означает, что ни в квадрате [1, 21, ни в квадрате [2, 11 нет ямы.
305 Глава 7. Логические агенты Приведенный выше процесс логического вывода (последовательиость применения правил логического вывода) называется Ъ. доказательством. Процесс формирования доказательств полностью аналогичен процессу обнаружения решений в задачах поиска.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
