Метод управления концептуальными моделями данных в системе представления знаний тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

РГ5 ОД

3 :1 г ' '

МАМЕДНИЯЗОВА Натали Сердаровна

МЕТОД УПРАВЛЕНИЯ КОНЦЕПТУАЛЬНЫМИ МОДЕЛЯМИ ДАННЫХ В СИСТЕМЕ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ

Специальность: 01.01.09 — математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 2000

Работа выполнена в Санкт-Петербургском государственном университете.

Научный руководитель: доктор физико-математических наук,

профессор Тузов В.А.

Официальные оппоненты: доктор физико-математических наук,

профессор Братчиков И.Л. кандидат физико-математических наук, Кривцов А.Н.

Ведущая организация: Экономико-математический институт РАН

Защита диссертации состоится " /-солВь^и 2000 г. в /6 часов на заседании диссертационного совета К.О63.57Аё по защите диссертаций на соискание ученой степени кандидата наук в Санкт-Петербургском государственном университете по адресу: Санкт-Петербург, Васильевский остров, 10 линия, дом 33, ауд. 66.

С диссертацией можно ознакомиться в научной библиотеке им. А.М.Горького Санкт-Петербургского государственного университета.

Автореферат разослан

„20« о^тлЪп^ 2000 г.

Ученый секретарь диссертационного совета.

д.ф.-м.н.

Горьковой В.Ф.

Общая характеристика работы

Актуальность темы. Среди различных моделей, лежащих в основе современных систем представления знаний, можно выделить два класса, получившие наиболее широкое распространение: класс дедуктивных и класс концептуальных моделей. Системы, основанные на дедуктивных моделях, обычно применяются для представления знаний дедуктивной природы, когда связи между утверждениями удобно выражать каузальными конструкциями "если-то". В тех же случаях, когда система знаний о предметной области сводится к иерархии понятий, определению их свойств и наследованию свойств в рамках иерархии, удобно строить ее на основе концептуальных моделей данных. На практике описание предметной области всегда содержит и иерархически связанные понятия и каузальные связи между утверждениями о понятиях, поэтому исследование методов построения гибридных систем, интегрирующих обе модели, является актуальной задачей. В последние годы гибридные модели приобретают особое значение как основа вычислительной онтологии— информационного ресурса, предназначенного для представления иерархической "модели мира" и использования такой модели в интеллектуальных информационных технологиях в качестве инструмента логического вывода. Типичными примерами вычислительных онтологии являются семантические словари естественных языков и базы знаний в различного рода гуманитарных исследованиях.

Цель и задачи исследования. Диссертация посвящена разработке методов логического вывода для гибридной системы представления знаний, комбинирующей средства описания иерархических отношений, свойственные языкам концептуального моделирования, и дедуктивные (пользовательские) правила, позволяющие осуществить логический вывод. Перед диссертантом были поставлены следующие задачи:

1. разработать алгоритм логического вывода на системе

пользовательских правил;

2. определить денотативную семантику отношений языка;

3. разработать и исследовать метод учета формальной семантики

в общей процедуре логического вывода, подтверждающего

истинность запроса к базе знаний.

Научная новизна работы.

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

Практическая значимость работы. Предлагаемый соискателем метод учета семантики отношени^формалъного языка, в процедуре логического вывода достаточно унивёрса5Ген, так как может быть применен для формального языка с любой гемантикой, допускающей преобразование в систему продукций. Предлагаемый метод гакже не зависит как от вида пользовательских правил, так и от используемого метода

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

Разработанные методы определения формальной семантики отношений и ее учета в процедуре логического вывода позволяют:

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

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

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

Апробация работы. Основные результаты диссертации были представлены на международном семинаре Диалог'2000 по компьютерной лингвистике и ее приложениям (Протвино, 2000г.)

Работа выполнялась в рамках проектов, поддержанных грантами РФФИ за 1996г. (96-06-80217) и 2000г. (00-06-80468).

По материалам диссертации опубликовано 4 печатные работы.

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

Содержание работы

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

Концептуальные модели данных предназначены прежде всего для представления иерархических связей между объектами. Основными элементами языка концептуального моделирования являются классы и экземпляры. Следовательно, универсум гибридной системы должен состоять из двух наборов обозначений: обозначений классов и экземпляров. Язык системы представления знаний должен содержать также некий набор типов отношений между объектами. Используя этот набор, мы можем зафиксировать различные факты отношений между объектами языка, среди которых можно выделить элементарные факты и неэлементарные. Отношения между экземплярами можем рассматривать как элементарные факты, а отношения между классами заключают в себе совокупность отношений между экземплярами этих классов, поэтому отношения между классами отнесем к неэлементарным фактам. Элементарные факты далее не трактуются и не выражаются через другие. Семантику неэлементарных фактов можно выразить в виде совокупности правил относительно элементарных фактов.

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

Основная идея предлагаемого в диссертации подхода заключается в следующем.

A. Каждому типу отношения можем сопоставить шаблон семантических правил. Используя этот шаблон, каждому неэлеменгарному отношению этого типа можно однозначно сопоставить совокупность семантических правил относительно элементарных отношений. Это значит, что семантические правила можно хранить в виде шаблонов по типам отношений в специально организованной семантической памяти. Отметим, что шаблоны являются элементом описания языка и инвариантны по отношению к конкретным описаниям предметной области.

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

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

1) Унифицируем предикат цели и следствия шаблона семантического правила.

2) Осуществляем вызов алгоритма Query, которому в качестве запроса передаем неэлеменгарный предикат, которому в семантической памяти сопоставлен указанный шаблон семантического правила.

3) Если алгоритм Query выдает в качестве ответа некоторую подстановку 0, это значит, что при применении 0 к указанному шаблону семантического правила получается семантическое правило, истинность которого установлена на основании фактов и пользовательских правил. Полученное семантическое правило можем применить для смены цели поиска.

В качестве практической предпосылки к решению поставленной задачи была использована система MAZE, разрабатываемая в СПб ЭМИ РАН. Формальный язык системы MAZE позволяет записать иерархические отношения между объектами, а также определить пользовательские правила, устанавливающие каузальную зависимость между отношениями. В базе знаний системы реализовано совместное хранение фактов и правил, записанных с использованием отношений формального языка. Факты и пользовательские правила, т.е. все, что пользователь желает зафиксировать в базе знаний, хранятся в концептуальной памяти системы. Единицей

хранения является терминаi — структура, в которой хранится вся информация об одном предикате отношения: тип отношения и значения его аргументов.

В первой главе диссертации определяется теоретико-множественная интерпретация синтаксических конструкций формального языка системы MAZE. Основными элементами формального языка являются классы, экземпляры и отношения между объектами. Class обозначает множество всех константных классов, a Obj— множество всех константных экземпляров базы знаний. Имена классов записываются прописными буквами, а имена экземпляров — строчными. Переменные, обозначенные прописными буквами X, Y, Z, определены на множестве понятий Class, а переменные, обозначенные строчными буквами х, у, z — на множестве экземпляров Obj.

Введем функцию интерпретации I, взаимно однозначно отображающую множество экземпляров Obj в некоторое множество элементов произвольной природы — универсум UNIV:

I(Obj) = UNIV.

Относительно этого универсума будем интерпретировать утверждения формального языка. Отображение 1 сопоставляет экземплярам из Obj отдельные элементы множества UNIV, а классам из Class — подмножества UNIV. Для произвольных экземпляра а из Obj и класса А из Class: 1(a) е UNIV,

1(A) с UNIV.

Истинностные значения отображаются: 1( "истина" ) = 1; 1( "ложь" ) = 0.

Class есть множество всех классов базы знаний, поэтому:

I(Class) с 2UMV, где 2UNW есть множество всех подмножеств UNTV.

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

flfli,

В связи с особенностями определения отношений рассматриваемого языка, определим 3 типа интерпретации бинарных отношений: OOBin, OCBin и COBin. Классы могут быть аргументами любого типа бинарных отношений, но в зависимости от типа, данное отношение либо устанавливается только с самим классом, либо распространяется на все элементы данного класса. Интерпретацию отношении языка указанных типов будем разрабатывать в общем виде, что позволит в дальнейшем вводить в язык новые отношения данных типов, не определяя их интерпретацию заново.

Далее приведем примеры интерпретации нескольких видов отношений языка.

Отношение конкретизации является примером отношения из COBin, поскольку его первым аргументом может быть только класс, а вторым аргументом может быть либо класс, либо экземпляр. При этом, если вторым аргументом является класс, например, А: В, то это означает, что отношение конкретизации класса А распространяется на все экземпляры данного класса В.

Для произвольных классов А, В и произвольного экземпляра b определим следующую интерпретацию отношения конкретизации:

1(А:Ь) = 1 о 1(Ь) е 1(А); 1(А:В) = I <»1(В)с1(А); 1(~А:Ь) = 1 1(Ь) е 1(А); 1(~А:В) = 1 «> 1(В) сг 1(А).

Т.е., отношение конкретизации класса экземпляром отображается в отношение принадлежности элемента множеству, а отношение конкретизации между классами — в отношение вложения множеств. Отношение же вложения множеств можно определить следующим образом:

1(В) с 1(А) «>(УхеШР/) [х е 1(В) ->хе 1(А); х г 1(А) ->х ё 1(В)] 1(В)«1(А) <?> (ЭхеШГУ) [х е 1(В); х € 1(А>]

То есть, отношение конкретизации между классами выражается через отношение конкретизации класса экземпляром. Это означает, что отношение конкретизации класса экземпляром есть элементарное отношение, а отношение конкретизации между классами — неэлементарное.

На основании введенной теоретико-множественной интерпретации отношений языка разрабатывается их денотативная семантика. Так, денотативную семантику отношения конкретизации определим следующим образом:

(УХ,У) [ Х:У <-» (Ух) (У:х-»Х:х;~Х:х->~У: х)], (УХ,У) [~Х:У о (Эх) (У: х; ~ X : х)].

Введя теоретико-множественную интерпретацию отношения конкретизации, мы определили смысл введенной в языке операции "отрицания" Все ввды ''отрицаний" отношений языка сводятся к "отрицанию" элементарных отношений и интерпретируются через теоретико-множественное отношение НЕ принадлежности элементов множеству.

Примером отношения из ОСВт является отношение "иметь атрибут", поскольку его вторым аргументом может быть только класс, а первым—либо класс, шбо экземпляр. Записью а(В) мы утверждаем факт наличия атрибута В у экземпляра а, т.е., класс В выражает некоторое свойство данного экземпляра. Если же первым фгументом отношения является класс, например, А(В), то это означает, что все жземпляры данного класса А имеют атрибут В. Для произвольного класса В и троиз вольного экземпляра а определим следующую интерпретацию: ( а{ В) ) = 1о( 1(а), 1(В) )6Ц '()'), 1( ~ я(В) )=!«( 1(а), 1(В) )г1( '( )' ),

■де'( )' используется для символьного обозначения отношения "атрибут".

В записи неэлементарного отношения А(В) по умолчанию опускается :лужебное слово ЕАСН:

1(А(В)) = 1 <=> 1(А)х1(В) с 1( '()' ), где 1(А) с 1Ж1У, а 1(В) е 2°™ 1(~А(В)) = 1« 1(А)х1(В) с 1('()'),

Согласно этой интерпретации определяется денотативная семантика [еэлементарного отношения "атрибут":

(УХ,У) [ Х(У) о (Ух) (X : х -> х(У); ~ х(У) -> ~ X : х)]. (УХ,У) [~Х(У) о (Эх) (X: х; ~ х(У) ) ].

В языке есть средство для задания произвольных бинарных отношений между кземплярами. Такое отношение называется связкой и является примером отношения о ООВт. В качестве связки, т.е. имени отношения, может выступать любой класс, имя оторого пишется в кавычках. Аргументами связки могут быть как классы, так и кземпляры. Если связка задается между классами или между классом и экземпляром, о по умолчанию принимается, что данное отношение распространяется на все кземпляры данного класса (явно это можно указать с использованием служебного

слова EACH). Если же мы хотим указать, что данное отношение выполняется только для некоторых экземпляров данного класса, то перед именем класса указывается служебное слою SOME.

Для произвольных экземпляров a, b и произвольного элементарного отношения 7L из OOBin интерпретацию определим следующим образом: I(aRb)= 1 »(1(a), 1(b) )s ICR), I(~«Rb)=l<=>( 1(a), 1(Ъ) Дадим интерпретацию одного из видов неэлементарного отношения типа "связка": 1(А 7? SOME В) = 1 о

(VxeUNIV) [х е 1(A) (3yeUNIV) (yel(B), (х, у) € 1(К));

(VyeUNIV) (уг 1(B) v (х, у)<21(К)) 1(A)], На основании заданной интерпретации определим денотативную семантику отношения:

(VX, У, Z) [X "Y" SOME Z <-> (Vx) (X: х (3z) (Z : z; x"Y"z);

(Vz) (~Z:zv~ x"Y"z) ~ X: x] Трехместные отношения формального языка будем интерпретировать как комбинации отношений типов OCBin и СОВш, а интерпретацию будем вводить в общем виде, так же как и для бинарных отношений:

1(аП1ВЮ.с)=1<=>( 1(a), 1(B), i(c)) е \{К1_К2), при этом должно выполняться:

(1(a), 1(B), I(i) ) е KKIJIZ) (1(a), 1(B)) е 1(К1); (1(B), 1(c) ) е 1(К2). Примером такого трехместного отношения является отношение "атрибут со значением", которое позволяет задать значение атрибута для данного объекта, либо для данного класса объектов. Интерпретацию его определим в соответствии с общей интерпретацией отношения 1( а(В.с))= 1 о(1(a), 1(B), 1(c) 1(<(.)'), При этом выполняется:

(1(a), 1(B), 1(c) ) е 1('(• )' ) ^ ( Ш 1(B) ) е 1('( )' ); 1(c) б 1(B),

где'(.)' есть символьное обозначение отношения "атрибут со значением".

Последнее означает, что для произвольного класса В и произвольных экземпляров а, с: я(В.с) => а(В); В:с.

Т.е., элементарное отношение "атрибут со значением" удовлетворяет следующему правилу:

(Vx, Y, z) [ (x(Y.z) -> x(Y); Y : z); ((- x(Y) v ~Y : z) ~ x(Y.z)) ] Дадим теперь интерпретацию неэлементарного отношения "атрибут со значением". Согласно неформальному определению выражения А(В.С), в языке принято следующее умолчание: А(В.С) = EACH А(В. SOME С). I(A(B.C)) = 1 о

(VxeUNIV) [ (xeI(A) (3yeUNIV) (yel(C), (x, 1(B), у) e I('(.)'));

((VyeUNIV) (ygl(C) v (x, 1(B), y)el('(.)'))-> xgl(A))]. Согласно этой интерпретации можем определить денотативную семантику неэлементарного отношения "атрибут со значением": (VX, Y, Z) [ X(Y.Z) <-> (Vx) (X: х -> (3z)( Z : z; x(Y.z));

(Vz) (~Z: z v ~x(Y.z)) ->~X:x)] В отличие от денотативной семантики отношений других языков концептуального моделирования, разработанная денотативная семантика определяет

неэлементарные отношения не через отношение принадлежности элементов классу, а через элементарные отношения.

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

Во второй главе определяется эрбрановская интерпретация отношений формального языка. Эрбрановский универсум HU есть множество всех константных термов базы знаний, т.е. в нашем случае совпадает с множеством всех констант: HU = Class о Obj. Необходимо отметить, что в отличие от эрбрановекого базиса обычных дедуктивных систем, HU содержит константы двух типов: Class и Obj.

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

Полученная при этом дедуктивная модель не охватывает правила, скрытые в семантике неэлеменгарных отношений языка. Предикаты вида ~Р полагаются положительными предикатами и трактуются как ложные лишь при выдаче ответа на пользовательский запрос.

На основе эрбрановской интерпретации отношений языка разработан алгоритм Query(<5) логического вывода на системе пользовательских правил. В основу алгоритма положен нисходящий метод вывода на основе метода SLD-резолюции. При реализации метода возникают следующие практические трудности.

Для записи пользовательского правила используется конструкция:

* ?й ... ;fn<=(Qi;... ;Qs) v... v(V,;... ;Vm),

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

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

больших базах знаний, а также для представления словарных статей семантического словаря, количество введенных в языке констант может составлять порядка сотен тысяч, тогда как количество зарезервированных типов отношений не превышает и десятка. В связи с этим, невозможно искать нужный предикат в базе, перебирая все предикаты заданного типа. Поэтому ключом для поиска предиката в базе являются константы, входящие в отношение. При непосредственном поиске предиката в концептуальной памяти могут быть найдены только предикаты, непосредственно содержащие константы, входящие в предикат запроса. Это значит, что запрос к концептуальной памяти может составлять только вычислимый предикат, т.е. предикат отношения, в котором хотя бы одна переменная замещена константой, т.е. хотя бы один терм в Р(Х{,..., £",) является константой. Вычислением предиката будем называть означивание константами переменных предиката при получении ответа на запрос, состоящий из одного этого предиката.

Конъюнкция предикатов вычислима, если она:

1) содержит хотя бы один вычислимый предикат и

2) допускает такую последовательность вычисления предикатов, что при

вычислении очередного предиката будут означены переменные, входящие в

последующие предикаты, так, чтобы в результате все предикаты могли быть

вычислены.

Следствие пользовательского правила может представлять собой только вычислимую конъюнкцию предикатов, а посылка — дизъюнкцию вычислимых конъюнкций предикатов.

Из ограничения вычислимости вытекает ограничение совместимости предикатов правила и цели: правило К применяется для получения резольвенты с целевым предикатом Р, если конъюнкция следствия К содержит вычислимый предикат <5, совместимый с Р.

Два предиката, ($иР, совместимы, если:

а) существует унифицирующая подстановка 0: <50 = Р0,

б) хотя бы одно аргументное место этих предикатов замещено общей константой.

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

Для разработанного алгоритма Оаггу(()) сохраняется корректность, свойственная методу Б LD-pe30.u0 ции, однако, используемый метод вывода и

ограничение совместимости предикатов не позволяют обеспечить полноту вывода при помощи алгоритма Query(<5).

Разработан метод оптимизации алгоритма Query(Cj), обеспечивающий более быстрое получение части ответов на запрос к концептуальной памяти.

В третьей главе получены семантические правила для отношений формального языка на основании введенной в главе 1 денотативной семантики отношений.

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

На примере отношения "атрибут со значением" разберем, как получаются семантические правша из правил денотативной семантики: X(Y.Z)

(VX, Y, Z) [ X(Y.Z) <н> (Vx) (~Х: х v (3z)( Z : z; x(Y.z))]

Заменим в формуле денотативной семантики переменную г, стоящую под квантором существования, одноместной сколемовской функцией f(x), получим результирующее логическое правило:

(VX, Y, Z) [ X(Y.Z) -о- (Vx) (~Х: х v ( x(Y.f(x)); Z : f(x)))] Помня, что при формировании правил денотативной семантики операция рассматривается как логическое отрицание, заменим дизъюнкцию эквивалентными импликациями:

(VX, Y, Z) [ X(Y.Z) (Vx) ((X: х --> x(Y.f(x)); Z : f(x));

(~Z: f(x) v ~x(Y.f(x)) -> ~X: x))] Теперь все переменные в выражении находятся под квантором всеобщности, поэтому сам квантор можем опустить. Семантические правила формулируются для отношения в общем виде, а конкретные правила получаются в дальнейшем при унификации этого отношения с конкретными отношениями данного типа. При этом переменные, не входящие в отношение, семантика которого представлена правилами, в такой унификации не участвуют, а используются только в процессе применения семантических правил. Эти переменные не входят в пользовательский запрос и оказываются скрытыми от пользователя, поэтому будем их называть системными переменными и отмечать знаком $. Окончательно семантические правила для отношения Х( Y.Z) имеют вид:

X(Y.Z) <=> { X : х$ => Z: Дх$); x$(Y.f(x$));

~Z: f(x$) v ~x$(Y.f(x$) => ~X: x$ } Таким образом, каждое неэлементарное отношение эквивалентно совокупности правил над элементарными отношениями. Правая часть эквивалентности 'о' содержит только предикаты элементарных отношений.

Полученные правила имеют синтаксис пользовательских правил, однако, они не могут быть просто помещены в общую концептуальную память, поскольку: а) они не

содержат вычислимых предикатов, Ь) они могут содержать сколемовские функции и константы. Поэтому семантические правила должны храниться в отдельной, иначе организованной семантической памяти, из которой можно извлекать совокупность семантических правил по заданным типу отношения и типам аргументов.

Итак, окончательно сформирована структура базы знаний: база знаний должна состоять из концептуальной памяти, в которой хранятся факты и пользовательские правила, и семантической памяти.

Рассмотрим теперь полный алгоритм логического вывода на базе знаний. Перед нами стоит задача: учесть семантику отношений, т.е. семантические правила при выводе ответа на запрос к базе знаний.

Введем обозначения.

F, 5 и So — совокупность, соответственно, фактов концептуальной памяти, пользовательских правил и правил семантической памяти.

Р(Х)— произвольный n-местный предикат отношения, аргументные места которого замещены переменными из набора К. Переменные из набора К могут быть определены в концептуальной памяти как на множестве классов, так и на множестве экземпляров.

V0OS)— вычислимый предикат, некоторые из аргументных мест которого применением унифицирующей подстановки X замещены константами.

Query(f\XX,)) = {9i,...,0m} — результат запроса к концептуальной памяти, представленный множеством ответных подстановок, удовлетворяющих условиям:

