Дескрипционная логика

Дескрипционные логики оперируют понятиями «концепт» и «роль», которые соответствуют в других разделах математической логики понятиям «одноместный предикат» (или множество, класс) и «двуместный предикат» (или бинарное отношение). Интуитивно, концепты используются для описания классов объектов, например, «Люди», «Женщины», «Машины». Роли описывают двуместные отношения между объектами (например, «X есть_родитель_для Y» или «X имеет_в_собственности Y»). С помощью языка дескрипционной логики можно формулировать как общие утверждения о классах (например, всякая Женщина есть Человек, всякая Машина не более чем у одного Человека), так и частные — о конкретных объектах (например, Мария есть Женщина, Иван имеет_в_собственности Машину1).

Набор общих утверждений или терминологии (англ. terminology) называется TBox, а набор утверждений (англ. assertions) частного вида — ABox; вместе они образуют базу знаний^[2] или онтологию. Онтологии на основе дескрипционных логик используются во многих областях — биоинформатика, генетика, медицина, химия, биология. Реализация логического вывода на уровне программ обеспечивают так называемые механизмы рассуждений (англ. reasoners), которые позволяют автоматически выводить знания из онтологий и выполнять другие операции.

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

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

Типичные конструкторы составных концептов:

• пересечение (или конъюнкция) концептов: ${\displaystyle C\sqcap D}$;
• объединение (или дизъюнкция) концептов: ${\displaystyle C\sqcup D}$;
• дополнение (отрицание) концепта: ${\displaystyle \neg C}$;
• ограничение на значения роли (квантор всеобщности): ${\displaystyle \forall R.C}$;
• экзистенциальное ограничение (квантор существования): ${\displaystyle \exists R.C}$;
• численные ограничения: ${\displaystyle ({\leq }n\,R)}$, ${\displaystyle ({\geq }n\,R.C)}$ и др.

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

Дескрипционная логика ${\displaystyle {\mathcal {ALC}}}$ (от англ. attributive language with complement) разработана в 1991 году^[3]. и является базовой системой: многие логики строятся на её основе. Пусть заданы конечные множества атомарных концептов и ролей. Составные концепты в ${\displaystyle {\mathcal {ALC}}}$ определяются индуктивно:

• всякий атомарный концепт — концепт;
• ${\displaystyle \top }$ и ${\displaystyle \bot }$ — концепты;
• если ${\displaystyle C}$ — концепт, то ${\displaystyle \neg C}$ — концепт;
• если ${\displaystyle C}$ и ${\displaystyle D}$ — концепты, то ${\displaystyle C\sqcap D}$ и ${\displaystyle C\sqcup D}$ — концепты;
• если ${\displaystyle C}$ — концепт, а ${\displaystyle R}$ — роль, то ${\displaystyle \forall R.C}$ и ${\displaystyle \exists R.C}$ — концепты.

Фактически ${\displaystyle {\mathcal {ALC}}}$ — это семейство логик с конкретным набором атомарных символов, что аналогично сигнатуре теории первого порядка.

Семантика дескрипционных логик задаётся интерпретацией атомарных концептов как множеств объектов (англ. individual), а ролей — как множеств пар объектов (бинарных отношений) на домене ${\displaystyle \Delta ^{\mathcal {I}}}$.

Интерпретация ${\displaystyle {\mathcal {I}}}$ состоит из:

• домена ${\displaystyle \Delta ^{\mathcal {I}}}$ (непустое множество);
• функции, сопоставляющей каждому атомарному концепту ${\displaystyle A}$ подмножество ${\displaystyle A^{\mathcal {I}}\subseteq \Delta ^{\mathcal {I}}}$, а каждой атомарной роли ${\displaystyle R}$ — подмножество ${\displaystyle R^{\mathcal {I}}\subseteq \Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}}}$.

Правила для ${\displaystyle {\mathcal {ALC}}}$:

• ${\displaystyle \top ^{\mathcal {I}}=\Delta ^{\mathcal {I}}}$
• ${\displaystyle \bot ^{\mathcal {I}}=\varnothing }$
• ${\displaystyle (\neg C)^{\mathcal {I}}=\Delta ^{\mathcal {I}}\setminus C^{\mathcal {I}}}$
• ${\displaystyle (C\sqcap D)^{\mathcal {I}}=C^{\mathcal {I}}\cap D^{\mathcal {I}}}$
• ${\displaystyle (C\sqcup D)^{\mathcal {I}}=C^{\mathcal {I}}\cup D^{\mathcal {I}}}$
• ${\displaystyle (\forall R.C)^{\mathcal {I}}=\{\,e\in \Delta ^{\mathcal {I}}\mid \forall d\in \Delta ^{\mathcal {I}}:(e,d)\in R^{\mathcal {I}}\Rightarrow d\in C^{\mathcal {I}}\,\}}$
• ${\displaystyle (\exists R.C)^{\mathcal {I}}=\{\,e\in \Delta ^{\mathcal {I}}\mid \exists d\in \Delta ^{\mathcal {I}}:(e,d)\in R^{\mathcal {I}}\land d\in C^{\mathcal {I}}\,\}}$

Например, если ${\displaystyle M}$ — множество мужчин, ${\displaystyle R}$ — «есть родитель для», то ${\displaystyle \forall R.M}$ — множество людей, у которых все дети мужского пола; ${\displaystyle M\sqcap \exists R.\top }$ — множество отцов.

В 1991 году^[4] было показано, что ${\displaystyle {\mathcal {ALC}}}$ эквивалентна многомодальной модальной логике ${\displaystyle \mathbf {K} _{n}}$ (n независимых модальностей): атомарные концепты переходят в пропозициональные переменные, пересечение/объединение/отрицание — в булевы связки, ${\displaystyle \forall R_{j}}$ — в ${\displaystyle \Box _{j}}$, ${\displaystyle \exists R_{j}}$ — в ${\displaystyle \Diamond _{j}}$. Фактически, это один и тот же язык в разных обозначениях, и их семантика согласуется (семантика Крипке и др.), что даёт возможность переносить результаты по разрешимости, сложности и процедурам из модальных логик.

