First Logic Logics支持哪些描述逻辑不支持？

Question

在研究描述逻辑(DL)时,很常见的是它是一阶逻辑(FOL)的一个片段,但很难从DL中排除的内容中明确地读出一些内容,这是FOL的一部分,这使得DL (所有方言ALC,SHOIN等......)可判定.或者换句话说,你能否在FOL中提供一些不能通过DL表达的例子(这是FOL中半/非可判定性的原因)？

Answer 1

有关描述逻辑的以下事实与可判定性密切相关：

1. （一种形式）树模型属性-该属性对于表格方法很重要；
2. 嵌入到多式联运系统中-众所周知，这是“可靠决定的”；
3. 可嵌入到FOL的受保护片段中-参见下文；
4. 可嵌入到两个变量的FOL片段中-这是可决定的；
5. 位置-参见下文。

这些事实中有些是句法上的，而有些是语义上的。以下是描述逻辑的两个有趣的，与可判定性相关的语法特征，或多或少具有以下语法特征：

位置（来自《描述逻辑手册》第二版，第3.6节）：

许多描述逻辑中的可满足性和包容性是可决定的（尽管非常复杂）的主要原因之一是，大多数概念构造函数只能表示元素的局部属性？...？直观地看，这意味着关于约束X不会“谈”，这是任意远（WRT角色链接）从元素X。这也意味着在 ALC和许多描述逻辑中，对一个个体的断言不能声明满足该结构的整个结构的属性。但是，并非每个描述逻辑都满足局部性。

受保护的片段（来自《描述逻辑手册》第二版，第4.2.3节）

通过允许使用量化的变量，仅当这些变量在公式的主体中使用之前由适当的原子保护时，才可以从一阶逻辑中获得保护的片段。更准确地说，量词只能以
     ？的形式出现。y（P（x，y）？？（y））或？y（P（x，y）？？（y））（第一保护片段）
     ？y（P（x，y）？？（x，y）） 要么 ？ 原子P的y（P（x（y））？α（x，y））（保护片段），变量x和y的向量和（第一）保护片段公式？在y和x中有自由变量（分别在y中）。

从这些观点出发，分析@JoshuaTaylor的评论中的示例：

• ？x。（C（X）？？y。（likes（x，y）？？z。（likes（y，z）？likes（z，x））））
• x（C（x）？zz。（favoriteTeacher（x，z）？firstGradeTeacherOf（x，z））））

对于知识表示，使用DL优于FOL的原因不仅与可确定性或计算复杂性有关。看一下名为“ FOL作为语义网络语言？”的幻灯片。在本讲座中。

Answer 2

正如 Turing 和 Church 所示，FOL 是不可判定的，因为没有算法可以判定 FOL 公式是否有效。许多描述逻辑是一阶逻辑的可判定片段，然而，一些描述逻辑比FOL具有更多的特征，并且许多空间、时间和模糊描述逻辑也是不可判定的。