— 1= iVÜA) (l<i<m);(|= обозначает отношение логического следования)

— все аргументные места Р замещены константами.

В частности, если набор переменных (X)}. пуст, т.е. Р(ХХ)— константный предикат, то Queiy(Р(Х1)) или пуст (Рне выводим из ¿Ор), или равен {X}.

А(Х,д$)= сч(Кх$) Л...Л сц(Кк$), B(X,x$)=bi(X,x$) А...А Ъг(Х,х$),... — обозначения компонент формул, представляющие конъюнкцию нескольких предикатов отношений (в частном случае один).

С учетом введенных обозначений семантические правила для отношения, заданного предикатом Р, можно записать в виде:

Р(Х) о { АГК У%>) -^SfX, у%)} (1)

Примечание:

В общем случае правая часть эквивалентности 'о' может содержать конъюнкцию отношений следования вцда А->Ъ.

Запись вида (1) мы будем называть шаблоном семантических правил предиката Р(Х), а сам предикат — владельцем шаблона.

Предположим теперь, что предикат Р(ХХ) вычислим, и для текущего состояния базы знаний известны все возможные подстановки {9j,...,0m}, при использовании которых SLipü5o |= i\XX6i). Тогда, учитывая, что в семантической памяти 5о содержится правило (1), из .ЯjJ^jSo следует истинность правил

А(ХХ0Ь x$J->ßfXX9i, *$,), (l<i <m).-

С другой стороны, предположим, что нас интересуют все возможные наборы значений переменных из Хл, при которых для текущего состояния базы знаний

SufUSo |= POOu). Мы решим поставленную задачу, если сможем найти полный набор {Oj,...,Q„} подстановок, для каждой из которых правило

AfiO.Oj, y$)-*B(XlGj, xS) является следствием S^FuSo.

Пусть Queiy(P(^))={0b...,6m}.

Согласно показанной в главе 2 корректности алгоритма Query, это означает, что Sop 1= Р(Х>Д), а значит, учитывая, что правило (1) содержится в семантической памяти 5о, правила вида AfXIOi, Х$) —>В(ХХО-,, )c$J, (1< i <ш) являются следствием SjfijSo-

Задача доказательства запроса к базе знаний формулируется следующим

образом:

имеется база знаний SufxjSo и запрос к ней в виде вычислимого предиката Р(ХХ). Нам необходимо по текущему состоянию базы знаний определить набор подстановок G={0j,...,Qn}, для каждой из которых выполняется SuTLjSo |= (1<}<п).

Рассмотрим сначала случай, когда запрос Р(ХХ) представляет предикат неэлементарного отношения. Это означает, что для этого предиката отношения в семантической памяти содержится шаблон семантических правил (1), и мы будем строить 0, доказывая, что истинность выражений A(KkQi, }($) —> BfX>.0|, х$) следует из S^RaSo.

Необходимо заметить, что при замене формулы запроса Р(ХХ) запросом вида ? Ар(Х, Ъ(ХХ, }t$), правило в запросе может содержать сколемовские константы

или функции. В этом случае производится следующая замена:

1) сколемовские константы заменяются несистемными переменными;

2) имена сколемозских функций становятся переменными, которые также необходимо означить при доказательстве запроса.

Действительно, сколемовские константы не могут быть заменены системными переменными, поскольку последние всегда находятся под квантором всеобщности.

Утверждение 1. Пусть Р(Х) о {А(Х, x$)->8fX, *$)} и —

вычислимый предикат. Выражение xSJX.O-^Bf'X, Х$Д0 следует из Занесли в семантической памяти найдется шаблон Q(X)o {CfX, yS)->Dl(K, у$)лТ>2(Я, xSJ} для которого выполняются условия:

а) найдется унифицирующая подстановка я, в результате которой

SlfX, х$Дтс= VI(К

где 8ГХ, ^ = Ъ\(К, у$,)лЪ2(К

б) 0иегу(0(ХХя»={ф1,..., фь}.

в) найдется унифицирующая подстановка р, такая, что для любого предиката ег в конъюнкции С(Х, Х$)/\В2(К, Х$) найдется унифицирующийся с гам Of в конъюнкции А(Х, Х$) такой, что е<(К Х$)/-лфр=0((Х, х$)Хяфр, где фе{фь..., фк},

либо навдется такая подстановка р, что правило А(К х$)Ьгфр CfK, *$)Х.яфрлВ2^Х, $>)Х.лфр следует из S^>TL>So для фе {фь ..., фк}.

В этих условиях 0=Яяфр.

Рассмотрим теперь запрос V[KX) в виде предиката элементарного отношения.

Утверждение 2. Пусть P(XJ.) — элементарный вычислимый предикат. Р(ХХО) следует из SufL>So, если выполняется:

либо l)Queiy(№))={O1,...,em},Qe{0b ...,0га},

либо 2) в семантической памяти 5о найдется шаблон Q(K) <=> {С(К X$)~>Vl(K X$)/\D2(>i, х$)} для которого выполняются условия:

а) найдется унифицирующая подстановка it, в результате которой ?(ХХ%)= VI(К,

б) Query(Q(X/.7i))={(pb ..., ф,}.

в) найдется такая подстановка р, что конъюнкция предикатов С(Х, ie$)Xmpp следует из SL/fLiSo для фе{ф1, ..., ipk}.

В этих условиях 0=Хтс<рр.

Алгоритм General_Queiy доказательства запроса к базе знаний строится на основании утверждений 1 и 2. Чтобы перебрать все семантические правила, применимые к предикатам цели, мы перебираем все шаблоны семантических правил, выделяя из них подходящие для смены цели. Применяя к ним унифицирующую подстановку, мы определяем в самом общем виде шаблон правил, которые можно применить к текущей цели. Затем, применяя ту же подстановку к владельцу шаблона, мы посылаем запрос в концептуальную память, чтобы определить, какие же правила из соответствующих шаблону реально могут быть выведены из фактов и правил концептуальной памяти. И уже полученные семантические правила мы применяем в процессе вывода.

Перебор всех применимых шаблонов организован методом рекурсии и бэктрекинга. При этом помимо нескольких возможных шаблонов правил, применимых к текущему предикату цели возникают дополнительные точки ветвления: в результате запроса к концептуальной памяти Query(Q(Xn)) = ф может быть получено несколько подстановок ф, удовлетворяющих запросу.

В диссертации доказана корректность разработанного алгоритма Gcneral_Query.

Необходимо заметить, что данный алгоритм не обеспечивает полноты, т.е. в результате могут получены не все подстановки 0, при которых истинность формулы запроса следует из S~>FuSo- При указанном методе перебора правил возможно зацикливание при вхождении в бесконечную рекурсию. Так же как и в алгоритме Query, возникает проблема остановки, для решения которой нужно либо исследовать динамическое поведение программы, либо искусственно ограничивать глубину рекурсии какой-либо заранее заданной величиной. На данный момент в реализованном алгоритме принято решение об искусственном ограничении глубины рекурсии, что ведет к потере полноты.

Второе условие неполноты алгоритма General_Query следует из неполноты самого алгоритма Query, используемого для получения ответов на запрос к концептуальной памяти.

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

Выводы

Была рассмотрена гибридная система представления знаний, комбинирующая юдства описания иерархических отношений, свойственные языкам концептуального эделирования, и дедуктивные (пользовательские) правила, позволяющие осуществить >гический вывод. Для такой системы представления знаний были решены следующие дачи:

1. Определена эрбрановская интерпретация отношений языка и разработан ггоритм логического вывода на системе пользовательских правил. Алгоритм яшизован в экспериментальной системе управления базой знаний.

2. Предложен метод определения денотативной семантики отношений языка 'азирующейся на теоретико-множественной интерпретации) в виде представления •ношений между классами через отношения между экземплярами.

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

4. В рамках предложенного метода разработана методика представления :мантики отношений в семантической памяти базы знаний в виде шаблонов, зависимых от конкретного наполнения базы. Построены шаблоны семантики -ношений языка.

5. Разработаны алгоритмы комбинированного логического вывода на основе «вил пользователя и семантики отношений языка.

Основные публикации по теме диссертации

1. МамедниязоваН.С. Поисх информации в концептуальной памяти.// нформационные технологии в гуманитарных и общественных науках. СПб.: СПб МИ РАН, 1997. Вып.6. С.45-50.

2. Мамедниязова Н.С., Попова А.И. Интерпретатор формального языка для нщегпуальиого моделирования текстов в системе MAZE. // Информационные хнолопш в гуманитарных и общественных науках. СПб.: СПб ЭМИ РАН, 1998. ып.7. С. 15-23.

3. Боярский К.К., Мамедниязова Н.С., Попова А.И. Представление и обработка шцептуальной информации в системе MAZE. В кн. Экономико-математические ¡следования. Математические модели и информационные технологии. СПб: Наука, )00г.

4. Лезнн Г.В., Мамедниязова Н.С. О представлении семантики концептуальных эделей в базах знаний. // Труды Международного семинара Диалог'2000 по )мпьютерной лингвистике и е£ приложениям. Т.2. С.235-242. Протвино, 2000г.

' ЛР № 040815 от 22.05.97.

Подписано к печати 05.10.2000 г. Формат бумаги 60x90 1/16. Бумага офсетная. Печать ризографическая. Объем 1 п.л. Тираж 100 экз. Заказ 1561. Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ с оригинал-макета заказчика. 198904, Санкт-Петербург, Старый Петергоф, Университетский пр. 2.

Введение

1) Модели представления знаний

2) Практические предпосылки исследования.

Постановка задачи. Краткое содержание работы

1. Формальный язык. Денотативная семантика отношений языка

1) Основные определения

2) Семантическая интерпретация. Денотативная семантика отношений

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

1) Эрбрановская интерпретация конструкций языка

2) Алгоритм доказательства запроса к базе знаний без учета семантики отношений

3. Интегрированная модель предметной области

1) Семантическая память

2) Предварительные определения и обоснование выводимости

3) Общий алгоритм доказательства запроса к базе знаний 110 Выводы

Модели представления знаний

Среди различных моделей, лежащих в основе современных систем представления знаний, можно выделить два класса, получившие наиболее широкое распространение: класс дедуктивных и класс концептуальных моделей.

Системы, основанные на дедуктивных моделях, обычно применяются для представления знаний дедуктивной природы, когда связи между утверждениями удобно выражать каузальными конструкциями "если-то".

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

На практике описание предметной области всегда содержит и иерархически связанные понятия и каузальные связи между утверждениями о понятиях.

В данной работе исследуется возможность интеграции методов этих двух моделей в общей системе представления знаний.

В основе дедуктивных моделей лежит эрбрановская интерпретация данных. В формализмах такого рода основными элементами языка являются термы (константы, переменные, функции), служащие для обозначения различных объектов, и п-местные предикаты (имеющие термы в качестве аргументов), предназначенные для фиксации отношений между объектами. В эрбрановской интерпретации любая константа представляет собой лишь цепочку символов, а интерпретация предиката отношения задается множеством значений аргументов, на которых этот предикат истинен. Истинность предиката в базе знаний задается либо фактом — явным указанием константных термов, на которых предикат истинен, либо вычисляется при помощи заданных пользователем правил (логической программы). Таким образом, множество значений аргументов, на которыхпредикат истинен, определяется результатом работы логической программы. Это означает, что интерпретация данных отделена от самих данных и перенесена на работающие с ними логические программы. Сами данные без соответствующих программ представляют собой не более чем набор символов, которому различные программы могут придать различную интерпретацию. Таким образом, представление знаний в системах на основе дедуктивных моделей определяется способом его обработки.

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

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

Классическими примерами языков, в основу определения которых положена дедуктивная модель, являются язык логического программирования Пролог [40, 39, 44] и логический язык программирования баз данных Дейталог [8, 9, 53].

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

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

Чтобы удовлетворить этому требованию, были созданы различные варианты языков логического программирования, где логика предикатов первого порядка ограничивалась неким ее подклассом (в ущерб вычислительной полноте). Дейталог, будучи примером такого языка, является первым специализированным логическим языком программирования баз данных [41, с. 12]. Создатели языка [53] ставили целью совместить возможности языка логического программирования с возможностью хранения фактов в больших базах данных. В связи с этим, накладываются ограничения на язык логики предикатов первого порядка: в языке отсутствуют функциональные выражения, т.е. возможность конструирования сложных объектов — в качестве терма может выступать только константа или переменная. В отличие от прологовского нисходящего вывода, основанного на методе резолюций, в Дейталоге используется восходящий метод вывода. За счет такого метода вывода решается проблема перестановочности клауз, т.е. в Дейталоге результат работы логической программы не зависит от порядка записи клауз.

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

Заметим, что, как в Прологе, так и в Дейталоге нет явно вводимого отрицания, т.е. невыводимость истинности предиката в данной базе знаний приравнивается к ложности этого предиката.

Представляется, что недостаточная выразительность и процедурность описаний, выстраиваемых на основе дедуктивных моделей, явилась одной из побудительных причин создания специальных языков, нацеленных на описание данных [51, с.4]. В основу таких языков положены концептуальные модели данных, ориентированные, в первую очередь, на представление сложных иерархических структур.

