10.6 前向链接 (Forward Chaining)

一种算法，前向链接 (forward chaining)，迭代遍历每个蕴涵语句，其中前提（左侧）已知为真，将结论（右侧）添加到已知事实列表中。

10.6.1 前向链接：示例

假设我们有以下知识库：

\[A \to B\]
\[A \to C\]
\[B \land C \to D\]
\[D \land E \to Q\]
\[A \land D \to Q\]
\[A\]

我们想使用前向链接来确定 \(Q\) 是真还是假。

为了初始化算法，我们将初始化一个数字列表 \textit{count}。列表中的第 \(i\) 个数字告诉我们第 \(i\) 个子句的前提中有多少个符号。例如，第三个子句 \(B \land C \to D\) 的前提中有 2 个符号（\(B\) 和 \(C\)），所以我们列表中的第三个数字应该是 2。注意第六个子句 \(A\) 的前提中有 0 个符号，因为它等价于 \(\text{True} \to A\)。

然后，我们将初始化 \textit{inferred}，这是每个符号到真/假的映射。这告诉我们我们发现哪些符号为真。最初，所有符号都为假，因为我们还没有证明任何符号为真。

最后，我们将初始化一个符号列表 \textit{agenda}，这是一个我们可以证明为真但尚未传播其影响的符号列表。例如，如果 \(D\) 在议程中，这将表明我们准备证明 \(D\) 为真，但我们仍然需要检查这对任何其他子句有何影响。最初，\textit{agenda} 将仅包含我们直接知道为真的符号，这里只有 \(A\)。（换句话说，\textit{agenda} 从前提中符号为 0 的任何子句开始。）

我们的起始状态如下所示：

count:\([1, 1, 2, 2, 2, 0]\)
inferred: \(\{A:F, B:F, C:F, D:F, E:F, Q:F\}\)
agenda: \([A]\)

在每次迭代中，我们将从 \textit{agenda} 中弹出一个元素。在这里，我们只能弹出一个元素：\(A\)。我们弹出的符号不是我们要分析的符号 (\(Q\))，所以我们还没有完成算法。

根据 \textit{inferred} 表，\(A\) 为假。然而，由于我们刚刚从议程中弹出了 \(A\)，我们能够将其设置为真。

接下来，我们需要传播 \(A\) 为真的后果。对于 \(A\) 在前提中的每个子句，我们将减少其相应的计数，以表明前提中需要检查的符号少了一个。在这个例子中，子句 1、2 和 5 的前提中包含 \(A\)，所以我们将减少 \textit{count} 中的元素 1、2 和 5。

最后，我们检查是否有任何子句的计数达到 0。我们注意到子句 1 和 2 发生了这种情况。这表明子句 1 和 2 中的每个前提都已满足，因此子句 1 和 2 中的结论已准备好被推断。例如，在子句 1 中，所有前提（这里只有 \(A\)）都已满足，因此结论 \(B\) 已准备好被推断。我们将子句 1 和 2 的结论添加到议程中。

迭代 0 后，我们的算法如下所示：

count:\([{\color{red} 0}, {\color{red} 0}, 2, 2, {\color{red} 1}, 0]\)
inferred: \(\{A:T, B:F, C:F, D:F, E:F, Q:F\}\)
agenda: \([{\color{red} B}, {\color{red} C}]\)

在下一次迭代中，我们将从 \textit{agenda} 中弹出一个元素。在这里我们选择弹出 \(B\)。我们弹出的符号不是我们要分析的符号 (\(Q\))，所以我们还没有完成算法。

根据 \textit{inferred} 表，\(B\) 为假。然而，由于我们刚刚从议程中弹出了 \(B\)，我们能够将其设置为真。

接下来，我们需要传播 \(B\) 为真的后果。\(B\) 在前提中的唯一子句是子句 3。我们必须减少其相应的计数。

最后，我们检查是否有任何子句的计数达到 0。没有子句新达到计数 0，所以我们不能得出任何新结论，也不能向议程添加任何新内容。

迭代 1 后，我们的算法如下所示：

count:\([0, 0, {\color{red} 1}, 2, 1, 0]\)
inferred: \(\{A:T, {\color{red} B:T}, C:F, D:F, E:F, Q:F\}\)
agenda: \([C]\)

接下来，我们将从 \textit{agenda} 中弹出 \(C\)（它不是 \(Q\)，所以算法尚未完成）。我们可以在 \textit{inferred} 列表中将 \(C\) 设置为真。

为了传播 \(C\) 为真的后果，我们减少子句 3 的计数（前提中唯一包含 \(C\) 的子句）。

子句 3 新达到了计数 0，所以我们可以将其结论 \(D\) 添加到议程中。

迭代 2 后，我们的算法如下所示：

count:\([0, 0, {\color{red} 0}, 2, 1, 0]\)
inferred: \(\{A:T, B:T, {\color{red} C:T}, D:F, E:F, Q:F\}\)
agenda: \([{\color{red} D}]\)

接下来，我们将从 \textit{agenda} 中弹出 \(D\)（不是 \(Q\)，所以算法未完成）。我们可以在 \textit{inferred} 列表中将 \(D\) 设置为真。

为了传播 \(D\) 为真的后果，我们减少子句 4 和 5 的计数（前提中包含 \(D\)）。

子句 5 新达到了计数 0，所以我们将其结论 \(Q\) 添加到议程中。

迭代 3 后，我们的算法如下所示：

count:\([0, 0, 0, {\color{red} 1}, {\color{red} 0}, 0]\)
inferred: \(\{A:T, B:T, C:T, {\color{red} D:T}, E:F, Q:F\}\)
agenda: \([{\color{red} Q}]\)

接下来，我们将从 \textit{agenda} 中弹出 \(Q\)。这是我们想要评估的符号，将其从议程中弹出表明它已被证明为真。我们得出结论 \(Q\) 为真并完成算法。