如何证明某物不能*不能*翻译成描述逻辑? [英] How to prove that something can *not* be translated into description logic?

问题描述

我的直觉表明无法翻译句子

My intuition says that it is not possible to translate the sentence

所有红色汽车比所有蓝色汽车都要好

all red cars are better than all blue cars

进入描述逻辑(在FOL中为

into description logics (in FOL this would be

∀x∀y(红色(x)∧蓝色(y)→更好(x，y))

∀x∀y (red(x) ∧ blue(y) → better(x,y))

在汽车领域解释).确实，唯一的结构是包含域中所有元素对的完整二进制关系，是通用角色 U .我看不到如何要求左侧的红色集合的所有元素对和右侧的蓝色集合的元素，即如何将 U 限制为特定的前辈集合和后继者.

interpreted in the domain of cars). Indeed, the only construction that is a complete binary relation containing all pairs of elements of the domain is the universal role U. I don't see how to ask for all pairs of elements of the set red on the left and elements of the set blue on the right, i.e., how to restrict U to a specific set of predecessors and successors.

但是不知道怎么做并不能证明这是不可能的.因此，我的问题是:当您使用特定种类的描述逻辑(例如 SROIQ 时，如

But not seeing how to do it is not proof that it is not possible. Therefore my question: when you work with a specific kind of description logic (for example SROIQ as described here), how do you prove that it is impossible to represent a given natural language sentence or FOL formula in it?

推荐答案

很难证明描述逻辑中无法表达某些内容.有几种方法可以做到这一点.例如，考虑可以表达所有SROIQ的FOL片段，向其中添加涵盖您的案例的FOL片段，并研究所产生逻辑的复杂性.如果复杂度严格高于SROIQ之一，那么显然SROIQ不足以表达您想要的内容.您还可以研究模型的形状.例如，在ALC中，始终存在任何一致的KB的有限模型.如果通过添加新的构造可以显示必须有无限个模型，那么您就无法在ALC中表达构造.等等.

Proving that something cannot be expressed in a description logic is difficult. There are several ways to do it. For instance, consider the fragment of FOL that can express all of SROIQ, add to it the fragment of FOL that covers your case, and study the complexity of the resulting logic. If the complexity is strictly higher than the one of SROIQ, then clearly SROIQ is insufficient to express what you want. You could also study the shapes of the models. For instance, in ALC, there are always finite models of any consistent KB. If by adding new constructs you can show that there must be infinite models, then you can't express your constructs in ALC. Etc.

回到您的特定情况，所有红色汽车都比所有蓝色汽车好(高度的说法值得商!！).您不能证明它不能在SROIQ中表达，因为它可以！这种构造(称为 concept-product ，因为它对应于两个类别的笛卡尔积，在您的情况下为red和blue)在2008年题为的研究论文中得到了解决. Rudolph，Krötzsch，和希兹勒.本文证明了概念产品可以用OWL 2 DL表示，并解释了一般如何实现.

Back to your specific case where all red cars are better than all blue cars (a statement that is highly debatable!). You con't prove that it cannot be expressed in SROIQ because it can! This kind of constructs (called concept-product because it corresponds to a carthesian product of two classes, namely red and blue in your case) is addressed by a 2008 research paper titled All elephants are bigger than all mice by Rudolph, Krötzsch, and Hitzler. The paper proves that concept-products can be expressed in OWL 2 DL and explains how it can be done in general.

这在OWL中按以下步骤进行，并以Turtle语法进行序列化(:r1和:r2必须是新鲜的角色名称，不能在其他任何地方使用，而:x必须是新鲜的个人名称，不能在其他地方使用) :

This is done as follows in OWL, serialised in the Turtle syntax (:r1 and :r2 must be fresh role names, not used anywhere else, and :x must be a fresh individual name, not used elsewhere):

:r1 a owl:ObjectProperty .
:r2 a owl:ObjectProperty .
:x a owl:Thing .
:better a owl:ObjectProperty;
    owl:propertyChainAxiom (:r1 :r2) .
:Red a owl:Class;
    rdfs:subClassOf [
        a owl:Restriction;
        owl:onProperty :r1;
        owl:hasValue :x
    ] .
 :Blue a owl:Class;
    rdfs:subClassOf [
        a owl:Restriction;
        owl:onProperty [owl:inverseOf :r2];
        owl:hasValue :x
    ] .

这篇关于如何证明某物不能*不能*翻译成描述逻辑?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！