В настоящее время одной из областей применения языков концептуального моделирования являются системы обработки текстов на естественном языке, являющиеся составной частью систем для представления знаний. Системы обработки текстов на естественном языке (NLP — natural language processing) нацелены на извлечение семантической информации, содержащейся в тексте, на основе общеязыковых представлений. Необходимые лексические сведения в такой системе обеспечивает словарь с достаточно формализованной словарной статьей. В настоящее время большинство исследователей в данной области признают необходимость построения специального концептуального словаря (вычислительной онтологии), где данные словарной статьи представляются при помощи некоторого формального языка [49, 48, 20, 21, 26, 15]. Формальный язык используется в системе NLP двояким образом: во-первых — для представления словарной статьи, во-вторых — для окончательного представления извлеченной из текста информации.

Пример описания из семантического словаря В.А. Тузова:ВЫПУСК $1202(Тв, Род, Из, наВинЩля)— описание базового понятия в классе, имеет четыре аргумента, которые должны быть заполнены соответствующими актантами: кем осуществляется выпуск, кого (что) выпускают, откуда и для чего.

ВЫПУСКНИК Орег01о2(ШКОЛА$1119110, BbinyCK$1202(Singo%2)) "Выпускник - это тот, кто является вторым актантом действующего (или действовавшего когда-то) процесса выпуска из класса $1202, осуществляемого некоторой школой из класса $1119110 ".

Здесь ВЫПУСК$1202— далее не трактуемое базовое понятие класса, т.е. концепт, а понятие ВЫПУСКНИК определяется через концепты ВЫПУСК$1202иШКОЛА$1119110. Цифры обозначают положение класса в общей иерархии объектов.

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

Основными элементами языков концептуального моделирования являются классы объектов и бинарные отношения. Поскольку любой парный предикат может быть представлен совокупностью бинарных предикатов [43, с Л 46], то эти элементы языка позволяют выразить практически любые отношения между объектами.

Семантика классов и бинарных отношений задается при помощи интерпретации I относительно некоторого множества Б1 (домен интерпретации). Произвольному объекту а сопоставляется элемент а1 е Б1, произвольному классу А — некое подмножество А1 с Б1, а произвольному бинарному отношению Я— подмножество ^с^хБ1. [1, с.6] Далее эта интерпретация распространяется на все операции, определенные для классов и бинарных отношений. Из такой интерпретации вытекает, что мы можем определить некоторое бинарное отношение между классами объектов, или задать некоторое свойство класса, и это отношение, или это свойство будет автоматически распространяться на все элементы этих классов.

Таким образом, интерпретация данных в языках концептуального моделирования связывается с самими данными. В этом случае данные приобретают семантическую значимость, одновременно выражая и факты, и способ их интерпретации [52, с. 18]. Если в прологовской базе знаний взаимосвязи между различными данными представлены отдельно от самихданных, т.е. при помощи логических программ, то в концептуальной модели языковые средства, использованные для записи самих данных, определяют виды связей между данными.

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

В настоящее время выделяются два вида языков, в основе которых лежат концептуальные модели данных: концептуальные графы и языки, обычно обозначаемые как "языки типа KL-ONE". "KL-ONE" — название первой системы такого типа, реализованной Бречманом (Brachmann) и Шмульцем (Schmölze) [4].

Концептуальные графы [30, 43, 19, 27, 28, 22, 11, 2] и построенные на их основе семантические сети — наиболее полно разработанный на сегодняшний день формализм для наглядного (графического) представления знаний. Концептуальный граф содержит два типа узлов: узлы, представляющие объекты (или классы объектов), и узлы, представляющие отношения между объектами. На концептуальном графе выделяются отношения вида IS-A, которым устанавливается принадлежность объекта некоторому типу (классу) или вложение одного типа (класса) в другой. Относительно отношений вида IS-A определено наследование свойств объектов (их отношений с другими объектами) от типа к подтипу и к объекту, конкретизирующему данный тип. Это означает, что денотативная семантика остальных отношений задана относительно отношений вида IS-A. Наряду с отношениями вида IS-A, вводится отношение между множеством и элементом множества, относительно которого не определено наследование свойств. Наконцептуальных графах также могут быть введены кванторы существования и всеобщности, а также явное отрицание, что отличает концептуальные модели от Пролога и Дейталога. Например, фраза: "каждый слон — серый", может быть изображена концептуальным графом, который приведем здесь в текстовой форме: [ELEPHANT: V]->(COLR)->[COLOR:grey]Здесь в квадратных скобках изображаются концепты, а в круглых — отношения. На графе они заключаются соответственно в прямоугольники и окружности. Двоеточием изображено отношение принадлежности объекта некоторому типу: grey— это конкретный объект, тогда как COLOR и ELEPHANT определяют тип.

Концептуальные графы предоставляют широкие изобразительные возможности, позволяющие непосредственно обобщать концептуальные графы на модальные системы и другие формализмы, трудно представимые логикой первого порядка [43]. Однако, широкие выразительные возможности концептуальных графов, имеют и свою обратную сторону. Задача выстраивания иерархии классов в общем случае сводится к задаче: определить, является ли один концептуальный граф частью другого, а последнее не всегда разрешимо.

Ограничения, накладываемые на изобразительные возможности в языках типа KL-ONE [1, 31, 7, 23, 24, 25, 12], делают задачу выстраивания иерархии разрешимой.

После создания первой системы KL-ONE было создано большое количество систем, реализующих сходные идеи. Был разработан язык ALC, введенный в [29], который принято рассматривать как основу языков типа KL-ONE, так или иначе дополняемую в конкретных системах. [31]Основными объектами языков типа KL-ONE являются концепты и роли. Концепты представляются унарными предикатами, а роли — бинарными. Имеется также достаточно ограниченный набор конструктов для формирования новых концептов и ролей.[1, с.5] В языке ALC дляопределения нового концепта используются только конструкты NOT, AND, OR, а также кванторы существования и всеобщности.

Описание предметной области в языке ALC задается набором утверждений вида:концепт = условие принадлежности элементов концепту. Например, лягушку можно определить как животное зеленого цвета: Лягушка = (and Животное (all цвет Зеленый)).

Это определение системой автоматически транслируется в формулу логики предикатов:(\/х) (Лягушка(х) оЖивотное(х) л (\/у)(цвет(х,у) -> Зеленый(у))). В дальнейшем эта формула используется для осуществления логического вывода.

Особенностью языков типа KL-ONE является разделение знаний на терминологическую часть ("Т-box"), содержащую определения концептов и ролей, и базу фактов ("A-box"). Каждому определению концепта или роли в "Т-box" может быть автоматически сопоставлено правило на языке логики предикатов, в зависимости от конструктов, использованных в определении.

Семантическая интерпретация концептов и ролей фиксируется однократно при их определении в "Т-box" и связывается с самими данными. В этом случае данные приобретают семантическую значимость, одновременно выражая и факты, и способ их интерпретации.

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

Используя определения концептов, система KL-ONE может построить классификатор, автоматически определяющий место каждого из концептов в иерархии. Так, например, если в "Т-box" присутствуют следующие определения концептов: Высчеловек = (and Человек (some рост Высокий))Выстолстчеловек = (and Человек (some рост Высокий) (some вес Большой)),то классификатор автоматически поместит Выстолстчеловек в иерархии ниже Высчеловек, сравнив роли, использованные в определении этих концептов. Заметим, что такой классификатор для концептуальных графов отсутствует [3, с.85], и в аналогичной иерархии для концептуальных графов оба концепта Высчеловек и Выстолстчелоеек останутся подтипами концепта Человек."A-box" в KL-ONE состоит из фактов, фиксирующих истинность или ложность унарных и бинарных предикатов при определенных значениях аргументов. На основе рассмотренной выше семантической интерпретации, это означает факты принадлежности (или НЕ принадлежности, ввиду возможности явно указать этот факт) объектов классам или пар объектов бинарным отношениям. Таким образом, база фактов системы состоит из фактов принадлежности объектов классам. Правила, получаемые системой при трансляции определений из "Т-Ьох", позволяют вывести новые факты такого же вида. При таком подходе база фактов допускает хранение в виде таблицы, где названия столбцов есть имена классов и бинарных отношений, а в строках располагаются пометки о принадлежности (или НЕ принадлежности) этим классам или ролям объектов или пар объектов. Такая система хранения приводит к возможности использовать для логического вывода какую-либо вариацию метода семантических таблиц, введенного Э. Бетом. [34] В частности, в системах CARIN и AL-LOG, представляющих собой попытку комбинировать язык типа KL-ONE с применением хорновских правил, была использована техника систем с ограничениями (constraint systems), представляющая собой вариацию метода семантических таблиц. [16, 14]иСерьезным продвижением в развитии концепции языков типа KLONE, явилась система CBR (Classes and Binary Relations"), представленная Г.С. Плесневичем в [46, 47]. Предлагается совершенно иная структура входного языка: описание предметной области задается в виде предложений, содержащих утверждения об отношениях между классами, а также между классами и экземплярами. Такой язык обладает большей выразительностью по сравнению с языком систем типа KL-ONE, предназначенным в основном, для описания типов данных. Например, утверждение "любое животное питается либо растениями, либо животными, которые меньше его и питаются растениями" на языке CBR записывается в виде:EACH Животное X (Ест EACH Растение OR Ест EACH Животное THAT (Меньше X AND Ест SOME Растение)) Для описания предметной области определено его каноническое представление в виде конъюнкции терминальных элементов, где терминальный элемент — это выражение, содержащее единственное отношение или связку (THAT, OR, AND). Имеется ограниченный перечень конструкций терминальных элементов. Утверждения языка строятся при помощи связок AND, OR, NOT, а также префиксов SOME и EACH в качестве кванторов существования и всеобщности.

Например, можно записать утверждение о том, что все гусеницы едят некоторые растения:EACH Гусеница Ест SOME Растение.

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

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

Например, можно определить класс животных, которые едят некоторые растения:Травоядное == Животное THAT Ест SOME Растение.

Здесь Ест — бинарное отношение, Гусеница, Растение, Животное, Травоядное — классы, Ест SOME Растение — предикат.

База знаний в CBR, делится на концептуальную схему, в которую вк1[ючаются все предложения общего характера и базу фактов. База фактов, как и "A-box" в системах типа KL-ONE, включает в себя утверждения о принадлежности элементов классам или пар элементов бинарным отношениям.

Для всех конструкций языка определена денотативная семантика на основании теоретико-множественной интерпретации классов и отношений.

Существенной особенностью системы CBR является метод преобразования концептуальной схемы в систему продукций на основании введенной денотативной семантики отношений. Концептуальная схема на этапе трансляции преобразуется в систему продукций в соответствии с определенными правилами трансляции. Продукции представляют собой правила для получения новых фактов.

Так, например, факт принадлежности подкласса классу A ISA В транслируется в систему продукций: XINA =>Х IN В; XIN -В =>Х IN -А,(X— переменная, IN отражает принадлежность элемента классу) а факту А ISA В соответствует продукция: => g:A IN А; д:А IN -В,где д:А — сколемовская константа из класса А, а -В есть дополнение класса 6.

Полученная при трансляции концептуальной схемы система продукций применяется для осуществления логического вывода, основанного на методе семантических таблиц Бета. Как уже упоминалось, база фактов в CBR представляет собой таблицу с именами классов ибинарных отношений в качестве названий столбцов. Строка в таблице отражает состояние базы фактов, т.е. в нее заносятся элементы, принадлежащие или не принадлежащие соответствующим классам или бинарным отношениям. К базе фактов добавляется отрицание запроса и также заносится в таблицу. Последовательное применение системы продукций к состояниям базы фактов приводит к появлению новых элементов в таблице. Появление в одном столбце пометки о принадлежности и НЕ принадлежности ему одного и того же элемента позволяет сделать вывод о противоречивости базы фактов (т.е. подтверждает запрос). Можно заметить, что в CBR применяется восходящий метод вывода, аналогично восходящему выводу в Дейталоге.

Отметим, что в системе CBR явным образом вводится отрицание, причем теоретико-множественная интерпретация позволяет свести возможные формы отрицания в утверждениях языка к отрицанию элементарного факта принадлежности элемента классу (или пары элементов бинарному отношению). Это сведение осуществляется в процессе трансляции концептуальной схемы в систему продукций. (См. пример трансляции A ISA В.)Сопоставляя особенности и области применения дедуктивных и концептуальных моделей в системах представления знаний, мы можем видеть, что эти модели предназначены для представления знаний различной природы и не конкурируют, а скорее, дополняют одна другую. Удобно описывать свойства данной предметной области семантической сетью понятий и отношений и столь же удобно каузальные зависимости между отдельными фрагментами сети задавать средствами дедуктивной модели. В связи с этим большой интерес представляет интеграция методов обеих моделей в рамках единой системы представления знаний. Исследованию возможных подходов к решению этой задачи и посвящена данная работа.

В качестве примеров языков, комбинирующих методы дедуктивных и концептуальных моделей, можно привести языки CARIN [16] и AL-LOG [5, 6, 13, 14], в которых описание данных при помощи языков типа KL-ONE дополняется правилами в виде хорновских дизъюнктов. В обеих системах используются правила дейталоговского типа, т.е., без функциональных символов. При этом следствие правила может представлять собой только новый n-арный предикат и не может содержать описания концептов или ролей из терминологической части языка ("Т-box".). В языке CARIN посылка правила может содержать предикаты, представляющие собой концепты и роли из "Т-box", т.е. может содержать отношения принадлежности вида:хеС или оеС, а также (хь x2)eR или (oi, o2)eR, где х — обозначения переменных, о — экземпляров, С — концепта, R — роли.

В языке AL-LOG правило содержит только предикаты, отличные от ролей и концептов терминологической части, но при этом может дополняться набором ограничений вида хеС или оеС на переменные и константы, входящие в правило. В обеих системах (CARIN и AL-LOG) для осуществления логического вывода используется техника систем с ограничениями (constraint systems).

Недостатками предложенного в языках CARIN и AL-LOG подхода к построению гибридной системы представления знаний являются:1) правила не позволяют получить новых знаний об отношениях, представленных в дескриптивной части языка;2) используемые в правилах переменные и константы могут быть определены только на экземплярах.

Это означает, что правила языков CARIN и AL-LOG не позволяют вывести новых сведений ни о принадлежности объектов классам или ролям, ни об отношениях между классами.

В противоположность такому подходу, в данной работе ставится задача использовать дедуктивные правила с целью получения новыхсведений именно об объектах и отношениях, описываемых в языке. Предполагается, что вся необходимая информация может быть передана при помощи отношений языка (как это, кстати, изначально полагается и в языках типа KL-ONE), следовательно, не имеет смысла вводить новые предикаты только для использования в дедуктивных правилах.

Практические предпосылки исследования. Постановка задачи.

Краткое содержание работыВ качестве практической предпосылки к решению поставленной задачи была использована система MAZE, разрабатываемая в СПб ЭМИ РАН.[35, 36, 37, 42]Система MAZE предназначена для поддержки исследований в гуманитарных областях и представляет собой электронную картотеку, интегрирующую в единый комплекс средства гипертекста, филологический инструментарий (построение тезаурусов и лексических указателей, определение семиотических сопоставлений) и средства описания семантики накапливаемых в ней текстов. Тексту в системе может быть сопоставлено формализованное представление его содержания, которое пользователь желает зафиксировать в базе знаний системы.

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

В системе MAZE описание предметной области складывается из двух частей: "дескриптивной" и "процедурной". Дескриптивная часть описания представляет собой семантическую сеть, образованную набором утверждений об отношениях между классами, а также между классами и экземплярами. Набор утверждений формального языка системы может быть представлен в канонической форме в виде конъюнкции терминальныхэлементов. Терминальный элемент выражает единственное отношение языка. Набор конструкций для записи отношений фиксирован. Аргументами отношений могут быть как классы так и экземпляры. Например, утверждение Животное: Лягушка(Цвет.зеленый) будет преобразовано в каноническое представление: Животное: Лягушка; Лягушка(Цвет.зеленый).

Первый факт говорит о том, что класс Лягушка конкретизирует класс Животное, а второй факт означает, что класс Лягушка имеет атрибут Цвет со значением зеленый.

Процедурная часть описания предметной области имеет форму правил вида А <== В, устанавливающих зависимость между различными отношениями языка. Например:х"Любит"у; у"Любит"х <== Человек : х; Собака : у; у(Хозяин.х). Если у человека есть собака, то они любят друг друга. Домашнееживотное : X <== Животное : X; Х(Порода). Домашнее животное определяется как подкласс животных, имеющих атрибут Порода. Переменные х, у в примерах определены на экземплярах, а переменная X — на классах.

Существенными особенностями системы MAZE являются:— следствие правила может содержать конъюнкцию отношений;— отношения между классами могут входить в состав правил, т.е., правила позволяют выразить одни отношения между классами через другие.

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

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

Решение этих задач позволило бы:1) Строго сформулировать семантику отношений дедуктивного языка, тем самым в формальном языке априорно регламентировать использование тех или иных обозначений.

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

Основные результаты диссертации.

