《人工智能与专家系统(第二版)》第4章 逻辑推理

1、人工智能与专家系统第4章 逻辑推理4.1 推理的基本概念4.2 归结演绎推理4.4 归结反演的改进策略4.3 基于归结反演的问题求解4.1 推理的基本概念4.1.1 推理方式及其分类4.1.2 推理的控制策略4.1.3 模式匹配及其变量代换4.1.1 推理方式及其分类1 演绎推理、归纳推理、默认推理 演绎推理:是从全称判断推导出特称判断的过程，即由一般性知识推理适合于某一具体情况的结论，是一种从一般到个别的推理。 归纳推理:是从足够多的事例中归纳出一般性结论的推理过程，是一种从个别到一般的推理。 默认推理:是在知识不完全的情况下假设某些条件已经具备所进行的推理 2 确定性推理、不确定性推理 确

2、定性推理:是指推理时所用的知识都是精确的，推出的结论也是确定的，其真值或者为真，或者为假。 不确定性推理:是指推理时所用的知识不都是精确的，推出的结论也不完全是肯定的，其真值位于真与假之间。3 单调推理、非单调推理 单调推理:随着推理过程向前推进及新知识的进入，推出的结论呈单调增加的趋势。 非单调推理:由于新知识的加入，不仅没有加强已推出的结论，反而要使得推理退回到前面的某一步，重新开始。4 启发式推理、非启发式推理 启发式推理:运用与问题有关的启发性知识，且能加快推理进程的推理。5 基于知识的推理、直觉推理 基于知识的推理:根据已掌握的事实，通过运用知识进行推理。 直觉推理:根据常识进行的推

3、理。4.1.2 推理的控制策略1 推理方向 （1）正向推理 （2）逆向推理 （3）混合推理2 求解策略 推理的求解策略:推理是只求一个解，还是求所有解以及最优解等。3 限制策略 推理的限制策略:在控制策略中指定推理的限制条件，以对推理的深度、宽度、时间、空间等进行限制。4 冲突消解策略 在推理过程中，可能发生已知事实可与知识库中的多个知识匹配成功；或者有多个已知事实可与知识库中的多个知识匹配成功。称这种情况为发生了冲突。 冲突消解:需要按一定策略解决冲突，以便从中挑选一个知识用于当前的推理，称这一解决冲突的过程为冲突消解。 解决冲突所用的方法称为冲突消解策略。4.1.3 模式匹配及其变量代换

4、模式匹配: 两个知识模式（如两个谓词公式、两个框架片断等）比较，检查这两个知识模式是否完全一致或近似一致。如果两者完全一致，或者虽不完全一致但其相似程度落在指定的限度内，就称它们是可匹配的，否则为不可匹配。 确定性匹配: 两个知识模式完全一致，或者经过变量代换后变得完全一致。 例:设有如下两个知识模式：P1：Father（李四，李小四）and Man (李小四)P2：Father(x,y) and Man (y) 若用常量“李四”代换变量x，用常量“李小四”代换变量y，则P1与P2就变得完全一致。 定义4.1 代换是形如 t1/x1 , t2/x2, ，tn/xn 的有限集合。其中 t1, t

5、2 tn是项； x1, x2 xn是互不相同的变元； ti /xi 表示用ti 代换 xi , 不允许ti 与 xi 相同，也不允许变元xi循环地出现在另一个tj中。 定义4.2 设 =t1/x1, t2/x2, ，tn/xn =u1/y1, u2/y2, ，um/ym是两个代换，则此两个代换的复合也是一个代换，它是从t1/x1, t2/x2, , tn/xn, u1/y1, u2/y2, ，um/ym中删去如下两种元素： ti/xi 当ti=xi ui/yi 当yix1, x2, ，xn后剩下的元素所构成的集合，记为 定义4.3 设有公式集F=F1, F2, , Fn,若存在一个代换使得F1

6、=F2= =Fn则称为公式集F的一个合一，且称F1, F2, Fn是可合一的。 定义4.4 设是公式集F的一个合一，如果对任一个合一都存在一个代换，使得= 。则称是公式集F的最一般合一(mgu)。 差异集：设有如下两个谓词公式：F1：P（x, y, z） F2：P (x, f (A), h(B) )分别从F1与F2的第一个符号开始比较，得到第一个差异集：D1=y, f (A)当继续比较，又发现F1中的z与F2中的h(B)不同，则得到第二个差异集： D2=z, h(B)求最一般合一算法: （1）初始化，令k=0, Fk=F,k=。其中，是代换空集。 （2）若Fk只含一个表达式，则算法停止，k就是

