Удк 519. 816 Способ представления термов в логике предикатов первого порядка. Алгоритм унификации

Вид материала

Документы

Содержание S. Рис. 1. Представление терма в виде размеченного ациклического орграфа составного объекта S Список литературы

Подобный материал:

• «Искусственный интеллект.», 86.69kb.
• 6. Исчисление предикатов и теории первого порядка, 101.56kb.
• Урок математики во 2-м классе  по теме: Порядок действий. Алгоритм, 63.65kb.
• Б. Д. Плющенков 1/2 года I. Общая теория дифференциального уравнения (нелинейного), 16.96kb.
• Концепция языка Пролог и сферы его применения. Процедурная и декларативная трактовка, 31.15kb.
• Удк 631. 816 Рижова К.І.,, 127.54kb.
• Удк 004. 89 Реализация системы логического вывода для логики первого порядка на базе, 68.27kb.
• 2. Лекция: Системы представления знаний, 171.88kb.
• Реляционные базы данных термины и определения, 203.51kb.
• Конспект лекций москва 2004 удк 519. 713(075)+519. 76(075) ббк 22. 18я7, 1805.53kb.

УДК 519.816

Способ представления термов в логике предикатов первого порядка. Алгоритм унификации

А.П. Раговский (anton_ragovskiy@rambler.ru)

Московский Государственный Университет Приборостроения и Информатики, Москва

Предложен способ представления термов в логике предикатов первого порядка и алгоритм унификации, использующий данное представление. Приведен результат работы алгоритма унификации.

Создание высокопроизводительных процедур доказательства теорем, способных эффективно решать задачи практической степени сложности в условиях экспоненциального роста пространства поиска, требует решения ряда задач. Первая задача относится к структурам представления термов и алгоритмам их обработки. Это связано с тем, что термы являются основной структурой обработки в процедурах вывода и их неэффективное представление может значительно ухудшить общую производительность процедур вывода. Вторая задача относится к разработке более производительного и эффективного алгоритма унификации, чем алгоритм, предложенный Дж. Робинсоном [Вагин и др., 2004].

В настоящее время в алгоритмах доказательства теорем, как правило, используются достаточно простые и экономные структуры представления термов, которые очень хорошо сочетаются и с процедурой дедуктивного вывода, и с процедурой унификации. Такими структурами часто являются ориентированные ациклические графы и плоские термы [Касьянов и др., 2003] [Christian, 1993]. Достоинством ациклических орграфов является реализация всевозможных операций просмотра термов в разных направлениях и манипулирования их частями. Главным их недостатком является усложнение работы с памятью, из-за того, что размер каждого узла в первую очередь зависит от количества потомков. Однако этого нельзя сказать о плоском представлении термов. Достоинством плоских термов является предоставление удобного способа прямого разбора терма и значительное упрощение работы с памятью, из-за фиксированной структуры.

При разработке эффективного и простого в использовании представления термов необходимо объединение достоинств вышеописанных структур. Для этого необходимо решить две основные задачи: определение основной структуры представления термов и расширение такой структуры для удобного хранения в памяти. В качестве основной структуры представления термов предлагается использование размеченных ациклических орграфов , формальное определение которых описывается с помощью составного объекта , при условии , где – множество меток, – множество натуральных чисел, – множество вершин, – начальная вершина, – функция разметок вершин, – множество упорядоченных связей, таких, что , [Касьянов и др., 2003] [Капитонова и др., 2004] [Андерсон, 2003] [Дистель, 2002].

Для удобного описания термов рассматриваются только инициальные составные объекты, т.е. объекты для любой вершины которых, , где – транзитивное замыкание отношения непосредственной достижимости. Каждая вершина составного объекта S порождает составной объект, начальной вершиной которого является она сама. Причем i-м аргументом составного объекта , порожденного вершиной v, при условии существования такой, что , является составной объект , порожденный вершиной .

Задача представления терма размеченным ациклическим орграфом составного объекта S дополняется префиксным способом прохождения вершин с расстановкой на ребрах порядковых номеров потомков заданного родителя. Для этого выполняются следующие действия:

1. исследуется корневая вершина терма ;
   
2. рассматривается самый левый аргумент вершины , который еще ни разу не рассматривался ;
   
3. помечается ребро функцией разметок ребер , при условии что , где – множество меток.
   

Пример 1. На рисунке 1 терм представлен размеченным ациклическим орграфом составного объекта S.



Рис. 1. Представление терма в виде размеченного ациклического орграфа составного объекта S

Таким образом, вершины орграфа хранят вспомогательную информацию: о функциональных символах, о позициях подтермов, о номере аргумента и помеченных ребрах, при прямом обходе. Причем, все висячие вершины, описывающие переменные или константные символы, располагаются на одном уровне. Они имеют путь на орграфе, который состоит из вершин орграфа вместе с пометками ребер, которые расположены вдоль этого пути. При этом любой путь рассматривается с корневой вершины , которая помечена символом самого терма. Благодаря такому отождествлению, данное представление терма можно задать в виде массива вершин с дополнительной информацией.

