- •Содержание
- •Введение
- •Глава 1. Основные понятия
- •1.1. Понятие об искусственном интеллекте
- •1.1.1. Точка зрения Петрунина.
- •1.1.2. Интеллектуальные алгоритмы.
- •1.2. Основные направления исследования в области ии
- •1.3. Данные и знания. Основные модели представления знаний
- •Глава 2. Логические модели представления знаний
- •2.1. Логика высказываний
- •2.1.1. Булева алгебра.
- •2.1.2. Понятие о логическом следствии.
- •2.1.3. Метод резолюции в лв.
- •Имеет место теорема о полноте резолютивного вывода. Множество клозов противоречиво тогда и только тогда, когда из него методом резолюции можно вывести пустой клоз.
- •2.2. Логика предикатов первого порядка
- •2.2.1. Основные определения.
- •2.2.2. Метод резолюции в лппп.
- •2.2.3. Стратегии проведения резолюции.
- •2.2.4. Упорядоченный линейный вывод в лппп.
- •2.2.5.Применение поиска в пространстве состояний при реализации автоматизированного логического вывода.
- •2.2.6. Логический вывод на хорновских дизъюнктах.
- •Понятие экспертной системы и применение логического вывода при построении экспертных систем.
- •2.2.9. Запросы класса b.
- •2.2.10. Запросы класса c.
- •2.3. Понятие о нечетком выводе
- •2.4. Неклассические логики
- •2.4.1. Логики высших порядков.
- •2.4.2. Модальные логики.
- •2.4.3. Многозначные логики.
- •Глава 3. Продукционные модели представления знаний
- •3.1. Основные понятия
- •3.2. Стратегии управления
- •3.2.1. Поиск с возвратом.
- •3.2.2. Поиск в пространстве состояний.
- •3.3. Понятие о коммутативных системах продукций
- •3.4. Понятие о нечетком выводе на продукциях
- •3.5. Сравнение продукционных и логических моделей
- •Глава 4. Реляционные языки представления знаний
- •4.1. Основные элементы естественных языков
- •4.2. Дескрипторные модели
- •4.2.1. Понятие об ипс.
- •4.2.2. Линейная модель работы ипс.
- •4.2.3. Понятие о многоуровневом поиске.
- •4.2.4. Основные характеристики ипс.
- •4.4. Синтагматические цепи
- •4.4.1. Понятие синтагматических цепей.
- •4.4.2. Фреймы.
- •4.5. Сетевые модели представления знаний
- •4.5.1. Понятие семантической сети.
- •4.5.2. Структура интеллектуальной системы доступа к данным на основе семантической сети.
- •4.5.3. Задача поиска кратчайшего обхода образца в семантической сети.
- •4.5.4. Понятие о логическом выводе на семантических сетях.
- •Глава 5. Нейронные сети
- •5.1. Параллели из биологии
- •5.2. Базовая искусственная модель
- •5.3. Применение нейронных сетей
- •5.4. Обучение сети
- •Глава 6. Организация диалога с эвм на естественном языке
- •6.1. Элементы теории формальных языков
- •6.2. Обратная польская запись
- •6.3. Недостатки применения аппарата формальных грамматик
- •6.4. Элементы семиотики
- •6.5. Модель непосредственных составляющих
- •6.6. Многозначность в естественных языках
- •6.7. Расширенные сети переходов
- •6.8. Глубинные (семантические) падежи
- •Глава 7. Логическое программирование на языке пролог
- •7.1. Основные понятия в языке Пролог
- •7.2. Пакет Turbo Prolog
- •7.3. Структура программы
- •7.4. Поиск решений
- •7.5. Механизм отката
- •7.6. Операторы. Декларативный и процедурный смысл программы
- •7.7. Повторение и рекурсия
- •7.8. Повторение и откат
- •7.8.1. Метод отката после неудачи (опн).
- •7.8.2. Метод отсечения и отката (оо).
- •7.8.3. Метод повтора, определенный пользователем.
- •7.9. Методы организации рекурсии
- •7.10. Отладка программы и обнаружение ошибок
- •7.11. Графика в Turbo Prolog’е
- •7.11.1 Создание меню.
- •7.11.2. Создание графического режима.
- •7.11.3. Черепашья графика
- •7.12. Списки и их использование
- •7.12.1. Использование списка.
- •7.12.2. Поиск элементов в списке.
- •7.12.3. Создание нового списка путем слияния двух списков
- •7.12.3. Разделение на два списка.
- •7.13. Сортировки
- •7.13.1. Наивная сортировка.
- •7.13.2. Сортировка включением.
- •7.13.3. Метод «пузырька».
- •7.13.4. Быстрая сортировка.
- •7.14. Компоновка данных из базы в список
- •7.15. Работа с символами и строками
- •7.16. Специальные строки
- •7.17. Работа с файлами
- •7.18. Создание динамических баз данных
- •7.19. Библиотеки Turbo Prolog’а
- •7.19. Модульное программирование
- •7.20. Решение задачи о волке, козе и капусте
- •Глава 8. Введение в язык лисп
- •8.1. Основные особенности языка Лисп
- •8.2. Понятия языка Лисп
- •8.2.1 Атомы и списки.
- •8.2.2 . Внутреннее представление списка.
- •8.2.3 .Написание программы на Лиспе.
- •8.2.4. Определение функций.
- •8.2.5. Рекурсия и итерация.
- •В) maplist. Эта функция действует подобно mapcar, но действия осуществляет не над элементами списка, а над последовательными cdr этого списка.
- •8.2.6 . Функции интерпретации выражения.
- •8.2.7. Макросредства.
- •8.2.8. Функции ввода-вывода.
- •Список используемых источников
- •Перечень используемых сокращений
2.2.2. Метод резолюции в лппп.
Литеры L1 и L2 называются контрарными, если они являются отрицанием друг друга c точностью до унификации (то есть одна из литер изначально является отрицанием другой или ее можно таковой сделать с помощью подстановки).
Примечание. Формальное определение подстановки будет приведено ниже.
Бинарной резольвентой клозов С1 и С2, содержащих контрарные литеры L1 и L2 назовается клоз C, полученный следующим образом:
С={C1\L1}{C2\L2}
Примечание. Очевидно, что данное определение аналогично соответствующему определению в логике высказываний.
Примеры.
//примеры - без подстановки и с подстановкой (6)
P (x) Q (x, y) P(x) R(z) Q(x, y) R (z) |
P (x) Q (x, y) P(a) R (z) {a/x} Q(a, y) R (z) |
Доказано, что бинарная резольвента является логическим следствием.
В отличии от ЛВ, в ЛППП различают понятия резольвенты и бинарной резольвенты. Для того, чтобы определить понятие резольвенты необходимо рассмотреть подстановки.
Множество вида /подстановка (7)/ {ti/xi, … tn/xn}, где ti – термы, а xi – переменные называется подстановкой термов ti вместо переменных xi.
Если E – клоз, а Θ – подстановка, то EΘ – подстановочный частный случай, получаемый вследствие замены переменных xi на термы ti.
Пример.
//пример (8)
P (x) Q (f (x), b, y)
{a/x, c/y}
P (a) Q (f (a), b, c)
Примечание. Подстановка действительно приводит к переходу от более общего случая к частному и таким образом обеспечивает сохранение противоречивости.
Пусть даны 2 подстановки Θ и Ω. Применим подстановку Θ, а затем подстановку Ω. Тогда будем говорить, что применили композицию подстановок ΩΘ.
Подстановка Θ называется унификатором множества выражений {E1,..,En}, если E1Θ =E2Θ =….=EnΘ.
Подстановка Ω - есть наиболее общий унификатор множества выражений {E1,…,Ek}, если любой унификатор это множества выражений Θ можно получить путем композиции Ω с некоторой подстановкой Ψ. (Θ= ΩΨ).
П. С – дизъюнкт, а Θ - наиболее общий унификатор двух и более его литер, тогда СΘ называется склейкой дизъюнкта С.
Пример.
//пример склейки (9)
P (x) Q (f(x), b, y) P (a)
{a/x)
P (a) Q (f(x), b, y)
Резольвентами дизъюнктов С1 и С2, содержащих контрарные литеры L1 и L2 называются бинарные резольвенты:
-
клозов С1 и С2;
-
любой склейки клоза C1 и клоза С2;
-
клоза С1 и любой склейки клоза С2;
-
любых склеек клоза С1 и С2
Последовательность получения резольвент из множества клозов, в результате которой получают пустой клоз, называется резолютивным выводом в ЛППП.
Примечание. Фактически, вывод сводится к последовательности вычисления бинарных резольвент и склеек.
Пример.
Аксиома 1. Мао Цзедун – человек
Аксиома 2. Все люди смертны.
Теорема. Мао Цзедун – смертен.
//пример формализации и вывода (10)
Вводим предикаты:
C (x) – x - человек
S (x) – x - смертен
Аксиома 1 C (Мао)
Аксиома 2 [C (x) → S (x)] =
Теорема S (Мао)
С (Мао) S (Мао)
С (x) S (x) {Мао / x}
S (Мао) S (Мао)
Здесь также справедлива теорема о полноте резолютивного вывода. Множество клозов S противоречиво, если и только если существует резолютивный вывод пустого клоза из S.
Очевидно, что для того чтобы проверить противоречиво ли множество клозов, следует перебрать множество попыток провести резолюции. Таким образом, строится дерево резолюций. Способ построения такого дерева фактически является стратегией проведения резолюции.
Формальный алгоритм незначительно отличается от имеющегося в ЛВ.
ВХОД: S – входное множество клозов.
ВЫХОД: OK – удается получить пустой клоз, NO – не удается.
M:=S; // - M-текущее множество клозов.
while M do
if not Choose (M, C1, C2, p1, p2) then return(NO);
N:=R(M, C1, C2, p1, p2); // - вычисление резольвенты.
M:=M N; // - пополнение текущего множества.
end
return (OK); //получен пустой клоз
Примечание. Результат функции R здесь множество возможных резольвент клозов С1 и С2, содержащих контрарные литеры р1 и р2.