3

我想知道你不能用 Prolog 表达什么样的句子？我一直在研究逻辑编程，并了解到与 Prolog 所基于的明确子句逻辑（Horn 子句）相比，一阶逻辑更具表现力。这对我来说是一个很难理解的话题。

因此，例如，可以表达以下句子：

For all cars, there does not exist at least 1 car without an engine

如果有，还有其他不能表达的句子吗？如果不是，为什么？

4

4 回答 4

4

您可以使用否定 ( ) 使用 Prolog 直接表达您的句子\+。

例如：

car(bmw).
car(honda).
...
car(toyota).

engine(bmw, dohv).
engine(toyota, wenkel).

no_car_without_engine:-
  \+(
    car(Car),
    \+(engine(Car, _))
  ).

no_car_without_engine/0如果每辆车都有引擎，程序将成功，否则失败。

于 2012-09-11T15:32:01.303 回答
3

Prolog 中最有问题的定义是左递归的。定义如

g(X) :- g(A), r(A,X).

由于 Prolog 的搜索算法，最有可能失败，该算法是简单的深度优先搜索，将运行到无穷大甚至更远。

然而，号角子句的一般问题是，它们被定义为最多具有一个积极的元素。也就是说，可以找到一个仅限于这些条件的子句，例如：

A ∨ B

因此，∀ X: cat(X) ∨ dog(X)不能直接表达诸如此类的事实。有一些方法可以解决这些问题，并且有一些方法可以允许这样的声明（见下文）。

阅读材料：

  • 这些幻灯片(p. 3) 举例说明了您无法使用 Prolog 构建哪个句子。

  • 这项工作（第 10 页）还解释了喇叭子句及其含义，并介绍了一种允许“无效”喇叭子句的方法。

于 2012-09-11T20:26:40.577 回答
2

Prolog 是一种编程语言，而不是自然语言界面。

您展示的句子以一种令人费解的方式表达，以至于我很难理解它。实际上，我必须感谢 gusbro 以可以理解的方式表达它的痛苦。但他完全掩盖了任何编程语言在应用于自然语言时所带来的知识表示问题，甚至只是简单地否定一阶逻辑。这些问题是如此紧迫，以至于所选择的语言常常被认为是“不重要的”。

关于编程，Prolog 缺乏在 O(1)（恒定时间）内访问任何线性数据结构（即数组）的能力。然后，例如需要访问 O(1) 中的数组元素的快速排序，就不能以有效的方式实现。

但它仍然是一个图灵完备的语言，值得。那么就没有不能用 Prolog 表达的语句了。

于 2012-09-11T16:11:34.920 回答
0

因此，您正在寻找无法用分句逻辑表达的句子，而这些句子可以用一阶逻辑表达。

严格来说有很多，只是因为从句逻辑是FOL的限制。所以根据定义这是正确的。但是，您可以做的是，您可以将任何一组 FOL 语句重写为一个不等价但具有良好属性的逻辑程序。因此，例如，如果您想知道p是否是您的理论的结果，您可以等效地使用转换后的逻辑程序。

关于其他答案的几点说明：

  1. Prolog (\+) 中的否定是失败的否定，而不是一阶逻辑否定
  2. Prolog 是一种编程语言，正如正确指出的那样，我们应该讨论从句逻辑。
  3. 左递归不是问题。您可以轻松地使用不同的选择规则或其他一些推理机制。
于 2012-09-21T10:02:44.167 回答