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

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