人工智能lesson3-4.ppt

,第三章 基于谓词逻辑的机器推理-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) （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) (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 Q的子句集不可满足。由于子句之间是合取关系，只要有一个子句不可满足，则整个子句集不可满足。由于空子句是不可满足的，所以如果子句集中包含空子句，则该子句集是不可满足的。若子句集中不包含空子句，则可通过Robinson提出的归结原理对子句集进行归结，归结过程保证子句集的不可满足性不变。一旦归结出空子句，则证明结束。因此，归结原理把定理的证明化为子句集中归结出空子句的过程。,定义、设L是一个文字，则称L与L为互补文字。 定义、设C1、C2是命题逻辑中的两个子句， C1 中有文字L1 ， C 中有文字L，且L1与L互补， 从C1，C中分别删除L1 ， L，再将剩余部分析取起来，构成的新子句C1称为C1与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 / 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(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的一个合一（Unifier），并称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）、令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分别是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、谓词逻辑中的归结式是它的亲本子句的逻辑结果。 类似于命题逻辑中的两个推论仍成立。 归结反演：应用归结原理证明定理的过程称为归结反演。 若F为已知前提的公式集，Q为结论，用归结反演证明Q为真的步骤是： （1）、否定Q，得到Q； （2）、把Q并入到公式集F中，得到F, Q； （3）、把公式集F, Q化为子句集S； （4）、应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，直到出现空子句，就证明了Q为真。,例、自然数都是大于零的数；所有整数不是偶数就是奇数；偶数除以2是整数。求证：所有自然数不是奇数就是其一半为整数的数。 证明：前提： F1 ：x(N(x) GZ(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/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的变元应与问题的变元完全一致。 （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 ) （）、 T(B) ANS(C) ( (9), (1) ) （）、ANS(C ) ( (10), (11) ) 因此C是老实人。无论如何归结，推不出ANS(A), ANS(B)。下证A是说谎者，即T(A)，其否定为 （） T(A)即T(A) （） T(B) ( (8), (1) ) （） T(C ) （），（） ） （） T(C ) （ （）， （） ） （） NIL （ （）， （） ）,3. 归结策略,3.4.1 问题的提出 归结反演的一般过程。 步 将子句集S置入CLAUSES表； 步 若空子句NIL在CLAUSES中，则归结成功，结束。 步 若CLAUSES表中存在可归结的子句对，则归结之，并将归结式并入CLAUSES表，转步； 步 归结失败，退出。,穷举算法（广度优先策略） 第一轮：将原子句集S中的子句两两归结，产生的归结式集合记为S1，再将S1并入CLAUSES表； 第二轮：将新的CLAUSES表即SS1中的子句与S1中的子句两两归结，产生的归结式集合记为S2，再将S2并入CLAUSES； 第三轮：将新的CLAUSES表即SS1 S2中的子句与S2中的子句两两归结，。 如此下去，直到出现空子句。,例1 设有如下的子句集，用穷举算法归结如下： S： （1） PQ （2） PQ （3） P Q （4） P Q S1： （5） Q (1), (2) （6） P (1), (3) （7） Q Q (1), (4) （8） P P (1), (4) （9） Q Q (2), (3) （10） P P (2), (3) （11） P (2), (4),（12） Q (3), (4) S2：（13） P Q (1), (7) （14） P Q (1), (8) （15） P Q (1), (9) （16） P Q (1), (10) （17） Q (1), (11) （18） P (1), (12) （19） Q (2), (6) （20） PQ (2), (7) （21） PQ (2), (8) （22） PQ (2), (9),（23） PQ (2), (10) （24） P (2), (12) （25） P (3), (5) （26） P Q (3), (7) （27） P Q (3), (8) （28） P Q (3), (9) （29） P Q (3), (10) （30） Q (3), (11) （31） P (4), (5) （32） Q (4), (6),（33） P Q (4), (7) （34） P Q (4), (8) （35） P Q (4), (9) （36） P Q (4), (10) （37） Q (5), (7) （38） Q (5), (9) （39） (5), (12),3.4.2 几种常用的归结策略,1、删除策略 定义、设C1，C2是两个子句，若存在替换，使得C1 C2 ，则称子句C1类含C2 。 例、P(x)类含P(a) Q(y)； P(x)类含P(a)。 删除策略。在归结过程中可随时删除以下子句： （1）、含有纯文字的子句；纯文字是指在子句中无补文字的文字。 （2）、含有永真式的子句； （3）、被子句集中别的子句类含的子句。 使用删除策略，例1可简化为： （1） PQ （7） P (2), (4) （2） PQ （8） Q (3), (4) （3） P Q （ 9） (5), (8) （4） P Q （5） Q (1), (2) （6） P (1), (3),删除策略的特点： 删除策略的思想是及早删除无用字句，以避免无效归结，缩小搜索空间。 删除策略是完备的。一个归结策略是完备的，是指对于不可满足的子句集，使用该策略进行归结，最终必导出空子句。,2、支持集策略 支持集是指目标公式的否定的子句集。支持集策略指每次归结时，两个亲本子句中至少要有一个是目标公式否定的子句或其后裔。 例、见教材P84例4. 支持集策略的特点： 支持集策略实际是一种目标制导的反向推理。 支持集策略是完备的。,3、线性归结策略 在归结过程中，除第一次归结可都用初始子句集S中的子句外，其它的各次归结至少要有一个亲本子句是前次归结的结果。 例、P85例5 线性归结策略的特点：完备、高效、与别的策略兼容。,4、输入归结策略 每次参加归结的亲本子句，必须至少有一个是初始子句集S中的子句。 输入策略的特点： 输入归结策略实际是一种自底向上的推理，它有相当高的效率。 输入归结策略不完备。例如S= PQ , PQ, P Q, P Q不可满足，但用输入归结策略导不出空子句。 可与支持集策略、线性归结策略结合。,5、单元归结策略（单文字归结策略） 每次参加归结的两个亲本子句中，必须至少有一个是单元子句（单文字子句）。 单元归结策略的特点： 可以尽快逼近空字句； 效率高但不完备 改进型的单元归结策略：单元优先策略。,6、祖先过滤形策略 参加归结的两个子句，要么至少有一个是初始子句集中的子句，要么一个是另一个的祖先。 例6、P86例6 祖先过滤形策略的特点： 是输入策略的改进。 是完备的,3.4.3 归结策略的类型 简化性策略。 限制性策略。 有序性策略。 3.5 归结反演程序举例（略）,3.6 Horn子句归结与逻辑程序,3.6.1 子句的蕴含表示形式 正文字：原子公式称为正文字。 负文字：原子公式的否定称为负文字。 把所有正、负文字分别放在一起，任意子句可写为： Q1 Qn P1 Pm 可近一步化为蕴含式： Q1 Q2 Qn P1 P2 Pm 如果约定前提文字之间恒为合取关系，结论文字之间恒为析取关系，则上式可简化为： Q1 ， Q2 ， ，Qn P1，P2 ， ，Pm,写成另一种方式： P1，P2 ， ，Pm Q1 ， Q2 ， ，Qn 两种特殊情形： 当m=0时，变为 Q1 ， Q2 ， ，Qn ，相当于 （Q1 Q2 Qn ）。 当n=0时，变为P1，P2 ， ，Pm ，这相当于P1 P2 Pm 。 对于子句的蕴含表示形式，归结过程变为：从其中一个子句的“”号左（右）侧与另一个子句的“”号右（左）侧的文字中寻找可合一文字对