（《机器学习》完整版系列）第15章 规则学习——15.3 归结与逆归结（你可知“反证法”原理？）

归结原理（即消解）：可以“消除”该互补项

归结与逆归结

上篇我们用“十一条规则”形成一套命题逻辑的形式推理体系，归结原理强大到只需一个规则就可形成一套命题逻辑的形式推理体系。

若互补项（即正文字$L$与负文字$\neg L$）分别在两子句$C_1$与$C_2$中，则可以“消除”该互补项，称为归结原理（即消解），如图15.1 所示。
$$\begin{array}{r}C=C_1\cdot C_2\end{array}\text{\hspace{1em}(15.9)}$$
称$C$为$C_1$与$C_2$的消解式，简记为

不可满足指恒假，参见后续的（15.6 一阶逻辑公式及“分拆”），常用结论：空子句是不可满足的、含有空子句的子句集是不可满足的。
归结原理有一个重要的推论：设$C_1$与$C_2$是子句集$S$中的子句，如果把它俩的消解式$C$加入到子句集$S$中，得到子句集$S^{\prime }$，则子句集$S$与$S^{\prime }$的可满足性相同，即
$$\begin{array}{r}\text{“S是不可满足的”等价于“S′是不可满足的”}\end{array}\text{\hspace{1em}(15.10)}$$
由此，通常将要证“$S$是不可满足的”转化为证“$S^{\prime }$是不可满足的”。

归结原理式(15.9)的逆运算（逆归结）简记为
$$\begin{array}{r}\{\begin{array}{l}{C}_1=C/C_2\\ C_2=C/C_1\end{array}\end{array}\text{\hspace{1em}(15.11)}$$

式(15.9)、式(15.11)为图15.1 的简记，$C,C_1,C_2$三者中，已知二者可求另一个。

若已知$C,C_1$，如何“逆归结”出$C_2$？

我们先将式(15.9)用集合论变形
C = A ∨ B = ( C 1 − { L } ) ∨ ( C 2 − { ¬ L } ) \begin{align} C & =A\lor B \notag \\ & =(C_1-\{L \})\lor (C_2-\{\lnot L \}) \tag{15.12} \end{align} C​=A∨B=(C1​−{L})∨(C2​−{¬L})​(15.12)​
通过“移项”得
C − ( C 1 − { L } ) = C 2 − { ¬ L } C 2 = ( C − ( C 1 − { L } ) ) ∨ { ¬ L } \begin{align} & C-(C_1-\{L \})= C_2-\{\lnot L \}\notag \\ & C_2=(C-(C_1-\{L \}))\lor \{\lnot L \} \tag{15.13} \end{align} ​C−(C1​−{L})=C2​−{¬L}C2​=(C−(C1​−{L}))∨{¬L}​(15.13)​
式(15.13)这即【西瓜书式(15.9)】，从中可知，选取不同的$L$，则得到不同的$C_2$，即$C_2$不唯一（未给定$L$时）。

设$\Sigma$为子句集（多条件），$p$为子句（结论），定理（蕴涵符“$\models$”参见后续15.8 三种蕴涵） ：
$$\begin{array}{rl}\Sigma \models p& \text{当且仅当：}(p\vee \neg \Sigma )=\mathrm{True}\\ & \text{当且仅当：}\Sigma \wedge (\neg p)\text{不可满足（即总不成立）}\end{array}\text{\hspace{1em}(15.14)(15.15)}$$
其中，式(15.15)即是“反证法”原理，结合式(15.10)得到利用归结进行“反证法”的步骤（参见后续15.11 基于逆归结的机器证明给出了示例）：

（1）设条件集（子句集）为$\Sigma$，将结论的反面$\neg p$加入到$\Sigma$中；

（2）在$\Sigma$集中反复归结，结果仍然放到$\Sigma$中；

（3）直到归结出一个空子句，即推导出了矛盾（空子句不可满足）。

(i) 证$\Sigma \models p\Rightarrow p\vee \neg \Sigma$：

若$\Sigma \models p$，则表明（逻辑代数（布尔代数）中，1表示True；0表示False，通常通过对变量进行赋值来检验式子是否可满足）：若$\Sigma =1$，则$p=1$

即： 若$\neg \Sigma =0$，则$p=1$

即有：$p\vee \neg \Sigma =1$

(ii) 证$\Sigma \models p\Leftarrow p\vee \neg \Sigma$：

若$\Sigma =1$，则$\neg \Sigma =0$

设$p\vee \neg \Sigma =1$，则$p\vee 0=1$，即$p=1$

上述由$\Sigma =1$推出$p=1$，即说明在此条件下$\Sigma \models p$。

受式(15.11)分数表达的启发，我们将图15.1 表达成“分数”，形成逆归结如图15.2 所示。

在上述归结的理论下，我们可以考虑命题逻辑的两个特殊子集：（1）限定子句：子句中只有一个正文字（其余为负文字）；（2）霍尔子句：子句中至多只有一个正文字（其余为负文字），这两种特性在归结下保持不变，如，一对限定子句（各有一个正文字），若能利用归结原理抵消一对正、负文字后，得到一个新的子句还是只有一个正文字。 在这两种特殊的范围内，可以得到较简单的、机器易于实现的推理系统，这里不作讨论。

本文为原创，您可以：

• 点赞（支持博主）
• 收藏（待以后看）
• 转发（他考研或学习，正需要）
• 评论（或讨论）
• 引用（支持原创）
• 不侵权

上一篇：15.2 形式推理（哥德尔怎么说？）
下一篇：15.4 序贯覆盖（规则集与数据集）