Что поддерживается в логике первого порядка, которая не поддерживается в описании логики?

При изучении логики описания (DL) очень часто следует читать, что это фрагмент логики первого порядка (FOL), но трудно что-то явно прочитать о том, что исключено из DL, который является частью FOL, что делает DL (со всеми его диалектами ALC, SHOIN и т.д.). Или, другими словами, можете ли вы предоставить мне несколько примеров в FOL, которые не могут быть выражены через DL (и которые являются причиной полу/недискриминации в FOL)?

Ответы

Ответ 1

Следующие факты об логиках описания тесно связаны с разрешимостью:

  1. (форма) свойства tree-model - это свойство важно для методов tableu;
  2. вложимость в мультимодальные системы, которые, как известно, "устойчиво разрешимы";
  3. вложимость в так называемые охраняемые фрагменты FOL - см. ниже;
  4. вложимость в фрагменты FOL с двумя переменными - которые разрешимы;
  5. местность - см. ниже.

Некоторые из этих фактов являются синтаксическими, а некоторые - семантическими. Ниже приведены две интересные, разрешимые и более или менее синтаксические характеристики логики описания:

Местность (из Справочника по описанию описания, 2-е издание, раздел 3.6):

Одна из основных причин, по которым выполнимость и подчинение во многих описаниях логики разрешимы - хотя и очень сложная - заключается в том, что большинство конструкторов понятий могут выражать только локальные свойства элемента <...> Интуитивно, это означает, что ограничение относительно x будет не "говорить о" элементах, которые произвольно далеки (wrt role links) от x. Это также означает, что в ALC и во многих описаниях логики утверждение об индивидууме не может определять свойства всей удовлетворяющей ей структуры. Однако не каждая логика описания удовлетворяет локальности.

Охраняемый фрагмент (из "Руководства по описанию описания", 2-е издание, раздел 4.2.3)

Охраняемые фрагменты получают из логики первого порядка, позволяя использовать количественные переменные только в том случае, если эти переменные защищены соответствующими атомами, прежде чем они будут использованы в теле формулы. Точнее, кванторы ограничиваются появлением только в форме
∃ y (P (x, y) ∧ Φ (y)) или ∀ y (P (x, y) ⊃ Φ (y)) (первый охраняемый фрагмент)
∃ y (P (x, y) ∧ Φ (x, y)) или ∀ y (P (x, y) ⊃ Φ (x, y)) (охраняемый фрагмент)
для атомов P, векторов переменных x и y и (первых) формул защищенного фрагмента Φ со свободными переменными по y и x (соответственно y).

С этих точек зрения проанализируйте примеры из комментариев @JoshuaTaylor:

  • ∀x. (C (X) ↔ ∃y. (Нравится (x, y) ∧ ∃z. (Нравится (y, z) ∧ нравится (z, x))))
  • ∀x. (C (x) ↔ ∃z. (FavoriteTeacher (x, z) ∧ firstGradeTeacherOf (x, z)))

Причины, по которым DL предпочтительнее FOL для представления знаний, связаны не только с разрешающей способностью или вычислительной сложностью. Посмотрите на слайд под названием "FOL как семантический веб-язык"? в этой лекции.

Ответ 2

Как показано Тьюрингом и Церковью, FOL неразрешима, потому что нет алгоритма для решения, является ли формула FOL действительной. Многие логики описания являются разрешимыми фрагментами логики первого порядка, однако некоторые логики описания имеют больше возможностей, чем FOL, и многие пространственные, временные и нечеткие логики описания также неразрешимы.