第3章确定性推理方法

前面讨论了把知识用某种模式表示出来存储到计算机中去。但是，为使计算机具有智能，还必须使它具有思维能力。推理是求解问题的一种重要方法。

3.1 推理的基本概念

3.1.1 推理的定义

推理：已知事实（证据） $+$ 知识 $\rightarrow$ 某种策略 $\rightarrow$ 结论

3.1.2 推理方式及其分类

1.演绎推理、归纳推理、默认推理

（1）演绎推理 (deductive reasoning)：一般 $\rightarrow$ 个别

三段论式（三段论法）

足球运动员的身体都是强壮的；（大前提）
高波是一名足球运动员；（小前提）
所以，高波的身体是强壮的。（结论）

（2）归纳推理(inductive reasoning)：个别 $\rightarrow$ 一般

完全归纳推理（必然性推理）

不完全归纳推理（非必然性推理）

完全归纳推理：检查全部产品合格 $\rightarrow$ 该厂产品合格。
不完全归纳推理：检查全部样品合格 $\rightarrow$ 该厂产品合格

（3）默认推理（default reasoning，缺省推理）

知识不完全的情况下假设某些条件已经具备所进行的推理。

A 成立
B 成立？ $\rightarrow$ 结论
（默认B成立）

2.确定性推理、不确定性推理

（1）确定性推理：推理时所用的知识与证据都是确定的，推出的结论也是确定的，其真值或者为真或者为假。

（2）不确定性推理：推理时所用的知识与证据不都是确定的，推出的结论也是不确定的。

不确定性推理：似然推理（概率论）、近似推理或模糊推理（模糊逻辑）

3.单调推理、非单调推理

（1）单调推理：随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。（基于经典逻辑的演绎推理）

（2）非单调推理：由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使推理退回到前面的某一步，重新开始。（默认推理是非单调推理）

4．启发式推理、非启发式推理

启发性知识：与问题有关且能加快推理过程、提高搜索效率的知识。

3.1.3 推理的方向

推理方向：正向推理、逆向（反向）推理、混合推理、双向推理

1.正向推理

正向推理（事实驱动推理）: 已知事实 $\rightarrow$ 结论

基本思想：

（1）从初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可适用知识集KS。
（2）按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库DB中作为下一步推理的已知事实，再在KB中选取可适用知识构成KS 。
（3）重复（2），直到求得问题的解或KB中再无可适用的知识。

正向推理流程.png

实现正向推理需要解决的问题：

确定匹配（知识与已知事实）的方法。
按什么策略搜索知识库。
冲突消解策略。

正向推理简单，易实现，但目的性不强，效率低。

2.逆向推理

逆向推理需要解决的问题：

如何判断一个假设是否是证据？
当导出假设的知识有多条时，如何确定先选哪一条？
一条知识的运用条件一般都有多个，当其中的一个经验证成立后，如何自动地换为对另一个的验证？
...

逆向推理：目的性强，利于向用户提供解释，但选择初始目标时具有盲目性，比正向推理复杂。

3.混合推理

正向推理：盲目、效率低。
逆向推理: 若提出的假设目标不符合实际，会降低效率。
正反向混合推理：
（1）先正向后逆向：先进行正向推理，帮助选择某个目标，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度；
（2）先逆向后正向：先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。

先正向后逆向.png

先逆向后正向.png

4.双向推理

双向推理：正向推理与逆向推理同时进行，且在推理过程中的某一步骤上“碰头”的一种推理。

双向推理.png

3.1.4 冲突消解策略 PPT P28-29

3.2 自然演绎推理

自然演绎推理：从一组已知为真的事实出发，运用经典逻辑的推理规则推出结论的过程。

推理规则：P规则、T规则、假言推理、拒取式推理

假言推理： $P, P \rightarrow Q \implies Q$

“如果x是金属，则x能导电” , “铜是金属” 推出 “铜能导电”

拒取式推理： $P \rightarrow Q, \neg Q \implies \neg P$

“如果下雨，则地下就湿” , “地上不湿” 推出 “没有下雨”

错误：（PPT P32）
否定前件： $P \rightarrow Q, \neg P 不能 \implies \neg Q$

肯定后件： $P \rightarrow Q, Q 不能 \implies P$

