一个简单的前向链接算法

9.3.2 一个简单的前向链接算法

我们将考虑的第一个前向链接算法非常简单，如图 9.3 所示。它从已知的事实开始，触发所有前提得到满足的规则，把结论添加到已知事实中。重复该过程直到查询得到回答（假定只需要一个答案）或者没有新的事实加入。注意如果某个事实只是已知事实的重命名，那它就不是“新的”。如果两个语句除了变量名称以外其它都相同，那么其中一个语句是另外一个语句的重命名。例如，Likes(x, IceCream)和Likes(y, IceCream)互为重命名，因为仅仅是在对x或y的选择上有所不同；它们的含义是一样的：每个人都喜欢冰淇淋。

图9.3 一个概念上简明直接、但效率非常低的前向链接算法。在每次迭代过程中，算法把所有只用一步就可以从KB中已有的蕴含语句和原子语句推导出来的原子语句都添加到KB中

我们仍用我们的犯罪问题来解释 FOL-FC-ASK是怎样进行的。蕴涵语句为（9.3）、（9.6）、（9.7）和（9.8）。需要两次迭代：

• 在第一次迭代中，规则（9.3）有未满足的前提。

{x/M1}满足规则（9.6），添加Sells(West, M1, Nono)。

{x/M1}满足规则（9.7），添加Weapon(M1)。

{x/Nono}满足规则（9.8），添加Hostile(Nono)。

• 在二次迭代时，{x/West, y/M1, z/Nono}满足规则（9.3），添加Criminal(West)。

图 9.4 显示了所生成的证明树。注意在目前不可能有新的推理生成，因为前向链接可能包括的每个语句都已经显式地包含在KB中。这样的知识库被称为推理过程的不动点。一阶确定子句的前向链接达到的不动点和命题前向链接（第7.5.5节）的不动点类似；最主要的区别在于一阶不动点可以包含全称量化原子语句。

图9.4 犯罪例子中通过前向链接生成的证明树。最初始的事实出现在底层，第一次迭代推理出来的事实位于中层，第二次迭代推理出来的事实处于顶层

FOL-FC-ASK 很容易分析。首先，它是可靠的，因为每个推理只是一般化分离规则的一个应用，而一般化分离规则是可靠的。第二，对确定子句知识库而言，它是完备的；也就是，它可以回答每个查询，只要查询的答案被任何确定子句的知识库所蕴涵。对于不包括函数符号的数据日志知识库而言，证明它的完备性相当容易。我们从统计可以添加的事实的数量开始，此数值决定了迭代的最大次数。令k表示任何谓词的最大元数（参数的个数），p表示谓词的数量，n表示常量符号的数量。显然，存在不多于pnk个不重复的基本事实，所以经过这么多次迭代后，算法一定能到达一个不动点。然后，我们可以提出一个和命题前向链接的完备性证明非常相似的论证。（参见第7.5.5节）。如何从命题完备性转换到一阶完备性的具体内容将在第9.5节给出，并用于归结算法中。

对含有函数符号的一般确定子句，FOL-FC-ASK会生成无限多的新事实，因此我们需要更加谨慎。在查询语句q的答案被蕴涵的情况下，我们必须使用海布兰定理来确定算法将会找到一个证明。（参见第9.5节中归结的情况。）如果查询没有答案，那么在某些情况下算法将无法终止。例如，如果知识库包含皮亚诺公理

NatNum(0)

那么前向链接将添加 NatNum(S(0))、NatNum(S(S(0)))、NatNum(S(S(S(0))))，等等。一般情况下，这个问题无法避免。与一般的一阶逻辑一样，确定子句的蕴涵是半可判定的。