Лекции - Искусственный интеллект
Подождите немного. Документ загружается.
2. Операция отрицания продвигается внутрь формул с
помощью законов де Моргана
3. Логические формулы приводятся к дизъюнктивной
форме.
Правило резолюции содержит в левой части конъюнкцию
дизъюнктов, поэтому приведение посылок, используемых для
доказательства, к виду, представляющему собой конъюнкции
дизъюнктов, является необходимым этапом практически
любого алгоритма, реализующего логический вывод на базе
метода резолюции. Метод резолюции легко программируется,
это одно из важнейших его достоинств.
Предположим, нужно доказать, что если истинны
соотношения
RP
,
QP
и
SQ
, то можно вывести
формулу
SR
. Для этого нужно выполнить следующие шаги.
1. Приведение посылок к дизъюнктивной форме:
RP
,
QP
,
SQ
.
SRSR )(
.
Полученная конъюнкция справедлива, когда
R
и
S
одновременно истинны.
3. Применение правила резолюции:
,)( PRRP
,)( QPQP
,)( QSSQ
FQQ
(противоречие или «пустой дизъюнкт»).
Итак, предположив ложность выводимого заключения,
получаем противоречие, следовательно, выводимое заключение
является истинным, т.е.
SR
выводимо из исходных посылок.
Именно правило резолюции послужило базой для
создания языка логического программирования PROLOG. По
сути дела, интерпретатор языка PROLOG самостоятельно
реализует вывод, формируя ответ на вопрос пользователя,
обращенный к базе знаний.
В логике предикатов для применения правила резолюции
предстоит осуществить более сложную унификацию логических
формул в целях их приведения к системе дизъюнктов. Это
123
связано с наличием дополнительных элементов синтаксиса, в
основном кванторов, переменных, предикатов и функций.
Унификация. Чтобы применять правила вывода, система
вывода должна уметь определять, когда два выражения
являются эквивалентными (равносильными). В исчислении
высказываний это тривиально: два выражения равносильны
тогда и только тогда, когда они синтаксически идентичны. В
ИП определение равносильности двух предложений
усложняется наличием переменных. Существуют правила,
позволяющие заменять переменные под знаком квантора
всеобщности () термами из области определения. Необходимо
определить процесс замены переменных, при которых
несколько выражений могут стать идентичными. Унификация
определяет условия, при которых два (или больше) выражения
ИП могут быть эквивалентными (равносильными).
Унификация – это алгоритм определения необходимых
подстановок с целью приведения в соответствие двух
выражений ИП. Унификация и такие правила вывода как modus
ponens, позволяют делать выводы на множестве логических
утверждений. Для этого база данных должна быть выражена в
соответствующей форме. Важный аспект этой формы
заключается в требовании, чтобы все переменные стояли под
знаком квантора всеобщности. Это обеспечивает в выполнении
подстановок. Переменные, стоящие под квантором
существования () можно устранить из предложений, заменив
их константами, обеспечивающими истинность предложения.
Например, х родитель (х, Олег) может быть заменено
выражением родитель (Роман, Олег) или (Надежда, Олег),
принимая во внимание, что Роман и Надежда являются
родителями Олега в этой интерпретации.
Процесс удаления переменных, связанных квантором
существования, усложняется тем, что значение этих
подстановок может зависеть от значения других переменных.
Например, в высказывании
yx
мать (х,у) значение
переменной у под квантором зависит от значения х.
Сколемизация – это замена каждой переменной, связанной
124
квантором существования, функцией нескольких переменных,
которая возвращает соответствующую константу. В примере у
можно заменить сколемовской функцией f от х, получаем
предикат х мать (х, f(x)). Сколемизация также позволяет
связывать переменные, стоящие под квантором всеобщности, с
константами.
При создании алгоритма унификации, который вычисляет
подстановки, возникают следующие проблемы.
1. Так как константу можно использовать в качестве
подстановки для переменной, любая константа рассматривается
как «базовый экземпляр» и не может быть заменена. Нельзя
также два различных «базовых экземпляра» использовать в
качестве подстановки для одной и той же переменной.
2. Переменная не может быть унифицирована с термом,
содержащим ее. Поэтому переменная х не может быть заменена
на f(x).
Процесс решения задачи требует ряда выводов и,
следовательно, ряда последовательных унификаций. Логические
решающие устройства задач должны поддерживать
согласованность установок для переменных. Важно, чтобы
любая унифицирующая подстановка была сделана, согласовано
по всем вхождениям этой переменной во все выражения. А
выражения должны быть приведены в соответствие друг другу.
3. Если переменная связана, все последующие
унификации и процедуры вывода должны учитывать это. Если
переменная связана с константой, ее уже нельзя связывать с
другим термом при последующих унификациях. Если
переменная х
1
использовалась в качестве подстановки для х
2
, а
затем была заменена константой, то в х
2
тоже необходимо
отразить это связывание.
4. Унификатор должен быть максимально общим, т.е. для
любых двух выражений должен быть найден наиболее общий
унификатор. Это очень важно, так как при потере общности в
процессе решения уменьшается вероятность достижения
окончательного решения или такая возможность исчезает.
125
Алгоритм унификации предикатных логических формул
включает следующие шаги.
1. Исключение операций эквивалентности.
2. Исключение операций импликации.
3. Внесение операций отрицания внутрь формул.
4. Исключение кванторов существования. Это может про-
изойти на шаге 3 вследствие применения законов де Моргана, а
именно: в результате отрицания меняется на , но при этом
может произойти и обратная замена. Тогда для исключения
поступают следующим образом: все вхождения некоторой
переменной, связанной квантором существования, например
(X), заменяются в формуле на новую константу, например а.
Эта константа представляет собой некоторое (неизвестное)
значение переменной X, для которого утверждение, записанное
данной формулой, истинно. При этом важно то, что на все
места, где присутствует X, будет подставлено одно и то же
значение а, пусть оно и является неизвестным в данный момент.
Такие константы называются сколемовскими, а операция —
сколемизацией (по имени известного математика Сколема).
5. Кванторы общности выносятся на первые места в
формулах. Это также не всегда является простой операцией,
иногда при этом приходится делать переименование
переменных.
6. Раскрытие конъюнкций, попавших внутрь дизъюнкций,
т.е. бескванторную часть формулы привести к конъюнктивной
нормальной форме (КНФ).
После выполнения всех шагов описанного алгоритма
унификации можно применять правило резолюции. Обычно при
этом осуществляется отрицание выводимого заключения, и
алгоритм вывода можно кратко описать следующим образом:
Если задано несколько аксиом (теория Тh) и предстоит сделать
заключение о том, выводима ли некоторая формула Р из аксиом
теории Тh, строится отрицание Р и добавляется к Тh, при этом
получают новую теорию Тh1. После приведения
P
и аксиом
теории к системе дизъюнктов можно построить конъюнкцию
P
и аксиом теории Тh. При этом существует возможность
126
выводить из исходных дизъюнктов дизъюнкты-следствия. Если
Р выводимо из аксиом теории Тh, то в процессе вывода можно
получить некоторый дизъюнкт Q, состоящий из одной литеры, и
противоположный ему дизъюнкт
Q
. Это противоречие
свидетельствует о том, что Р выводимо из аксиом Тh. Вообще
говоря, существует множество стратегий доказательства, нами
рассмотрена лишь одна из возможных — нисходящая.
Пример. Представим средствами логики предикатов
следующий текст:
«Если студент умеет хорошо программировать, то он
может стать специалистом в области информационных
технологий».
«Если студент хорошо сдал экзамен по технологии
программирования, значит, он умеет хорошо программировать».
Представим этот текст средствами логики предикатов
первого порядка. Введем обозначения: X — переменная для
обозначения студента; хорошо — константа, соответствующая
уровню квалификации; Р(Х) — предикат, выражающий
возможность субъекта X стать специалистом в области
информационных технологий; Q(X, хорошо) — предикат,
обозначающий умение субъекта X программировать с оценкой
хорошо; R(Х, хорошо) — предикат, задающий связь студента X
с экзаменационной оценкой по технологии программирования.
Теперь построим множество ППФ:
(Х)Q(Х, хорошо)Р(Х).
(Х)R(Х, хорошо) Q(Х, хорошо).
Дополним полученную теорию конкретным фактом R(ива-
нов, хорошо).
Выполним логический вывод с применением правила
резолюции, чтобы установить, является ли формула Р(иванов)
следствием вышеприведенной теории. Другими словами, можно
ли вывести из этой теории факт, что студент Иванов станет
специалистом в области информационных технологий, если он
хорошо сдал экзамен по технологии программирования.
Доказательство.
127
1. Выполним преобразование исходных формул теории в
целях приведения к дизъюнктивной форме:
(Х)
Q(Х,хорошо)Р(Х);
(Х)
R(Х,хорошо)Q(Х,хорошо);
R(иванов, хорошо).
2. Добавим к имеющимся аксиомам отрицание
выводимого заключения
Р(иванов).
3. Построим конъюнкцию дизъюнктов
(Х)
Q(Х, хорошо) Р(Х)
Р(иванов)
Q(иванов, хорошо),
заменяя переменную X на константу иванов.
Результат применения правила резолюции называют
резольвентой. В данном случае резольвентой является
Q(иванов).
4. Построим конъюнкцию дизъюнктов с использованием
резольвенты, полученной на шаге 3:
(Х)
R(Х, хорошо)(Х, хорошо) /\
Q(иванов,
хорошо)
R(иванов, хорошо).
5. Запишем конъюнкцию полученной резольвенты с
последним дизъюнктом теории:
R(иванов, хорошо) /\ R(иванов, хорошо) F
(противоречие). Следовательно, факт Р(иванов) выводим из
аксиом данной теории.
Для определения порядка применения аксиом в процессе
вывода существуют следующие эвристические правила:
1. На первом шаге вывода используется отрицание
выводимого заключения.
2. В каждом последующем шаге вывода участвует
резольвента, полученная на предыдущем шаге.
Рассмотрим пример применения методов поиска решений
на основе исчисления предикатов. Пример «интересная жизнь»
взят из [6]. Заданы утверждения 1-4 в 1-м столбце таблицы 6.2.
Требуется ответить на вопрос: «Существует ли человек,
живущий интересной жизнью?» В виде предикатов эти
128
утверждения записаны во 2-ом столбце таблицы. В третьем
столбце таблицы записаны дизъюнкты.
Таблица 6.2
Утверждения
и заключение
Предикаты Дизъюнкты
1 2 3
1. Все
небедные и
умные люди
счастливы
))(
)(
)((
xhappy
xsmart
xpoorx
)(
)()(
xhappy
xsmartxpoor
2. Человек,
читающий
книги, - неглуп
))(
)((
xsmart
xreadx
)()( xsmartxread
3. Сергей
умеет читать и
является
состоятельным
человеком
)(
)(
Сергейpoor
Сергейread
)(
),(
Сергейpoor
Сергейread
4. Счастливые
люди живут
интересной
жизнью
))(
))((
xexciting
xhappyx
)()( xexcitingxhappy
Продолжение табл. 6.2
1 2 3
5. Заключение:
Существует ли
человек,
живущий
интересной
жизнью?
))(( xexcitingx
)(xexciting
6. Отрицание
заключения
))(( xexcitingx
)(xexciting
129
Одно из возможных доказательств (их более одного) дает
следующая последовательность резольвент:
1. Резольвентой дизъюнктов
)()( xexcitingxhappy
и
)(xexciting
является
)(xhappy
.
2.
)(xhappy
и
)()()( xhappyxsmartxpoor
дают
резольвенту
)()( xsmartxpoor
.
3.
)()( xsmartxpoor
и
)()( xsmartxread
-
)()( xreadxpoor
.
4. Унифицируем
)()()()( СергейreadСергейpoorxreadxpoor
x
Сергей
.
Резольвентой дизъюнктов
)()( СергейreadСергейpoor
и
)(Сергейread
является
)(Сергейpoor
.
5. Дизъюнкты
)(Сергейpoor
и
)(Сергейpoor
дают
пустую резольвенту.
Получение пустой резольвенты означает, что база
данных выражений содержит противоречие и поэтому
предположение о том, что существует человек, живущий
интересной жизнью, верно.
6.2. Прямой и обратный вывод в экспертных системах
продукционного типа
Любая экспертная система продукционного типа должна
содержать три основные компоненты: базу правил, рабочую
память и механизм вывода.
База правил (БП) — формализованные с помощью правил
продукций знания о конкретной предметной области.
Рабочая память (РП) — область памяти, в которой
хранится множество фактов, описывающих текущую ситуацию,
и все пары атрибут-значение, которые были установлены к
определенному моменту. Содержимое РП в процессе решения
задачи изменяется обычно, увеличиваясь в объеме по мере
применения правил. Другими словами, РП — это динамическая
часть базы знаний, содержимое которой зависит от окружения
130
решаемой задачи. В простейших ЭС хранимые в РП факты не
изменяются в процессе решения задачи, однако существуют
системы, в которых допускается изменение и удаление фактов
из РП. Это системы, работающие в условиях неполноты инфор-
мации.
Механизм вывода выполняет две основные функции:
• просмотр существующих в рабочей памяти фактов и
правил из БП, а также добавление в РП новых фактов;
• определение порядка просмотра и применения правил.
Порядок может быть прямым или обратным.
Прямой порядок — от фактов к заключениям. В
экспертных системах с прямыми выводами по известным
фактам отыскивается заключение, которое из этих фактов
следует. Если такое заключение удается найти, оно заносится в
рабочую память. Прямые выводы часто применяются в
системах диагностики, их называют выводами, управляемыми
данными.
Обратный порядок вывода - от заключений к фактам. В
системах с обратным выводом вначале выдвигается некоторая
гипотеза о конечном суждении, а затем механизм вывода
пытается найти в рабочей памяти факты, которые могли бы
подтвердить или опровергнуть выдвинутую гипотезу. Процесс
отыскания необходимых фактов может включать достаточно
большое число шагов, при этом возможно выдвижение новых
гипотез (целей). Обратные выводы управляются целями.
Для выполнения указанных функций механизм вывода
включает компоненту вывода и управляющую компоненту.
Компонента вывода. Ее действие основано на применении
правила логического вывода Modus Ponendo Ponens. Суть
применения этого правила в продукционных системах состоит в
следующем. Если в РП присутствует истинный факт А и в БП
существует правило вида «ЕСЛИ А, ТО В», то факт В
признается истинным и заносится в РП. Такой вывод легко
реализуется на ЭВМ, однако при этом часто возникают
проблемы, связанные с распознаванием значений слов, а также с
тем, что факты могут иметь внутреннюю структуру и между
131
элементами этой структуры возможны различного рода связи.
Например, пусть имеется факт А — «Автомобиль Иванова -
белый» и правило «ЕСЛИ Автомобиль — белый, ТО
Автомобиль легко заметить ночью». Человек легко выведет
заключение «Автомобиль Иванова легко заметить ночью», но
это не под силу ЭС чисто продукционного типа. Она не сможет
сформировать такое заключение, потому что А не совпадает
точно с антецедентом правила. Подобная проблема уже
затрагивалась, когда рассматривались различия логики
высказываний и логики предикатов. Кроме того, невысокая ин-
теллектуальная мощность продукционных систем обусловлена
тем, что человек выводит заключения, имея в своем распоряже-
нии все свои знания, т.е. БЗ огромного объема, в то время как
ЭС способны вывести сравнительно небольшое количество
заключений, используя заданное множество правил. Из
сказанного можно сделать вывод о том, что компонента вывода
в ЭС должна быть организована так, чтобы быть способной
функционировать в условиях недостатка информации.
Управляющая компонента. Она определяет порядок
применения правил, а также устанавливает, имеются ли еще
факты, которые могут быть изменены в случае продолжения
работы. Механизм вывода работает циклически, при этом в
одном цикле может сработать только одно правило. Схема
цикла приведена на рис. 6.1. В цикле выполняются следующие
основные операции:
• сопоставление — образец (антецедент) правила
сравнивается с имеющимися в РП фактами;
• разрешение конфликтного набора — выбор одного из не-
скольких правил в том случае, если их можно применить одно-
временно;
• срабатывание правила — в случае совпадения образца
некоторого правила из базы правил с фактами, имеющимися в
рабочей памяти, происходит срабатывание правила, при этом
оно отмечается в БП;
• действие — изменение содержимого РП путем
добавления туда заключения сработавшего правила. Если в
132