Теория LP-структур для построения и исследования моделей знаний продукционного типа

• Автор: Махортов, Сергей Дмитриевич
• Шифр специальности: 05.13.17
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Воронеж
• Количество страниц: 307 с. + Прил. ( 308-557 с.)

Оглавление
Введение.

Обзор содержания.

Глава 1. Задачи, приводящие к ЬРструктурам

1.1.0 многоуровневом прораммировании.

1.2. Основная терминология решаемых задач.

1.3. Стандартная продукционная система

1.4. Расширенная продукционная система

1.5. Продукционная система первого порядка

1.6. Условная эквациональная теория.

1.7. Модель иерархии типов

1.8. Продукционная модель императивных алгоритмов.
Глава 2. Общая теория ЬРструктур
2.1. Порождающие множества в продукционных системах.
2.1.1. Основные определения и обозначения.
2.1.2. Эквивалентные преобразования баз знаний
2.1.3. Построение минимальных порождающих множеств
2.1.4. Корректность и верификация баз знаний
2.2. Дополнительные сведения о бинарных отношениях и решетках
2.3. Понятие ЬРструктуры. Логические отношения.
2.4. Эквивалентные преобразования.
2.5. Логическая редукция
2.6. Логические уравнения на решетках.
Глава 3. ЬРструктуры на полных решетках
3.1. Определение ЬРструктуры на полной решетке
3.2. Эквивалентные преобразования.
3.3. Логическая редукция
3.4. Логические уравнения на полных решетках.
Глава 4. Расширенные модели.
4.1. структуры нулевого порядка.
4.1.1. Логическое замыкание и эквивалентные преобразования
4.1.2. Структура логических связей
4.1.3. Логическая редукция
4.2. сгруктуры первого порядка.
4.2.1. Логическое замыкание и эквивалентные преобразования
4.2.2. Структура логических связей.
4.2.3. Логическая редукция
4.3. Эквациональные структуры.
4.3.1. Модель условной эквациональной теории
4.3.2. Логическое замыкание и эквивалентные преобразования
4.3.3. Структура логических связей.
4.3.4. Логическая редукция.
4.3.5. Некоторые итоги
Глава 5. Немонотонные структуры
5.1. структуры на решетках типов
5.1.1. Определение основных понятий
5.1.2. Свойства дистрибутивных троек и совместимых пар.
5.1.3. Логическое замыкание и эквивалентные преобразования
5.1.4. Структура логических связей и редукция
5.1.5. Алгоритмические вопросы.
5.2. структуры на некоммутативных решетках
5.2.1. Некоммутативные решетки.
5.2.2. Некоммутативные решетки с расширенным множеством X
5.2.3. Немонотонные логические отношения.
5.2.4. О продукционной модели императивных алгоритмов
Глава 6. Компьютерная реализация и применение
ЬРсгруктур
6.1. Общие принципы реализации.
6.2. Кодирование ЬРструктур.
6.3. Класс ЬРБткДиге.
6.4. ЬРЕхрег интегрированная среда логического программирования
6.4.1. Структура базы знаний.
6.4.2. Синтаксис базы знаний.
6.4.3. Структура пакета ЬРЕхреЛ и принципы реализации
6.4.4. Релевантный ЬРвывод
6.4.5. Функциональные возможности и интерфейс пользователя
6.4.6. Исследование и оптимизация тестовых баз знаний
6.5. Моделирование математических знаний.
Заключение
Приложение А. Демонстрационные базы знаний
А.1. Здоровье
А.2. Электрики.
.З Закон распределения
Приложение В. Теория весовых псевдодифференциальных операторов
.1. Весовые пространства обобщенных функций.
В.2. Весовые пссвдодифференциальные операторы
В.З. Вырождающиеся эллиптические псевдодифференциальные
операторы.
В.4. Вырождающиеся операторы с однородными символами
Литература


Обзор имеющихся подходов к данному вопросу содержится в []. Воспользуемся алгебраизацией кванторов, предложенной в [6], поскольку она естественным образом расширяет рассматриваемую продукционную логику на решетке и содержит достаточные возможности для решения поставленных задач. Согласно этой теории, кванторы общности и существования соответственно моделируются в общем случае бесконечноместными операциями пересечения и объединения. Пусть Р(х) — предикат со свободной переменной х, интерпретируемый в некоторой предметной области X. Его можно представить совокупностью элементов решетки Линденбаума-Тарского, соответствующих формуле Р(х) при различных значениях хеХ. Тогда, в силу свойств логических операций, выражение VxP(x) алгебраически представляется операцией пересечения всех элементов решетки, соответствующих Р(х). Аналогично формула ЗхР(х) может быть представлена объединением всех элементов решетки, порожденных предикатом Р(х). Как уже отмечалось выше, не каждая решетка допускает выполнение бесконечноместных операций. В полной решетке для любого подмножества элементов (конечного или бесконечного) молено определить (многоместное) пересечение и объединение. Л Р(х) и V Р(х). Изложенные соображения открывают возможности формальных исследований, преобразований и автоматической оптимизации продукционных баз знаний с логикой первого порядка. В качестве иллюстрации рассмотрим пример из приложения В данной работы, относящийся к области исклассических уравнений с частными производными. В этом приложении в коэффициентах символов псевдодифференциальных операторов используется «весовая» вещественная функция а, существенно влияющая на разрешимость уравнений с этими операторами. В основе результатов, представленных в приложении В, лежат следующие два условия на данную функцию. C*(. M :«еС,м(Л). Для построения соответствующей LP-структуры введем обозначения логических формул. Пусть ^,(/), /? Тогда при каждом значении переменной / имеем элементы решетки /{,(/), /«(О и каждой паре значений сопоставляем элемент Р(/,с). Условию 1 соответствует элемент Pu{t>c). М раз непрерывно дифференцируема в точке /». Алгебраическая запись условия 2 будет выглядеть как Ap7I(/)aV Л P„(t,M). Еще одним из возможных направлений. ЬР-структур является построение и исследование моделей эквациональных теорий и систем переписывания термов (СПТ) [, ]. Важными задачами, связанными с СПТ, являются эквивалентные преобразования и оптимизация их множеств правил. В то время как для обычных СПТ подобные вопросы уже рассматривались в ряде работ [, , ], для условных СПТ они, по-видимому, еще остаются открытыми. Этот факт можно объяснить более сложной структурой правил условных СПТ. Для обычных систем задача минимизации множества правил в конечном счете сводится к транзитивной редукции некоторого бинарного отношения («элиминация транзитивности»). Для условных систем, как и в предыдущих разделах, можно говорить о более сложной задаче нахождения логической редукции. При определении системы переписывания термов отправной точкой обычно является эквациональная теория, множество правил которой состоит из равенств. Совокупность правил переписывания получается путем «ориентации» равенств и, возможно, их пополнения для достижения свойства конфлюэнтносги. Аналогичный подход используется и для условных СПТ []. Поскольку обычно именно эквациональная теория является критерием эквивалентности систем переписывания, исследование в этом плане условных СПТ можно начать с рассмотрения эквивалентности условных эквациональных теорий. Для дальнейшего изложения потребуется ряд базовых определений, связанных с термами []. Пусть ? V — множество переменных; 2„, « = 0,1,-. Ея и е Г(2), то e Г(2). Отображение 7'(2) называется подстановкой. Г(2) и f = /(/„. Эквациональная теория определяется парой (2,? T(Z)). В рамках этой теории определяется понятие выводимости равенства s = t из Е ((2,? ТО (2,? Предположим, что эквациональная теория (аналогично []) содержит набор позитивно-условных правил вида si=tl,.