prolog - Herbrand 宇宙和最小 Herbrand 模型

Question

我阅读了 Herbrand universe, 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}

Herbrand 基础:

Bp = {q(s, t) | s, t E Up}

• 现在来回答我的问题(请原谅我的无知)，我将 q(a, g(a)) 作为我的 Herbrand 宇宙中的一个元素包含在内，但事实上，它指出了 q(a, g(b)) 。这是否意味着 q(a, g(a)) 不应该存在？
• 此外，由于 Herbrand 模型是 Herbrand 基础的子集，我如何通过归纳法确定最小 Herbrand 模型？

注意:我对此做了很多研究，有些部分我很清楚，但我仍然有这样的疑问，这就是为什么我想寻求社区的意见。谢谢。

Answer 1

来自事实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,gn+1(b)), g(b, gn+1(b))}

<小时/>

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