例已知事实：
（1）凡是容易的课程小王( $Wang$ )都喜欢；
（2） $C$ 班的课程都是容易的；
（3） $ds$ 是 $C$ 班的一门课程。
求证：小王喜欢 $ds$ 这门课程。

证明：
定义谓词：

$EASY(x)$ ： $x$ 是容易的
$LIKE(x, y)$ ： $x$ 喜欢 $y$
$C(x)$ ： $x$ 是 $C$ 班的一门课程
已知事实和结论用谓词公式表示：
$(\forall x)(EASY(x) \rightarrow LIKE(Wang, x))$
$(\forall x)(C(x) \rightarrow EASY(x))$
$C(ds)$
$LIKE(Wang, ds)$

应用推理规则进行推理：
$(\forall x)(EASY(x) \rightarrow LIKE(Wang, x))$
$\rightarrow EASY(z) \rightarrow LIKE(Wang, z)$ （全称固化）
$(\forall x)(C(x) \rightarrow EASY(x))$
$\rightarrow C(y) \rightarrow EASY(y)$
所以 $C(ds), C(y) \rightarrow EASY(y)$
$\implies EASY(ds)$ （P规则及假言推理）
所以 $EASY(ds), EASY(z) \rightarrow LIKE(Wang, z)$
$\implies LIKE(Wang, ds)$ （T规则及假言推理）

优点：
表达定理证明过程自然，易理解。
拥有丰富的推理规则，推理过程灵活。
便于嵌入领域启发式知识。

缺点：易产生组合爆炸，得到的中间结论一般呈指数形式递增。

归结演绎推理

反证法： $P \implies Q$ ，当且仅当 $P \land \neg Q \iff F$ ，即 $Q$ 为 $P$ 的逻辑结论，当且仅当 $P \land \neg Q$ 是不可满足的。

定理： $Q$ 为 $P_1, P_2, \dots, P_n$ 的逻辑结论，当且仅当 $(P_1 \land P_2 \land \dots \land P_n) \land \neg Q$ 是不可满足的。

3.3 谓词公式化为子句集的方法

原子（atom）谓词公式：一个不能再分解的命题。
文字（literal）：原子谓词公式及其否定。
$P$ ：正文字， $\neg P$ ：负文字。
子句（clause）：任何文字的析取式。任何文字本身也都是子句。（ $\lor$ ）
空子句（NIL）：不包含任何文字的子句。空子句是永假的，不可满足的。
子句集：由子句构成的集合。

例将下列谓词公式化为子句集
$(\forall x)((\forall y)P(x,y) \rightarrow \neg (\forall y)(Q(x,y) \rightarrow R(x,y)))$

步骤：
（1）消去谓词公式中的“ $\rightarrow$ ”和“ $\leftrightarrow$ ”符号
$P \rightarrow Q \iff \neg P \lor Q, P \leftrightarrow Q \iff (P \land Q) \lor (\neg P \land \neg Q)$

得：

$(\forall x)(\neg(\forall y)P(x,y) \lor \neg(\forall y)(\neg Q(x,y) \lor R(x,y)))$

（2）把否定符号 $\neg$ 移到紧靠谓词的位置上，使得每个否定符号最多只作用于一个谓词上
双重否定律 $\neg (\neg P) \iff P$
德.摩根律 $\neg(P \land Q) \iff \neg P \lor \neg Q, \neg(P \lor Q) \iff \neg P \land \neg Q$
量词转换律 $\neg(\exists x)P \iff (\forall x)\neg P, \neg(\forall x)P \iff (\exists x)\neg P$

得：

$(\forall x)((\exists y)\neg P(x,y) \lor (\exists y)(Q(x,y) \land \neg R(x,y)))$

（3）变量标准化，在一个量词的辖域内，把谓词公式中受该量词约束的变元全部用另一个没有出现过的任意变元代替，使不同量词约束的变元有不同的名字。
$(\exists x)P(x) \equiv (\exists y)P(y), (\forall x)P(x) \equiv (\forall y)P(y)$

$(\forall x)((\exists y)\neg P(x,y) \lor (\exists z)(Q(x,z) \land \neg R(x,z)))$

（4）消去存在量词
分为两种情况：

存在量词不出现在全称量词的辖域内。
存在量词出现在一个或者多个全称量词的辖域内。

