- •Содержание
- •Введение
- •Глава 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.6. Логический вывод на хорновских дизъюнктах.
Клозом Хорна (дизъюнктом Хорна, хорновским дизъюнктом) называется выражение вида (A1….An)->(B1…Bm), где n>=0, 0<=m<=1. Ai, Bj – литеры.
Клозы Хорна действительно являются дизъюнктами, так как возможны следующие случаи:
-
m=0, n=0 - имеем пустой клоз.
-
m=0, n>0 – A1….An. Клоз Хорна такого вида называется теоремой (и используется для формулирования теорем). А так как в выводе участвуют теоремы, а их отрицания, то имеем A1…An.
-
m=1, n=0. Такой клоз Хорна называют фактом. Факт состоит из одной литеры.
-
m=1, n>0 – аксиома. A1….An->B=A1 … AnB.
Задача. Методом резолюции получить пустой клоз.
Доказательство начинается с теоремы (предполагается, что она единственная). Далее пытаемся найти факт или аксиому, с которой можно провести резолюцию (непосредственно или посредством подстановки).
//здесь расписать формально шаги резолюции (16)
Пусть имеем список целей:
C1 , … , Ci-1, Ci , Ci+1 , … , Ck
Его отрицание является дизъюнктом:
C1 … Ci-1 C i Ci+1 … Ck
А) Если факт B = Ci , то:
C1 … Ci-1 Ci Ci+1 … Ck
B
C1 … Ci-1 Ci+1 … Ck
Т.е. получили список:
C1 … , C i-1 , C i+1, … , Ck
Фактически мы исключили цель, имеющую подтверждающий факт.
В) Если аксиома (A1 … An) B, где:
B - Ci
Имеем:
С1 … Ci-1 Ci Ci+1 … Ck
A1 … Ak B
C1 … Ci-1 A1 … An Ci+1 … Ck
таким образом происходит подмена доказываемой цели на утверждения, стоящие в левой части:
C1 , …, C i-1 , A1 , …, An , Ci+1 , … , Ck
Далее, процесс продолжается и так до тех пор, пока мы не получим пустой клоз или не будет возможности применить ни аксиому, ни факт. Заметим, что боковой клоз всегда выбирается из входного множества, что увеличивает скорость вывода. Но этот метод имеет крупный недостаток. Он в отличие от OL-вывода не обладает свойством полноты, и может зацикливать в довольно тривиальных случаях.
Подход, основанный на клозах Хорна, лег в основу концепции логического (рекурсивно-логического) программирования, которая реализована в языке программирования Пролог.
Язык Пролог удобно применять для решения задач, предполагающих автоматизацию процесса логического вывода, так как компилятор Пролога по сути является системой автоматизированного логического вывода. К таковым задачам относится проектирование экспертных систем, сюда же можно отнести и автоматические дифференциаторы (процесс дифференцирования функция легко описывается на языке предикатов) и т.д.
Основными элементом программы на Прологе является предикат. Понятие предиката несколько расширено по сравнению с ЛППП. Прологовский предикат также имеет значение «истина» или «ложь» также может содержать в качестве аргументов константы, переменные или функции. В тоже время пролог-предикат несет в себе и процедурную нагрузку, т.е. выполняет какие-либо действия. Более того, в Прологе в виде предикатов оформлены все стандартные подпрограммы.