第三章 演绎推理.doc

第三章 演绎推理 自动定理证明是人工智能一个重要的研究领域，是早期取得较大成果的研究课题之一，在发展人工智能方法上起过重大作用。 1956，美国，Newell, Simon, Shaw编制逻辑理论机：The Logic Theory Machine 简称 LT. 证明了数学原理（罗素）第二章中38个定理, 改进后证明了全部52个定理。是对人的思维活动进行研究的重大成果，是人工智能研究的真正开端。在此之后，发展了一些机械化推理算法，很成功地用到人工智能系统中。第一节 鲁滨逊归结原理一、命题逻辑中归结推理1.归结： 消去子句中互补对的过程： 子句： 任何文字的析取式C称为子句，C=PQ7R=P,Q,7R 如：C1=LVC1=L,C1 C2=7LVC2=7L,C2 可以证明C12=C1VC2=C1,C2是C1,C2的逻辑结论： 即：C1C2C12 证明：C1=LVC1=77C1VL=7C1L C2=7LVC2=LC2 所以7C1C2=77C1VC2=C1VC2 实际上是PQ, Q PPR的应用 即前提成立结论成立，也即结论不成立前提不成立 S子句集：其中有C1,C2归结式 S子句集：C12代替C1,C2 则： S不可满足S不可满足2.归结推理步骤 要证AB成立(或证AB重言、永真)，只要证A7B不可满足(永假) 化A7B为合取范式C1C2Cm 子句集S=C1,C2, Cm 归结规则用于S，归结式入S中.重复，直到S中出现空子句。 证明：SVR是PQ , P R，QS的逻辑结论。 （PQ) (P R) (QS) 7(SR) =（PQ） (7PR) (7QS) 7S7R 所以S=PQ,7PR,7QS,7S,7R (1)PQ (2)7PR (3)7QS (4)7S (5)7R (6)QR (1)(2) 归结 (7)7Q (3)(4) 归结 (8)Q (5)(6) 归结 (9)F (7)(8) 归结命题逻辑中不可满足的子句集S，使用归结原理，总能在有限步内得到一个空子句归结原理是完备的。二、谓词逻辑中的归结原理 谓词和子句中含有个体变元，同一谓词含有不同的个体变元。所以寻找互补对更困难。 例：C1=P(y)Q(y) C2=7P(f(a)R(a)1. 置换定义：形如t1/a1，t2/a2，tn/an的有限集合，表示ti代换ai，其中ti是项，变量，常量，函数。ai是变量，且ti不同于ai。置换的目的是使得S中有相同互补文字的子句中谓词各对应项变得一致，以便于归结。,l,a表示置换。F=G，则F是F的逻辑推论。 例如，F=P(x, f(x),y), P(a,z,g(z) 做置换a1=a/x之后得: G1=Fa1 =P(a,f(a),y)， P(a,z,g(z) a2 =f(a)/z G2=G1a2 =P(a,f(a),y)， P(a, f(a),g(f(a) a3 =g(f(a)/y G3=G2 a3 =P(a,f(a),g(f(a), P(a, f(a),g(f(a)= a1 a2a3=a/x, f(a)/z, g(f(a)/y是一个置换.2.合一 定义：设有公式集F=F1, F2, , Fn，若存在一个置换，可使F1=F2=Fn, 则称为F的合一置换。称F是可合一的。 如上面“置换”一节中的例子。 很明显，很多F是不可合一的，而且一个公式集合的合一置换不唯一（如上例中， a2 = g(a)/y。 定义：如果a是公式集F的一个合一置换，且对F的任何一个合一i，都存在一个置换li，使得i =a li，则称a为F的最一般合一.（Most General Unifier简记为 MGU） 最一般合一是最简单的合一置换。求F的最一般合一方法：从左到右比较F中公式的对应项，若不同则作置换，直到对应项完全相同为止。3.斯柯林范式： 不含存在量词和母式为合取范式的前束范式为斯柯林范式 (x)(y)(z)P(x,y,z)化为: (y)P(a,y,f(y) (x)(y)(z)Q(x,y,z)化为： (x)Q(x,f(x),g(x)(x)(y)(z)(u)R(x,y,z.u)化为： (y)(z)R(a,y,z,f(y,z) 4.归结推理过程 例：C1=P(x)Q(x) C2=7P(a)R(y) 令=a/x C1=C1=P(a)Q(a) C2=7P(a)R(y) C12=Q(a)R(y)是C1,C2的逻辑推论 定义：设C1和C2是两个子句，L1，L2分别是C1和C2中的文字，如果是L1与7L2的最一般合一，那么 C12(C1-L1)C2-C2为C1，C2的双归结式。如上例：L1= P(x)，L2=7P(a) 在一阶谓词中, 对于不可满足的子句集S，一定可以在有限步内推出空子句。所以谓词逻辑中的归结原理也是完备的。 并非所有符号相同但变元不同的谓词公式都可合一，如 C1= P(x)Q(x)C1= P(z)Q(z) C2=7 P(f(x)R(y)所以要易名 例：F1=(x)( P(x)( Q(x)R(x) F2=(x)( P(x)S(x) G=(x)(S(x) R(x) 证明G是F1F2的逻辑推论证明:F1F27G =(x)(7P(x)(Q(x)(R(x)(x)(P(x)S(x)(x)(7S(x)7R(x) (7P(x)Q(x)( 7P(x)R(x) P(a)S(a)(7S(x)7R(x) S=7P(x)Q(x), 7P(y)R(y), P(a), S(a), 7S(z)7R(z) 归结树如下： 7P(x)Q(x) 7P(y)R(y) P(a) S(a) 7S(z)7R(z) = = | a/y | a/z R(a) 7R(a) = | F 所以G是F1,F2的逻辑推论。 例2：证明G是F1, F2的逻辑推论，其中： F1=(x)(P(x)(y)(Q(y) 7L(x,y) F2=(x)(P(x)(y)(R(y) L(x,y)G=(x)(R(x) 7Q(x)解： 对F1: (x)(7P(x)(y)(7Q(y)7L(x,y) S1=7P(x)7Q(y)7L(x,y) 对F2: (P(a) (y)(7R(y)L(a,y) S2=P(a), 7R(z)L(a,z) 对7G : (x)(77R(x)77Q(x) S3=R(b), Q(b)7P(x)7Q(y)7L(x,y) P(a) 7R(z)L(a,z) R(b) Q(b)= = | a/x | b/z7Q(y)7L(a,y) L(a,b)= | b/y7Q(b)= | F5.归结策略 用归结推理方法可以证明S的子句不可满足性. 由于该过程不断产生新子句，因此，子句会越来越多，同样会出现组合爆炸问题。并且会产生大量的无用子句。因此在归结中选择哪两个子句（含有互补对）进行归结，是一个控制策略问题。 如果用树来表示推理过程，就容易理解控制策略。 演绎树（倒长的树） 例如证S=7AB, A, D, 7D7B不可满足。 7AB A D 7D7B = = | |B 7B= | F 1)宽度优先策略 第一级归结： 生成可能生成的全部归结式S1, S1=S1S0 第二级归结： 生成可能生成的全部归结式S2, S2=S2S1(这时已进行归结的子句对不再归结) 直到生成空子句该方法效率低，但它是完备的。即只要子句集不可满足，则一定能在有限步内归结得到空子句。 例如证S=7AB, A, D, 7D7B不可满足。 2)支持集优先策略每次归结时，要归结的两个子句(亲本子句)至少有一个是与目标公式的否定式有关的子句（目标公式的否定式化成的子句本身或它的有关后商）该策略完备？且效率高(相当于在宽度优是策略中有了启发式信息) 例如证DB 是7AB，A, D的逻辑推论 3）单元子句优先策略 每次归结时，优先选择单文字子句作归结（至少一个是原文字子句）。这样得出的归结式简单，可能会提高效率。 很显然，这种归结策略不完备。 4)删除策略删除在归结时产生的无用子句，从而减少了中子句数量。可以删除下面子句： a.永真式：P7P，Q7Q b.重复出现的子句c.被归类的子句：子句C把D归类，当且仅当存在一个置换l，使得ClD ,称D为被归类子句。 5)线性归结 首先选择一个子句C0，与其它式作归结产生C1，然后，对于新生成的Ci， i=1,2,n立刻被选中与其它子句Bi或Cj归结，生成C i+1。 如果初始子句选择得正确，线性归结是完备的。 类似深度优先搜索方法。其中C0选择是重要的，要选择的是关键子句，即缺了C0剩余子句集可满足，这是在支持集优先策略上的改进。 6)组合策略： 组合以上几种方法。6.应用 用于证明定理，如果x=A，W(x)真否? 即x=A W(x)取