В первой главе определяется теоретико-множественная интерпретация синтаксических конструкций формального языка системы MAZE. В связи с особенностями определения отношений рассматриваемого языка, определяется 3 типа интерпретации бинарных отношений: OOBin, OCBin и COBin. Классы могут быть аргументами любого типа бинарных отношений, но в зависимости от типа, данное отношение либо устанавливается только с самим классом, либо распространяется на все элементы данного класса. Трехместные отношения рассматриваемого языка интерпретируются как комбинации отношений типов OCBin и COBin. Интерпретация отношений указанных типов разрабатывается в общем виде, что позволит в дальнейшем вводить в язык новые отношения данных типов, не определяя их интерпретацию заново.

Определяется смысл введенной в языке операции "отрицания" Данная операция не интерпретируется как логическое отрицание: предикатотношения при применении к нему операции считаетсяположительным литералом. Все виды "отрицаний" отношений языка сводятся к "отрицанию" элементарных отношений и интерпретируются через теоретико-множественное отношение НЕ принадлежности элементов множеству.

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

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

Рассматривается разработанный алгоритм (Зиегу(ф логическоговывода на системе пользовательских правил. В основу алгоритма положен нисходящий метод вывода на основе метода БиЗ-резолюции. При реализации метода возникают следующие практические трудности:— следствие правила на формальном языке может содержать конъюнкцию предикатов;— в связи с несоизмеримостью возможного количества констант языка и количества предопределенных в языке типов отношений невозможно использовать обычный способ вызова правил по имени предиката.

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

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

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

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

Разработан метод логического вывода на базе знаний с использованием семантических и пользовательских правил. Разработанный алгоритм GeneralQuery представляет собой нисходящий метод вывода с использованием семантических правил. При этом организован динамический метод вызова пользовательских правил: разработанный в главе 2 алгоритм Query логического вывода на системе пользовательских правил встроен в процедуру унификации при вызове семантического правила. Семантические правила хранятся в виде шаблонов, поэтому привызове семантического правила осуществляется поэтапная унификация предиката цели и правила:а) унифицируется предикат цели и следствия шаблона семантического правила;б) осуществляется вызов алгоритма Query, которому в качестве запроса передается неэлементарный предикат, которому в семантической памяти сопоставлен указанный шаблон семантического правила. (Если алгоритм Query выдает в качестве ответа некоторую подстановку 6, это значит, что при применении 0 к указанному шаблону семантического правила получается семантическое правило, истинность которого усгановлена на основании фактов и пользовательских правил концептуальной памяти);в) если алгоритм Query выдает в качестве ответа некоторую подстановку 0, эта подстановка применяется к семантическому правилу и предикату цели. На этом унификация завершается.

Доказана корректность алгоритма GeneraLQuery и рассмотрены условия его неполноты.

1. Формальный язык. Денотативная семантика отношений языкаОсновные определенияМодели текстов в системе MAZE представлены в концептуальной памяти в канонической форме в виде общей конъюнкции терминальных двух- или трехместных предикатов, образованных отношениями языка. Факты представляются константными предикатами. Пользовательские правила также хранятся в общей концептуальной памяти системы. Устройство и механизмы работы концептуальной памяти представлены более подробно в [35]. В общих чертах, концептуальная память организована в виде сетевой базы данных, где единицей хранения является отношение языка, т.е. запись, в которой фиксируется тип отношения и значения аргументов. Поскольку в языке только несколько фиксированных типов отношений, то на каждый тип приходится огромное количество записей. Поэтому записи организованы в наборы по константам, являющимся значениями аргументных полей, а не по типу отношения. Это накладывает определенные ограничения на поиск в концептуальной памяти, т.е. возникает понятие вычислимого предиката, которое будет рассмотрено далее. Обработка накопленной информации по заданным правилам инициализируется запросами к концептуальной памяти.

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

В правилах языка может присутствовать дизъюнкция и конъюнкция предикатов. Будем использовать V для обозначения операции дизъюнкции.

В языке допускается определение следующих видов объектов:— понятия (классы),— экземпляры понятий,— переменные,— отношения (бинарные, трехместные и четырехместные),— числа.

Вид объекта явно указывается в его обозначении.

Имена классов записываются прописными буквами, а имена экземпляров — строчными. Будем обозначать Class множество всех константных классов, a Obj — множество всех константных экземпляров базы знаний. Таким образом, Class и Obj представляет собой множество всех констант концептуальной памяти.

Для обозначения переменных мы зарезервируем буквы X х, Y, у, Z, z, и в случае необходимости будем индексировать эти буквы цифрами 1,., 9. Переменные, обозначенные прописными буквами X, Y, Z, определены на множестве понятий Class, а переменные, обозначенные строчными буквами х, у, z— на множестве экземпляров Obj. Множество всех переменных обозначим Var, и будем использовать обозначение у или у дляобозначения произвольной переменной из Var (т.е. переменной, определенной либо на Class, либо на Obj).

