- •Глава 1. Основные определения, история проблемы,
- •Глава 2 Онтологическая инженерия описания предметной области ……50
- •Глава 3. Представление и вывод знаний в системах искусственного интеллекта на основе логических моделей. 65
- •Глава 4 Представление и вывод знаний в системах искусственного интеллекта на основе семантических сетей 98
- •Контрольные вопросы и задание 110
- •Глава 5. Представление и вывод знаний в системах искусственного интеллекта на основе фреймовых моделей. 111
- •Глава 6. Представление и вывод знаний в системах искусственного интеллекта на основе продукционных моделей. 118
- •Глава 7. Представление и вывод неопределённых знаний в системах искусственного интеллекта. 132
- •Глава 1. Основные определения, история проблемы, современные направления развития.
- •Основные определения искусственного интеллекта.
- •Лекция 1
- •1.2. Тест Тьюринга
- •Науки, лежащие в основе искусственного интеллекта
- •Вычислительная техника (период с 1940 года по настоящее время)
- •История искусственного интеллекта.
- •Рождение искусственного интеллекта (1956 год)
- •Ранний энтузиазм, большие ожидания (период с 1952 года по 1969 год)
- •Столкновение с реальностью (период с 1966 года по 1973 год)
- •Лекция 2
- •Основные современные направления развития искусственного интеллекта
- •1.6. Основные понятия о знаниях.
- •1.7. Выводы по 1-ой главе:
- •Контрольные вопросы и задание
- •Лекция 3
- •Глава 2 Онтологическая инженерия описания предметной области.
- •2.1. Понятие онтологии.
- •2.2. Теория множеств - математический аппарат описания онтологии.
- •2.2.1. Основные понятия и определения.
- •Лекция 4
- •2.2.2.Операции над множествами
- •2.2.3. Декартово произведение множеств
- •2.2.4. Отношения и их свойства.
- •2.3. Предметы, свойства и отношения предметной области.
- •Лекция 5
- •2.4. Понятие цели
- •2.5. Методика решения задач.
- •2.6. Понятие модели.
- •2.7. Методика построения онтологии.
- •2.8. Выводы по 2-ой главе.
- •2.9. Контрольные вопросы и задание.
- •Лекция 6
- •Глава3 Представление и вывод знаний в системах искусственного интеллекта на основе логических моделей.
- •3.1. Основы математической логики
- •3.1.1. Классификация и определение логик, алгебр, исчислений, теорий.
- •3.1.2.Традиционная логика.
- •Лекция 7
- •3.1.3.Логика, алгебра и исчисление высказываний.
- •3.1.4. Логика, алгебра и исчисление предикатов
- •Лекция 8
- •3.1.5. Формальные методы вывода решений в аксиоматических теориях.
- •3.1.6. Приведение формул исчисления предикатов к дизъюнктам Хорна.
- •4. Исключение кванторов существования.
- •3.2. Логическая модель представления знаний.
- •3.3. Вывод в системах искусственного интеллекта с логическим представлением знаний.
- •3.3.1. Правило резолюции.
- •Стратегия полного перебора.
- •Стратегия опорного множества.
- •3. Линейная по входу стратегия.
- •3.4. Выводы по 3-ой главе.
- •Контрольные вопросы и задание.
- •Лекция 9
- •Глава 4 Представление и вывод знаний в системах искусственного
- •Элементы теории графов
- •4.1.1. Способы задания графов.
- •1. Графический
- •2. С помощью матрицы инцидентности.
- •3. С помощью списка ребер.
- •4. С помощью матрицы смежности.
- •4.1.2. Задачи, решаемые с помощью графов.
- •Задача поиска наикратчайшего пути на графе.
- •Транспортная задача.
- •Задача о назначении (задача коммивояжера).
- •Задача о назначении работ.
- •Лекция 10
- •4.2. Представления знаний в виде семантических сетей.
- •4.3. Вывод в системах искусственного интеллекта с представлением знаний в виде семантических сетей.
- •Выводы по 4-ой главе.
- •Контрольные вопросы и задание.
- •Лекция 11
- •Глава 5. Представление и вывод знаний в системах искусственного интеллекта на основе фреймовых моделей.
- •5.1. Представления знаний в виде фреймов
- •5.2. Вывод в системах искусственного интеллекта с фреймовым
- •Выводы по 5-ой главе.
- •5.4. Контрольные вопросы и задание.
- •Лекция 12
- •Глава 6. Представление и вывод знаний в системах искусственного интеллекта на основе продукционных моделей.
- •Представление знаний в виде в виде системы продукций.
- •6.2. Продукционные системы
- •6.3. Прямой и обратный вывод в продукционных системах.
- •Лекция 13
- •6.4. Пример работы продукционной системы.
- •6.5. Выводы по 6-ой главе
- •6.6. Контрольные вопросы и задание
- •Лекция 14
- •Глава 7. Представление и вывод неопределённых знаний в системах искусственного интеллекта
- •Представление и вывод при нечётких знаниях.
- •7.1.1. Определение нечёткого множества.
- •7.1.3. Нечёткие отношения.
- •7.1.2. Операции над нечёткими множествами.
- •Лекция 15
- •Формальные методы вывода решений в нечёткой логике.
- •Лекция 16
- •7.2.Представление и вывод при неполных знаниях.
- •Вероятностный подход к представлению неопределённых знаний.
- •Определения и виды вероятности
- •Аксиомы вероятностей
- •Лекция 17
- •7.2.4. Формальные методы вывода решений при вероятностном подходе.
- •7.2.5. Правило Байеса и его использование.
- •Байесовская сеть представления и вывода вероятностных знаний.
- •Другие способы представления и вывода неопределённых знаний.
- •Выводы по 7-ой главе
- •7.5. Контрольные вопросы и задание.
- •Литература
Лекция 8
3.1.5. Формальные методы вывода решений в аксиоматических теориях.
Под аксиоматической теорией, построенной на основе данной системы аксиом, понимается совокупность всех теорем, доказываемых исходя из этой системы аксиом. Аксиоматическая теория считается определённой, если выполнены следующие
условия:
1.Задан язык теории.
2.Опрелено понятие формулы в этой теории.
3.Выделено некоторое множество формул, называемых аксиомами.
4.Определены правила вывода в этой теории.
Основным вопросом практического использования любой теории является проблема доказательства теорем данной теории или, что одно и тоже, определения принадлежности правильно построенной формулы (ППФ) в этой теории, выражающей доказуемую теорему, системе аксиом теории. В исчислении высказываний эта задача сводится к доказательству того, что ППФ утверждения является доказуемой формулой. Следует отметить, что доказуемая формула, принадлежащая множеству аксиом, является тождественно-истинной формулой. Исходя из этого замечания и определения формулы, доказуемой в данном исчислении можно предложить два способа доказательства доказуемости формулы в исчислении высказываний: семантический и синтаксический. Первый основан на семантике (истинностных значениях) формулы, а второй - на синтаксических преобразованиях аксиом.
Например: доказать что выводима. Рассмотрим два способа доказательства семантический и синтаксический.
Семантический способ.
Обозначим = и =, тогда исходная формула примет вид: . Составим таблицу истинности для этой формулы.
Таблица 10
|
|
|
|
|
1 0 1 0 |
1 1 0 0 |
0 0 0 1 |
0 0 0 1 |
1 1 1 1 |
Таким образом, при всех комбинациях значений переменных формула принимает только значение истина, следовательно, эта формула является тождественно-истинной и доказуемой в исчислении высказываний.
Синтаксический способ.
Возьмём аксиому 3 II-ой группы исчисления высказываний и заменим на , а на получим: также выводимую формулу. Выполним подстановку
получим:
Обозначим: ; ;
- докажем что эти формулы доказуемы. Выполним подстановку
1 акс.IV гр
получим: заметим, что условием этой импликации является 1-ая аксиома III-ей группы и по правилу заключения формула доказуема. Заменим в формуле на , а на получим, что формула также доказуема. Применяя правило заключения к доказуемой формуле и помня что доказуема, получим, что также доказуема. Применяя правило заключения к формуле и исходя из доказуемости , получим доказуемость исходной формулы. В этом примере синтаксический способ доказательства требует некоторых навыков в использовании правил вывода и аксиом, а также кажется более трудоёмким и сложным чем семантический, хотя на самом деле всё определяется данным примером. Рассмотрим другой пример.
По подозрению в совершённом преступлении задержали Брауна, Джона и Смита. Один из них был уважаемым в городе стариком, другой был малоизвестным чиновником, третий - известным мошенником. В процессе следствия старик говорил правду, мошенник лгал, а третий задержанный в одном случае говорил правду, а в другом ложь.
Браун: “ Я совершил это. Джон не виноват.”
Джон: “ Браун не виноват. Преступление совершил Смит”.
Смит: “Я не виноват, виновен Браун”.
Определите имя старика, мошенника и чиновника и кто из них виноват, если известно что преступник один.
Семантический способ решения.
Обозначим высказывания: Б - виноват Браун, Д - виноват Джон, С - виноват Смит. Тогда утверждения, высказанные задержанными примут вид:
1. БД; 2. БС; 3. БС и истинной должна быть общая дизъюнкция всех утверждений: А=(БД) (БС) ( БС).
Составим таблицу истинности для всех вариантов высказываний, утверждений и общей дизъюнкции.
Таблица 11
номер вариа-нта |
Б |
Д |
С
|
БД
|
БС
|
БС
|
А |
1 2 3 4 5 6 7 8 |
1 1 1 1 0 0 0 0 |
1 1 0 0 1 1 0 0 |
1 0 1 0 1 0 1 0 |
0 0 1 1 0 0 0 0 |
0 0 0 0 1 0 1 0 |
0 1 0 1 0 0 0 0 |
0 1 1 1 1 0 1 0 |
Проведём анализ вариантов, когда А-истинно.
Варианты: 2,3 и 5 отпадают, т.к. в этих случаях существует одновременно два преступника, а это противоречит условию задачи (“преступник один”).
Вариант 4 также отпадает, т.к. в этом случае два утверждения, высказанные задержанными одновременно истинны, а это противоречит условию (“правду говорит только один старик”).
Отсюда следует, что верным остаётся 7-ой вариант, соответствующий всем условиям задачи и следовательно преступник Смит. В этом варианте 2-ое утверждение, высказанное задержанным Джоном является истинным, следовательно Джон-старик(“старик говорил правду”) и остаётся утверждать, что чиновник-Браун.
Синтаксический способ.
Рассмотрим данную задачу как теорию предметной области, которой соответствует набор аксиом и в которой верны правила вывода. В качестве аксиом теории выберем утверждения, высказанные задержанными:
1. БД;
2. БС;
3. БС.
По условиям задачи только одно утверждение является истинным (“правду говорил старик”) и, следовательно, только один из вариантов утверждений является аксиомой теории. Рассмотрим предположение, что первое утверждение является аксиомой, тогда третье утверждение тоже правда, т.к. преступник был один, если предположить, что третье утверждение – аксиома, то по этой же причине первое утверждение тоже правда, а это противоречит условиям задачи (“правду говорил только один”). Следовательно, единственно верной аксиомой этой теории является второе утверждение, которое высказал Джон, о том, что Браун не виноват, а преступление совершил Смит. Таким образом, получаем следующее решение задачи: Джон-старик, Смит-преступник, Браун-чиновник. В данном примере синтаксический способ решения задачи кажется более простым и лёгким, таким образом, как уже отмечалось выше, трудоёмкость способа определяется задачей.
В случае исчисления предикатов необходимо доказать, что ППФ доказуемой теоремы является общезначимой и здесь возникают проблемы, связанные с возможным существованием в ППФ кванторных операций, определённых на бесконечных множествах переменных. В этом случае семантический способ неприемлем, в принципе (невозможно составить таблицу истинности для бесконечного множества переменных), и остаётся использовать синтаксический способ.
Синтаксический способ для исчисления предикатов.
Пример: Доказать, что формула xxx xxx является общезначимой.
Используя равносильности алгебры высказываний и алгебры
предикатов проведём следующие преобразования этой формулы:
xxxxxxxx xxxxxxx xxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxxxxxxxxxx
истина истина истина. Исходная формула общезначима.
Таким образом, для теорий, построенных как на исчислении высказываний, так и на исчислении предикатов существует принципиальная возможность доказательства теорем вычислительным способом.
В связи с этим возникает задача построения формальной процедуры (алгоритма) определения к какому классу относится данная формула? Эта задача носит название проблемы разрешимости. Очевидно, проблема разрешимости алгебры высказываний разрешима, т.к. для каждой формулы алгебры логики может быть формально построена таблица истинности, которая и даст ответ на поставленный вопрос. Проблема разрешимости в алгебре предикатов ставится также, как в алгебре высказываний: существуют ли алгоритмы, позволяющие для любой формулы алгебры предикатов установить к какому классу она относится, то есть, является ли общезначимой, или выполнимой, или тождественно-ложной. Отметим, что в отличие от алгебры высказываний здесь не применим метод перебора всех вариантов значений переменных, входящих в формулу, так как таких вариантов может быть бесконечное множество.
В 1936г. американский математик А.Черч доказал, что проблема разрешимости алгебры предикатов в общем виде алгоритмически не разрешима, то есть не существует алгоритма, который бы позволил установить к какому классу формул относится любая формула алгебры предикатов. В этом смысле говорят о неразрешимости исчисления предикатов. Вместе с тем доказано (Эрбран, 1930г.), что исчисление предикатов первого порядка полуразрешимо, т.е. доказано существование процедуры подтверждения выводимости некоторой ППФ из заданногомножества формул 1n, если известно, что эта ППФ является теоремой. Основной процедурой, позволяющей реализовать эту полуразрешимость, является правило резолюции Дж. Робинсона (1965 г.), имеющее различные модификации.
Теории первого порядка отличаются от теорий высших порядков тем, что не допускают в своём изложении предикаты, которые имеют в качестве возможных значений своих аргументов другие предикаты и функции. Кроме того, они не допускают кванторные операции по предикатам или функциям. Процесс доказательства теоремы некоторой теории или общезначимости ППФ для данной ситемы аксиом с использованием правила резолюций основан на опровержении отрицания этой ППФ. В этом случае к системе аксиом теории добавляется отрицание доказуемой ППФ и с помощью правила резолюций доказывается противоречивость новой системы аксиом. Такая схема построения доказательства теоремы называется процедурой опровержения. Ещё одним ограничением правила резолюций является то, что этот метод применим к аксиомам теории и доказуемой теореме только тогда, когда выражающие их формулы записаны в виде дизъюнкт (фраз, предложений) Хорна. Дизъюнкта Хорна это формула, состоящая из дизъюнкций одной позитивной и остальных негативных элементарных формул, т.е формула вида: 12n Аксиомы теории, выраженные в виде дизъюнкт Хорна имеют вполне объяснимую интерпретацию.
Преобразуем общую форму дизъюнкта Хорна на основании закона равносильности к виду 12n, получим импликацию, в виде которой обычно записывают закон предметной области. Здесь из истинности посылок и самой импликации (формула является аксиомой теории) следует истинность заключения (обратное неверно: из ложности посылок не следует ложность заключения). Набор законов или система аксиом теории образуется путём объединения знаком конъюнкция отдельных законов или аксиом теории. Однако, можно показать, что любую ППФ исчисления предикатов можно по определённой методике привести к дизъюнктам Хорна, объединённых знаком конъюнкции.
