人工智能lesson3-4

《人工智能lesson3-4》由会员分享，可在线阅读，更多相关《人工智能lesson3-4（48页珍藏版）》请在金锄头文库上搜索。

1、,第三章 基于谓词逻辑的机器推理-3.2 归结演绎推理,3.2.1子句集 定义1 原子谓词公式及其否定称为文字；文字的析取式称为子句；r个文字组成的子句称为r-文字子句。1-文字子句也称为单元子句。不含任何文字的子句称为空子句，记为或NIL。由子句构成的集合称为子句集。 任何一个谓词公式都可以化为子句集，步骤如下： （1）、利用等价式A B A B 和 A B (A B) (B A)消去联结词“ ” 和 “ ”。 （2）、缩小否定联结词的作用范围，使其仅作用于原子公式。可利用下列等价式：, A A； (AB) A B； (A B) A B； xA(x) x A(x)； xA(x) x A(x)

2、 （3）、重新命名变元名，使不同量词约束的变元有不同的名字。,（4）、消去存在量词。若存在量词不在全称量词的辖域内，则用一个常量符号替换该存在量词辖域中的相应约束变元。这样的常量称为Skolem常量；若该存在量词在一个或多个全称量词的辖域内，则用这些全称量词指导变元的一个函数替换该存在量词约束的变元。这样的函数称为Skolem函数。 例如x1 x2 xnyP(x1,x2, xn,y)中y可用Skolem函数f(x1,x2, xn)替换为x1 x2 xnP(x1,x2, xn,f(x1,x2, xn)。,（5）、把全称量词全部移到公式的左边。 （6）、把全称量词后面的公式利用等价关系A(B C)

3、 (AB) (A C)化为子句的合取式，得到的公式称为Skolem标准形。Skolem标准形的一般形式为x1 x2 xnM，其中M是子句的合取式。 （7）、消去全称量词。 （8）、对变元更名，使子句间无同名变元。,（9）、消去合取词 ，以子句为元素组成的集合称为谓词公式的子句集。 例、把谓词公式xyP(x,y) yQ(x,y)R(x,y)化为子句集。 定理1 谓词公式G 不可满足当且仅当其子句集S不可满足。子句集S是不可满足的是指其全部子句的合取式是不可满足的。,3.2.2 命题逻辑中的归结原理,要证明在前提P下结论Q成立，即是证明P Q永真，这只须证明P Q不可满足。根据定理1，只须证明P

4、Q的子句集不可满足。由于子句之间是合取关系，只要有一个子句不可满足，则整个子句集不可满足。由于空子句是不可满足的，所以如果子句集中包含空子句，则该子句集是不可满足的。若子句集中不包含空子句，则可通过Robinson提出的归结原理对子句集进行归结，归结过程保证子句集的不可满足性不变。一旦归结出空子句，则证明结束。因此，归结原理把定理的证明化为子句集中归结出空子句的过程。,定义、设L是一个文字，则称L与L为互补文字。 定义、设C1、C2是命题逻辑中的两个子句， C1 中有文字L1 ， C 中有文字L，且L1与L互补， 从C1，C中分别删除L1 ， L，再将剩余部分析取起来，构成的新子句C1称为C1

5、与C2的归结式（消解式）， C1，C2称为C1的亲本子句。,定理、归结式C1是其亲本子句C1与C2的逻辑结论。 推论、设C1，C2是子句集S的两个子句， C1是它们的归结式，则 （）若用C1代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子句集S的不可满足性。即 S1不可满足S不可满足,（）若把C1加入到S中，得到新子句集S，则S与S在不可满足意义上是等价的。即 S2不可满足 S不可满足 例、用归结原理证明R是P， （P Q） R， （ SU） R，U的逻辑结果。,3.2.3 替换与合一,定义、一个替换(Substitution)是形如t1 / x1, t2 / x2 ,tn /

6、 xn 的有限集合，其中t1 , t2 ,tn 是项， x1, x2 ,xn是互不相同的个体变元。 ti / xi表示用ti代换xi 。 ti与xi不同，xi也不能出现在tj中(j=1,2,n)。 例、a/x, g(y)/y, f(g(b)/z是一个替换，g(y)/x, f(x)/y不是一个替换。,定义、设t1 / x1, t2 / x2 ,tn / xn 是一个替换，E是一个表达式（项、原子公式、文字、子句），把E中出现的所有个体变元xi都用ti 替换，得到的结果记为E ，称为E在下的替换实例。 例、若E=P(x,y,g(z), a / x, f(b) /y ,c /z ，则E= P(a,f

7、(b),g(c)。,定义、设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 ，当yi x1, x2 , xn 。 得到的集合仍是一个替换，称为与的复合，记为。 例、见教材p67例3.13。,定义、设S= F1, F2 , Fn 是一个原子谓词公式集，若存在一个替换，使得F1 F2 Fn ，则称为S的一个合一（Unifi

8、er），并称S为可合一的。 一个公式集的合一一般不唯一。 定义、设是公式集S的一个合一，如果对S的任何一个合一，都存在一个替换，使得 ，则称为S的一个最一般合一（Most General Unifier），简称MGU。,定义、设S是一个非空的具有相同谓词名的原子公式集，从S中各公式的左边第一个项开始，同时向右比较，每一组不都相同的项的差异部分组成的集合称为S的差异集。 例、公式集S=P(a,x,f(g(y),P(z,h(z,u),f(u)的差异集为a,z, x,h(z,u), g(y),u,3.2.3 替换与合一,设S为一非空有限具有相同谓词名的原子谓词公式集，求S的MGU的算法： （1）、令

9、k=0, Sk=S, k= （ 表示空替换）。 （2）、若Sk只含有一个谓词公式，则算法停止， k就是要求的最一般合一。 （3）、求Sk的差异集Dk 。 （4）、若Dk中存在元素 xk 和 tk ，其中xk是变元， tk是项且xk不在tk中出现，则置Sk+1 = Sktk /xk ， k+1 = k tk /xk ，k=k+1，然后转步（2）。 （5）、算法停止，S的最一般合一不存在。,定理3（合一定理）、如果S是一个非空有限可合一的公式集，则合一算法总是在步（2）停止，且最后的k即是S的最一般合一。,3.2.4 谓词逻辑中的归结原理,定义12、设C1，C2是两个没有相同变元的子句，L1，L2

10、分别是C1，C2中的两个文字，如果L1与L2有最一般合一 ，则子句C12=(C1-L1) (C2-L2)，称作C1和C2的二元归结式（二元消解式）。 C1和C2称为C12的亲本子句， L1，L2称为消解文字。 若在参加归结的子句内部含有可合一文字，则在进行归结之前，应对这些文字进行合一。 定义13、如果子句C中，两个或两个以上的文字有一个最一般合一 ，则称C为C的因子。,定义14、子句C1，C2的归结式，是下列二元归结式之一： 1）、 C1和C2的二元归结式； 2）、 C1和C2的因子的二元归结式； 3）、 C1的因子和C2的二元归结式； 4）、 C1的因子和C2的因子的二元归结式。,定理4、

11、谓词逻辑中的归结式是它的亲本子句的逻辑结果。 类似于命题逻辑中的两个推论仍成立。 归结反演：应用归结原理证明定理的过程称为归结反演。 若F为已知前提的公式集，Q为结论，用归结反演证明Q为真的步骤是： （1）、否定Q，得到Q； （2）、把Q并入到公式集F中，得到F, Q； （3）、把公式集F, Q化为子句集S； （4）、应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，直到出现空子句，就证明了Q为真。,例、自然数都是大于零的数；所有整数不是偶数就是奇数；偶数除以2是整数。求证：所有自然数不是奇数就是其一半为整数的数。 证明：前提： F1 ：x(N(x) G

12、Z(x) I(x) F2 ：x(I(x) E(x) O(x) F3 ：x(E(x) I(h(x) 结论：G：x(N(x) O(x) I(h(x) F1、 F2、 F3 及G 化为子句集： （1） N(x)GZ(x) （2） N(y)I(y) （3） I(z)E(z) O(z),（4） E(u)I(h(u) （5）N( c) （6） O(c) （7） I(h( c) 归结： （8）I( c) ( (2), (5), c/y ) （9） I(c) E( c) ( (3), (6), c/z ) （10） E( c) ( (8), (9) ) （11） I(h( c) ( (4), (10), c/

13、u ) （12） ( (7), (11) ),定理5（归结原理的完备性）、如果子句集S是不可满足的，则必存在一个由S推出空子句的归结序列。 其它例见教材p78,例15，16。 课堂练习：p94，题6。,归结演绎树： N(y)I(y) N( c) I(z)E(z) O(z) O(c) I( c) I(c) E( c) E(c ) E(u)I(h(u) I(h (c ) I(h( c) ,3.3 应用归结原理求取问题答案,应用归结原理求取问题答案的步骤： （1）、把已知前提用谓词公式表示出来，并化为子句集S。 （2）、把待求解问题也用谓词公式表示出来，然后把它的否定与谓词ANS构成析取式。ANS的

14、变元应与问题的变元完全一致。 （3）、把此析取式化为子句集，并把该子句集并入S中得到子句集S。 （4）、对S应用归结原理进行归结。 （5）、若得到归结式ANS，则答案就在ANS中。,例、设A、B、C三人中有人从不说真话，也有人从不说假话，某人向这三人分别提出同一个问题：谁是说谎者？A答：“B和C都是说谎者”；B答：“A和C都是说谎者”；C答：“A和B中至少有一个是说谎者”。求谁是老实人，谁是说谎者？ 解、设T(x)表示x说真话。如果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 ) 化为子句集S： （1）、 T(A) T(B ) （2）、 T(A) T(C ) （3）、 T(A)T(B)T(C ) （）、 T(B) T(C ) （）、 T(A) T(B ) T(C ),（）、 T(C)T(A) （）、 T(C)T(B) 先求谁是老实人， 把T(x) ANS(x)并入S （）、 T(x) ANS(x) （）、 T(A) ANS( C) ( (8), (6), C/x ) （）、T(B) ANS(C) ( (7), (8), C/x ) （