Herbrand宇宙和最少的herbrand模型

Question

我阅读了Herbrand宇宙中提出的问题,Herbrand Base和Herbrand模型的二叉树(prolog)和给出的答案,但我有一个稍微不同的问题,更像是一个确认,希望我的困惑将得到澄清.

设P是一个程序,以便我们有以下事实和规则:

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

从上面的程序,Herbrand宇宙

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,gⁿ⁺¹(b)), g(b, gⁿ⁺¹(b))}

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