Силлогистики для семантических сетей

Размещено на http://www.allbest.ru/

СИЛЛОГИСТИКИ ДЛЯ СЕМАНТИЧЕСКИХ СЕТЕЙ

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

Язык семантических сетей L включает: (а) термины; (b) бинарные отношения; (c) тройки вида (А б В), где А и В - термины, а б - бинарное отношение. Семантическую сеть можно отождествить с конечным множеством S троек в языке L. Таким образом, в графовом представлении A и B будут вершинами, а тройка (А б В) будет дугой с меткой б. (Иногда тройку-дугу мы будем записывать короче, без скобок.)

Простейшим языком семантических сетей является язык L_isa, содержащий, единственное бинарное отношение isa (от английского «есть некоторый»), которое интерпретируется как теоретико-множественное включение классов: А isa В XY, где X и Y - соответственно значения терминов А и В в данной интерпретации. В этом языке имеется единственное правило вывода, при помощи которого вычисляется транзитивное замыкание семантической сети:

В классической логике Аристотеля используется четыре бинарных отношения, традиционно обозначаемые a, i, e, o. Эти отношения следующим образом выражаются в теоретико-множественном языке:

Обозначим через L{a,i,e,o} язык семантических сетей с указанными четырьмя бинарными отношениями. Транзитивное замыкание семантической сети в этом языке вычисляется при помощи следующих четырех правил вывода:

Очевидно, что эти правила вывода состоятельны: они сохраняют истинность предложений, т.е. заключение правила логически следует из его посылок. Например, правилу п3 отвечает логическое следствие XY=, YZ= |= XZ=. Вообще, пусть для некоторого языка L семантических сетей имеется состоятельное правило вывода вида

Тогда, если в семантической сети S языка L присутствуют две тройки (A б B) и (B в C), то правило п применимо к ним, и в результате его применения к сети S добавляется тройка (А г С). Правило вида п можно формулировать алгебраически как «умножение» бинарных отношений: б*в = г.

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

1. Общая схема силлогистики для семантических сетей.

Введем следующие основные определения.

1) Язык семантических сетей L состоит из:

* счетного множества терминов T;

* конечного множества имен для бинарных отношений R, заданных на множестве Т;

* множества всех троек вида (А б В), где А, ВT и бR; другими словами, это есть множество TRT.

Тройка (А б В) называется предложением языка L. Словарем называется подмножество VT. Языком в словаре V, обозначаемым L(V), называется часть языка L, в которую входят только предложения вида (А б В), где А, В V.

2) Семантическая сеть в языке L - это конечное предложений S этого языка. Словарь V_S семантической сети S - это множество всех участвующих в этой сети терминов. (Таким образом, все предложения сети S являются также предложениями языка L (V_S).)

3) Интерпретация языка L(V) - это назначение I булева значения каждому предложению этого языка. Другими словами, интерпретация - это функция I: VRV {0,1}, где 0 обозначает ложь, а 1 - истину. Для данного языка L, на самом деле, в качестве интерпретаций допускаются не любые такие функции. Таким образом, с языком L ассоциируется некоторый класс I допустимых интерпретаций. Через (А б В) ^I обозначим значение предложения (А б В) в интерпретации I.

4) Обозначим через б* обратное к б бинарное отношение, т.е. (А,В)б* (В,А)б. Каждую интерпретацию II продолжим на предложения с обратными отношениями, полагая (А б*В) ^I = (В б А) ^I.

5) Интерпретация предложений языка L семантических сетей зависит от интерпретации терминов и бинарных отношений. Таким образом, для задания I следует указать, как значение (A б B) ^I получается из значений A ^I, B ^I и б ^I. Интерпретация I включает указание:

* множества D ^I - области значений для терминов в интерпретации I, т.е. A ^ID ^I для каждого термина АТ ;

* для каждого бR подмножества б ^I D ^ID ^I.

Интерпретация I распространяется на предложения языка L по правилу: (A б B) ^I = 1 (A ^I, B ^I) б ^I.

6) Символом 1 обозначим тождественно истинное бинарное отношение, т.е. 1 ^I = D ^ID ^I в любой интерпретации I. (Таким образом, А 1 В) ^I = 1 для любых терминов A, BТ и любой интерпретации II.) Символом 0 обозначим тождественно ложное бинарное отношение, т.е. 0 ^I =. (Таким образом, (A 0 B) ^I = 0 для любых терминов А, ВТ и любой интерпретации II.)

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

(~б) ^I = (D ^ID ^I) \ б ^I, (бв) ^I = б ^Iв ^I, (бв) ^I = б ^Iв ^I

для любой интерпретации II.

