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

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

Свое современное название ДЛ получили в 1980-х. Прежние названия (в хронологическом порядке): терминологические системы, логики концептов. Изначально ДЛ зародились как расширение фреймовых структур и семантических сетей механизмами формальной логики. В настоящее время ДЛ являются важным в концепции Семантической паутины, где их предполагается использовать при построении онтологий. Фрагменты OWL-DL и OWL-Lite языка веб-онтологий OWL также основаны на ДЛ.

Содержание

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

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

На жаргоне ДЛ набор утверждений общего вида или терминоголии (англ. terminology ) называется TBox, набор утверждений (англ. assertions ) частного вида — ABox, а вместе они составляют так называемую базу знаний [3] или онтологию. Многочисленные онтологии построены и строятся в самых различных предметных областях, таких как биоинформатика, генетика, медицина, химия, биология. Как только онтология построена, встает вопрос о том, как можно извлекать знания, следующие из содержащихся в онтологии знаний, можно ли это делать программно и каковы соответствующие алгоритмы. Все эти вопросы решаются теоретически в науке «дескрипционная логика», а практически уже реализовано множество программных систем — механизмов рассуждений (англ. reasoners ), которые и позволяют автоматизированно выводить знания из онтологий и производить другие операции с онтологиями.

Синтаксис

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

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

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

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

Синтаксис логики ALC

Дескрипционная логика (от Attributive Language with Complement) была введена в 1991 году [5] и является одной из базовых ДЛ, на основе которой строятся многие другие ДЛ. Пусть заданы непустые конечные множества атомарных концептов и атомарных ролей. Тогда следующее является индуктивным определением составных концептов логики (для краткости в этом определении будем называть их просто концептами):

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

Семантика

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

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

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

Семантика логики ALC

Интерпретирующая функция распространяется на составные концепты логики по следующим правилам:

Пример. Пусть домен интерпретации состоит из всех людей, атомарный концепт интерпретирован как множество людей мужского пола, а роль как отношение «есть родитель для». Тогда концепт будет интерпретирован как множество людей, у которых все дети мужского пола, а концепт — как множество «отцов», то есть людей мужского пола, имеющих хотя бы одного ребенка.

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

На первый взгляд синтаксис ДЛ является непривычным для тех, кто знаком с «традиционными» логиками (логикой высказываний, логикой предикатов, модальной логикой и др.). Однако уже в 1991 году [6] было замечено, что ДЛ есть не что иное, как записанная в других обозначениях модальная логика , имеющая независимых модальностей. А именно, если в имеются атомарные концепты и атомарные роли , то соответствие между логиками осуществляется следующим образом:

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

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

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

Многие ДЛ, включая , можно рассматривать как фрагменты логики предикатов при «естественном» переводе концептов в предикатные формулы. Если в имеются атомарные концепты и атомарные роли , то для перевода вводятся одноместные предикатные символы и двуместные предикатные символы , а сам перевод задается индуктивно следующим образом:

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

Легко видеть, что данный перевод согласуется с описанной выше семантикой ДЛ, то есть в любой интерпретации, если атомарные концепты и атомарные роли интерпретированы так же, как соответствующие им предикаты и , то и всякий составной концепт интерпретируется тем же самым множеством, что и соответствующая ему при переводе предикатная формула от одной переменной. Следует также отметить, что не всякая формула логики предикатов является переводом какого-либо концепта; например, формула не является таковой.

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

База знаний

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

В соответствии с этим делением, записываемые с помощью языка ДЛ знания подразделяются на

Совокупность аксиом и утверждений вместе составляют так называемую базу знаний . Далее мы по отдельности рассмотрим виды аксиом и утверждений, из которых может состоять TBox и ABox.

Аксиомы и TBox

Аксиомой вложенности концептов называется выражение вида , а аксиомой эквивалентности концептов — выражение вида , где и — произвольные концепты. Аналогично, аксиомой вложенности ролей называется выражение вида , а аксиомой эквивалентности ролей — выражение вида , где и — произвольные роли. Здесь есть символ вложенности (subsumption).

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

Семантика терминологии определяется естественным образом. Пусть дана интерпретация . Аксиома выполняется в интерпретации , если ; в этом случае также говорят, что является моделью аксиомы . Аналогично для остальных видов аксиом. Терминология выполняется в интерпретации , а интерпретация называется моделью терминологии , если является моделью всех входящих в аксиом.

Пример. Следующая совокупность является терминологией (или TBox) в языке логики :

Интуитивно (то есть при «естественной» интерпретации, когда концепту соответствует множество всех людей, роли соответствует отношение «имеет_ребенка» и т. д.) эти аксиомы говорят, что быть женщиной означает в точности быть человеком и быть женского пола; быть матерью означает в точности быть женщиной и иметь ребенка; у всякого человека всякий ребенок есть тоже человек; всякий доктор является человеком. Первые две аксиомы вместе представляют собой пример так называемой ациклической терминологии.

