6

我阅读了Herbrand 宇宙中提出的问题，Herbrand Base and Herbrand Model of binary tree (prolog)以及给出的答案，但我有一个稍微不同的问题，更像是一个确认，希望我的困惑能够得到澄清。

令 P 是一个程序，使得我们有以下事实和规则：

q(a, g(b)).
q(b, g(b)).
q(X, g(X)) :- q(X, g(g(g(X)))).

从上述程序中，赫布兰德宇宙 

Up = {a, b, g(a), g(b), q(a, g(a)), q(a, g(b)), q(b, g(a)), q(b, g(b)), g(g(a)), g(g(b))...e.t.c}

赫布兰德基地：

Bp = {q(s, t) | s, t E Up}
  • 现在来回答我的问题（请原谅我的无知），我将 q(a, g(a)) 作为我的 Herbrand 宇宙中的一个元素，但事实上，它声明了 q(a, g(b))。这是否意味着 q(a, g(a)) 不存在？
  • 此外，由于 Herbrand 模型是 Herbrand 基础的子集，我如何通过归纳确定最小的 Herbrand 模型？

注意：我对此做了很多研究，有些部分对我来说很清楚，但我仍然有这个疑问，这就是为什么我想征求社区意见的原因。谢谢你。

4

2 回答 2

7

从事实来看，q(a,g(b))您无法得出结论是否q(a,g(a))在模型中。您必须先生成模型。

为了确定模型，从事实开始{q(a,g(b)), q(b,g(b))}，现在尝试应用您的规则来扩展它。但是，在您的情况下，无法将规则的右侧q(X,g(X)) :- q(X,g(g(g(X)))).与上述事实相匹配。因此，你完成了。

现在想象规则

q(a,g(Y)) :- q(b,Y).

这个规则可以用来扩展我们的集合。事实上，实例

q(a,g(g(b))) :- q(b,g(b)).

使用：如果q(b,g(b))存在，则得出结论q(a,g(g(b)))。请注意，我们在这里使用从右到左的规则。所以我们得到

{q(a,g(b)), q(b,g(b)), q(a,g(g(b)))}

从而达到一个固定点。

现在以您建议的规则为例

q(X, g(g(g(X)))) :- q(X, g(X)).

哪个允许（我将不再显示实例化的规则）一步生成：

{q(a,g(b)), q(b,g(b)), q(a,g(g(g(b)))), q(b, g(g(g(b))))}

但这还没有结束，因为同样可以应用该规则来生产更多！事实上，你现在有一个无限的模型！

{g(a,g n+1 (b)), g(b, g n+1 (b))}

当您试图理解 Prolog 中的递归规则时，这种从右到左的阅读方式通常非常有用。自上而下的阅读（从左到右）通常非常困难，特别是因为您必须考虑回溯和一般统一。

于 2014-01-27T20:26:52.343 回答
3

关于你的问题：

“此外，由于 Herbrand 模型是 Herbrand 基础的子集，我如何通过归纳确定最小 Herbrand 模型？”

如果你有一组 P 的 horn 子句，即确定的程序，那么你可以定义一个程序运算符：

T_P(M) := { H S | S is ground substitution, (H :- B) in P and B S in M }

最小的模型是：

inf(P) := intersect { M | M |= P }

请注意，并非确定程序的所有模型都是程序运算符的固定点。例如，全赫布兰德模型始终是程序 P 的模型，这表明确定的程序始终是一致的，但不一定是固定点。

另一方面，程序运算符的每个固定点都是确定程序的模型。也就是说，如果您有 T_P(M) = M，那么可以得出 M |= P。因此，经过进一步的数学推理（*），我们会发现最小固定点也是最小模型：

lfp(T_P) = inf(P)

但是我们需要一些进一步的考虑，以便我们可以说我们可以通过一种计算来确定最小模型。也就是说，很容易观察到程序运算符是连续的，即保留了无限的链联合，因为 horn 子句在它们的主体中没有 forall 量词：

union_i T_P(M_i) = T_P(union_i M_i)

因此，在进一步的数学推理（*）之后，我们发现我们可以通过迭代计算最小固定点，巫婆可以用于简单的归纳。最小模型的每个元素都有一个简单的有限深度推导：

union_i T_P^i({}) = lpf(T_P)

再见

(*) 您很可能会在本书中找到有关精确数学推理的更多提示，但不幸的是我不记得哪些部分是相关
的：逻辑编程的基础，John Wylie Lloyd，1984
http://www.amazon.de /基础-编程-计算-人工智能/dp/3642968287

于 2014-02-02T17:55:37.047 回答