Дескрипционные логики (включая ${\displaystyle {\mathcal {ALC}}}$) можно рассматривать как фрагменты логики предикатов, когда концепты переводятся в формулы с одним объектным переменным. Атомарные концепты ${\displaystyle A_{i}}$ переходят в ${\displaystyle P_{i}(x)}$, роли ${\displaystyle R_{j}}$ — в ${\displaystyle S_{j}(x,y)}$. Выражения ${\displaystyle \forall R_{j}.C}$ — в ${\displaystyle \forall y(S_{j}(x,y)\Rightarrow C'(y))}$, ${\displaystyle \exists R_{j}.C}$ — в ${\displaystyle \exists y(S_{j}(x,y)\land C'(y))}$ (где ${\displaystyle C'}$ — перевод ${\displaystyle C}$). В этом переводе используются только две переменные^[5], поэтому ${\displaystyle {\mathcal {ALC}}}$ и её расширения — это фрагменты логики предикатов с двумя переменными, которая разрешима^[6].

Концепты дескрипционных логик важны как инструмент для формализации знаний об описываемой предметной области. Знания делятся на общие (интенсиональные — о понятиях и связях) и знания об объектах (экстенсиональные — о свойствах и отношениях между ними).

Выделяют:

• набор терминологических аксиом — ${\displaystyle TBox{\mathcal {T}}}$
• набор утверждений о конкретных объектах — ${\displaystyle ABox{\mathcal {A}}}$

Их объединение образует базу знаний ${\displaystyle {\mathcal {K}}={\mathcal {T}}\cup {\mathcal {A}}}$.

Аксиома вложенности концептов — ${\displaystyle C\sqsubseteq D}$, аксиома эквивалентности — ${\displaystyle C\equiv D}$ (для ролей — аналогично). Терминология (TBox) — конечный набор таких аксиом. Иногда аксиомы для ролей выделяют отдельно как RBox. В терминологии могут быть и другие аксиомы (например, транзитивность ролей).

Аксиома ${\displaystyle C\sqsubseteq D}$ выполняется в интерпретации ${\displaystyle {\mathcal {I}}}$, если ${\displaystyle C^{\mathcal {I}}\subseteq D^{\mathcal {I}}}$. Моделью терминологии называется интерпретация, в которой выполняются все аксиомы.

Пример TBox для ${\displaystyle {\mathcal {ALC}}}$:

${\displaystyle {\mathsf {Woman}}\equiv {\mathsf {Person}}\sqcap {\mathsf {Female}}}$

${\displaystyle {\mathsf {Mother}}\equiv {\mathsf {Woman}}\sqcap \exists {\mathsf {hasChild}}.\top }$

${\displaystyle \forall {\mathsf {hasChild}}.{\mathsf {Person}}\sqsubseteq {\mathsf {Person}}}$

${\displaystyle {\mathsf {Doctor}}\sqsubseteq {\mathsf {Person}}}$

Интуитивно: женщина = человек и женского пола; мать = женщина и имеет ребёнка; у человека все дети — тоже люди; любой доктор — человек.

Для конкретных объектов утверждения бывают двух видов:

• объект ${\displaystyle a}$ принадлежит концепту ${\displaystyle C}$: ${\displaystyle C(a)}$
• между ${\displaystyle a}$ и ${\displaystyle b}$ выполняется роль ${\displaystyle R}$: ${\displaystyle R(a,b)}$

Набор таких утверждений называется ${\displaystyle ABox}$.

Семантика: имя объекта интерпретируется элементом домена. ${\displaystyle C(a)}$ выполняется, если ${\displaystyle a^{\mathcal {I}}\in C^{\mathcal {I}}}$; ${\displaystyle R(a,b)}$ — если ${\displaystyle (a^{\mathcal {I}},b^{\mathcal {I}})\in R^{\mathcal {I}}}$. Интерпретация, где выполняются все утверждения, называется моделью ABox.

Пример ABox:

${\displaystyle {\mathsf {Mary}}\colon {\mathsf {Woman}}\sqcap \neg {\mathsf {Doctor}}}$

${\displaystyle {\mathsf {Mary}}\colon \exists {\mathsf {hasChild}}.{\mathsf {Female}}}$

${\displaystyle {\mathsf {Mary}}\,{\mathsf {hasChild}}\,{\mathsf {Peter}}}$

${\displaystyle {\mathsf {Peter}}\colon {\mathsf {Doctor}}\sqcap \forall {\mathsf {hasChild}}.\bot }$

Имена объектов Mary и Peter; утверждения означают, что Mary — женщина, не доктор, у неё есть девочка-ребёнок, у Mary есть ребёнок Peter, Peter — доктор и не имеет детей.

Часто принимается соглашение о различии имён объектов (unique name assumption); в OWL оно не по умолчанию, но может быть явно указано.

В отличие от баз данных, в ДЛ принимается предположение об открытости мира: если утверждение не известно, оно не объявляется ложным (в отличие от замкнутых баз данных). Это существенно влияет на логический вывод и понятие логического следования.

Существуют расширения ${\displaystyle {\mathcal {ALC}}}$ дополнительными конструкторами и аксиомами. Принято обозначать буквой добавленную возможность:

${\displaystyle {\mathcal {F}}}$	Функциональность ролей: ${\displaystyle ({\leq }1\,R)}$ — не более одного R-последователя
${\displaystyle {\mathcal {N}}}$	Ограничения кардинальности: ${\displaystyle ({\leq }n\,R)}$
${\displaystyle {\mathcal {Q}}}$	Качественные ограничения: ${\displaystyle ({\leq }n\,R.C)}$
${\displaystyle {\mathcal {I}}}$	Обратные роли: ${\displaystyle R^{-}}$
${\displaystyle {\mathcal {O}}}$	Номиналы: ${\displaystyle \{a\}}$ — одноэлементное множество
${\displaystyle {\mathcal {H}}}$	Иерархия ролей: аксиомы ${\displaystyle R\sqsubseteq S}$
${\displaystyle {\mathcal {S}}}$	Транзитивные роли: аксиомы ${\displaystyle {\mathsf {Tr}}(R)}$
${\displaystyle {\mathcal {R}}}$	Составные аксиомы вложенности ролей (${\displaystyle R\circ S\sqsubseteq R}$)
${\displaystyle (D)}$	Расширения конкретными доменами (типами данных)

Например, ${\displaystyle {\mathcal {ALCIOQ}}}$ — логика с инверсными ролями, номиналами и качественными ограничениями. ${\displaystyle {\mathcal {SHIQ}}}$ — расширения инверсными ролями (${\displaystyle I}$), качественными ограничениями (${\displaystyle Q}$), транзитивными ролями (${\displaystyle S}$) и иерархией ролей (${\displaystyle H}$). Буква ${\displaystyle S}$ выбрана из-за исторической связи с модальной логикой ${\displaystyle \mathbf {S4} }$^[4].

Для некоторых логик дополнительные ограничения требуются для разрешимости^[7].

Базы знаний из дескрипционных логик применяются не только для представления знаний, но и для логического анализа (англ. reasoning) — проверки непротиворечивости знаний, логического вывода, ответа на запросы.

Определения:

• концепт ${\displaystyle C}$ выполняется в интерпретации ${\displaystyle {\mathcal {I}}}$, если ${\displaystyle C^{\mathcal {I}}\neq \varnothing }$
• выполнимый концепт — существует интерпретация, где он выполняется
• вложение: ${\displaystyle C}$ вложен в ${\displaystyle D}$, если во всех интерпретациях ${\displaystyle C^{\mathcal {I}}\subseteq D^{\mathcal {I}}}$

Аналогично для TBox, ABox и базы знаний ${\displaystyle {\mathcal {K}}={\mathcal {T}}\cup {\mathcal {A}}}$.

Практически важные задачи:

• выполнимость концепта (относительно TBox)
• вложение концептов
• совместимость TBox (есть ли модель)
• совместимость базы знаний (модель для пары TBox, ABox)
• построение таксономии (иерархии) концептов
• извлечение экземпляров концепта
• наименее общий над-концепт
• наилучшее описание для объекта
• ответ на запрос к базе знаний

Запросы вида конъюнктивных запросов похожи на методы в базах данных; для более сложных запросов вычислительная трудоёмкость высока или задача становится неразрешимой^[8][9].

Ключевые свойства:

• разрешимость основных задач
• вычислительная сложность, в том числе сложность по данным (англ. data complexity)
• свойство конечности моделей (англ. finite model property)
• свойство древовидности моделей (англ. tree model property)

Исследованы многочисленные результаты по этим характеристикам^[10].

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

Понятия дескрипционных логик (концепт, роль, объект, база знаний) в OWL соответствуют понятиям «класс», «свойство», «объект», «онтология».

Официальная рекомендация W3C от 10 февраля 2004 года:

• OWL-Lite — соответствует ${\displaystyle {\mathcal {SHIF}}(D)}$
• OWL-DL — соответствует ${\displaystyle {\mathcal {SHOIN}}(D)}$
• OWL-Full — не соответствует никакой разрешимой логике

Рабочий проект OWL 1.1 (будущая версия) охватывает логику ${\displaystyle s{\mathcal {ROIQ}}(D)}$, допуская составные аксиомы вложенности ролей (буква ${\displaystyle R}$), аксиомы непересекаемости, рефлексивности, асимметрии и др. новые конструкции^[11].

OWL 2 позволит выражать онтологии на языке ${\displaystyle {\mathcal {EL}}}$ (с полиномиальной сложностью), расширит средства для запросов и аналитики^[12].

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

Некоторые известные reasoners^[13]:

• CEL — реализует ${\displaystyle {\mathcal {EL}}+}$ (полиномиальная сложность), написан на Лисп^[14]
• FaCT++ — поддержка ${\displaystyle s{\mathcal {ROIQ}}(D)}$ и OWL 2.0, реализует табло-алгоритм (C++)^[15]
• Kaon2 — реализует ${\displaystyle {\mathcal {SHIQ}}}$ и специальные правила, механизм резолюции (Java)^[16]
• Pellet — реализует ${\displaystyle s{\mathcal {ROIQ}}(D)}$ и OWL 1.1 (Java)^[17]
• RacerPro — реализует ${\displaystyle {\mathcal {SHIQ}}(D)}$ (Лисп)^[18]

Широко используются редакторы онтологий; например, Protégé, поддерживающий OWL Full и подключение reasoner-рассуждателя.