Утверждения и ABox

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

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

Наконец, набором утверждений об индивидах или ABox (от англ. assertional box) называется конечный набор утверждений этих двух видов.

Примечание. В некоторых ДЛ допускаются также утверждения вида в ABox.

Чтобы задать семантику ABox, необходимо расширить интерпретацию , а именно каждому имени индивида сопоставить некоторый элемент домена . Тогда говорят, что утверждение или выполняются в интерпретации , если имеет место или , соответственно. Говорят, что ABox выполняется в интерпретации , а интерпретация является моделью данного ABox, если все его утверждения выполняются в этой интерпретации.

Пример. Следующая совокупность является набором утверждений об индивидах (или ABox) в языке логики :

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

Примечание. Часто рассматриваются лишь интерпретации, которые удовлетворяют соглашению об уникальности имён (unique name assumption). Оно означает, что разным именам индивидов интерпретация обязана сопоставлять различные элементы домена. Язык OWL по умолчанию не предполагает данное соглашение, однако в нем есть конструкции, с помощью которых можно явно указать, какие имена индивидов считать равным либо различными.

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

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

Выразительные ДЛ

Существуют многочисленные расширения логики дополнительными конструкторами для построения концептов, ролей, а также дополнительными видами аксиом в TBox. Имеется неформальное соглашение об именовании получающихся при этом логик — обычно путем добавления к имени логики букв, отвечающих добавленным в язык конструкторам. Наиболее известными расширениями являются: [4]

	Функциональность ролей: концепты вида , означающие: существует не более одного -последователя
	Ограничения кардинальности ролей: концепты вида , означающие: существует не более -последователей
	Качественные ограничения кардинальности ролей: концепты вида , означающие: существует не более -последователей в
	Обратные роли: если есть роль, то тоже является ролью, означающей обращение бинарного отношения
	Номиналы: если есть имя индивида, то есть концепт, означающий одноэлементное множество
	Иерархия ролей: в TBox допускаются аксиомы вложенности ролей
	Транзитивные роли: в TBox допускаются аксиомы транзитивности вида
	Составные аксиомы вложенности ролей в TBox (, ) с условием ацикличности, где есть композиция ролей
	Расширение языка конкретными доменами (типами данных)

Например, логика , расширенная инверсными ролями, номиналами и ограничениями кардинальности ролей, обозначается как .

Примечание. Буква не добавляется к имени логики, а замещает в нем буквы . Так, например, логика , расширенная инверсными ролями (буква ), качественными ограничениями кардинальности ролей (буква ), транзитивными ролями (буква ) и иерархией ролей (буква ), имеет название . Происхождение всех букв понятно из английских названий конструкторов; буква же была выбрана из-за тесной связи получающейся ДЛ с модальной логикой [6] (хотя в последней буква S означает просто system, саму же логику выделяет среди других модальных логик именно цифра 4).

Примечание. Если в ДЛ присутствуют одновременно буквы , и либо либо , то дополнительное ограничение налагается на правило построения концептов: в концептах вида нельзя использовать роли , имеющие (с точки зрения аксиом RBox) транзитивные под-роли. Если не налагать данные ограничения, то логика становится неразрешимой. [9]

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

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

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

Пусть мы фиксировали некоторую ДЛ. Введем несколько важных понятий.

Аналогичные понятия можно ввести относительно некоторого заданного TBox , ограничиваясь моделями данного TBox. Например, концепт называется выполнимым относительно TBox , если существует интерпретация, являющаяся моделью этого TBox, в которой данный концепт выполняется.

Когда задан не только TBox , но и ABox , а значит имеется база знаний , то возникает еще одно понятие.

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

В логиках, содержащих , проблема вложенности концептов сводится к выполнимости концепта. [4] Важное практическое значение имеют нестандартные алгоритмические проблемы, в частности:

Свойства ДЛ

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

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

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

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

Соответствие терминов: имеющиеся в ДЛ понятия концепт, роль, индивид и база знаний в OWL соответствуют понятиям класс, свойство, объект и онтология, соответственно.

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

Находящаяся в стадии рабочего черновика новая версия языка OWL 1.1 покрывает дескрипционную логику , включающую в себя логику , составные аксиомы вложенности ролей в TBox (буква в названии логики), а также аксиомы непересекаемости, рефлексивности, иррефлексивности и асимметричности ролей, универсальную роль (интерпретируемую как ), конструктор концепта (интерпретируемый как множество элементов, являющихся -последователем самих себя) и допускает утверждения в ABox. [12]

Одновременно с этим разрабатывается следующая версия языка OWL 2.0, которая, помимо перечисленного, даст возможность формулировать онтологии в языке, соответствующем дескрипционной логике (преимущество которой в том, что она имеет полиномиальную вычислительную сложность); привнесет синтаксические улучшения, позволяющие легче составлять запросы к базам знаний и выдавать ответы на них; а также будет содержать механизмы для формулировки правил логического вывода. [13]

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

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

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

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

Источник