Русская Википедия:Дескрипционная логика

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Современное название семейство получило в 1980-е годы, в то же время изучались как расширения теорий фреймовых структур и семантических сетей механизмами формальной логики. В 2000-е годы дескрипционные логики получили применение в рамках концепции семантической паутины, где их предлагалось использовать при построении онтологий. Фрагменты OWL-DL и OWL-Lite языка веб-онтологий OWL также основаны на дескрпиционных логиках.

Общие сведения

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

Набор утверждений общего вида или терминологии (Шаблон:Lang-en) называется TBox, набор утверждений (Шаблон:Lang-en) частного вида — ABox, а вместе они составляют так называемую базу знанийШаблон:Sfn или онтологию. Многочисленные онтологии построены и строятся в самых различных предметных областях, таких как биоинформатика, генетика, медицина, химия, биология. Как только онтология построена, встает вопрос о том, как можно извлекать знания, следующие из содержащихся в онтологии знаний, можно ли это делать программно и каковы соответствующие алгоритмы. Все эти вопросы решаются теоретически в науке «дескрипционная логика», а практически уже реализовано множество программных систем — механизмов рассуждений (Шаблон:Lang-en), которые и позволяют автоматизированно выводить знания из онтологий и производить другие операции с онтологиями.

Синтаксис

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

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

Типичными конструкторами для построения составных концептов являются:

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

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

ALC

Дескрипционная логика <math>\mathcal{ALC}</math> (от Шаблон:Lang-en) разработана в 1991 году и является одной из базовых систем, на основе которой строятся многие другие дескрипционные логики. Пусть заданы непустые конечные множества атомарных концептов и атомарных ролей. Тогда следующее является индуктивным определением составных концептов логики <math>\mathcal{ALC}</math> (концепты):

• всякий атомарный концепт является концептом;
• выражения <math>\top</math> и <math>\bot</math> являются концептами;
• если <math>C</math> есть концепт, то его дополнение <math>\neg C</math> является концептом;
• если <math>C</math> и <math>D</math> есть концепты, то их пересечение <math>C\sqcap D</math> и объединение <math>C\sqcup D</math> являются концептами;
• если <math>C</math> есть концепт, а <math>R</math> есть роль, то выражения <math>\forall R.C</math> и <math>\exists R.C</math> являются концептами.

Строго говоря, <math>\mathcal{ALC}</math> — это не одна логика, а семейство логик, где каждая логика этого семейства задается выбором конкретных множеств атомарных концептов и ролей. Это аналогично заданию сигнатуры теории первого порядка. Однако, этим различием обычно пренебрегают.

Семантика

Семантика дескрипционных логик задается путём интерпретации её атомарных концептов как множеств объектов (Шаблон:Lang-en), выбираемых из некоторого фиксированного множества («домена»), а атомарных ролей — как множеств пар объектов, то есть бинарных отношений на домене.

Формально, интерпретация <math>\mathcal{I}</math> состоит из непустого множества <math>\Delta^\mathcal{I}</math> (домена) и интерпретирующей функции, которая сопоставляет каждому атомарному концепту <math>A</math> некоторое подмножество <math>{A^\mathcal{I}\subseteq\Delta^\mathcal{I}}</math>, а каждой атомарной роли <math>R</math> — некоторое подмножество <math>{R^\mathcal{I}\subseteq\Delta^\mathcal{I}\times\Delta^\mathcal{I}}</math>. Если пара объектов принадлежит интерпретации некоторой роли <math>R</math>, то есть <math>(e,d)\in R^\mathcal{I}</math>, то говорят, что объект <math>d</math> является <math>R</math>-последователем объекта <math>e</math>.

Далее интерпретирующая функция распространяется на составные концепты и роли. Поскольку последние в каждой ДЛ свои, то в качестве примера рассмотрим семантику для описанной выше логики <math>\mathcal{ALC}</math>.

Например, для ALC интерпретирующая функция распространяется на составные концепты логики <math>\mathcal{ALC}</math> по следующим правилам:

• <math>\top</math> интерпретируется как весь домен: <math>\top^\mathcal{I}=\Delta^\mathcal{I}</math>
• <math>\bot</math> интерпретируется как пустое множество: <math>\bot^\mathcal{I}=\varnothing</math>
• дополнение концепта интерпретируется как дополнение множества: <math>(\neg C)^\mathcal{I}=\Delta^\mathcal{I}\setminus C^\mathcal{I}</math>
• пересечение концептов интерпретируется как пересечение множеств: <math>(C\sqcap D)^\mathcal{I}=C^\mathcal{I}\cap D^\mathcal{I}</math>
• объединение концептов интерпретируется как объединение множеств: <math>(C\sqcup D)^\mathcal{I}=C^\mathcal{I}\cup D^\mathcal{I}</math>
• выражение <math>\forall R.C</math> интерпретируется как множество тех объектов, у которых все <math>R</math>-последователи принадлежат интерпретации концепта <math>C</math>. Формально:

<math>(\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} \,\}</math>

• выражение <math>\exists R.C</math> интерпретируется как множество тех объектов, у которых имеется <math>R</math>-последователь, принадлежащий интерпретации концепта <math>C</math>. Формально:

<math>(\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} \,\}</math>

Пример: если домен интерпретации <math>\Delta^\mathcal{I}</math> состоит из всех людей, атомарный концепт <math>M</math> интерпретирован как множество людей мужского пола, а роль <math>R</math> как отношение «есть родитель для». Тогда концепт <math>\forall R.M</math> будет интерпретирован как множество людей, у которых все дети мужского пола, а концепт <math>M\sqcap\exists R.\top</math> — как множество «отцов», то есть людей мужского пола, имеющих хотя бы одного ребёнка.

Связь с модальной логикой

В 1991 году было замечено, что логика <math>\mathcal{ALC}</math> есть не что иное, как записанная в других обозначениях модальная логика <math>\mathbf{K}_n</math>, имеющая <math>n</math> независимых модальностей. А именно, если в <math>\mathcal{ALC}</math> имеются атомарные концепты <math>A_1,\ldots,A_m</math> и атомарные роли <math>R_1,\ldots,R_n</math>, то соответствие между логиками осуществляется следующим образом:

• атомарные концепты <math>A_i</math> переходят в пропозициональные переменные <math>p_i</math> модальной логики;
• пересечение <math>\sqcap</math>, объединение <math>\sqcup</math> и дополнение <math>\neg</math> концептов переходит в булевы связки конъюнкцию <math>\land</math>, дизъюнкцию <math>\lor</math> и отрицание <math>\neg</math>;
• выражение <math>\forall R_j</math> переходит в <math>\Box_j</math>, а выражение <math>\exists R_j</math> переходит в <math>\Diamond_j</math>.

Например, концепт <math>\exists R_1.(A_1\sqcup\forall R_2.\neg A_2)</math> переходит в модальную формулу <math>\Diamond_1(p_1\lor\Box_2p_2)</math>. При таком преобразовании всякий составной концепт логики <math>\mathcal{ALC}</math> превращается в правильно построенную формулу модальной логики <math>\mathbf{K}_n</math>, причем всякая модальная формула является переводом некоторого концепта (тем самым, это один и тот же язык, только записанный в двух разных системах обозначений). Более того, данное преобразование согласуется с вышеописанной семантикой логики <math>\mathcal{ALC}</math> с одной стороны и семантикой Крипке модальной логики с другой.

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

Связь с логикой предикатов

Многие дескрипционные логики, включая <math>\mathcal{ALC}</math>, можно рассматривать как фрагменты логики предикатов при «естественном» переводе концептов в предикатные формулы. Если в <math>\mathcal{ALC}</math> имеются атомарные концепты <math>A_1,\ldots,A_m</math> и атомарные роли <math>R_1,\ldots,R_n</math>, то для перевода вводятся одноместные предикатные символы <math>P_1,\ldots,P_m</math> и двуместные предикатные символы <math>S_1,\ldots,S_n</math>, а сам перевод задается индуктивно следующим образом:

• атомарные концепты <math>A_i</math> переходят в формулы <math>P_i(x)</math>;
• пересечение <math>\sqcap</math>, объединение <math>\sqcup</math> и дополнение <math>\neg</math> концептов переходит в булевы связки конъюнкцию <math>\land</math>, дизъюнкцию <math>\lor</math> и отрицание <math>\neg</math>;
• выражение <math>\forall R_j.C</math> переходит в <math>\forall y (S_j(x,y)\Rightarrow C'(y))</math>;
• выражение <math>\exists R_j.C</math> переходит в <math>\exists y (S_j(x,y)\land C'(y))</math>.

В последних двух пунктах переменная <math>y</math> — свежая (не встречавшаяся ранее), а <math>C'</math> есть перевод концепта <math>C</math> (который уже построен по предположению индукции).

Такой перевод согласуется с семантикой дескрипционной логики, то есть в любой интерпретации, если атомарные концепты <math>A_i</math> и атомарные роли <math>R_j</math> интерпретированы так же, как соответствующие им предикаты <math>P_i</math> и <math>S_j</math>, то и всякий составной концепт интерпретируется тем же самым множеством, что и соответствующая ему при переводе предикатная формула от одной переменной. Следует также отметить, что не всякая формула логики предикатов является переводом какого-либо концепта; например, формула <math>\forall x P_1(x)</math> не является таковой.

В данном переводе можно обойтись всего двумя переменными, и таким образом <math>\mathcal{ALC}</math> (а также многие её расширения) можно рассматривать как фрагменты логики предикатов с двумя переменными, которая, как известно, разрешима. Данный перевод позволяет переносить результаты о разрешимости, вычислительной сложности, разрешающих алгоритмах и т. п. из области логики предикатов в область дескрипционных логик.

База знаний

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

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

• набор терминологических аксиом или <math>TBox \mathcal{T}</math> и
• набор утверждений об объектах или <math>ABox \mathcal{A}</math>.

Совокупность аксиом и утверждений вместе составляют так называемую базу знаний <math>\mathcal{K}=\mathcal{T}\cup\mathcal{A}</math>.

Терминологические аксиомы

Аксиомой вложенности концептов называется выражение вида <math>C\sqsubseteq D</math>, а аксиомой эквивалентности концептов — выражение вида <math>C\equiv D</math>, где <math>C</math> и <math>D</math> — произвольные концепты. Аналогично, аксиомой вложенности ролей называется выражение вида <math>R\sqsubseteq S</math>, а аксиомой эквивалентности ролей — выражение вида <math>R\equiv S</math>, где <math>R</math> и <math>S</math> — произвольные роли. Здесь <math>\sqsubseteq</math> есть символ вложенности (subsumption).

Терминологией или набором терминологических аксиом <math>TBox</math> называется конечный набор аксиом перечисленных видов. Иногда аксиомы для ролей выделяются в отдельный набор и называют его иерархией ролей или <math>RBox</math>. Помимо перечисленных видов аксиом, в терминологии могут допускаться и другие аксиомы (например, транзитивность ролей).

Семантика терминологии определяется естественным образом. Пусть дана интерпретация <math>\mathcal{I}</math>. Аксиома <math>C\sqsubseteq D</math> выполняется в интерпретации <math>\mathcal{I}</math>, если <math>C^\mathcal{I}\subseteq D^\mathcal{I}</math>; в этом случае также говорят, что <math>\mathcal{I}</math> является моделью аксиомы <math>C\sqsubseteq D</math>. Аналогично для остальных видов аксиом. Терминология <math>\mathcal{T}</math> выполняется в интерпретации <math>\mathcal{I}</math>, а интерпретация <math>\mathcal{I}</math> называется моделью терминологии <math>\mathcal{T}</math>, если <math>\mathcal{I}</math> является моделью всех входящих в <math>\mathcal{T}</math> аксиом.

Например, следующая совокупность является терминологией (или TBox) в языке логики <math>\mathcal{ALC}</math>:

<math>\mathsf{Woman}\equiv\mathsf{Person}\sqcap\mathsf{Female}</math>

<math>\mathsf{Mother}\equiv\mathsf{Woman}\sqcap\exists\mathsf{hasChild}.\top</math>

<math>\forall\mathsf{hasChild}.\mathsf{Person}\sqsubseteq\mathsf{Person}</math>

<math>\mathsf{Doctor}\sqsubseteq\mathsf{Person}</math>

Интуитивно (то есть при «естественной» интерпретации, когда концепту <math>\mathsf{Person}</math> соответствует множество всех людей, роли <math>\mathsf{hasChild}</math> соответствует отношение «имеет_ребенка» и т. д.) эти аксиомы говорят, что быть женщиной означает в точности быть человеком и быть женского пола; быть матерью означает в точности быть женщиной и иметь ребёнка; у всякого человека всякий ребёнок есть тоже человек; всякий доктор является человеком. Первые две аксиомы вместе представляют собой пример так называемой ациклической терминологии.

Утверждения об объектах

Терминологии позволяют записывать общие знания о концептах и ролях. Однако помимо этого обычно требуется также записать знания о конкретных объектах: к какому классу (концепту) они принадлежат, какими отношениями (ролями) они связаны друг с другом. Это делается в той части базы знаний ДЛ, которая называется <math>ABox</math> (или набор утверждений об объектах).

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

• утверждение о принадлежности объекта <math>a</math> концепту <math>C</math> — записывается как <math>C(a)</math> или <math>a\colon C</math>;
• утверждение о связи двух объектов <math>a</math> и <math>b</math> ролью <math>R</math> — записывается как <math>R(a,b)</math> или <math>(a,b)\colon R</math> или <math>a\,R\,b</math>.

Наконец, набором утверждений об объектах или <math>ABox</math> (от Шаблон:Lang-en) называется конечный набор утверждений этих двух видов.

В некоторых дескрипционных логиках допускаются также утверждения вида <math>\neg R(a,b)</math> в <math>ABox</math>.

Чтобы задать семантику ABox, необходимо расширить интерпретацию <math>\mathcal{I}</math>, а именно каждому имени объекта <math>a</math> сопоставить некоторый элемент домена <math>a^\mathcal{I}\in\Delta^\mathcal{I}</math>. Тогда говорят, что утверждение <math>C(a)</math> или <math>R(a,b)</math> выполняются в интерпретации <math>\mathcal{I}</math>, если имеет место <math>a^\mathcal{I}\in C^\mathcal{I}</math> или <math>(a^\mathcal{I},b^\mathcal{I})\in R^\mathcal{I}</math>, соответственно. Говорят, что ABox выполняется в интерпретации <math>\mathcal{I}</math>, а интерпретация <math>\mathcal{I}</math> является моделью данного ABox, если все его утверждения выполняются в этой интерпретации.

Например, следующая совокупность является набором утверждений об объектах (или ABox) в языке логики <math>\mathcal{ALC}</math>:

<math>\mathsf{Mary}\colon\mathsf{Woman}\sqcap\neg\mathsf{Doctor}</math>

<math>\mathsf{Mary}\colon\exists\mathsf{hasChild}.\mathsf{Female}</math>

<math>\mathsf{Mary}\,\mathsf{hasChild}\,\mathsf{Peter}</math>

<math>\mathsf{Peter}\colon\mathsf{Doctor}\sqcap\forall\mathsf{hasChild}.\bot</math>

Здесь Mary и Peter есть имена объектов. Интуитивно эти утверждения означают, что Mary является женщиной, но не доктором, у неё есть ребёнок женского пола, Peter также является ребёнком Mary, причем Peter является доктором и не имеет детей.

Часто рассматриваются лишь интерпретации, которые удовлетворяют Шаблон:Iw. Оно означает, что разным именам объектов интерпретация обязана сопоставлять различные элементы домена. Язык OWL по умолчанию не предполагает данное соглашение, однако в нём есть конструкции, с помощью которых можно явно указать, какие имена объектов считать равным либо различными.

Отличие от баз данных

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

Выразительные дескрипционные логики

Существуют многочисленные расширения логики <math>\mathcal{ALC}</math> дополнительными конструкторами для построения концептов, ролей, а также дополнительными видами аксиом в <math>TBox</math>. Имеется неформальное соглашение об именовании получающихся при этом логик — обычно путём добавления к имени логики букв, отвечающих добавленным в язык конструкторам. Наиболее известными расширениями являются:

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

Например, логика <math>\mathcal{ALC}</math>, расширенная инверсными ролями, номиналами и ограничениями кардинальности ролей, обозначается как <math>\mathcal{ALCIOQ}</math>.

Буква <math>\mathcal{S}</math> не добавляется к имени логики, а замещает в нём буквы <math>\mathcal{ALC}</math>. Так, например, логика <math>\mathcal{ALC}</math>, расширенная инверсными ролями (буква <math>\mathcal{I}</math>), качественными ограничениями кардинальности ролей (буква <math>\mathcal{Q}</math>), транзитивными ролями (буква <math>\mathcal{S}</math>) и иерархией ролей (буква <math>\mathcal{H}</math>), имеет название <math>\mathcal{SHIQ}</math>. Происхождение всех букв понятно из английских названий конструкторов; буква <math>\mathcal{S}</math> же была выбрана из-за тесной связи получающейся ДЛ с модальной логикой <math>\mathbf{S4}</math> (хотя в последней буква S означает просто system, саму же логику <math>\mathbf{S4}</math> выделяет среди других модальных логик именно цифра 4).

Если в логике присутствуют одновременно буквы <math>\mathcal{S}</math>, <math>\mathcal{H}</math> и либо <math>\mathcal{Q}</math> либо <math>\mathcal{N}</math>, то дополнительное ограничение налагается на правило построения концептов: в концептах вида <math>({\le}n\,R.C)</math> нельзя использовать роли <math>R</math>, имеющие (с точки зрения аксиом RBox) транзитивные под-роли. Если не налагать данные ограничения, то логика становится неразрешимой.

Рассматриваются также дескрипционные логики, в которых можно строить составные роли с помощью операций объединения, пересечения, дополнения, инверсии, композиции, транзитивного замыкания и других. Кроме того, исследованы ДЛ, в которых имеются многоместные роли (обозначающие n-арные отношения).

Логический анализ

Базы знаний, формулируемые на языке дескрипционных логик, применяются не только для представления знаний о предметной области, но также для логического анализа (Шаблон:Lang-en) знаний, как то проверки отсутствия в них противоречий, вывода новых знаний из уже имеющихся, обеспечения возможности делать запросы к базам знаний (по аналогии с запросами к базам данных). Благодаря тому, что базы знаний ДЛ записаны в формализованном виде, имеется возможность делать строгий логический вывод. А поскольку синтаксис и семантика дескрипционных логик построены таким образом, что основные логические проблемы являются разрешимыми, то вывод новых знаний можно осуществлять компьютерными средствами — специальными программами (Шаблон:Lang-en2).

Некоторые определения логического анализа:

• концепт <math>C</math> данной логики выполняется в интерпретации <math>\mathcal{I}</math>, если <math>C^\mathcal{I}\ne\varnothing</math>;
• концепт <math>C</math> называется выполнимым, если существует интерпретация, в которой он выполняется;
• концепт <math>C</math> вложен в концепт <math>D</math> (или содержится в нём; Шаблон:Lang-en), если в любой интерпретации <math>\mathcal{I}</math> выполняется <math>C^\mathcal{I}\subseteq D^\mathcal{I}</math>.

Аналогичные понятия можно ввести относительно некоторого заданного TBox <math>\mathcal{T}</math>, ограничиваясь моделями данного TBox. Например, концепт <math>C</math> называется выполнимым относительно TBox <math>\mathcal{T}</math>, если существует интерпретация, являющаяся моделью этого TBox, в которой данный концепт выполняется.

Когда задан не только TBox <math>\mathcal{T}</math>, но и ABox <math>\mathcal{A}</math>, а значит имеется база знаний <math>\mathcal{K}=\mathcal{T}\cup\mathcal{A}</math>, то возникает ещё одно понятие:

• объект <math>a</math> является экземпляром концепта <math>C</math> относительно базы знаний <math>\mathcal{K}</math>, если в любой модели <math>\mathcal{I}</math> базы знаний <math>\mathcal{K}</math> имеет место <math>a^\mathcal{I}\in C^\mathcal{I}</math>.

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

• выполнимость концепта: является ли заданный концепт выполнимым относительно заданного TBox?
• вложенность концептов: верно ли, что один заданный концепт вложен в другой относительно заданного TBox?
• совместимость TBox: имеет ли заданный TBox хотя бы одну модель?
• совместимость базы знаний: имеет ли заданная пара (TBox, ABox) хотя бы одну модель?

В логиках, содержащих <math>\mathcal{ALC}</math>, проблема вложенности концептов сводится к выполнимости концепта. Важное практическое значение имеют нестандартные алгоритмические проблемы, в частности:

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

Свойства

Фундаментальными характеристиками той или иной дескрипционной логики являются следующие:

• разрешимость: обычно рассматривают разрешимость проблем выполнимости концепта (относительно TBox), совместимости базы знаний, ответа на конъюнктивные запросы;
• вычислительная сложность: изучается вычислительная сложность указанных выше алгоритмических проблем относительно размера входных данных (концепта, TBox, ABox). Отдельно выделяют сложность проблемы выполнимости концепта при фиксированном TBox, сложность проблемы выполнимости базы знаний или проблемы ответа на запросы при фиксированном TBox и меняющемся ABox (так называемая сложность по данным, Шаблон:Lang-en);
• Шаблон:Iw (полнота относительно конечных моделей): исследуется вопрос, всегда ли верно, что если концепт выполним (относительно TBox), то он выполним и на некоторой конечной модели (данного TBox); из наличия данного свойства у конкретной логики обычно следует, что для неё более просто строится разрешающая процедура, например, табло-алгоритм;
• свойство древовидности моделей (полнота относительно древовидных моделей, Шаблон:Lang-en): аналогичный вопрос, но не о конечных, а о «древовидных» моделях, при этом древовидными здесь могут считаться структуры, слегка отличающиеся от традиционного понятия дерева; например, могут допускаться петли (ребра, ведущие из вершины в эту же вершину), мультирёбра (несколько ребер различных «типов», ведущих из одной вершины в другую), транзитивные деревья (структуры, являющиеся транзитивным замыканием обычных деревьев), а также их комбинации; у логик, обладающих данным свойством, обычно более низкая вычислительная сложность, в частности, более просто строится разрешающий табло-алгоритм.

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

Связь с языком OWL

Язык веб-онтологий OWL разрабатывается как язык, на котором можно формулировать и публиковать в веб так называемые сетевые онтологии — формально записанные утверждения о понятиях и объектах некоторой предметной области. Одним из требований к таким онтологиям заключается в том, чтобы содержащиеся в них знания были «доступны» для машинной обработки, в частности, для автоматизированного логического вывода новых знаний из уже имеющихся. Для этого требуется, чтобы язык, на котором формулируются онтологии, имел точную семантику, а соответствующие логические проблемы были разрешимы (и имели практически допустимую вычислительную сложность). Кроме того, желательно, чтобы такой язык имел довольно большую выразительную силу, пригодную для формулировки на нём практически значимых фактов.

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

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

Официальной рекомендацией W3C от 10 февраля 2004 года является версия языка OWL 1.0. Данная спецификация языка OWL подразделяется на следующие варианты:

• OWL-Lite — соответствует дескрипционной логике <math>\mathcal{SHIF}(D)</math>;
• OWL-DL — соответствует дескрипционной логике <math>\mathcal{SHOIN}(D)</math>;
• OWL-Full — не соответствует какой-либо дескрипционной логике, более того, является неразрешимым.

Находящаяся в стадии рабочего черновика новая версия языка OWL 1.1 покрывает дескрипционную логику <math>s\mathcal{ROIQ}(D)</math>, включающую в себя логику <math>\mathcal{SHOIQ}(D)</math>, составные аксиомы вложенности ролей в TBox (буква <math>\mathcal{R}</math> в названии логики), а также аксиомы непересекаемости, рефлексивности, иррефлексивности и асимметричности ролей, универсальную роль (интерпретируемую как <math>\Delta^\mathcal{I}\times\Delta^\mathcal{I}</math>), конструктор концепта <math>\exists R.\mathsf{Self}</math> (интерпретируемый как множество элементов, являющихся <math>R</math>-последователем самих себя) и допускает утверждения <math>\neg R(a,b)</math> в ABox.

Одновременно с этим разрабатывается следующая версия языка OWL 2.0, которая, помимо перечисленного, даст возможность формулировать онтологии в языке, соответствующем дескрипционной логике <math>\mathcal{EL}</math> (преимущество которой в том, что она имеет полиномиальную вычислительную сложность); привнесет синтаксические улучшения, позволяющие легче составлять запросы к базам знаний и выдавать ответы на них; а также будет содержать механизмы для формулировки правил логического вывода.

Машины вывода и редакторы

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

• CEL — поддерживает логику <math>\mathcal{EL}+</math>, имеющую полиномиальную сложность, написана на Лиспе;
• FaCT++ — поддерживает логику <math>s\mathcal{ROIQ}(D)</math>, а также OWL 2.0, реализует табло-алгоритм, написана на C++;
• Kaon2 — поддерживает логику <math>\mathcal{SHIQ}</math>, расширенную специальными правилами вывода, реализует алгоритм, основанный на резолюции, написан на Java;
• Pellet — поддерживает логику <math>s\mathcal{ROIQ}(D)</math>, а также OWL 1.1, реализует табло-алгоритм, написан на Java;
• RacerPro — поддерживает логику <math>\mathcal{SHIQ}(D)</math>, реализует табло-алгоритм, написана на Лиспе.

Существуют также редакторы онтологий, позволяющие создавать онтологии, сохранять их в различных форматах, некоторые позволяют подключить блок рассуждений (Шаблон:Lang-en) и с его помощью произвести логический анализ онтологии. Одним из наиболее известных является редактор онтологий Protégé, позволяющий работать с онтологиями в языке OWL Full.

Литература

• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Официальный сайт сообщества исследователей дескрипционных логик
• Навигатор по вычислительной сложности дескрипционных логик
• Список ДЛ reasoners