8) Предложение р логически следует из семантической сети S (в записи: S |= p), если во всякой допустимой интерпретации, в которой истинны все предложения из S, будет также истинно и предложение р, другими словами, если нет допустимой интерпретации, в которой истинны все предложения из S, но ложно предложение р.

Естественно считать, что логическое следствие не зависит от того, как названы термины в семантических сетях. Формально это можно выразить в виде следующего свойства инвариантности отношения |=:

? Пусть какое-либо соответствие А > A' является биекцией словаря V на себя. Оно индуцирует соответствие предложений p = (A,б,B) > p' = (A',б,B') и соответствие семантических сетей S > S' = {p' | pS}. Тогда для любых S и p имеет место эквивалентность S |= p S'|= p'.

Через Cn(S) обозначим множество всех предложений, которые логически следуют из S, т.е. Cn(S) = { p | S |= p }.

Два предложения p и q логически эквивалентны (в записи: p q), если p ^I = q ^I для любой интерпретации II. (Ясно, что p q p |= q и q |= p.) Также два отношения б и в назовем эквивалентными (в записи: бв), если для любых терминов б^I = в^I в любой допустимой интерпретации II.

9) Мы будем предполагать, что для множества R бинарных отношений справедливы ограничения:

* в R нет различных, но эквивалентных отношений, т.е. для любых б,вR б в б = в;

* дизъюнкция всех отличных от 1 отношений из R эквивалентна 1, т.е. 1{б | бR, б1}.

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

10) Предположим, что S |= p, но не существует предложения q такого, что S |= q |= p и q не эквивалентно p. Тогда мы скажем, что p минимально следует из S (в записи: S |=? p). Через Cm(S) обозначим множество всех предложений, которые минимально следуют из S, т.е. Cm(S) = { p | S |=? p }.

11) Предположим, что для данных бинарных отношений б, вR и трех различных терминов А, В и С существует единственное предложение A г C такое, что А б В, В в С |=? A г C. В силу инвариантности логического следствия бинарное отношение г на самом деле не зависит от выбора терминов А, В и С. Поэтому мы можем определить «умножение» б_в = г. Если же таких г несколько, то считается, что умножение б_в не определено. (Заметим, что существует хотя бы одно такое г, если 1R.) В дальнейшем, однако, рассматриваются только такие множества R, что умножение б_в определено для всех б, вR.

Ясно, что для любого отношения бR имеют место равенства 0_б = б_0 = 0 и 1_б = б_1 = б

12) Соотношение б_в = г определяет следующее состоятельное правило вывода:

силлогистика логика семантический сеть

В том случае, когда г1, это правило вывода называется силлогизмом. (Заметим, если г = 1, то из предложений А б В и В в С мы не получаем никакой информации.) Множество этих силлогизмов назовем силлогистикой для языка L. Таким образом, силлогистика определяется «таблицей умножения», т.е. совокупностью всех соотношений б_в = г.

13) Через Cs(S) обозначим множество всех предложений, выводимых с помощью силлогизмов и правил

Легко видеть, что Cs(S)Cm(S). Силлогистика называется дедуктивно полной, если Cs(S) = Cm(S), т.е. если всякое предложение, минимально следующее из S, выводимо из S с помощью силлогизмов и правил (2).

Возьмем произвольный язык семантических сетей, силлогистика которого определена некоторой таблицей умножения для отношений из R. Ясно, что дедукция в семантических сетях определяется только этой таблицей. Другими словами, множество Cs(S) может быть найдено, исходя из S с использованием таблицы умножения. Существует простой алгоритм для нахождения Cs(S), основанный на специальном произведении матриц, элементами которых служат конъюнкции бинарных отношений.

С семантической сетью S свяжем следующим образом матрицу M = M(S). Пусть V_S = {A₁, A₂,…,A_n}. Положим M = ||M_ij||, где M_ij - конъюнкция всех отношений б таких, что предложение (A_i б A_j) или (A_j б*A_i) входит в сеть S, т.е. M_ij = (Л{ б | (A_i б A_j)S})(Л{ б | (A_j б*A_i)S}). Заметим, что конъюнкция пустого множества отношений эквивалентна отношению 1. Поэтому, если в сети S нет предложений вида (A_i б A_j) или (A_j б*A_i), то полагаем M_ij = 1.

Наоборот, по матрице М можно построить семантическую сеть, записывая в S предложение (A_i б A_j) в том и только случае, если б входит в конъюнкцию M_ij. Эту сеть обозначим S(M).

Операцию умножения можно продолжить на конъюнкции отношений:

(б₁б₂… б_r_( (в₁в₂…в_s) = { б_i_в_j | 1ir, 1js }.

Ее можно также распространить на матрицы: если N = ||N_ij|| - другая матрица (того же размера), элементами которой служат конъюнкции бинарных отношений, то M_N= K= ||K_ij||, где

K_ij = M_ij (Л{ M_ik_N_kj | 1kn }) N_ij.

Возводя матрицу М в степени, получим последовательность матриц М, М², М³ и т.д., которая стабилизируется в том смысле, что, начиная с некоторого t, все дальнейшие степени матрицы М будут совпадать. На самом деле tn, и поэтому стабилизированную матрицу можно получить за число шагов, меньшее или равное log₂ n, если последовательно возводить матрицы в квадрат. Отсюда получаем следующий алгоритм для нахождения Cs(S).

Легко видеть, что этот алгоритм имеет верхнюю оценку О(n³log₂ n) для числа операций умножения и конъюнкции, совершаемых при вычислении, когда на вход подается семантическая сеть, имеющая n терминов.

Вообще говоря, конъюнкции бинарных отношений можно упрощать, заменяя их на эквивалентные. Например, 0б и 1б можно заменить на 0 и б, соответственно. В замкнутой силлогистике можно упрощать конъюнкции бинарных отношений до отдельных бинарных отношений. В частности, тогда элементами матрицы M(S) будут отношения из R; также, если M и N -матрицы с элементами из R, то их произведение M_N будет матрицей с элементами из R.

2. Семантические сети с обобщенными кванторами

В обычных семантических сетях термины считаются понятиями и интерпретируются как множества - экстенсионалы этих понятий. Если L - язык семантических сетей, термины которого интерпретируются как произвольные множества, то произвольная интерпретация I языка L(V) включает:

* универсум U ^I - непустое множество, подмножества которого служат значениями терминов в этой интерпретации (таким образом, D ^I = { X | XU ^I});

* назначение каждому термину АV некоторого подмножества A ^IU ^I (таким образом, A ^ID ^I, и мы имеем отображение из V в D ^I );

* назначение каждому отношению бR некоторого подмножества б ^ID ^ID ^I, причем выбор этого подмножества зависит только от выбора универсума U ^I, но не зависит от выбора значений А ^I для терминов AV.

Таким образом, можно сказать, что имя бR интерпретируется как функтор F_б, который каждому множеству U сопоставляет бинарное отношение F_б(U), заданное на подмножествах множества U: F_б(U) 2^U = {X | XU}.

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

* Пусть существует биекция U на V, сопоставляющая каждому элементу xU элемент x'V и, значит, также сопоставляющая каждому подмножеству ZU подмножество Z'V. Тогда для любых X, YU должна выполняться эквивалентность (X,Y)F_б(U) (X',Y')F_б(V)

Функтор F_б действует из категории множеств Set в Set.

Замечание. Определяя функтор F_б, следует также определить значения F_б(g) этого функтора на морфизмах g категории Set (т.е. на отображениях множеств) и показать, что F_б сохраняет композицию: F_б(f?g) = F_б(f)?F_б(g). Естественно определить отображение F_б(g) как такое, которое индуцируется на парах множеств отображением g, т.е. F_б(g)(X,Y)= (gX,gY), где gZ= {g(z) | zZ}.

Свойство инвариантности функтора F_б означает, очевидно, что F_б(U) = F_б(V), если существует изоморфизм (т.е. биекция) g: U>V.

Данное выше определение функтора F_б, ассоциированного с именем бинарного отношения, совпадает, в сущности, с определением обобщенного квантора типа <1,1> по П. Линдстрёму [Lindstrцm] (см. также [Westerstahl] ).

Свойство инвариантности функтора F_б означает, очевидно, что F_б(U) = F_б(V), если существует изоморфизм (т.е. биекция) g: U>V. Поэтому обобщенные кванторы фактически определяются через мощности множеств.

В дальнейшем вместо (X,Y)F_б(U) будем писать короче X б Y (предполагая, что универсум U известен из контекста).

Примеры обобщенных кванторов: (1) Бинарные отношения a, i, e, o в логике Аристотеля являются обобщенными кванторами. Например, для отношения а имеем: X a Y _df XY X \ Y= |X \ Y| = 0; (2) X more Y _df |X| > |Y|; (3) X 3 Y _df |XY| = 3.

3. Конкретные силлогистики

Аристотелевская силлогистика. В аристотелевской силлогистике имеется счетное множество T терминов, интерпретируемых как множества (т.е. как объекты категории Set), и четыре основных бинарных отношения a, i, e, o, которые имеют интерпретацию (1) (см. введение).

Добавив к этим четырем бинарным отношениям обратные отношения (т.е. а* и о*, поскольку i*= i и e*= e), а также тождественно истинное отношение 1, получим R₀ = {a, a*, i, e, o, o*, 1}. Для отношений R (как легко установить) справедлива следующая таблица умножения:

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

К десяти силлогизмам п1 - п10 добавим еще четыре правила для обращения бинарных отношений:

Утверждение 1. Силлогистика с отношениями R = {a, i, e, o, a*, o*, 1} и с правилами вывода п1 - п14 является дедуктивно полной, т.е. Cs(S) = Cm(S) для любой семантической сети S.

Силлогистика с бинарными отношениями, выразимыми в логике первого порядка. Пусть ц[X,Y] - какое-либо предложение в языке логики первого порядка, построенное (с использованием обычных пропозициональных связок и кванторов и ) из атомарных формул вида vX и вида v Y, где v - произвольная индивидная переменная.

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

Примарной формулой назовем любую из следующих четырех формул:

р₁:x(xXY), р₂:x(xX-Y),

р₃:x (x-XY), р₄: x(x-X-Y).

Конституентой назовем конъюнкцию вида у₁у₂у₃у₄, где каждое у_j есть либо примарная формула р_j, либо ее отрицание р_j. Очевидно, что имеется ровно 16 конституент. Каждая из конституент определяет бинарное отношение, называемое базовым и обозначаемое буквой в с нижними индексами из чисел 1,2,3,4; если в конституенту входят примарные формулы (без отрицаний), то в индексы для в мы записываем номера этих примарных формул. Например, имеем

X в Y _df р₁р₂р₃р₄,

X в₁ Y _df р₁р₂р₃р₄,

X в₁₂ Y _df р1р2р3р4,

X в₁₃₄ Y _df р1р2р3р4.

Лемма. Любое предложение ц[X,Y] эквивалентно дизъюнкции некоторых конституент. Если два предложения ц[X,Y] и ш[X,Y] не эквивалентны, то соответствующие им дизъюнкции различны.

Следствие. Любое бинарное отношение, выразимое в логике первого порядка, эквивалентно дизъюнкции некоторых базовых отношений, причем эта дизъюнкция определена однозначно. Существует ровно 2¹⁶= 65534 попарно не эквивалентных бинарных отношений.

Итак, для произвольного предложения ц[X,Y] существует однозначно определяемая дизъюнкция д = д(ц) базовых отношений такая, что X д Y ц[X,Y]. Определим теперь произведение в'_в” двух произвольных базовых отношений в' и в” как дизъюнкцию всех базовых отношений в таких, что A в'BB в”C |=A в C. Тогда нетрудно составить таблицу умножения для базовых отношений. (Например, в эту таблицу входит, в₁₃_в₁₂= в₁₂в₂₃.) Используя таблицу умножения для базовых отношений, можно вычислять произведения d(ц)_d(ш) для любых формул ц[X,Y] и ш[X,Y]. (Произведение двух дизъюнкций есть дизъюнкция всех попарных произведений компонент этих дизъюнкций.)

Таким образом, мы получаем силлогистику для выразимых в логике первого порядка отношений R₁={ d(ц) | ц[X,Y].

Утверждение 2. Силлогистика для выразимых в логике первого порядка отношений R₁ конъюнктивно замкнута, но не является дедуктивно полной.

Утверждение 3. Проблема распознавания pCn(S)? является co-NP-полной, в то время как множество Cs(S) вычисляется полиномиальным алгоритмом.

Интервальная логика Аллена [Allen]. Эту логику можно рассматривать как силлогистику, подобную силлогистике для отношений R₁. Здесь термины интерпретируются как временные интервалы, представленные парами чисел (t-,t⁺), где t- - начало интервала, а t⁺ - его конец. Базовыми отношениями являются 13 темпоральных отношений R₂ = {e, s, s*, m, m*, f, f*, d, d*, o, o*, b, b*}. (Мнемоника этих отношений такова: e - equal to, d - during, s - starts, f - finishes, m - meets, o - overlaps, b - before.) Таким образом, А е В означает (в данной интерпретации I), что интервалы A^I и B^I равны, А d B означает, что интервал A^I входит в интервал B^I и т.д. Произвольное темпоральное отношение между интервалами - это дизъюнкция базовых отношений. Таблица умножения называется алгеброй Аллена.

Известные результаты в логике Аллена можно сформулировать следующим образом.

Утверждение 4. Силлогистика для отношений - дизъюнкций базовых отношений из R₂ - конъюнктивно замкнута, но не является дедуктивно полной. Проблема распознавания pCn(S)? является co-NP-полной.

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

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

1. Lindstrцm P. First-order predicate logic with generalized quantifiers // Theoria, vol.32, no.1, 1966.

2. Westerstahl D. Generalized quantifiers Stanford Encyclopedia оf Philosophy

3. Smiley T. Aristotle's completeness proof // Ancient Philosophy, special issue, 1994.

4. Allen J.F. Maintaining knowledge about temporal intervals // Communications of the ACM, v. 26, no. 11. 1983.

Размещено на Allbest.ru