7、最一般合一；否则转步骤（3）。 （3）找出Fk的差异集Dk。 （4）若Dk中存在变元xk和项tk，且xk不在tk中出现，则：k+1=k 。tk/ xk Fk+1=Fk tk/ xk k=k+1 转步骤（2）；否则， 算法终止，F的最一般合一不存在。例4.1 设有公式集：F=P(A, x, f (g (y), P(z, f (z), f (u) ，求其最一般合一。解：初始化，令k=0，0=， F0=F= P (A, x, f (g (y), P(z, f (z), f (u) Loop 1： F0含有2个表达式，故0不是最一般合一， F0的差异集D0=A，z， 可有代换A/z， 1=0A/z=A

8、/z F1=F0A/z = P(A, x, f (g (y), P(A, f (A), f (u) Loop 2： F1含有2个表达式，故1不是最一般合一， F1的差异集D1=x，f (A)，可有代换f (A)/x，2=1 。f (A)/x =A/z 。f (A)/x =A/z, f (A)/x F2=F1f (A)/x = P(A, f (A), f (g (y), P(A, f (A), f (u)Loop 3： F2的差异集D2=g (y)，u，可有代换g (y)/u， 3=2 。g (y)/u = A/z, f (A)/x 。g (y)/u =A/z, f (A)/x, g (y)/u

9、 F3=F2g (y)/u = P(A, f (A), f (g (y), P(A, f (A), f (g(y) = P(A, f (A), f (g (y) Loop 4：F3中只含有一个表达式，故算法成功终止。公式集 F的最一般合一为3 =A/z, f (A)/x, g (y)/u4.2 归结演绎推理 4.2.1 谓词公式化为子句集的方法 4.2.2 归结原理 4.2.3 归结反演 定理证明的实质是对已知前提P和待证结论Q证明PQ的永真性。 应用反证法的思想可把关于永真性的证明转化为不可满足性的证明，即证明PQ是不可满足的。4.2.1 谓词公式化为子句集的方法 定义4.5 在谓词逻辑中，

10、把原子谓词公式及其否定统称为文字。任何文字的析取式称为子句。 定义4.6 不包含任何文字的子句称为空子句。 由于空子句不含有文字，它不能被任何解释满足，所以空子句是永假的，不可满足的。谓词公式化成子句集的步骤: （1）消去蕴涵连词 利用下述等价关系消去谓词公式中的蕴涵连词“”：PQ PQ （2）减小否定连词的辖域 利用下述等价关系把“”移到紧靠谓词的位置上： （3）约束变元标准化 （4）消去存在量词 若存在量词不在全称量词的辖域内，则用一个个体常量替换受该存在量词约束的变元。 若存在量词位于一个或多个全称量词的辖域内，则需要用Skolem函数f (x1, x2, ，xn )替换受该存在量词约束

11、的变元y。 （5）组成全称量词前缀 （6）利用等价关系把母式化为Skolem标准形： （7）消去全称量词。 （8）对变元更名，使不同子句中的变元不同名。 （9）消去合取连词，得到子句集。例4.2 请将下述谓词公式化为子句集：解：4.2.2 归结原理 子句集中的子句之间是合取关系，其中只要有一个子句不可满足，子句集就不可满足。空子句是不可满足的。因此，若一个子句集中包含空子句，则这个子句集是不可满足的。1. 命题逻辑中的归结原理 定义4.7 若P是原子谓词公式，则称P与P为互补文字。 定义4.8 设C1与C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么从C1和C2中

12、分别消去L1和L2，并将二个子句中余下的部分析取，构成一个新子句C12，则称这一过程为归结，称C12为C1和C2的归结式，称C1和C2为C12的亲本子句。 定理4.2 归结式C12是其亲本子句C1与C2的逻辑结论。 推论4.1 设C1与C2是子句集S中的两个子句，C12是它们的归结式，若用C12代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集S的不可满足性，即 S1的不可满足性 S的不可满足性 推论4.2 设C1与C2是子句集S中的两个子句，C12是它们的归结式，若把C12加入S中，得到新子句集S2，则S与S2在不可满足的意义上是等价的，即 S2的不可满足性 S的不可满足性

13、2. 谓词逻辑中的归结原理 在谓词逻辑中，由于子句中含有变元，所以不可直接消去互补文字，先对变元代换，才能进行归结。例如： 用最一般合一：=A / x 对两个子句分别进行代换： C1=P(A)Q(A) C2=P(A)R(y) 得到归结式：Q(A) R(y) 定义4.9 设C1与C2是两个没有相同变元的子句，L1和L2分别是C1和C2中的文字，若是L1和L2的最一般合一，则称C12=(C1-L1)(C2-L2)为C1和C2的二元归结式，L1和L2称为归结式的文字。例4.3 设C1=P(A)Q(x)R(x)，C2=P(y)Q(B)，给出C1和C2的归结式。 上述归结过程可以用归结树表示如图4.1所

14、示。 图4.1 例4.3的一种归结树 若选L1= Q(x), L2=Q(B), =B/x, 则可得：C12 = (P(A), Q(B), R(B)- Q(B)( P(y), Q(B)-Q(B) =(P(A), R(B)(P(y) =P(A), R(B), P(y) =P(A)R(B)P(y)上述归结过程的归结树如图4.2所示。图4.2 例4.3的另一种归结树4.2.3 归结反演 应用归结原理证明结论为真的过程称为归结反演。 设F为已知前提的公式集，Q为目标公式（结论），用归结反演证明Q为真的步骤： 否定Q，得到 Q； 把 Q并入到公式集F中，得到F， Q； 把公式集F， Q化为子句集S； 应用

15、归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，若出现了空子句，则停止归结，此时就证明了Q为真。例4.6 已知求证：G 是F的逻辑结论。证：首先把F和G 化为子句集图4.4 例4.6的归结树例4.7 在第2章例2.4中曾经得到如下公式： 自然数都是大于零的整数。所有整数不是偶数就是奇数。偶数除以是整数。求证：所有自然数不是奇数就是其一半为整数的数。证：首先把求证的问题用谓词公式表示出来：把F1，F2，F3及G 化成子句集：(1) N(x) GZ(x) (2) N(u) I(u)(3) I(y)E(y)O(y) (4) E(z)I(s(z)(5)N(t)(6

16、) O(t)(7) I(s(t)图4.5 例4.7的归结树4.3 基于归结反演的问题求解问题求解的步骤： 把已知前提用谓词公式表示，并且化为相应的子句集S。 把待求解的问题也用谓词公式表示，把它的否定式与谓词ANSWER构成一个析取式，ANSWER的变元数量和变元名必须与问题公式的变元一致。 把此析取式化为子句集，并且把该子句集加入到子句集S中，得到子句集S。 对S应用归结原理进行归结。 若在归结树的根节点中仅得到归结式ANSWER，则答案就在ANSWER中。例4.8 已知F1：王（Wang ）先生是小李（Li）的老师。F2：小李与小张（Zhang ）是同班同学。F3：如果x与y是同班同学，则

17、x的老师也是y的老师。求：小张的老师是谁？解： 1 定义谓词 T(x, y) x是y的老师。 C(x, y) x与y是同班同学。2 谓词公式表示目标公式G的否定式与ANSWER的析取式为：3 化为子句集(1)T(Wang , Li)(2) C (Li, Zhang )(3) C(x, y) T(z, x)T(x, y)(4) T(u, Zhang )ANSWER(u)图4.6 例4.8的归结树 例4.9 设A，B，C三人中有人从不说真话，也有人从不说假话，某人向这三人分别提出同一个问题：谁是说谎者？A答：“B和C都是说谎者”；B答：“A和C都是说谎者”；C答：“A和B中至少有一个是说谎者”。求

18、谁是老实人，谁是说谎者？解：1 定义谓词： T(x) 表示x说真话。 2 谓词公式表示如果A说的是真话，则有： T(A) T(B)T(C)如果A说的是假话，则有： T(A) T(B)T(C)对B和C说的话作相同的处理，可得： T(B) T(A) T(C) T(B) T(A)T(C) T(C ) T(A) T(B) T(C ) T(A)T(B)3 化成子句集S(1) T(A) T(B)(2) T(A) T(C)(3)T(A)T(B)T(C)(4) T(B) T(C)(5) T(C ) T(A) T(B)(6)T(C )T(A)(7)T(C )T(B)求谁是老实人的目标公式：( x)T(x) (8

19、) T(x)ANSWER(x) 图4.7 求谁是老实人的归结树 证明A和B不是老实人： 设A不是老实人，则有T(A)，把它的否定式T(A) 加入到S中，得到子句集S2。 对S2归结，从而证明了A不是老实人。 同理，可证明B也不是老实人。图4.8 例4.9证明A不是老实人的归结树4.4 归结反演的改进策略4.4.1 删除策略4.4.2 限制策略4.4.1 删除策略1 纯文字删除 如果某文字L在子句集中不存在可与之互补的文字L，则称该文字为纯文字。 在归结时纯文字不可能被消去，因而用包含它的子句进行归结时不可能得到空子句。例如，设有子句集：S= PQR, QR，Q, R 其中，P是纯文字，因此可将子句 PQR从S中删去。2 重言式删除 如果一个子句中同时包含互补文字时，则称该子句为重言式。 例如 P(x) P(x), P(x)Q(x) P(x)都是重言式。 重言式是真值为真的子句。对于一个子句集来说，增加或者删去一个真值为真的子句都不会影响它的不可满足性，因而可从子句集中删去重言式。3 包孕删除 设有子句C1和C2，如果存在一个代换，使得 则称C1包孕于C2。 例如： P(x) 包孕于 P(y)Q(z) =y/x 或称 P(x) 被 P(y)Q(z) 包孕 把子句集中被包孕的子句删去后，不会影响子句集的不可