Описательные логики
Синтаксис логики первого порядка предназначен для упрощения процедуры формирования высказываний об объектах, а описательные логики представляют собой системы обозначений, которые предназначены для упрощения процедуры описания определений и свойств категорий. Системы описательной логики развились из семантических сетей в ответ на необходимость формализовать тот смысл, который несут в себе сети, сохранив вместе с тем акцент на использование таксономической структуры в качестве принципа организации.
Основные задачи логического вывода для описательных логик сводятся к обобщению (проверке того, является ли одна категория подмножеством другой путем сравнения их определений) и классификации (определению принадлежности некоторого объекта к какой-то категории). В некоторых системах предусматривается также проверка непротиворечивости категории, т.е. того, являются ли выполнимыми критерии принадлежности к категории с точки зрения логики.
Типичным языком описательной логики является Classic [155]. Синтаксис описаний8 Classic показан в листинге 10.2. Например, чтобы сформулировать утверждение, что холостяками называют неженатых взрослых мужчин, можно записать следующее:
Bachelor = And(Unmarried, Adult, Male)
Эквивалент этого утверждения в логике первого порядка выглядел бы так: Bachelor (х) <> Unmarried(x) л Adult (х) л Ма1е{х)
Листинг 10.2. Синтаксис описаний в подмножестве языка Classic
Следует отметить, что в этом языке описательной логики фактически разрешается непосредственно выполнять логические операции с предикатами, что исключает необходимость в первую очередь создавать высказывания, которые должны быть соединены связками. Любое описание на языке Classic может быть сформулировано и в логике первого порядка, но некоторые описания Classic формулируются проще. Например, чтобы описать множество мужчин, имеющих трех сыновей, из которых все безработны и женаты на врачах, и, самое большее, двух дочерей, из которых все являются преподавателями на кафедрах физики или математики, можно записать следующее:
Concept —> Thing | ConceptName I And (Concept, ...) I All {RoleName, Concept) I AtLeast(Integer,RoleName) I AtMost(Integer,RoleName) I Fills {RoleName, IndlvidualName,...) j SameAs(Path,Path) I OneOf (IndlvidualName,...) Path —> [RoleName,...]
And{Man,AtLeast(3,Son),AtMost(2, Daughter),
All{Son,And{Unemployed,Married,All{Spouse, Doctor))) ,
All{Daughter,And{Professor,Fills{Department, Physics,Math))))
Перевод этого высказывания на язык логики первого порядка оставляем читателю в качестве упражнения.
По-видимому, одной из наиболее важных характерных особенностей описательных логик является сделанный в них акцент на осуществимости логического вывода. Решение любого экземпляра проблемы осуществляется путем его описания, а затем выполнения запроса, касающегося того, является ли этот экземпляр обобщением одной из нескольких возможных категорий решений. В стандартных системах логики первого порядка предсказание времени выработки решения часто оказывается невозможным, а пользователю чаще всего самому приходится разрабатывать представление, позволяющее исключать множества высказываний, которые, по-видимому, вынудят систему выполнять вычисления в течение нескольких недель, чтобы решить задачу. С другой стороны, в описательных логиках все направлено на обеспечение того, чтобы проблема проверки обобщения могла быть решена за время, полиномиально зависящее от размера описаний9.
На первый взгляд такое свойство описательных логик может показаться удивительным, пока не станет очевидно, что в процессе формулировки задачи может быть достигнут только один из двух безуспешных результатов: либо задача окажется настолько сложной, что ее описание вообще невозможно будет сформулировать, либо она потребует экспоненциально большого описания! Тем не менее анализ осуществимости логического вывода позволяет пролить свет на то, какого рода конструкции вызывают проблемы, и поэтому помочь пользователю понять, какие следствия вытекают из использования различных представлений. Например, в описательных логиках обычно не используются такие отношения, как отрицание и дизъюнкция. Дело в том, что каждое из этих отношений вынуждает логические системы первого порядка для обеспечения полноты проходить через этап анализа вариантов, который может потенциально характеризоваться экспоненциальной сложностью. По той же причине эти отношения исключены из языка Prolog. В языке Classic допускается использовать только ограниченную форму дизъюнкции в конструкциях Fills и OneOf, которые допускают выполнение дизъюнкции по явно заданным объектам, а не по их описаниям. Если бы было разрешено использовать дизъюнктивные описания, то вложенные определения могли бы легко привести к появлению экспоненциального количества альтернативных путей, по которым одна категория могла бы обобщать другую.
В предыдущем разделе был приведен простой пример утверждения с заданной по умолчанию информацией о состоянии: люди имеют две ноги. Это заданное по умолчанию значение можно переопределить с помощью более конкретной информации,