Для обозначения предопределенных в языке отношений зарегистрированы символы:Y — для обозначения бинарного отношения конкретизации;Л( У — для обозначения бинарного отношения "иметь атрибут";\.У — для обозначения трехместного отношения "иметь атрибут со значением";. У —для автонимного обозначения подкласса.

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

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

Текущее состояние объектов концептуальной памяти описывается наборами предикатов. Аргументом предиката отношения является терм— константный класс из Class, константный экземпляр из Obj, либо переменная.

Предикат отношения в общем виде можно представить: P(t\, где Р—тип отношения, t¡,., í^ — термы, п принимает значения от 2 до 4.

Будем называть основным предикат, не содержащий переменных.

В языке также введена операция применимая к отношениям и имеющая смысл отрицания. Более подробно смысл этой операции будет рассмотрен в главе, посвященной семантической интерпретации отношений. Стандартное обозначение отрицания не используется, чтобы подчеркнуть, что данная операция не является отрицанием с точки зрения логики предикатов. Поэтому обозначение P(t[,., íñ) есть по сути обозначение нового отношения, отличного от отношения P(tí,., Связьмежду этими двумя отношениями будет определена при рассмотрении теоретико-множественной интерпретации отношений.

Литерал есть предикат P(ti,ÍÜ) (положительный литерал), либоотрицание предиката -iP(t\,.,t^) (отрицательный литерал). Основной литерал — это литерал, не содержащий переменных. В связи сКонъюнкция предикатов вычислима, если она:1) содержит хотя бы один вычислимый предикат и2) допускает такую последовательность вычисления предикатов, что при вычислении очередного предиката будут означены переменные, входящие в последующие предикаты, так, чтобы в результате все предикаты могли быть вычислены.

Определим теперь синтаксис пользовательских правил и запросов. Для записи пользовательского правила используется конструкция:*Р1;. -фч ;Кп), (1)где следствие представляет собой вычислимую конъюнкцию предикатов, а посылка— дизъюнкцию вычислимых конъюнкций предикатов. ПримерЖенщина:х; х(Семейноеположение.замужем); Мужчина:у <== Человек : х; х(Муж.у); Драгоценность : X <== Украшение : X; Бриллиант:у; Х"Содержит"уЗаметим, что каждое пользовательское правило может быть легко представлено в виде конъюнкции хорновских правил. Действительно, правило (1) эквивалентно конъюнкции правил:Ри. ;Рп<=Ох;..; (2)Ри. -,Рп<==Ки. ;Яп.

В свою очередь, каждое из правил вида (2) может быть представлено в виде конъюнкции хорновских правил. Поэтому, окончательно, правило (1) эквивалентно конъюнкции хорновских правил:КРп<== С2ь..; (3)Рх<==Ки. Л;.5Рп<— Пи. ;Яп.

Для обозначения запроса к базе знаний используется символ Т. Синтаксис запроса в общем виде:?(<3ь. V. v(Я1;. ;Яа),т.е. запрос может формулироваться при помощи дизъюнкции вычислимых конъюнкций предикатов.

Пример? Животное : X; Х(Ест.У); Растение : УДалее введем теоретико-множественную интерпретацию синтаксических конструкций языка и на ее основании определим денотативную семантику для каждого вида отношений языка.

Семантическая интерпретация. Денотативная семантика отношенийЧтобы определить теоретико-множественную интерпретацию конструкций формального языка, рассмотрим определенное в языке отношение конкретизации. Это отношение может быть задано между классом и экземпляром, либо между двумя классами:запись А:Ь (Ь конкретизирует А) означает факт принадлежности экземпляра Ь классу А,а запись А:В (В конкретизирует А) означает, что В является подклассом класса А.

Информацию, содержащуюся в таком определении, можно было бы передать и иным образом, а именно: фиксируя класс в бинарном отношении конкретизации класса экземпляром, каждому такому отношению можно сопоставить определенное на ОЬ) унарное отношение, где имя класса становится именем предиката. Данное унарное отношение будет принимать значение "истина" тогда и только тогда, когда его аргумент конкретизирует соответствующий класс.

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

Унарному предикату, определенному на Obj, можем сопоставить набор константных экземпляров, на которых данный предикат принимает значение "истина". Положим, что предикаты А:Ь и А:Ь не могут быть истинны одновременно. В этом случае наборы экземпляров, соответствующие предикатам А и А, не могут пересекаться. Такимобразом, произвольному константному классу А и его "отрицанию" А могут быть сопоставлены непересекающиеся наборы константных экземпляров.

Учитывая этот факт, можем теперь ввести теоретико-множественную интерпретацию конструкций формального языка.

Введем функцию интерпретации I, взаимно однозначно отображающую множество экземпляров базы знаний Obj в некоторое множество элементов произвольной природы — универсум UNIV: I(Obj) = UNIV.

Относительно этого универсума будем интерпретировать утверждения формального языка. Отображение I сопоставляет экземплярам из Obj отдельные элементы множества UNIY, а классам из Class — подмножества UNIV:1(a) е UNIY, где а - произвольный экземпляр из Obj, 1(A) œ UNIY, где А - произвольный класс из Class. Для отрицания класса введем следующую интерпретацию: 1(А) с UNIV; 1(A) п 1(А) = 0.

Истинностные значения функцией интерпретации отображаются:1( "истина" ) = 1 ; I( "ложь" ) = 0.

Заметим, что Class есть множество всех классов базы знаний, и, согласно введенной выше интерпретации:I(Class) с; где 2UMV есть множество всех подмножеств UNIY.

Рассмотрим теперь введенные в языке отношения. Выше были перечислены типы отношений, введенные в языке. При помощи каждого типа отношения можно задать элементарное и неэлементарное отношение.

Элементарным назовем отношение, далее не трактуемое и не выражаемое через другие отношения.

Семантика отношения конкретизации.

Рассмотрим, к примеру, отношение конкретизации. Отношение конкретизации класса экземпляром есть элементарное отношение. Через него может быть выражено отношение конкретизации между классами, которое поэтому есть неэлементарное отношение.

Чтобы пояснить это, дадим интерпретацию отношения конкретизации.

Этому новому факту, согласно семантике конкретизации, соответствует система правил:(\/х) ( Кольцообручальное : х Драгоценность : х; Драгоценность : х -» Кольцообручальное : х) Это значит, что при наличии корректной системы вывода у нас есть возможность выводить не только новые факты, но также и новые правила. Вопросам построения такой системы вывода будут посвящены последующие главы.

Мы видим, что одновременно с семантикой отношения конкретизации была введена и семантика операции "отрицания" Если отношение конкретизации класса экземпляром отображается в отношение принадлежности элемента множеству, то "отрицание" этого отношения интерпретируется через отношение НЕ принадлежности элемента множеству.

Как мы увидим далее, все остальные отношения языка и их "отрицания" так же как и отношение конкретизации между классами и его "отрицание" могут быть интерпретированы через принадлежность и НЕ принадлежность элементов множеству.

Таким образом, все виды "отрицаний" отношений языка могут быть сведены и проинтерпретированы через отношение НЕ принадлежности элементов множеству.

Область определения элементарных отношений.

Любое элементарное отношение языка может быть задано для определенных типов аргументов.

Так, первый аргумент отношения конкретизации класса экземпляром определен на множестве Class, а второй— на Obj, т.е. предикат этого отношения есть отображение ClassxObj -» {"ложь", "истина"}.

Как мы видели, при изменении области определения аргумента с Obj на Class мы задаем уже неэлементарное отношение конкретизации между классами. При этом соблюдается общее Правило 1:если на месте аргумента элементарного отношения, определенного на Obj, записан класс, то это означает, что задано неэлементарное отношение, и истинность этого неэлементарного отношения эквивалентна выполнению соответствующего элементарного отношения для всех (либо некоторых) экземпляров указанного класса.

Указать, выполняется ли соответствующее отношение для всех или некоторых экземпляров класса, можно при помощи служебных слов EACH либо SOME. При их отсутствии действуют принятые в языке умолчания.

Далее зададим область определения всех элементарных отношений языка. При этом будем иметь ввиду вышеприведенное Правило 1, из которого следует, что каждый тип отношения может употребляться не только с аргументами из указанной области определения.

Как уже было отмечено, элементарное отношение конкретизации есть частный случай бинарного отношения, задаваемого двухместным предикатом: Class х Obj -» {"ложь", "истина"}.

Элементарные бинарные отношения с указанной областью определения отнесем к типу COBin. Помимо них, в языке могут быть заданы элементарные бинарные отношения типов OCBin и OOBin: К е COBin: Class х Obj -> {"ложь", "истина"},Я е OCBin: Obj х Class -> {"ложь", "истина"},Я е OOBin: Obj х Obj {"ложь", "истина"}.

Дадим теперь интерпретацию элементарных бинарных отношений всех трех типов:I(K) ç UNIV х UNIY, где 11 е OOBin,1(11) ç 2UNIV х UNIY, где Я е COBin,I(Я) ç UNIV х 2univ, где К е OCBin.

Семантика отношений.

Рассмотрим теперь все типы отношений языка и определим их денотативную семантику.

Мы уже рассматривали интерпретацию отношения конкретизации, однако, оно является бинарным отношением из COBin, и поэтому может быть интерпретировано также и следующим образом.

Это также согласуется с приведенной ранее интерпретацией неэлементарного отношения конкретизации, и, следовательно, запись А:В по умолчанию означает, что перед В опущено служебное слово EACH.

Объект-класс представляет в концептуальной памяти множество элементов, имеющих общие атрибуты. Записью а(В) мы утверждаем факт наличия атрибута В у экземпляра а, т.е., класс В выражает некоторое свойство данного экземпляра. Назначение А(В) классу А атрибута В означает, что все экземпляры класса А имеют этот атрибут, иными словами, класс В обозначает некоторое свойство, общее для всех экземпляров класса А. В качестве атрибутов могут указываться лишь классы.

Из этого неформального определения видно, что элементарное отношение "атрибут" представляет собой отношение из OCBin.

Для произвольных класса В, экземпляра а и Яиз OCBin:1( а К В ) = 1 тогда и только тогда, когда (1(я), 1(B) )el(К),I( а К В ) = 1 тогда и только тогда, когда (1(a), 1(B) )gl(К).

Если же мы употребляем класс в качестве первого аргумента, то, согласно Правилу 1, для произвольного класса А запись EACH А К В будет означать: I(EACHAftB)=l«>(VxeUNIV) [х е 1(A) (х, 1(B)) € I(К); (х, 1(B)) £ 1(Я) х * 1(A)].

Тогда интерпретация элементарного отношения "атрибут":1(а(В))=1 о (1(a), 1(B) )el( <()'),I( а(В) ) = 1 ( 1(a), 1(B) )й1('()' ),где '()' используется для символьного обозначения отношения "атрибут".

В записи А(В) по умолчанию опускается служебное слово EACH: I(A(B)) = 1 «(VxeUNIV) [х е 1(A) (х, 1(B)) е 1('()'); (х, 1(B)) « 1( '()')-> х * 1(A)].

Другими словами, эта запись означает, что 1(А)х1(В) с 1('()' ).

Чтобы определить семантику отрицания Х(У), рассмотрим снова произвольные классы А и В. Как было уже сказано, отношение А(В) интерпретируется как отношение вложения следующих множеств:1(А(В))=1« 1(А)х1(В) с 1('()'), где 1(А) с иШУ, а 1(В) еПоэтому отрицание отношения А(В) интерпретируется как отрицание этого отношения вложения: 1(А(В))=Ю 1(А)х1(В) <£ 1('()'), что означает:1(А(В)) = 1 « (ЗхеШ1У) [х € 1(А); (х, 1(В)) £ 1( '( )')]. Согласно этой интерпретации можем определить денотативную семантику отрицания неэлементарного отношения "атрибут": (УХ,У) [Х(У) <н> (Зх) (X : х; х(У)) ].

Таким образом, отрицание отношения Х(У) означает, что существует некий представитель класса X, для которого У не является атрибутом.

Мы получили тот же результат, что и при рассмотрении только теоретико-множественных операций.

ПримерЕсли в концептуальной памяти есть факт: Человек(Длинаволос), то это значит, что существует некий экземпляр класса Человек, обозначим его #, для которого выполняется:Человек : #; #(Длинаволос).

Как мы видим, в языке введено всего одно отношение типа СОВш и одно отношение типа ОСВт. Разумеется, можно было и не выделять отдельные типы для отношений конкретизации и "атрибут", а лишь исследовать эти отношения сами по себе. Однако проведенное исследование отношений указанных типов позволяет выделить свойства, обшие для всего типа, а не характерные лишь для конкретного отношения. На данный момент язык имеет фиксированный набор отношений, однако он не ограничен этим набором. При дальнейшем практическом использовании может возникнуть необходимость введения в язык новых отношений. Поэтому в данной работе введена общая интерпретация и семантика для всех отношений типа СОВш и ОСВт, что позволит в дальнейшем вводить новые отношения этих типов.

В языке есть средство для задания произвольных бинарных отношений между экземплярами. Такое отношение называется связкой. В качестве связки, т.е. имени отношения, может выступать любой класс, имя которого пишется в кавычках. Если связка задается между классами или между классом и экземпляром, то по умолчанию принимается, что данное отношение распространяется на все экземпляры данного класса. Если же мы хотим указать, что данное отношение выполняется только длянекоторых экземпляров данного класса, то перед именем класса указывается служебное слово SOME. Примервася "Купил"коза Лиса "Меньше" Волк Лошадь "Ест" SOME РастениеИз определения видно, что связка задает бинарное отношение типа OOBin.

Если же мы в качестве какого-либо аргумента употребляем класс, то, согласно Правилу 1, для произвольных классов А и В: I(A ft В) = 1 <=> (Vx,yeUNIV) [х е 1(A), у е 1(B) -> (х, у) е I(Я);(х, у) f£ \{Я), x g 1(A) у е 1(B);(х, у) «s ЦП), у б 1(B) чхй 1(A)].

Для задания значений атрибутов в языке предусмотрено трехместное отношение "атрибут со значением". Запись а(В.с) означает факт наличия у экземпляра а атрибута В со значением с. Фактически, это отношение представляет собой комбинацию отношений "атрибут" и конкретизации, поскольку в записи а(В.с) класс В есть атрибут экземпляра а, и в то же время экземпляр с представляет собой значение В, т.е. является конкретизацией класса В. Однако, одними бинарными отношениями здесь не обойтись, поскольку данное отношение связывает между собой три сущности: сам объект, его атрибут и значение этого атрибута для данного объекта.

Мы можем также указать значение атрибута для всех объектов класса: запись А (В.с) означает, что каждый экземпляр класса А имеет атрибут В со значением с. В то же время указывая вместо значения атрибута некоторый класс: я(В.С), мы тем самым указываем, что данный экземпляр значением атрибута В имеет некоторый экземпляр из класса С. Запись А(В.С) означает, что каждый экземпляр класса А имеет значением атрибута В некоторый экземпляр из класса С.

Дадим интерпретацию отношения "атрибут со значением" как комбинации отношений "атрибут" и конкретизации. Учитывая, что эти отношения относятся к типам OCBin и COBin, рассмотрим сначала в общем виде комбинацию отношений этих типов.

Интерпретацию неэлементарного отношения 7*27*2 введем согласно Правилу 1.

Теперь мы можем рассматривать интерпретацию отношения "атрибут со значением" как частный случай комбинации отношений типов OCBin и COBin.

Здесь '(.)' использовано для символьного обозначения отношения"атрибут со значением".

Последнее означает, что для произвольных класса В и экземпляров а, с: а(В.с) => а(В); В:с. В:с v а(В) => а(В.с).

Т.е. элементарное отношение "атрибут со значением" удовлетворяет следующему правилу:(Vx, Y, z) [ (x(Y.z) -» x(Y); Y : z); ((- x(Y) v Y : z) -» x(Y.z)) ] ПримерПусть в концептуальной памяти зафиксирован факт мурка(Окрас.рыжий). Согласно приведенному правилу, система вывода должна получить также факты, что мурка имеет атрибут Окрас: мурка (Окрас) и что экземпляр рыжий является конкретизацией класса Окрас: Окрас : рыжий.

Рассмотрим интерпретацию неэлементарного отношения "атрибут со значением". Согласно неформальному определению выражений А(В.с), я(В.С) и А(В.С), в языке приняты следующие умолчания:А(В.с) = EACH А(В.с), я(В.С) = а{В. SOME С), А(В.С) = EACH А(В. SOME С).

Поскольку отношение "атрибут" в языке используется для фиксации свойств объектов, эти три способа употребления неэлементарного отношения "атрибут со значением" являются наиболее распространенными. При необходимости задания иной интерпретации неэлементарного отношения "атрибут со значением" служебные слова EACH и SOME указываются явно.

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

Учитывая данное неформальное определение и приведенную выше интерпретацию отношения "атрибут со значением", дадим интерпретацию автонимного подкласса: I(A[B.c]) = { xeUNIV | xel(A); (х, 1(B), 1(c)) е 1( <(. )' )}, I(A[B.C]) = { xeUNIV | xel(A); (ByeUNIV) (yel(C), (х, 1(B), у) е I( '(•)') }• Из такой интерпретации явно следует: 1(А[В.с]) с 1(A) е UNIV, 1(А[В.С]) с 1(A) ç= UNIV.

Выводы.

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

Был определен смысл операции "отрицания" все виды"отрицаний" отношений языка могут быть сведены к "отрицанию" элементарных отношений и проинтерпретированы через отношение НЕ принадлежности элементов множеству.

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

2. Дедуктивная модель предметной области. Реализация логического вывода в рамках дедуктивной моделиВ главе 1 были определены основные понятия и отношения формального языка. В базе знаний реализовано совместное хранение фактов и правил, записанных с использованием отношений формального языка. Факты и пользовательские правила, т.е. все, что пользователь желает зафиксировать в базе знаний, хранятся в концептуальной памяти системы. Единицей хранения является терминал— структура, в которой хранится вся информация об одном предикате отношения: тип отношения, значения его аргументов, а также вхождение. Вхождение для предиката отношения есть его место в общей базе знаний и имеет значение, например, когда данный предикат входит в какое-либо правило. В этом случае в поле вхождения помечается правило - владелец отношения.

Ключами поиска при извлечении информации из концептуальной памяти являются константы, входящие в отношения. Это означает, что при поиске в концептуальной памяти могут быть найдены только вычислимые терминалы. Этим обусловлено требование вычислимости конъюнкций, входящих в посылку и следствие пользовательских правил.

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

Эрбрановский универсум НИ есть множество всех константных термов базы знаний, т.е. в нашем случае совпадает с множеством всехконстант: HU = Class u Obj. Необходимо отметить, что в отличие от эрбрановского базиса обычных дедуктивных систем, HU содержит константы двух типов: Class и Obj.

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

Эрбрановской интерпретацией назовем произвольное множество основных предикатов из эрбрановского базиса: HI <z НВ.

Подстановка 0 есть произвольное отображение конечного набора переменных в термы 0: Var Class u Obj u Var. Основная подстановка — это подстановка, в которой используются только константные термы, т.е. 0: Var -> Class u Obj. Пусть Р(ХЬ.,Xn)— предикат, тогда 0Р =РфХ\,0Хп) = P(t\,., £0- То есть, 0Р получается заменой каждоговхо;кдения переменной в Р на соответствующий терм.

Две формулы А и В унифицируются, если существует подстановка 0такая, что 0Л = 0"В. При этом подстановка 0 называется унификаторомвыражений А и Ъ. Унификатор 0 называют наиболее общим для А и В, еслидля любого другого унификатора 0i этих формул найдется подстановка 02, такая, что 0] = 02 0.

Рассмотрим некоторую эрбрановскую интерпретацию HI с НВ и определим относительно нее значения истинности для конструкций формального языка.

Будем говорить, что основной предикат Ъ истинен в Н1, если и только если Ъ е Н1. Будем говорить, что основной предикат Ъ "ложен" в Н1, если В е Н1. Если не выполняется ни Ъ е Н1, ни е Н1, будем говорить, что значение Ъ в Н1 не определено. (Возможность этой третьей альтернативы и отличает связку от логического отрицания). Таким образом, мы говорим, что основной предикат Ъ "ложен" в Н1, если основной предикатЪ истинен в Н1.

Предикат Р истинен в Н1 тогда и только тогда, когда существуетосновная подстановка 0 такая, что основной предикат 0Р истинен в Н1.

Таким образом, предикат Р истинен в Н1 тогда и только тогда, когда существует факт, с которым унифицируется данный предикат. Будем говорить, что предикат Р "ложен" в Н1 тогда и только тогда, когдасуществует основная подстановка 0 такая, что основной предикат 0Р истинен в Н1. Если не выполняется ни одно из приведенных условий, будем говорить, что значение Р в Н1 не определено.

Таким образом, интерпретация Н1 сопоставляет каждому предикатному символу Р отношение на Ни, содержащее кортежи.,такие, что основной предикат Р^,.,^) истинен в Н1, т.е.

Р(£\, •••, е Н1. Аналогично, интерпретация Н1 сопоставляет каждомупредикатному символу Р отношение на Ни, содержащее кортежи., такие, что е Ш.

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

Конъюнкция формул Р= Р\, Рг истинна в Н1 тогда и только тогда,когда существует основная подстановка 0 такая, что формулы дР\ и 0Р2истинны в Н1. Будем говорить, что конъюнкция формул Р=Р\;Р2 "ложна" в Ш тогда и только тогда, когда истинна дизъюнкция формул Р\ V Р2.

Дизъюнкция формул Р= Р\ V Р2 истинна в Н1 тогда и только тогда, когда существует основная подстановка 0 такая, что либо формула 0Р\, либо 0Р2 истинна в Н1. Будем говорить, что дизъюнкция формул Р = Р\ V Р2 "ложна" в Н1 тогда и только тогда, когда истинна конъюнкцияформул Рь Р2. Правило*Ри. ;Рп<== ;Кп),истинно в Н1 тогда и только тогда, когда для каждой основной подстановки 0, для которой формула 0(((2ь. V. V (Ки ■ •• ;Кп))истинна на Н1, формула 0(Рь. ;РП) также истинна на Н1.

Интерпретация Эрбрана Н1 называется моделью Эрбрана для базы знаний, если каждый факт базы знаний и каждое пользовательское правило истинны в Н1.

Пусть Н1 — модель для базы знаний, а?(<2ь ••• V.— запрос к базе знаний.

Если для некоторой подстановки 0, где £=0Хь а Хь.,Хп— все переменные запроса, формула 0((С2ь. V. V (Т^;. истинна,либо "ложна" в Н1, то ответ на запрос содержит кортеж термов иинформацию об истинности или "ложности" формулы запроса при данных значениях переменных. Если в запросе нет переменных, то ответом на запрос будет "да" или "нет", если формула ((^ь. ;<38) V. V (Яь. ;Кт)соответственно истинна, либо "ложна" на Н1. Если не выполняется ни одно из этих условий, то ответом на запрос будет "неопределенность".

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

Из определения истинности дизъюнкции формул следует, что дизтэюнкция Р = Р\ V Р2 истинна в Н1 тогда и только тогда, когда либосуществует основная подстановка 61 такая, что формула в\Р\ истинна в Н1,либо существует основная подстановка 62 такая, что формула 02Рг истиннав Н1. Это означает, что дизъюнкция формул истинна тогда и только тогда, когда истинна одна из формул, входящих в дизъюнкцию. Поэтому общий запрос в виде?(<&; ••• V. V (Ки. -Яп)может быть разбит на подзапросы:.??№;. ;К0,каждый из которых может решаться отдельно.

Обозначим совокупность фактов базы знаний (концептуальной памяти) р, а совокупность правил 5. Тогда концептуальная памятьпредставляет собой 5ир. Поскольку совокупность правил 5 может быть представлена в виде эквивалентной совокупности хорновских правил, можем считать, что вся концептуальная память представляет собой множество хорновских дизъюнктов. Напомним определение: хорновский дизъюнкт - это дизъюнкт, содержащий не более одного положительного литерала, т.е. в общем случае А V V. V -.Вп.

Таким образом, мы имеем множество хорновских дизъюнктов Зири запрос в виде конъюнкции предикатов С}.

Определение 1. Дизъюнкт V является следствием множества дизъюнктов 5, если любая модель Эрбрана 5 является также моделью Эрбрана для D.

Нам необходимо решить вопрос об истинности формулы запроса. Иными словами, необходимо найти такие подстановки 0, что основные предикаты, полученные применением 0 к предикатам из Q, являются следствиями множества 5ир.

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

В более общем виде, перед нами стоит задача: определить денотат предикатного символа Р в Sup, т.е. определить, что означает предикатныйсимвол Р в соответствии с множеством фактов ри набором правил S.

Ван Эмденом и Ковальски [32] было разработано три вида семантики логических программ, в каждой из которых в качестве денотата предикатного символа определялось некоторое вычислимое отношение. Приведем определения денотата предикатного символа в соответствии с каждым из видов семантики логических программ.

Операционная семантика задает в качестве денотата Р в множестведизъюнктов Sup:D1(p)={(ti,.,tO: SuP I-Р(Ь,.,Ь)},т.е. кортеж термов (tj,., t^) принадлежит денотату Р, если и только если предикат P(t{,., Q выводим из Sup с помощью какой-либо корректной системы вывода.

Основное достижение исследования ван Эмдена и Ковальски состоит в получении доказательств эквивалентности всех трех видов семантики для логических программ на языке хорновских дизъюнктов, при условии полноты системы вывода, определяющей денотат D\(P) [32, 50].

Определение 2. Пусть 5- множество хорновских дизъюнктов.

Обозначим cons(S) множество всех основных предикатов, являющихся следствиями S:cons(5) = {F| FeHB;5|=F).

Теорема 1.cons(5) = пМ(5), где М(5) - совокупность всех моделей Эрбрана S.

При этом cons(S) является моделью Эрбрана S.

Доказательство теоремы приведено в [53, с. 118]. Заметим, что вид термов и правил, используемых при доказательстве запроса, совпадают для Дейталога и исследуемого формального языка, поэтому доказательство будет справедливо и в нашем случае.

В [32] было показано, что:lfp(TUF) = nM(5uF). Следовательно, согласно теореме 1, cons(Suf) = lfp(T u ), откуда следует:S гСвойство cons. Основной предикат А принадлежит cons(Suf) тогда итолько тогда, когда либо А принадлежит F, либо содержитправило:j4o <=— А\,. ',Ат,и существует подстановка ст такая, что А = Aqg и основные предикаты Ai<j,. т4та принадлежат cons(5uF).

Теперь можем сформулировать стоящую перед нами задачу следующим образом:для данного множества хорновских дизъюнктов и целевогопредиката Рнеобходимо вычислить cons(Svf)r\P.

Алгоритм доказательства запроса к базе знаний без учета семантики отношенийМетод логического вывода при доказательстве ответа на запрос к концептуальной памятиОграничим пока наше рассмотрение только концептуальной памятью. Сама по себе концептуальная память может рассматриваться как база знаний, состоящая из фактов и пользовательских правил. В главе 1 было показано, что конъюнкция пользовательских правил эквивалентна конъюнкции хорновских правил, следовательно, можем рассматривать концептуальную память как совокупность основных предикатов и хорновских правил. В предыдущем параграфе было показано, что мы можем ограничиться рассмотрением запросов в виде вычислимых конъюнкций предикатов.

Обозначим совокупность фактов концептуальной памяти р, а совокупность правил 5. Рассмотрим запрос к концептуальной памяти в виде предиката Р. Задача доказательства запроса тогда формулируется следующим образом:для данной концептуальной памяти 5ир и целевого предиката Рнеобходимо вычислить сопб(5и?г)пР.

Для решения этой задачи будем использовать нисходящий вывод на основе метода 8ЬВ-резолюции.

Это означает, что исходная цель 1Р представляется в виде утверждения:\/К: -1 Р(В,К), где Х - все переменные, входящие в целевой предикат, а Ъ - все входящие в него константы.

С помощью метода резолюции предпринимается попытка опровержения этого утверждения путем генерации контрпримеров, т.е. с помощью поиска констант А таких, что 5ир\=Р(В,А). Множество контрпримеров {Р(В,А)} является ожидаемым ответом на запрос. Если цель \/Х: -.Р(В,Х) не может быть опровергнута с помощью резолюции, то решение представляет собой пустое множество. Каждый вариант доказательства несправедливости цели Л/К: -нР(В,Х) называетсяопровержением цели ?Рна основе 5ир.

Опишем основные понятия используемого метода резолюции.

Вспомним теперь, что в общем случае рассматриваемый нами запрос к концептуальной памяти представляет собой вычислимую конъюнкцию предикатов. Формируемая нами цель представляет собой отрицание формулы запроса, а значит, цель есть дизъюнкт, состоящий из одного или более отрицательных литералов (а значит, по определению хорновский дизъюнкт).

Функция выбора есть отображение, соотносящее каждой цели один из ее литералов. [53, с. 149]Цель может производить резольвенту с помощью либо факта, либо пользовательского правила. Резольвента — это цель или пустой дизъюнкт. Пусть Е= -1К1 v.v v.v -иКк — цель и пусть К —пользовательское правило вида: Уь.; У3 <= Ц;.; Ц. Пусть у— функциявыбора, такая, что Ь(Е)=К\. Предположим также, что в следствии правилаимеется предикат унифицирующийся с Кь т.е. существует 0: 0 = К,0.

Правило М;.; И <= Ц;.; Ц может быть представлено в виде эквивалентной конъюнкции правил:М <= Ц;.; и, Ц <= Ц;.; и, У5<= и,.; и.

Резольвентой цели Е и хорновского правила V) <= Ц;.; Ц в соответствии с функцией выбора ^является цель:К = -.К 10 -,7^-10 V-!¿,10 v.-1Ln0 v-1Ki+l0 -,КкЭ,а следовательно, можем определить Н как резольвенту цели Е и правила К в соответствии с функцией выбора УФункцию выбора у определим в соответствии с ограничением вычислимости предикатов:будем использовать функцию выбора у извлекающую наиболееозначенный литерал из каждой цели, т.е. литерал, содержащий наибольшее количество констант (если существует несколько таких литералов, выбирается самый левый).

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

Если следствие правила "К содержит более одного предиката, унифицирующегося с выбранным предикатом цели, то правило И может образовывать более одной резольвенты с данной целью. В этом случае определяется дополнительная функция выбора которая припервом обращении к правилу с данным предикатом цели выбирает самый левый унифицирующийся с ним предикат, а при каждом последующем обращении следующий еще не выбиравшийся унифицирующийся предикат.

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

Пусть теперь £ = ->К\ V. V -.К, V. V — цель и пусть — факт. Пусть и существует унификатор для К* и Ь. К, 0 = Ь 6.

Тогда резольвента цели £ и факта I. в соответствии с функцией выбора у состоит из дизъюнкта:Н = -.£16 V.V 10 ч^Кнв v.v-^^<kQ,т.е. это цель, полученная из Е удалением К, и применением 0 ко всем литералам.

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

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

Пусть 5up— множество дизъюнктов концептуальной памяти, Q — цель, у и у— функции выбора.SLD-опровержение для SupOQ при у и у состоит из конечной последовательности целей Qq(= Q),., ( = пустой дизъюнкт) последовательности дизъюнктов Ci,., С„ и последовательности подстановок 0Ь., 0П, таких, что выполняются следующие условия:— каждый дизъюнкт Ci(l<i<n) есть либо дизъюнкт из Suf, либовариант дизъюнкта из 5ир;— каждая цель Gj\ (l<i<n) является резольвентой дизъюнктов и Q при функциях выбора Уи у;— при l<i<n 0i есть наиболее общий унификатор, используемый при резолюции и Q.

Каждое SLD-опровержение можно представить линейным деревом опровержения.

Опровержение цели Q = -iP(ti,., с помощью SLD-резолюцииэквивалентно доказательству того, что основная реализация P(t\, может быть выведена из заданного множества дизъюнктов. Такой основной дизъюнкт называется контрпримером цели В самом деле,существование такой реализации противоречит утверждению цели Gj.

Различные опровержения одной и той же цели могут вести к различным контрпримерам. При каждом опровержении генерируется только один контрпример, который состоит из основной реализации P(tj,., tQ, образуемой последовательным применением всех встречающихся в процессе вывода унификаторов 0Ь 02,0П к., t0. Другими словами,контрпример равен P(t., tk)0, где 0 = 0i02.0nНазовем подстановку 0 = 0iO2.0n, связанную с данным SLD-опровержением, ответной подстановкой, генерируемой этим опровержением.

Теорема 1. (Корректность SLD-резолюции)Пусть Sup— множество дизъюнктов концептуальной памяти, Q — цель вида -iP(tI,., tk). Для любого SLD-опровержения и ответнойподстановки 0:SuF \=P(tu.,tk)0i02.0„.

Теорема 2. (Полнота SLD-резолюции)Пусть 5о— множество хорновских дизъюнктов, (q— цель вида -лP(ti,., tk), а У— функция выбора. Если существует основная реализация С для P(tu., tQ, такая, что 5о |= С (т.е. если существует контрпример С для Q), то существует SLD-опровержение в соответствии с У иответной подстановкой 0, такой, что С = P{t\,iQ0.

Доказательство теорем 1 и 2 можно найти в [10, 18, 32, 17].

На основании теоремы 2 можем сформулировать теорему полноты SLEt-резолюции с применением пользовательских правил.

Теорема 3.

Пусть 5uF— множество дизъюнктов концептуальной памяти, Q — цель вида P(ti,., tQ, а у у — функции выбора. Если существует основная реализация С для P(tu., tQ, такая, что Suf |= С (т.е. если существует контрпример С для Q), то существует SLD-опровержение SufvGi в соответствии с уи у и ответной подстановкой 0, такой, что С = P(ti.,tQ0.

Доказательство.

Полнота 8и>резолюции с использованием хорновских правил и основных предикатов утверждается теоремой 2. Значит, достаточно показать, что каждое БиЗ-опровержение для при У и уэквивалентно БЬВ-опровержению для множества хорновских дизъюнктов и цели <5 при функции выбора УРассмотрим произвольное пользовательское правилоЯ: Уь.; У3 <=.; Iш которое может быть представлено в виде эквивалентной конъюнкции хорновских правил:У] <= и.; и,^ <= I,;.; (1)у8<= Ц-,.; иРассмотрим БЬВ-опровержение, в котором цель (я является резольвентой цели и правила К при функциях выбора У и у. Предположим, что в следствии правила К есть несколько предикатов, унифицирующихся с предикатом цели выбранным в соответствии с функцией выбора у Это значит, что может быть построено несколько БЬБ-опровержений, в которых цель является резольвентой цели и правила К. Каждое из этих БЫЗ-опровержений соответствует очередному предикату следствия К, выбранному в соответствии с функцией выбора у. Фактически же в каждом из этих 8ЬВ-опровержений цель является резольвентой цели при функции выбора уи очередного правила из (1), соответствующего очередному предикату следствия К.

Итак, каждое БЦО-опровержение, в котором цель Од является резольвентой цели и правила К в соответствии с функциями выбора У и у, есть ЭЫЭ-опровержение, в котором цель ^ является резольвентой целии хорновского правила в соответствии с функцией выбора у В силу произвольности выбора это означает, что каждое БЬО-опровержение для ЭириС} при У и у эквивалентно 81Л>опровержению длямножества хорновских дизъюнктов и цели (? при функции выбора у Теорема доказана.

Заметим, что теорема о полноте БХЛ^-резолюции лишь утверждает, что с помощью 8иЗ-резолюции можно сгенерировать все контрпримеры, соответствующие всем основным реализациям цели, следующим изОднако, она не определяет стратегию вычисления, позволяющую получить все контрпримеры цели. Поэтому окончательно полнота вывода, построенного на основе метода 81Л)-резолюции, определяется стратегией вычисления, используемой для получения всех контрпримеров.

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

При таком методе перебора дизъюнктов возможно зацикливание при вхождении в бесконечную рекурсию. Возникает проблема остановки, для решения которой нужно либо исследовать динамическое поведение программы, либо искусственно ограничивать глубину рекурсии какой-либо заранее заданной величиной. На данный момент в реализованномалгоритме принято решение об искусственном ограничении глубины рекурсии, что ведет к потере полноты.

Обозначим описанный выше алгоритм нисходящего вывода на основе SLD-резолюции Query((?). Поскольку к началу вычислений набордизъюнктов концептуальной памяти фиксирован, будем считать, чтона входе алгоритма всегда находится запрос к базе знаний в виде вычислимой конъюнкции предикатов. Результатом работы алгоритма является набор подстановок {0i,.,0k} — значения переменных запроса Q, при которых истинность формулы запроса выводится из истинности фактов и пользовательских правил в концептуальной памяти; набор 0 пуст при отсутствии таких значений.

Согласно теореме 1, при фиксированном множестве дизъюнктов концептуальной памяти SuF и цели <5 вида -if(ti,., tk), если результатомработы Query((?) является набор подстановок {Gi,.,0k}, т.е.SuF I Query TO,.,i0eb. Svf | QuerytoSuF |=P(ti,.,i00i,. 5uF|=TO,.,iQ0k.

Т.е. утверждается корректность вывода при помощи алгоритма Query(Ci).

Специфика реализации алгоритмаНеобходимо отметить, что на данный момент устройство концептуальной памяти накладывает еще одно ограничение, ведущее к потере полноты. Это ограничение вытекает из ограничения вычислимости предикатов. Как было сказано в главе 1, ограничение вычислимости естественным образом вытекает из несоизмеримости возможного количества констант языка и количества предопределенных в языке типов отношений. В связи с этим, невозможно искать нужный предикат в базе, перебирая все предикаты заданного типа (поскольку их количество можетсоставлять десятки, а то и сотни тысяч). Поэтому ключом для поиска предиката в базе являются константы, входящие в отношение. Отсюда вытекает ограничение: при непосредственном поиске предиката в концептуальной памяти могут быть найдены только предикаты, непосредственно содержащие те константы, которые входили в предикат, являющийся запросом на поиск. Отсюда вытекает ограничение совместимости предикатов правила и цели.

Выше было введено условие применимости правила % при вычислении целевого предиката Р: наличие в конъюнкции следствия К предиката унифицируемого с Р. Теперь необходимо уточнить это условие, а именно:правило К применяется для получения резольвенты с целевымпредикатом Р, если конъюнкция следствия К содержит вычислимый предикат совместимый с Р.

Определение. Два предиката, и Р, совместимы, если:а) существует унифицирующая подстановка 0: С>0 = РЭ;б) хотя бы одно аргументное место этих предикатов замещено общей константой.

Пример.

Предикаты А:В и А:Х являются совместимыми, а предикаты Х:Ь и А:у не являются совместимыми, хотя и являются унифицируемыми.

Как видим, ограничение совместимости предикатов правила и цели приводит к тому, что в процессе вывода будут перебраны не все правила, производящие резольвенту с предикатами цели. Это может привести к потере некоторых решений, а значит, к потере полноты вывода.

Можем утверждать, однако, что количество решений, потерянных из-за ограничения совместимости предикатов, будет невелико. Действительно, количество предопределенных в языке отношений ограничено и невелико, тогда как количество констант может быть огромно. Именно константы являются основной значимой единицей отношения, определяющей его67смысл. Следовательно, невелика вероятность того, что два отношения, связанные только типом отношения и не имеющие общих констант, могут быть связаны по смыслу.

Рассмотрим особенности практической реализации вызова правил, обусловленные ограничением совместимости предикатов.

Для непосредственного поиска предиката в концептуальной памяти существует две функции, одна из которых ищет предикаты, соответствующие искомому предикату запроса, среди фактов, записанных в концептуальной памяти, а другая ищет их в следствиях всех правил, записанных в концептуальной памяти. Обозначим функцию непосредственного поиска предиката в следствиях правил концептуальной памяти СеЫ1и1е(^). Предположим теперь, что функцией выбора У втекущей цели определен предикат V и нам необходимо найти в концептуальной памяти пользовательское правило, следствие которого содержит предикат, совместимый с V. Если предикат Р содержит толькоодну константу, то Се1Ыи1е(Р) найдет все предикаты, совместимые с V.

Если же предикат V содержит более одной константы, то Се1:Яи1е(Р)найдет лишь те предикаты, которые содержат все константы Р насоответствующих местах. Поэтому по предикату V подготавливаетсянесколько запросов для Ое1Яи1е(Р): каждый предикат содержит одну изконстант V на соответствующем месте, остальные же аргументные места заменены переменными. Затем поочередно выполняются запросы Се111и1е(Я) для всех 1 и совокупность предикатов, найденных в результатевсех, запросов Ое1Ки1е(Я), представляет собой совокупность всех совместимых с Р предикатов, содержащихся в следствиях правил концептуальной памяти.

ПримерПусть, например, в текущей цели функция выбора определила предикат А(В.Х). Тогда в концептуальную память отправляется 2 запроса:GetRule(A(Y.X)) и GetRule(Z(B.X)), где Y и Z — новые переменные, ранее не присутствовавшие в цели.

Пусть в концептуальной памяти есть правила, следствия которых содержат предикаты А(В.Х1), Х2(В.ХЗ), X4(B.D) и А(Х5.С) соответственно. Каждое из этих правил содержит предикат, совместимый с предикатом А(В.Х).

Запрос GetRule(A(B.X)) сможет найти только правило, содержащее А(В.Х1). Запэос GetRule(A(Y.X)) найдет правила, содержащие А(В.Х1) и А(Х5.С), а запрос Get.Rule(Z(B.X)) найдет правила, содержащие А(В.Х1), Х2(В.ХЗ), X4(B.D), т.е., оба запроса вместе найдут все правила, содержащие предикаты, совместимые с предикатом цели. При этом найденное дважды правило, содержащее А(В.Х1), во второй раз применяться не будет.

Оптимизация алгоритмаЕсли задающему запрос не требуется знать все решения, а необходимо быстро получить хотя бы часть решений, допустимо использоватьследующую оптимизацию алгоритма Query((£).

Пусть Е- —iTCi v. v -iKi v. v -,Кк — цель и пусть К — пользовательское правило вида: V\\.; Vs <= L\;.; Ц. Пусть &(E)=Ki и в следствии правила есть предикат Vji, совместимый с предикатом Vji 9 =KiQ.

Предположим также, что в следствии правила имеется несколько предикатов V^i, Vj2,., унифицирующихся с несколькими предикатамицели Кп(= К;), Kim после применения к ней подстановки 0, т.е.существует о: V^0g = KnQс при 1 < / < ш.

Тогда резольвентой цели Е и хорновского правила Vj <= L\,.; L^ всоответствии с функцией выбора ¿-является цель:и =-iKi6cy v. v —,Ki\.]Qcj v-iKn+iGa v.v-i7Cjm.i9a v-i7Cm+i0cv. v -iT^GavW,где Vf = -i L\Qg v. v—i LnBcr.

Т.е., из цели E исключены все предикаты Xi\(=Ki), Кц,., Kim и добавлено отрицание посылки правила.

Действительно, применим подстановку 9ст к правилу V\,.; Vs <= Li;.; I« и к цели Е= —1К.1 v. v —i7CkПравило VjOa;.; Vs0a <= Ц0ст;.; ¿.„Ост может быть представлено в виде эквивалентной конъюнкции правил: Vi0a <= LjBct;.; Ц0а,(Xii0a= )Vji9a <= LjGo;.; ЦОс,(Xi20a= )Vj20a <= Lj0a;.; ^Ba,(2)(7C0CT- )Vjm0c <= LjGa;.; Ц0а,К0ст<= /-10с;.;Образуем резольвенту цели -нК.10а v. v -чКк0а и хорновского правила из (2) со следствием \zji0a.

Затем образуем резольвенту полученной цели и хорновского правила из (2) со следствием \^20ст.

Затем образуем резольвенту полученной цели и хорновского правила из (2) со следствием \^т0ст.

В итоге, учитывая, что М V XV = XV, получим указанную выше цель Н.гЕсли существует несколько вариантов унификации предикатов правила и цели при различных комбинациях пар предикатов, то правило К может образовывать более одной резольвенты с данной целью. В этом случае определяется дополнительная функция выбора ^К), которая перебирает все возможные комбинации предикатов. Таким образом, при фиксированных функциях выбора у и & резольвента цели и правила определяется однозначно.

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

Пример 1.

Пусть концептуальная память содержит факты D:e; а1"С"е, a(B.d) и правило:Рассмотрим запрос к концептуальной памяти ?D:z; x1"C"z.

Применяя к этому запросу алгоритм Query, формируем цель:El = -i D:z V -i х1 "С" z.

Согласно функции выбора ¿(El) = D:z, цель образует резольвенту с правилом (3), 9i = {z/y}:Е2 = х(В.у) V —i х1 "С" у.

В концептуальной памяти нет правила, применимого к ¿(€2) = х(В.у), но есть факт a(B.d), с которым Е2 образует резольвенту при 02 = {х/а, y/d}:ЕЗ = x1"C"d.

Цель ЕЗ образует резольвенту с правилом (3). Переименуем переменные в правиле (3) так, чтобы их имена не совпадали с ранее использованными переменными:D:y; х "С" у <== х(В.у).(3)D:y'; х' "С" у' <== х'(Ву).(3)'Тогда резольвента цели ЕЗ и правила (3)' при 03 = {y'/d; х1/х'}:Е4- = -, x'(B.d).

В концептуальной памяти нет правила, применимого к х'(В.у), но есть факт a(B.d), с которым Е4- образует резольвенту при 94 = {х'/а}, причем резольвентой является пустой дизъюнкт.

Получено первое доказательство истинности формулы запроса при 0 = Oi020304, т.е. при значениях переменных запроса: z=d, х1=а. Чтобы получить другие доказательства, применяется бэктрекинг, или обратный ход. Т.е. мы возЕфащаемся к последней цели £4-и "забываем" подстановку 04.

Других фактов или правил, применимых к Е4-, нет, поэтому возвращаемся к цели ЕЗ и "забываем" подстановку 03. Для ЕЗ также больше нет подходящих фактов и правил, поэтому возвращаемся к цели Е2 и "забываем" подстановку 02. Для Е2 также больше нет подходящих фактов и правил, поэтому возвращаемся к цели Е2 и "забываем" подстановку 02. Для Е2 также больше нет подходящих фактов и правил, поэтому возвращаемся к цели El и "забываем" подстановку 61.El = -i D:z v -i х1 "С" z.

Согласно функции выбора ¿(El) = D:z. Других правил, применимых к D:z, нет, но есть факт D:e, с которым El образует резольвенту при 0V = {z/e}:Е21 = х1 "С" е.

Цель Е2'образует резольвенту с правилом (3), 02' = {х1/х, у/е}:ЕЗ' = -i х(В.е).

Фактов или правил, применимых к ЕЗ', нет, поэтому возвращаемся к цели Е2' и "забываем" подстановку 02'. В концептуальной памяти больше нет правил, применимых к х1 "С" е, но есть факт а1"С"е, с которым Е2' образует резольвенту при 02" = {х1/а1}, причем резольвентой является пустой дизъюнкт.

Получено второе доказательство истинности формулы запроса при 0 = 0i'02", т.е. при значениях переменных запроса: z=e, х1=а1.

Чтобы получить другие доказательства, мы возвращаемся к последней цели Е2' и "забываем" подстановку 02". Других фактов или правил, применимых к Е2', нет, поэтому возвращаемся к цели El и "забываем" подстановку ©Л Других фактов или правил, применимых к ¿(El) = D:z, нет, поэтому доказательство на этом завершается.

Рассмотрим теперь тот же пример, только резольвенту цели и правила будем образовывать по способу, описанному выше.

Пример 2.

Концептуальная память содержит факты D:e; а1"С"е, a(B.d) и правило:D:y; х "С" у <== х(В.у). (3)Рассматриваем запрос к концептуальной памяти ?D:z; x1"C"z, формируемцель:El = -i D:z V -i х1 "С" z.

В концептуальной памяти нет правила, применимого к ¿(E2) = х(В.у), но есть фает a(B.d), с которым Е2 образует резольвенту при 62 = {х/а, y/d}, причем резольвентой является пустой дизъюнкт.

Получено первое доказательство истинности формулы запроса при 0 = 0^2, т.е. при значениях переменных запроса: z=d, х1=а. Чтобы получить другие доказательства, мы возвращаемся к последней цели Е2 и "забываем" подстановку 02. Для Е2 также больше нет подходящих фактов и правил, поэтому возвращаемся к цели El и "забываем" подстановку 01.

Других правил, применимых к ¿(El) = D:z, нет, но есть факт D:e, с которым El образует резольвенту при 0i' = {z/e}:Е2' = -, х1 "С" е.

Цель Е2' образует резольвенту с правилом (3), 02' = {х1/х, у/е}:ЕЗ' = -i х(В.е).

Фактов или правил, применимых к ЕЗ', нет, поэтому возвращаемся к цели Е2' и "забываем" подстановку 02'. В концептуальной памяти больше нет правил,применимых к х1 "С" е, но есть факт a1"C"e, с которым £2' образует резольвентупри 02" = {х1/а1}, причем резольвентой является пустой дизъюнкт.

Получено второе доказательство истинности формулы запроса при 0 = 0i'62", т.е. при значениях переменных запроса: z=e, х1=а1.

Чтобы получить другие доказательства, мы возвращаемся к последней цели £2' и "забываем" подстановку 02". Других фактов или правил, применимых к Е2', нет, поэтому возвращаемся к цели £1 и "забываем" подстановку О/. Других фактов или праЕШл, применимых к ¿{El) = D:z, нет, поэтому доказательство на этом завершается.

Очевидно, второе доказательство короче, так как в нем сразу оба дизъюнкта цели El образуют резольвенту с правилом (3) и в доказательстве отсутствуют шаги ЕЗ, Е4-.

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

Пример 3.

Концептуальная память содержит факты B:d; c(D.b) и правило:А:х; В:у <== x(D.y). (4)Рассматриваем запрос к концептуальной памяти ? А:х1; B:z, формируем цель:El = -i А:х1 V -п B:z.

Согласно функции выбора ¿(El) = А:х1, правило (4) содержит предикат, совместимый с А:х1 подстановкой 0 = {х1/х} но, помимо этого, правило (4) содержит предикат, унифицирующийся с B:z 0 = B:z подстановкой а = {z/y}. Поэтому определим подстановку 01 = {х1/х, z/y}. Тогда цель образует резольвенту с правилом (4):Е2 = -, x(D.y).

В концептуальной памяти нет правила, применимого к ¿(E2) = x(D.y), но есть факт c(D.b), с которым Е2 образует резольвенту при 02 = {х/с, у/Ь}, причем резольвентой является пустой дизъюнкт.

Получено первое доказательство истинности формулы запроса при 0 = 0i62, т.е. при значениях переменных запроса: z=b, х1=с. Чтобы получить другие доказательства, мы возвращаемся к последней цели £2 и "забываем" подстановку 02. Для £2 также больше нет подходящих фактов и правил, поэтому возвращаемся к цели £1 и "забываем" подстановку 01.

Других правил или фактов, применимых к ¿(£1) = А:х1, нет, поэтому доказательство на этом завершается.

В данном случае используемый метод доказательства приводит к потере решения. Чтобы продемонстрировать это, применим для его доказательства алгоритм Query.

Пример 4.

Пусть концептуальная память содержит факты B:d; c(D.b) и правило:А:х; В:у <== x(D.y). (4)Рассматриваем запрос к концептуальной памяти ? А:х1; B:z, формируем цель:£1 = А:х1 v B:z.

Согласно функции выбора ¡J(E1) = А:х1, правило (4) образует резольвенту с целью £1 при подстановке 0 = {х1/х}:£2 = x(D.y) v B:z.

В концептуальной памяти нет правила, применимого к ¿(£2) = x(D.y), но есть факт c(D.b), с которым £2 образует резольвенту при 02 = {х/с, у/Ь}:£3 = -1 B:z.

Цель £3 образует резольвенту с правилом (4). Переименуем переменные в правиле (4) так, чтобы их имена не совпадали с ранее использованными переменными:А:х'; В:у' <== x'(D.y'). (4)'Тогда резольвента цели £3 и правила (4)' при 03 = {z/y'}: = -, x'(D.y')В концептуальной памяти нет правила, применимого к ¿(£4) = x'(D.y'), но есть фаст c(D.b), с которым £4 образует резольвенту при 04 = {х'/с, у'/Ь}, причем резольвентой является пустой дизъюнкт.

Получено первое доказательство истинности формулы запроса при 6 = ОчЭгЭзЭд, т.е. при значениях переменных запроса: z=b, х1=с. Чтобы получить другие доказательства, мы возвращаемся к последней цели Е4- и "забываем" подстановку 04. Для Е4 также больше нет подходящих фактов и правил, поэтому возвращаемся к цели ЕЗ и "забываем" подстановку 93.

ЕЗ = -, B:z.

В концептуальной памяти больше нет правил, применимых к ¿(ЕЗ) = B:z, но есть факт B:d, с которым ЕЗ образует резольвенту при 93' = {z/d}, причем резольвентой является пустой дизъюнкт.

Получено второе доказательство истинности формулы запроса при 9 = Э^гЭз', т.е. при значениях переменных запроса: z=d, х1=с. Чтобы получить другие доказательства, мы возвращаемся к последней цели ЕЗ и "забываем" подстановку 93'. Для ЕЗ больше нет подходящих фактов и правил, поэтому возвращаемся к цели Е2 ■л "забываем" подстановку 02. Для ¿(Е2) = x(D.y) также больше нет подходящих фактов и правил, поэтому возвращаемся к цели Е1 и "забываем" подстановку 0!. Для ¿(Е1) = А:х1 также больше нет подходящих фактов и правил, поэтому доказательство на этом завершается.

Как видим, алгоритм Query работает дольше, но позволяет найти еще одно решение: z=d, xl=c.

Итак, при использовании метода, описанного в данном разделе, алгоритм работает быстрее, но при этом часть решений может быть потеряна. Поэтому в дальнейшем изложении будем при доказательстве опираться на алгоритм Query.

Алгоритм Query(<5) позволяет получить ответы на запрос к базезнаний, выводимые без учета семантики отношений. Он может быть использован двояким образом:— во-первых, такой ограниченный вывод позволяет существенно сэкономить время вывода и получить часть ответов, возможно, достаточную для того, кто задает запрос;— во-вторых, алгоритм С2иегу((т) может использоваться в алгоритмеполного вывода с учетом семантики отношений как вспомогательный при подборе семантических правил, применимых к предикатам запроса.

Вопросы, связанные с учетом семантики отношений при поиске ответа на запрос рассматриваются в следующем разделе работы.

Выводы.

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

Был разработан алгоритм <3иегу((?) логического вывода на системепользовательских правил. В основу алгоритма был положен нисходящий метод вывода на основе метода 8ЬО-резолюции. При реализации метода возникли следующие практические трудности:— следствие правила на формальном языке может содержать конъюнкцию предикатов;— в связи с несоизмеримостью возможного количества констант языка и количества предопределенных в языке типов отношений невозможно использовать обычный способ вызова правил по имени предиката.

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

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

Разработан метод оптимизации алгоритма С>иегу((-7),обеспечивающий более быстрое получение части ответов на запрос к концептуальной памяти.

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

Семантическая памятьВ главе 1 были определены основные понятия и отношения формального языка и введена их денотативная семантика. Анализируя денотативную семантику неэлементарных отношений, можно видеть, что неэлементарные отношения могут быть выражены через элементарные, а именно: истинность неэлементарного отношения эквивалентна выполнению некоторых правил для элементарных отношений.

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

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

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

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

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

Приведем примеры применения семантических правил:Пример 1.

Пусть, например, пользователь фиксирует в концептуальной памяти факт А(В.С). Используя правила семантической памяти для отношения X(Y.Z), и унифицируя А(В.С) с X(Y.Z), система должна автоматически сделать вывод об истинности правил:А : х => С : f(x); x(B.f(x));С : f(x) v x(B.f(x)) => А : х,и учесть эти правила при поиске ответа на запрос к базе знаний.

Пример 2.

Пусть теперь запрос содержит неэлементарный предикат A(B.Z). Как выше было сказано, истинность этого предиката может следовать не только из наличия в базе унифицирующегося с ним факта, но и из истинности соответствующих ему правил. Поэтому при поиске ответа на запрос к базе знаний (используя правила семантической памяти для отношения X(Y.Z), и унифицируя A(B.Z) с X(Y.Z)) система должна попытаться доказать истинность правил:А : х => Z : f(x); x(B.f(x));Z : f(x) v x(B.f(x)) => A : x,и в случае успеха сделать вывод об истинности исходного запроса и выдать в качестве ответа значения переменных, полученные в ходе доказательства этих праЕ1Ил.

Таким образом, правила семантической памяти используются для учета денотативной семантики отношений в процессе доказательства ответа на запрос к базе знаний.

Заметим, что хотя все переменные, входящие в семантические правила, находятся под квантором всеобщности, эти переменные могут быть разделены на два различных сорта:I — переменные, входящие в отношение, семантика которого представлена правилами,II — переменные, не входящие в это отношение.

Семантические правила формулируются для отношения в общем виде, а конкретные правила получаются в дальнейшем при унификации этого отношения с конкретными отношениями данного типа. При этом переменные сорта I участвуют в такой унификации, а переменные сорта II в такой унификации не участвуют, а используются только в процессе применения семантических правил. Таким образом, переменные сорта II никогда не входят в пользовательский запрос и оказываются как бы внутренними, скрытыми от пользователя, поэтому будем их называть системными переменными и отмечать знаком $. Так, окончательно семантические правила для отношения "атрибут со значением" имеют вид:Х(У.г) <=> { X : х$ => Ъ : х$(УТ(х$));Ъ : Г(х$) V х$(УДх$) => Х : х$ }Семантические правила для остальных неэлементарных отношений могут быть получены из их денотативной семантики способом, аналогичным вышеописанному.

Приведем здесь список семантических правил для неэлементарных отношений.

Таким образом, каждое неэлементарное отношение эквивалентно совокупности правил над элементарными отношениями. Это значит, что правая часть эквивалентности '<=>' содержит только предикаты элементарных отношений.

Можно заметить, что при построении шаблонов семантических правил для некоторых видов отношений были получены шаблоны, у которых левая часть эквивалентности содержит TRUE. Это значит, что описываемое отношение является элементарным, а соответствующие ему семантические правила выполняются всегда. Поскольку отношение элементарно, оно само входит в правую часть эквивалентности, т.е., в соответствующие семантические правила.

Как видно, факт А:В эквивалентен конъюнкции двух элементарных фактов, а не совокупности правил. Следовательно, предикат А:В есть предикат элементарного отношения, а правила (*) истинны всегда, поскольку получены из семантики отношения конкретизации.

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

Можем теперь окончательно сделать вывод о структуре базе знаний: база знаний должна состоять из концептуальной памяти, в которой хранятся факты и пользовательские правила, и семантической памяти.

Предварительные определения и обоснование выводимостиРассмотрим теперь полный алгоритм логического вывода на базе знаний. Перед нами стоит задача: учесть семантику отношений, т.е. семантические правила при выводе ответа на запрос к базе знаний.

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

Если в концептуальной памяти есть факт А:В, то мы рассматриваем следование '=>' в эквивалентности '<=>' и, унифицируя А:В с Х:У, можем сделать вывод об истинности правил:В : х$ => А: х$; (I)А : х$ => В : х$.

Следовательно, из наличия в концептуальной памяти факта А:В и истинности правил семантической памяти следует истинность правил (I). Значит, в этом случае при доказательстве любого запроса к базе знаний необходимо считать, что база знаний содержит правила (I) и использовать их в процессе вывода.

Пусть теперь запрос к базе знаний содержит неэлементарный предикат А:У. При доказательстве запроса АГУ мы рассматриваем следование '<=' в эквивалентности и, унифицируя А:У с Х:У, пытаемся доказать истинность правил:У : х$ А : х$;А : х$ => : х$,и в случае успеха делаем вывод об истинности А:У.

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

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

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

Введем обозначения.

Р(К) - произвольный п-местный предикат отношения, аргументные места которого замещены переменными из набора X. Переменные изнабора X могут быть определены в концептуальной памяти как на множестве классов, так и на множестве экземпляров.

Р(Кк) — вычислимый предикат, некоторые из аргументных мест которого применением унифицирующей подстановки X замещены константами; (Х)А,— набор (возможно пустой) переменных этого предиката, оставшихся незамещенными.

С)иегу(Р(ХА,)) = {0ь.,0т} — результат запроса к концептуальнойпамяти, представленный множеством ответных подстановок, удовлетворяющих условиям:— |= Р(Ш{) (1< { <т);— набор переменных (Х)Щ пуст, т.е. все аргументные места Р замещены константами;В частности, если набор переменных (X)X пуст, т.е. Р(КХ) — константный предикат, то Оиегу(Р(ХХ)) или пуст (Р не выводим из или равен {А,}.обозначения компонент формул, представляющие конъюнкцию нескольких предикатов отношений (в частном случае один).

С учетом введенных обозначений семантические правила для отношения, заданного предикатом Р, можно записать в виде:р(К){ А(К, ->Ъ(К, х$)} (1)Примечание:В общем случае правая часть эквивалентности 'о' может содержать конъюнкцию отношений следования вида А-/В.

Предположим теперь, что предикат Р(ХХ) вычислим, и для текущего состояния базы знаний известны все возможные подстановки {0ь.,0т}, при использовании которых Зи^^о |= Р(ХХ$[)- Тогда, учитывая, что в89семантической памяти So содержится правило (1), из SupOSo следует истинность правилА(ХШЬ х$)->Ъ(Шi, (1< i <m).

С другой стороны, предположим, что нас интересуют все возможные наборы значений переменных из XX, при которых для текущего состояниябазы знаний SufL>So Р(ХХ). Мы решим поставленную задачу, еслисможем найти полный набор {0i,.,9n} подстановок, для каждой из которых правилоявляется следствием SvfvSo.

Далее мы рассмотрим некоторые методы решения этой задачи. Запись вида (1) мы будем называть шаблоном семантических правилпредиката Р(Х), а сам предикат — владельцем шаблона. Пусть Query= {еь.,Вт}.

Согласно показанной в главе 2 корректности алгоритма Query, это означает, что 5ир |= Р(КХд\), а значит, учитывая, что правило (1)содержится в семантической памяти 5о,правила вида A(XXQ\, xSJ—tBfXXQ¡, (l<i<m) являются следствиемSufUSo.

Вернемся к исходной задаче:имеется база знаний SufUSo и запрос к ней в виде вычислимого пргдиката Р(ХХ). Нам необходимо по текущему состоянию базы знаний определить набор подстановок 0={0i,.,0n}, для каждой из которых выполняется SvfuSo |= PQiA,0j), (1<j <n).

Рассмотрим для начала случай, когда запрос Р(КХ) представляетпредикат неэлементарного отношения. Это означает, что для этого предиката отношения в семантической памяти содержится шаблон семантических правил (1), и мы будем строить 0, доказывая, что истинность выражений А(ХХви )<$)->■ ^ следует из Би^иБо.

Необходимо заметить, что при замене формулы запроса Р(ХХ) запросом вида ? А(ХХ, )<$)—>■ Ъ(Кк, правило в запросе может содержать сколемовские константы или функции. В этом случае производится следующая замена:1) сколемовские константы заменяются несистемными переменными;2) имена сколемовских функций становятся переменными, которые также необходимо означить при доказательстве запроса.

Действительно, сколемовские константы не могут быть заменены системными переменными, поскольку последние всегда находятся под квантором всеобщности.

В дальнейших рассуждениях временно опустим переменные в составе правил А(Кк, }($)->3(Кк, ^ и будем записывать их в виде А(Кк)^Ъ(Кк).

Рассмотрим, какие семантические правила могут применяться для доказательства истинности правил вида А(ХХ)—>Ъ(ХХ).

Утверждение 1.

Если существуют подстановки п и ф, такие, что правила А(Хп) ->Ъ1 (Кл) и А(Х%<\>) ->В2(Х.п§) следуют из 5ири5о, то правилоА0<В)->(Ъ1(Х&)лЪ2(Щ следует из 5ир05о для подстановки 0=7иф.

Действительно,согласно условию, любая модель Эрбрана 5ир05о является также моделью Эрбрана для правил А(Кк) —>Ы(К%) (*) и А(Хлс^) (**).

Утверждение 2. Пусть Р(Х) <=> {А(Х)-*В(К)}, Р(КХ)— вычислимый предикат, а 13(Х)=Ъ1(Х) л.л Ь^(Х). Пусть Ь(Х)— один из предикатов Ь^К). Выражение А(КХ8)—>Ъ(ХХ8) следует из Зи'риБо, если в семантической памяти найдется шаблон 0(К) <?> {С(К)—> (1(К)лТ)(К)} для которого выполняются условия:а) найдется унифицирующая подстановка п, в результате которой Ъ(ХХп)= сЦХХп);б) известен полный набор подстановок {фь., фк}, для которых выполняется о |= (1 < j <к).в) найдется унифицирующая подстановка р, такая, что для любого предиката Сг в конъюнкции С(К) найдется унифицирующийся с ним с^ в конъюнкции А(К) такой, что о(ХА,яфр)=с1|(ХА,7гфр), где фе{фь •••, Фк}В этих условиях 0=А,7тфр.

Рассмотрим подробнее условия использования утверждения 2. Условие а) определяет шаблон семантических правил в качестве кандидата на использование в доказательстве истинности правила.

Условием б) для выбранного шаблона определяется множество семантических правил, истинность которых следует из БириБо: {фь •••, фк}И, наконец, условие в) позволяет отобрать из этих правил подходящие для доказательства истинности исходного правила.

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

Предикат Ъ^,.,"^) следствия цели А(ХХ)-/В(ХХ) унифицируетсяподстановкой я с предикатом сЯ/(Уь.,\/п) следствия шаблона семантического правила, если:1) предикаты определяют один и тот же тип отношения (Ь- = ¿1/);2) термы, стоящие на одних и тех же аргументных местах предикатов, определены на одном и том же множестве (либо оба на Class, либо оба на Obj).

А также если для всех l<i<n выполняется одно из следующих условий 3)7):3) Мл: — системная переменная. Полагаем тогда п := к {Х\п / £тс};4) Мл — несистемная переменная, при этом tin не является системной переменной. Полагаем тогда тс :=п {Мтг / £тс};5} Vj7t — сколемовская константа или сколемовская функция, tji — несистемная переменная. Полагаем тогда п := тс {tin / Мтг}. При этом, если Мтг = f(x$), то 7i := тс {у / х$}, где у — новая несистемная переменная;6) tjz и Мтс — сколемовские константы, при этом tire = Мл;7) tji и Мл — сколемовские функции, аргументы которых удовлетворяют одному из условий 3) - 6) и либо имя сколемовской функции в tj не определено, либо имя сколемовской функции в tf совпадает с именем сколемовской функции, полученным при замене шаблона правила конкретным правилом, определенным фе{фь., фк }.

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

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

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

Предикат o(ti,.,t^) из конъюнкции С(Ккп§) унифицируется с предикатом c*/(Vi,.,Vn) посылки цели А(Х1п<\>) подстановкой р, если:1) предикаты определяют один и тот же тип отношения (с = О/);2) термы, стоящие на одних и тех же аргументных местах предикатов, определены на одном и том же множестве (либо оба на Class, либо оба на Obj).

А также если для всех l<i<n выполняется одно из следующих условий 3)7):3) Мр и tip — системные переменные и при этом tip = Мр;4) tip — несистемная переменная, при этом Мр — не является системной переменной. Полагаем тогда р := р р / Мр};5) Мр — несистемная переменная, £р — не является переменной. Полагаем тогда р :=р {Mp/tip};6) tip и MP — константы или сколемовские константы и при этом Мр = tip;7) £ и V, — сколемовские функции, при этом их аргументы удовлетворяют одному из условий 3) - 6), а имена совпадают.

Здесь на унификацию налагается только одно ограничение: системные переменные унифицируются, только если они совпадают. Действительно, в доказываемом правиле А(Кк) —>Ъ(Кк) в левую и правую части входят одни и те же переменные, значит, они остаются унифицированными и при применении подстановки лф. Подстановкой п предикаты из правой части доказываемого правила Ь(Кк) унифицированы с предикатами из правой части шаблона семантического правила С(К)—> с1(Х.)лТ)(К). Поскольку любая системная переменная, входящая в следствие семантического правила, входит также и в его посылку, то после унификации с^Ккп) иС(Ккп) содержат те же системные переменные, что и Ъ(Ккж). Следовательно, системные переменные, входящие в Ъ(Ккк§), должны входить и в С(Ккп§), поэтому они могут унифицироваться только с одноименными переменными в А(Ккк§).