对于一般情况
$(\forall x_1)((\forall x_2) ··· ((\forall x_n)((\exists y)P(x_1,x_2,\dots,x_n,y)))\dots)$
存在量词 $y$ 的 $Skolem$ 函数为 $y=f(x_1,x_2,\dots,x_n)$

Skolem化：用Skolem函数代替每个存在量词量化的变量的过程。

$(\forall x)(\neg P(x,f(x)) \lor (Q(x,g(x)) \land \neg R(x,g(x))))$

（5）化为前束形
前束形 = （前缀）{母式}

（前缀）：全称量词串
{母式}：不含量词的谓词公式

（6）化为 $Skolem$ 标准形

$P \lor (Q \land R) \iff (P \lor Q) \land (P \lor R)$
$P \land (Q \lor R) \iff (P \land Q) \lor (P \land R)$

$(\forall x)(\neg P(x,f(x)) \lor (Q(x,g(x)) \land \neg R(x,g(x))))$
$\rightarrow (\forall x)((\neg P(x,f(x)) \lor Q(x,g(x))) \land (\neg P(x,f(x)) \lor \neg R(x,g(x))))$

（7）略去全称量词
由于母式中的全部变元均受全称量词的约束，并且全称量词的次序已无关紧要，因此可以省掉全称量词。但剩下的母式仍假设其变元是被全称量词量化的。

$(\neg P(x,f(x)) \lor Q(x,g(x))) \land (\neg P(x,f(x)) \lor \neg R(x,g(x)))$

（8）消去合取词
在母式中消去所有合取词，把母式用子句集的形式表示出来。

{ $\neg P(x,f(x)) \lor Q(x,g(x)), \neg P(x,f(x)) \lor \neg R(x,g(x))$ }

（9）子句变量标准化
对子句集中的某些变元重新命名，使任意两个子句中不出现相同的变元名。

{ $\neg P(x,f(x)) \lor Q(x,g(x)), \neg P(y,f(y)) \lor \neg R(y,g(y))$ }

3.4 海伯伦定理 PPT 49-53 重点把例子看懂

3.5 鲁滨逊归结原理

子句集中子句之间是合取关系，只要有一个子句不可满足，则子句集就不可满足。

鲁宾逊归结原理（消解原理）的基本思想：
检查子句集 $S$ 中是否包含空子句，若包含，则 $S$ 不可满足。
若不包含，在 $S$ 中选择合适的子句进行归结，一旦归结出空子句，就说明 $S$ 是不可满足的。

1.命题逻辑中的归结原理（基子句的归结）

定义（归结）：设 $C_1$ 与 $C_2$ 是子句集中的任意两个子句，如果 $C_1$ 中的文字 $L_1$ 与 $C_2$ 中的文字 $L_2$ 互补，那么从 $C_1$ 和 $C_2$ 中分别消去 $L_1$ 和 $L_2$ ，并将二个子句中余下的部分析取，构成一个新子句 $C_{12}$ 。

$C_{12}：C_1和C_2的归结式$
$C_1、C_2：C_{12}的亲本子句$

例：设 $C_1 = \neg P \lor Q, C_2 = \neg Q \lor R, C_3 = P$

鲁滨逊归结原理例子.png

定理：归结式 $C_{12}$ 是其亲本子句 $C_1$ 与 $C_2$ 的逻辑结论。即如果 $C_1$ 与 $C_2$ 为真，则 $C_{12}$ 为真。

推论1：设 $C_1$ 与 $C_2$ 是子句集 $S$ 中的两个子句， $C_{12}$ 是它们的归结式，若用 $C_{12}$ 代替 $C_1$ 与 $C_2$ 后得到新子句集 $S_1$ ，则由 $S_1$ 不可满足性可推出原子句集 $S$ 的不可满足性，即：

$S_1$ 的不可满足性 $\implies$ $S$ 的不可满足性

推论2：设 $C_1$ 与 $C_2$ 是子句集 $S$ 中的两个子句， $C_{12}$ 是它们的归结式，若 $C_{12}$ 加入原子句集 $S$ ，得到新子句集 $S_1$ ，则 $S$ 与 $S_1$ 在不可满足的意义上是等价的，即：

$S_1$ 的不可满足性 $\implies$ $S$ 的不可满足性

