Описательные логики

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

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

Типичным языком описательной логики является Classic. Синтаксис описаний Classic показан в листинге 3.1. Например, чтобы сформулировать утверждение, что холостяками называют неженатых взрослых мужчин, можно записать следующее:

Bachelor = And(Unmarried,Adult,Male)

Эквивалент этого утверждения в логике первого порядка выглядел бы так:

Bachelor(x) ßà Unmarried(x)∩Adult(x)∩Male(x)

Листинг 3.1. Синтаксис описаний в подмножестве языка Classic

Concept → Thing | ConceptName

| And (Concept,...)

|All (RoleName,Concept)

|AtLeast(Integer,RoleName)

| AtMost(Integer,RoleName)

| Fills(RoleName, IndividualName,...)

| SameAs (Path, Path)

|OneOf (IndividualName,...)

Path → [RoleName,...]

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

And(Man,A tLeast(3. Son),AtMost(2,Daughter),

All (Son, And(Unemployed, Married, All(Spause, Doctor))),

All {Daughter, And (Professor, Fills (Department, Phisics, Math)))

Перевод этого высказывания на языке логики первого порядка оставляем читателю в качестве упражнения.

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

На первый взгляд такое свойство описательных логик может показаться удивительным, пока не станет очевидно, что в процессе формулировки задачи может быть достигнут только один из двух безуспешных результатов: либо задача окажется настолько сложной, что ее описание вообще невозможно будет сформулировать, либо она потребует экспоненциально большого описания! Тем не менее анализ осуществимости логического вывода позволяет пролить свет на то, какого рода конструкции вызывают проблемы, и поэтому помочь понять, какие следствия вытекают из использования различных представлений. Например, в описательных логикахобычно не используются такие отношения, как отрицание и дизъюнкция. Дело в том, что каждое из этих отношений вынуждает логические системы первого порядка для обеспечения полноты проходить через этап анализа вариантов, который можетпотенциально характеризоваться экспоненциальной сложностью. По этой же причине эти отношения исключены из языка Prolog. В языке Classic допускается использовать только ограниченную форму дизъюнкции в конструкциях Fills и OneOf, которые допускают выполнение дизъюнкции по явно заданным объектам, а не по их описаниям. Если бы было разрешено использовать дизъюнктивные описания, то вложенные определения могли бы легко привести к появлению экспоненциального количества альтернативных путей, по которым одна категория могла бы обобщать другую.

Дата добавления: 2017-02-01