Рассмотрим терм, имеющий вид , где есть функциональный символ, а в качестве любой переменной или константы терма берется символ *. Тогда символ * имеет путь на орграфе, который можно сформулировать в виде строки , где есть пометка на ребре исходящая из заданного функционального символа. Этот путь имеет обозначение ПУТЬ_i(*), где i есть порядковый номер пути.

Пример 2. На рисунке 1 к переменной x₁ имеется несколько путей: ПУТЬ₁(x₁) := f1; ПУТЬ₂(x₁) := f2g1; ПУТЬ₃(x₁) := f4h1; ПУТЬ₄(x₁) := f6k1.

Для расширенного представления термов также используются две дополнительные операции: ТИП(*) – тип висячей вершины орграфа (переменная, обозначаемая символом v и константа, обозначаемая символом c), КВАНТОР(*) – в области действия какого квантора находится переменная.

Задавая пути, при прямом порядке обхода вершин орграфа, к символам переменных или констант в строковом виде, и обходя вершины слева направо и сверху вниз, можно получить некоторую последовательность, которая обязательно будет начинаться с корневой вершины. Такое множество строк удобнее всего записывать в виде некоторого массива.

Пример 3. На рисунке 2 приведено расширенное задание терма в виде массива, взятого из примера 1.



Рис. 2. Представление терма в виде массива

Для создания эффективных процедур дедуктивного вывода, решающих задачи практической степени сложности, необходимо решение задачи построения эффективного алгоритма унификации. При построении алгоритма унификации возникают такие проблемы, как проблема вычисления унификатора и предварительная проверка, являются ли термы унифицированными. Предложенная структура представления термов позволяет отойти от алгоритма унификации, предложенного Дж. Робинсоном [Вагин и др., 2004], и разбить этот алгоритм на две основные части. В первой части алгоритма, именуемой ТЕСТ (u, v: терм), проводится предварительная проверка, являются ли термы унифицированными, и, в случае положительного ответа на проверку унифицируемости конкретной позиции, создаются связи множества рассогласований подтермов.

Пример 4. На рисунке 3 представлен результат работы процедуры ТЕСТ (P(y, g(z), f(x)), P(a, x, f(g(y)))): 1) тип связи множества рассогласований {переменная/константа}; 2) тип связи – {переменная/функциональный символ}; 3) тип связи – {переменная/функциональный символ}.



Рис. 3. Представление задачи унификации пары термов с использованием предложенного способа представления термов

Во второй части алгоритма, именуемой УНИФИКАЦИЯ (u, v: терм), строится наиболее общий унификатор пары термов , которые успешно прошли предварительную проверку унифицируемости подтермов, используя информацию о множестве рассогласований, записанной в виде связей.

Пример 5. На рисунке 4 приведен результат работы алгоритма унификации, запрограммированного на Delphi в системе Borland Developer Studio 2006. Данный результат получен при запуске процедуры УНИФИКАЦИЯ (u, v: терм) на множестве пар термов мощностью равной 20.



Рис. 4. Результат работы последовательного алгоритма унификации

На оси абсцисс графика изображено общее количество операторов алгоритма унификации. При этом процедура ТЕСТ (u, v: терм) описывается 45 операторами. На оси ординат графика изображено среднее время, в миллисекундах, потраченное компьютером на обсчет одной пары термов.

Заключение

Рассматривается новый способ представления термов в логике предикатов первого порядка, включающий в себя основные достоинства ациклических орграфов и плоских термов. Данное представление явилось основой для создания удобного и высокоэффективного алгоритма унификации, что подтверждается приведенным графиком, показывающим результат работы алгоритма унификации.

Список литературы

[Андерсон, 2003] Андерсон Д.А. Дискретная математика и комбинаторика. – М.: Вильямс, 2003.

[Вагин и др., 2004] Вагин В.Н., Головина Е.Ю., Загорянская А.А., Фомина М.В Достоверный и правдоподобный вывод в интеллектуальных системах – М.: ФИЗМАТЛИТ, 2004.

[Дистель, 2002] Дистель Р. Теория графов. – Новосибирск, Изд-во Ин-та математики, 2002.

[Капитонова и др., 2004] Капитонова Ю.В., Кривой С.Л., Летичевский А.А., Луцкий Г.М. Лекции по дискретной математике – СПб.: БХВ-Петербург, 2004.

[Касьянов и др., 2003] Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003.

[Christian, 1993] Christian J. Flatterms, discrimination nets and fast term rewriting // Journal of Automated Reasoning. 1993. № 10 (1).