2.谓词逻辑中的归结原理（含有变量的子句的归结）

谓词逻辑中的归结原理例子.png

定义：设是 $C_1与C_2$ 两个没有相同变元的子句， $L_1$ 和 $L_2$ 分别是 $C_1$ 和 $C_2$ 中的文字，若 $\sigma$ 是 $L_1$ 和 $\neg L_2$ 的最一般合一，则称 $C_{12}=(C_1 \sigma -{L_1 \sigma}) \lor (C_1 \sigma - {L_2 \sigma})$ 为 $C_1$ 和 $C_2$ 的二元归结式。

对于谓词逻辑，归结式是其亲本子句的逻辑结论。
对于一阶谓词逻辑，即若子句集是不可满足的，则必存在一个从该子句集到空子句的归结演绎；若从子句集存在一个到空子句的演绎，则该子句集是不可满足的。
如果没有归结出空子句，则既不能说 $S$ 不可满足，也不能说 $S$ 是可满足的。

3.6 归结反演

应用归结原理证明定理的过程称为归结反演。

用归结反演证明的步骤是：
（1）将已知前提表示为谓词公式 $F$ 。
（2）将待证明的结论表示为谓词公式 $Q$ ，并否定得到 $\neg Q$ 。
（3）把谓词公式集{ $F, \neg Q$ } 化为子句集 $S$ 。
（4）应用归结原理对子句集 $S$ 中的子句进行归结，并把每次归结得到的归结式都并入到 $S$ 中。如此反复进行，若出现了空子句，则停止归结，此时就证明了 $Q$ 为真。

3.7 应用归结原理求解问题

应用归结原理求解问题的步骤：
（1）已知前提 $F$ 用谓词公式表示，并化为子句集 $S$ ；
（2）把待求解的问题 $Q$ 用谓词公式表示，并否定 $Q$ ，再与 $ANSWER$ 构成析取式 $(\neg Q \lor ANSWER)$ ；
（3）把 $(\neg Q \lor ANSWER)$ 化为子句集，并入到子句集 $S$ 中，得到子句集 $S'$ ；
（4）对 $S'$ 应用归结原理进行归结；
（5）若得到归结式 $ANSWER$ ，则答案就在 $ANSWER$ 中。

《人工智能原理及其应用》复习笔记——第3章确定性推理方法

《人工智能原理及其应用》复习笔记——第3章确定性推理方法

第3章确定性推理方法

3.1 推理的基本概念

3.1.1 推理的定义

3.1.2 推理方式及其分类

1.演绎推理、归纳推理、默认推理

2.确定性推理、不确定性推理

3.单调推理、非单调推理

4．启发式推理、非启发式推理

3.1.3 推理的方向

1.正向推理

2.逆向推理

3.混合推理

4.双向推理

3.1.4 冲突消解策略 PPT P28-29

3.2 自然演绎推理

归结演绎推理

3.3 谓词公式化为子句集的方法

3.4 海伯伦定理 PPT 49-53 重点把例子看懂

3.5 鲁滨逊归结原理

1.命题逻辑中的归结原理（基子句的归结）

2.谓词逻辑中的归结原理（含有变量的子句的归结）

3.6 归结反演

3.7 应用归结原理求解问题

相关阅读更多精彩内容

友情链接更多精彩内容

《人工智能原理及其应用》复习笔记——第3章确定性推理方法

第3章 确定性推理方法

3.1 推理的基本概念

3.1.1 推理的定义

3.1.2 推理方式及其分类

1.演绎推理、归纳推理、默认推理

2.确定性推理、不确定性推理

3.单调推理、非单调推理

4．启发式推理、非启发式推理

3.1.3 推理的方向

1.正向推理

2.逆向推理

3.混合推理

4.双向推理

3.1.4 冲突消解策略 PPT P28-29

3.2 自然演绎推理

归结演绎推理

3.3 谓词公式化为子句集的方法

3.4 海伯伦定理 PPT 49-53 重点把例子看懂

3.5 鲁滨逊归结原理

1.命题逻辑中的归结原理（基子句的归结）

2.谓词逻辑中的归结原理（含有变量的子句的归结）

3.6 归结反演

3.7 应用归结原理求解问题

相关阅读更多精彩内容

友情链接更多精彩内容

第3章确定性推理方法