Дескрипцио́нная логика (описательная логика, ранние наименования — терминологическая система, логика концептов) — язык представления знаний, позволяющий описывать понятия предметной области в недвусмысленном, формализованном виде, организованный по типу языков математической логики. Дескрипционные логики сочетают, с одной стороны, богатые выразительные возможности, а с другой — хорошие вычислительные свойства, такие как разрешимость и относительно невысокая вычислительная сложность основных логических проблем, что делает возможным их применение на практике, обеспечивая компромисс между выразительностью и разрешимостью. Могут быть рассмотрены как разрешимые фрагменты логики предикатов, синтаксически же они близки к модальным логикам.
Современное название семейство получило в 1980-е годы, в то же время изучались как расширения теорий фреймовых структур и семантических сетей механизмами формальной логики. В 2000-е годы дескрипционные логики получили применение в рамках концепции семантической паутины, где их предлагалось использовать при построении онтологий. Фрагменты OWL-DL и OWL-Lite языка веб-онтологий OWL также основаны на дескрипционных логиках.
Общие сведения Дескрипционные логики оперируют понятиями «конце́пт» и «роль», соответствующими в других разделах математической логики понятиям «одноместный предикат» (или множество, класс) и «двуместный предикат» (или бинарное отношение). Интуитивно, концепты используются для описания классов некоторых объектов, например, «Люди», «Женщины», «Машины». Роли используются для описания двуместных отношений между объектами, например, на множестве людей имеется двуместное отношение «X есть_родитель_для Y», а между людьми и машинами имеется двуместное отношение «X имеет_в_собственности Y», где в качестве X и Y можно подставлять произвольные предметы. С помощью языка дескрипционной логики можно формулировать утверждения общего вида — о классах вообще (всякая Женщина есть Человек, всякая Машина имеется_в_собственности не более чем у одного Человека) и частного вида — о конкретных объектах (Мария есть Женщина, Иван имеет_в_собственности Машину1).
Набор утверждений общего вида или терминологии () называется TBox, набор утверждений () частного вида — ABox, а вместе они составляют так называемую базу знаний или онтологию. Многочисленные онтологии построены и строятся в самых различных предметных областях, таких как биоинформатика, генетика, медицина, химия, биология. Как только онтология построена, встает вопрос о том, как можно извлекать знания, следующие из содержащихся в онтологии знаний, можно ли это делать программно и каковы соответствующие алгоритмы. Все эти вопросы решаются теоретически в науке «дескрипционная логика», а практически уже реализовано множество программных систем — механизмов рассуждений (), которые и позволяют автоматизированно выводить знания из онтологий и производить другие операции с онтологиями.
Синтаксис В математической логике всякий язык характеризуется своим синтаксисом, то есть правилами построения выражений этого языка, и семантикой, то есть способом приписывания этим выражениям некоторого формального значения, например, указанием, какие выражения считаются истинными и ложными.
Чтобы сформулировать синтаксис какой-либо дескрипционной логики, необходимо задать непустые (и обычно конечные) множества символов — так называемых атомарных концептов и атомарных ролей — из которых будут строиться выражения языка данной логики. Конкретная логика характеризуется набором конструкторов и индуктивным правилом, с помощью которого составные концепты данной логики строятся из атомарных концептов и атомарных ролей, используя эти конструкторы.
Типичными конструкторами для построения составных концептов являются: пересечение (или конъюнкция) концептов, обозначается как ; объединение (или дизъюнкция) концептов, обозначается как ; дополнение (или отрицание) концепта, обозначается как ; ограничение на значения роли (или ограничение квантором всеобщности), обозначается как ; экзистенциальное ограничение (или ограничение квантором существования), обозначается как ; численные ограничения на значения роли, например: , , и другие.
Конъюнкция и дизъюнкция в дескрипционных логиках обычно обозначаются иначе, чтобы подчеркнуть отличие от других видов логик. Существуют дескрипционные логики, в которых имеются также составные роли, строящиеся из простых ролей с помощью операций: инверсии, пересечения, объединения, дополнения, композиции ролей, транзитивного замыкания и других.
ALC Дескрипционная логика (от ) разработана в 1991 году и является одной из базовых систем, на основе которой строятся многие другие дескрипционные логики. Пусть заданы непустые конечные множества атомарных концептов и атомарных ролей. Тогда следующее является индуктивным определением составных концептов логики (концепты):
всякий атомарный концепт является концептом; выражения и являются концептами; если есть концепт, то его дополнение является концептом; если и есть концепты, то их пересечение и объединение являются концептами; если есть концепт, а есть роль, то выражения и являются концептами.
Строго говоря, — это не одна логика, а семейство логик, где каждая логика этого семейства задается выбором конкретных множеств атомарных концептов и ролей. Это аналогично заданию сигнатуры теории первого порядка. Однако, этим различием обычно пренебрегают.
Семантика Семантика дескрипционных логик задается путём интерпретации её атомарных концептов как множеств объектов (), выбираемых из некоторого фиксированного множества («домена»), а атомарных ролей — как множеств пар объектов, то есть бинарных отношений на домене.
Формально, интерпретация состоит из непустого множества (домена) и интерпретирующей функции, которая сопоставляет каждому атомарному концепту некоторое подмножество , а каждой атомарной роли — некоторое подмножество . Если пара объектов принадлежит интерпретации некоторой роли , то есть , то говорят, что объект является -последователем объекта .
Далее интерпретирующая функция распространяется на составные концепты и роли. Поскольку последние в каждой ДЛ свои, то в качестве примера рассмотрим семантику для описанной выше логики .
Например, для ALC интерпретирующая функция распространяется на составные концепты логики по следующим правилам:
интерпретируется как весь домен: интерпретируется как пустое множество: дополнение концепта интерпретируется как дополнение множества: пересечение концептов интерпретируется как пересечение множеств: объединение концептов интерпретируется как объединение множеств: выражение интерпретируется как множество тех объектов, у которых все -последователи принадлежат интерпретации концепта . Формально:
выражение интерпретируется как множество тех объектов, у которых имеется -последователь, принадлежащий интерпретации концепта . Формально:
Пример: если домен интерпретации состоит из всех людей, атомарный концепт интерпретирован как множество людей мужского пола, а роль как отношение «есть родитель для». Тогда концепт будет интерпретирован как множество людей, у которых все дети мужского пола, а концепт — как множество «отцов», то есть людей мужского пола, имеющих хотя бы одного ребёнка.
Связь с модальной логикой В 1991 году было замечено, что логика есть не что иное, как записанная в других обозначениях модальная логика , имеющая независимых модальностей. А именно, если в имеются атомарные концепты и атомарные роли , то соответствие между логиками осуществляется следующим образом:
атомарные концепты переходят в пропозициональные переменные модальной логики; пересечение , объединение и дополнение концептов переходит в булевы связки конъюнкцию , дизъюнкцию и отрицание ; выражение переходит в , а выражение переходит в .
Например, концепт переходит в модальную формулу . При таком преобразовании всякий составной концепт логики превращается в правильно построенную формулу модальной логики , причем всякая модальная формула является переводом некоторого концепта (тем самым, это один и тот же язык, только записанный в двух разных системах обозначений). Более того, данное преобразование согласуется с вышеописанной семантикой логики с одной стороны и семантикой Крипке модальной логики с другой.
Этот прием, применяемый как к описанным двум логикам, так и к различным их расширениям, позволяет перенести в область дескрипционных логик многочисленные известные факты о модальных логиках, например, об их разрешимости, вычислительной сложности, разрешающих процедурах и других важных свойствах (конечности моделей, древовидности моделей и тому подобные).
Связь с логикой предикатов Многие дескрипционные логики, включая , можно рассматривать как фрагменты логики предикатов при «естественном» переводе концептов в предикатные формулы. Если в имеются атомарные концепты и атомарные роли , то для перевода вводятся одноместные предикатные символы и двуместные предикатные символы , а сам перевод задается индуктивно следующим образом:
атомарные концепты переходят в формулы ; пересечение , объединение и дополнение концептов переходит в булевы связки конъюнкцию , дизъюнкцию и отрицание ; выражение переходит в ; выражение переходит в . В последних двух пунктах переменная — свежая (не встречавшаяся ранее), а есть перевод концепта (который уже построен по предположению индукции).
Такой перевод согласуется с семантикой дескрипционной логики, то есть в любой интерпретации, если атомарные концепты и атомарные роли интерпретированы так же, как соответствующие им предикаты и , то и всякий составной концепт интерпретируется тем же самым множеством, что и соответствующая ему при переводе предикатная формула от одной переменной. Не всякая формула логики предикатов является переводом какого-либо концепта; например, формула не является таковой.
В данном переводе можно обойтись всего двумя переменными, и таким образом (а также многие её расширения) можно рассматривать как фрагменты логики предикатов с двумя переменными, которая, как известно, разрешима.. Данный перевод позволяет переносить результаты о разрешимости, вычислительной сложности, разрешающих алгоритмах и т. п. из области логики предикатов в область дескрипционных логик.
База знаний Концепты дескрипционных логик интересны не столько сами по себе, сколько как инструмент для записи знаний об описываемой предметной области. Эти знания подразделяются на общие знания о понятиях и их взаимосвязях (интенсиональные знания) и знания об индивидуальных объектах, их свойствах и связях с другими объектами (экстенсиональные знания). Первые более стабильны и постоянны, тогда как вторые более подвержены модификациям.
В соответствии с этим делением, записываемые с помощью языка дескрипционных логик знания подразделяются на: набор терминологических аксиом или и набор утверждений об объектах или . Совокупность аксиом и утверждений вместе составляют так называемую базу знаний .
Терминологические аксиомы Аксиомой вложенности концептов называется выражение вида , а аксиомой эквивалентности концептов — выражение вида , где и — произвольные концепты. Аналогично, аксиомой вложенности ролей называется выражение вида , а аксиомой эквивалентности ролей — выражение вида , где и — произвольные роли. Здесь есть символ вложенности (subsumption).
Терминологией или набором терминологических аксиом называется конечный набор аксиом перечисленных видов. Иногда аксиомы для ролей выделяются в отдельный набор и называют его иерархией ролей или . Помимо перечисленных видов аксиом, в терминологии могут допускаться и другие аксиомы (например, транзитивность ролей).
Семантика терминологии определяется естественным образом. Пусть дана интерпретация . Аксиома выполняется в интерпретации , если ; в этом случае также говорят, что является моделью аксиомы . Аналогично для остальных видов аксиом. Терминология выполняется в интерпретации , а интерпретация называется моделью терминологии , если является моделью всех входящих в аксиом.