Утверждение 3.

Если существует подстановка 0, при использовании которой правила А(Щ -> С(Щ и С(Щ 3(Щ следуют из 5иР05о, то и правило А(Щ-> Ъ(Щ следует изДействительно,согласно условию, любая модель Эрбрана является такжемоделью Эрбрана для правил А(Щ С(ХВ) (*) и С(ХВ) -> Ъ(Щ (**). Это означает, что если существует такая подстановка а, что конъюнкция основных предикатов А(Кда) принадлежит модели Эрбрана то,согласно (*), и конъюнкция основных предикатов С(Х0ст) принадлежитмодели Эрбрана а значит, согласно (**), и конъюнкция основныхпредикатов 3(Х8а) принадлежит модели Эрбрана Это означает,что любая модель Эрбрана является также моделью Эрбрана дляправила А(ХВ) В(Кд), т.е. правило А(Хв)^> В(Х!д) следует изУтверждение 4 отражает суть метода, используемого для вывода истинности правил.

Утверждение 4. Пусть Р(Х) <=> {А(Х.)->Ь(К)}, Р(ХХ)— вычислимый предикат, а Ъ(Х) — один из предикатов конъюнкции В(Х). Правило А(Х1в) —>Ъ(КЩ следует из 5о, если в семантической памяти найдется шаблон <2(Х) <=> {С(К)-хЯ(К)л'0(Х)} для которого выполняются условия:а) найдется унифицирующая подстановка к, в результате которой Ъ(ХХ п)= (Я(КХк);б) известен полный набор подстановок {фь., фк}, для которых выполняется 5иК>'5о |= С2(ХА,лф), (1< ] <к).в) найдется унифицирующая подстановка р, такая, что для любого предиката Се в конъюнкции С(К) найдется унифицирующийся с ним оц вконъюнкции А(Х) такой, что о(ХАлгфр)=а}(ХАлсфр), где фе{фь., фк},либо найдется такая подстановка р, что правило А^КХпфр) -> С(КХп^р) следует из 5ир05о для фе{фь., фк}.

В этих условиях О^Ялгфр.

Действительно,если в пункте в) утверждения 4 выполняется первое условие, то утверждение 4 совпадает с утверждением 2.

С(ХХп<Ь)->Ъ(Хкж§).

Поэтому, согласно утверждению 3,5ири5о |= А(ХХпфр,) -> Ь^Х^тгфр^ для фе{фь., фк}.

Необходимо отметить, что данный метод не обеспечивает полноты вывода, а именно, не справедливо обратное утверждение: если существует подстановка 0 такая, что правило А(К\в)—>Ъ(КХв) следует из тоистинность правила А(ХХв)-+Ъ(Ккв) может быть доказана при помощи увтерждения 4.

Действительно, применяя утв. 4 для доказательства правила К, мы можем перебрать все применимые к К шаблоны семантических правил, адля каждого шаблона ищем полный набор подстановок, при котором его истинность может следовать из фактов и правил базы знаний. Значит, мы фактически можем перебрать все семантические правила (истинность которых следует из базы знаний), применимые для доказательства правила С одной стороны, поскольку доказываемое правило К представляетсобой семантическое правило, а все семантические правила хранятся в семантической памяти в виде шаблонов, мы таким образом перебираем практически все возможные варианты доказательства истинности правилаЯ. Приведем, однако, примеры ситуаций, которые исключительно редкомогут возникнуть в реальной базе знаний, но, тем не менее, демонстрируют варианты доказательства, не охватываемые утверждением 4. Пример 1.

Как уже упоминалось, семантические правила, не содержащие сколемовских функций, имеют синтаксис пользовательских правил. Это означает, чтопользователь, в принципе, может записать частный случай некоторого семантического правила непосредственно в концептуальной памяти. Например, пользователь может в явном виде записать следующие правила:А : х <== В : х; (III)В : х <== А : х.

Согласно определению семантики конкретизации, истинность такой совокупности правил эквивалентна истинности неэлементарного факта А: В. Разумеется, при заполнении реальной базы знаний пользователь не будет изображать совокупность правил (III), а напишет просто А:В. Но все же, ничто не запрещает ему записать правила (III), при этом не записывая факт А:В. В последнем случае доказательство истинности неэлементарного факта А:В не сможет быть найдено при помощи утверждения 4.

Пример 2.

Согласно определению, правило

Выводы

Была рассмотрена гибридная система представления знаний, комбинирующая средства описания иерархических отношений, свойственные языкам концептуального моделирования, и дедуктивные (пользовательские) правила, позволяющие осуществить логический вывод. Для такой системы представления знаний были решены следующие задачи:

1. Определена эрбрановская интерпретация отношений языка и разработан алгоритм логического вывода на системе пользовательских правил. Алгоритм реализован в экспериментальной системе управления базой знаний.

2. Предложен метод определения денотативной семантики отношений языка (базирующейся на теоретико-множественной интерпретации) в виде представления отношений между классами через отношения между экземплярами.

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

4. В рамках предложенного метода разработана методика представления семантики отношений в семантической памяти базы знаний в виде шаблонов, независимых от конкретного наполнения базы. Построены шаблоны семантики отношений языка.

5. Разработаны алгоритмы комбинированного логического вывода на основе правил пользователя и семантики отношений языка.

Решение этих задач позволяет:

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

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

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

1. Baader F. Logic-based knowledge representation. ftp://www-lti.informatik.rwth-aachen.de/pub/papers/1999/Baader-LNAI-1999.ps.gz

2. BrachmanR.J., Schmölze J.G. An overview of the KL-ONE knowledge representation system. // Cognitive Science 9(2), 1985, pp. 171-216.

3. Ceri S., Gotlob G., Tanca L. Datalog: a self-contained tutorial. Part One// Программирование, 1991, N4, с.20-40.

4. Ceri S., Gotlob G., Tanca L. Datalog: a self-contained tutorial. // Программирование, 1991, N5, c.9-31.

5. Chang C.L., LeeR.C. Symbolic logic and mechanical theorem proving, Academic Press, 1973. (пер. с англ. под ред. С.Ю. Маслова: Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М.:Наука, 1983, 360 с.)

6. CheinM., MugnierM.-L. Conceptual Graphs: Fundamental Notions.// Revue d'Intelligence Artificielle, volume 6-4, pp.365-406,1992.http://www.lirmm.fr/~mugnier/ArticlesPostscript/RIA92ChMu.ps

7. Donini F. M., Lenzerini M., Nardi D., Nutt W. The complexity of concept languages. // Infomation and Computation, 134, pp. 1-58,1997.http: //www. dis. uniroma 1. it/~donini/publications. shtml

8. Donini F. M., Lenzerini M., Nardi D., SchaerfA. AL-log: integrating datalog and description logics. // Journal of Intelligent and Cooperative Information Systems, 10, pp.227-252,1998.http://www.dis.uniromal.it/~nardi/Ricerca/pubblicazioni.html

9. Guthrie L., Pustejovsky J., Wilks Y., SlatorB.M. The role of lexicons in natural language processing. // Communications of the ACM, 1996, V.39, N1., pp.63-73.

10. Levy A. Y., RoussetM.C. CARIN: A representation language combining Horn rules and description logics. In Wahlster W., editor, Proceedings of the 12-th

11. European Conference on Artificial Intelligence (ECAI-96), pp.323-327. John Wiley & Sons Ltd., 1996. http://www.lri.fr/~mcr/publis/ecai96-carin.ps;http://www.lri.fr/~mcr/publis/carin-aij.ps 98r.

12. Lloyd J. Foundations of logic programming. Second, Extended edition, Springer Verlag, 1987.

13. Loveland D.W. Automated theorem proving: a logical basis. North Holland, New York, 1978.

14. LukoseD., KremerR. Knowledge engineering, Part A: Knowledge representation. Lecture 3. Conceptual graphs.http://ksi.cpsc.ucalgary.ca/~kremer/courses/CG/L3.html

15. Mugnier M.-L. On generalization / specialization for conceptual graphs. // Journal of Experimental and Theoretical Artificial Intelligence, volume 7, pp.325-344,1995. http://www.lirmm.fr/~mugnier/ArticlesPostscript/Jetai95Mu.ps

16. Nebel B., Computational Complexity of Terminological Reasoning in BACK, Artificial Intelligence, 34, pp.371-383, 1988.ftp://ftp.informatik.uni-freiburg.de/documents/papers/ki/nebel-aij88.ps.gz

17. NebelB., von Luck К. Issues of Integration and Balancing in Hybrid Knowledge Representation Systems. // Morik K. (ed.), GWAI-87, Springer-Verlag, Berlin 1987, pp.114-123.ftp://ftp.informatik.uni-freiburg.de/documents/papers/ki/nebel-luck-gwai-87.ps.gz

18. Onyshkevych В., NirenburgS. A Lexicon for Knowledge-Based MT.// Machine Translation, 1995. 10:1-2.http://crl.nmsu.edu/SN.bibliography/SN.papers/mikro-lex.pdf

19. Schmidt-Schauss, Smolka G. Attributive concept descriptions with complements. // Journal of Artificial Intelligence, 48(1), 1991, pp. 1-26.

20. Sowa J.F. Conceptual Structures: Information Processing in Mind and Machine. Reading, Massachusetts: Adison-Wesley.1984.

21. Tammet T. Using resolution for extending KL-ONE-type languages.http: //www. cs. chalmers. se/~tammet/

22. Van Emden M.H., Kowalski R. The semantics of predicate logic as a programming language // Journal of the ACM, 23(4), October, 1976, 733-742.

23. Бет Э. Метод семантических таблиц. В кн. Математическая теория логического вывода. Сборник переводов под ред. Идельсона А.В. и Минца Г.Е., Москва: Наука, 1967г., с.191-200.

24. Боярский K.K. Концептуальная память системы MAZE // Информационные технологии в гуманитарных и общественных науках. СПб.: СПбЭМИ РАН, 1997. Вып.6. С. 30-37.

25. Боярский К.К., Каневский Е.А., Лезин Г.В., Попова А.И. Формализация знаний в гуманитарных исследованиях. // Экономико-математические исследования. Математические модели и информационные технологии. СПб: Наука, 2000, с.248-264.

26. Боярский К.К., Мамедниязова Н.С., Попова А.И. Представление и обработка концептуальной информации в системе MAZE. // Экономико-математические исследования. Математические модели и информационные технологии. СПб: Наука, 2000, с.264-279.

27. Бранохе М. Управление памятью в реализациях Пролога// Сборник статей: Математическое обеспечение ЭВМ. Логическое программирование. М.: Мир, 1988, с.193-211.

28. Ковальский Р. Логика в решении проблем. М.: Наука, 1990, 280с.

29. Колмероэ А., Кануи А., ван Канегем М. Пролог — теоретические основы и современное развитие // Сборник статей: Математическое обеспечение ЭВМ. Логическое программирование. М.: Мир, 1988, с.27-134.

30. Лашманов A.B. Перспективы развития языковых средств баз данных (функциональные и логические языки и системы) // НТИ, серия 2, 1992г., N4.

31. Лезин Г.В., Боярский К.К, Каневский Е.А., Попова А.И. Анализ текстов: представление и обработка концептуальной информации // Труды Международного семинара Диалог'97 по компьютерной лингвистике и ее приложениям. М.:Рос.НИИ ИИ, 1997, с.170-174.

32. Логический подход к искусственному интеллекту. От классической логики к логическому программированию: Пер. с франц./ Тейз А., Грибомон П., Луи Ж. и др. — М.:Мир, 1990.

33. Малпас Дж. Реляционный язык Пролог и его применение. М.:Наука, 1990, 458 с.

34. Минский М. Структура для представления знания. — В сб. Психология машинного зрения. — М.:Мир, 1978.

35. Плесневич Г.С. Логика моделей "классы-бинарные отношения". I // Изв. РАН. Теория и системы управления, 1997, №5, с. 17-26.

36. Плесневич Г.С. Логика моделей "классы-бинарные отношения". II // Изв. РАН. Теория и системы управления, 1998, №5, с.69-80.

37. Рубашкин В.Ш., Лахути Д.Г. Семантический (концептуальный) словарь для информационных технологий. II // НТИ, сер.2, 1999, №5, с.1-12.

38. Тузов В.А. Компьютерная лингвистика. Опыт построения компьютерных словарей. Издательство СпбГУ. 43 печ. листа (в печати).

39. Хоггер К. Введение в логическое программирование. М.: Мир, 1988, 348 с.

40. Цаленко М.Ш. Моделирование семантики в базах данных. М.: Наука, 1989. —288с.

41. Цикритзис Д., Лоховски Ф. Модели данных. М.: Финансы и статистика, 1985, 344с.

42. Чери С., Готлоб Г., Танка Л. Логическое программирование и базы данных. М.: Мир, 1992, 352 с.