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

Аристотелевская силлогистика. В аристотелевской силлогистике имеется счетное множество 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¹⁶= 65 534 попарно не эквивалентных бинарных отношений.

Итак, для произвольного предложения ц[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-полной.

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