人工智能及应用_ch3_3.ppt

经典逻辑推理,归结反演求取问题的答案归结演绎推理的策略基于规则的演绎推理,归结反演求取问题的答案,归结原理还可以用于求取问题答案，其思想与定理证明相似，求解步骤为；把已知前提用谓词公式表示，并化为子句集S；把待求解的问题用谓词公式表示，然后把它的否定与谓词ANWSER析取构成析取式，ANWSER的变元与问题谓词的变元完全一致；把此析取式化为子句集，并添加到S中，构成新的子句集S1；对S1使用归结原理，直到得到归结式ANWSER，则问题答案在谓词ANWSER中。,归结反演求取问题的答案-示例,例：已知王先生是小李的老师，小李与小张是同班同学，如果x与y是同班同学，则x的老师也是y的老师。求小张的老师是谁？解：定义谓词T(x,y):x是y的老师；C(x,y):x与y是同班同学。,归结反演求取问题的答案-示例,用谓词表示已知条件T(Wang,Li):王先生是小李的老师;C(Li,Zhang):小李与小张是同班同学;(x)(y)(z)(C(x,y)T(z,x)T(z,y):如果x与y是同班同学，则x的老师也是y的老师。,归结反演求取问题的答案-示例,化子句集T(Wang,Li)C(Li,Zhang)C(x,y)VT(z,x)VT(z,y)表达待求解问题(u)T(u,Zhang)(u)T(u,Zhang)VANWSER(u),归结反演求取问题的答案-示例,化子句集(u)T(u,Zhang)VANWSER(u)(u)T(u,Zhang)VANWSER(u)T(u,Zhang)VANWSER(u)进行归结C(li,y)VT(Wang,y)456C(li,Zhang)VANWSER(Wang)26ANWSER(Wang),归结树,T(Wang,Li),C(x,y)VT(z,x)VT(z,y),C(Li,y)VT(Wang,y),=Wang/z,Li/x,T(u,Zhang)VANWSER(u),C(Li,Zhang)VANWSER(Wang),=Wang/u,Zhang/y,C(Li,Zhang),ANWSER(Wang),归结演绎推理的策略,用产生式系统表示归结过程综合数据库：子句集规则集：IFC1和C2有归结式C12THENS=SC12目标条件：NILS,归结演绎推理的策略,产生式系统基本算法初始化综合数据库，把问题的已知事实送入综合数据库。若规则库中存在尚未使用过的规则，若有则执行3；否则转7。检查规则库中未使用的规则前件能否与综合数据库中的事实匹配，若有从中选择一个；否则转6。执行当前选中的规则，并标记，将结论加入综合数据库，若结论是操作，则执行操作。检查综合数据库中是否包含了问题的解，若包含，问题解决，求解过程结束；否则转2。当规则库有未使用的规则，但均不能与已知事实匹配，要求用户提供新的事实，若提供，则转2；否则，问题无解停止求解过程。若规则库中不再有未使用过的规则，问题无解，停止求解过程。,归结演绎推理的策略,初始化综合数据库DB=S；若NILDB，停止问题得证；DB中是否有可归结的子句，若有执行下一步，否则转7；从DB中选择两个不同的可归结子句C1和C2；求C1和C2的归结式C12；DB=DBC12，返回2；停止，无法证明问题。,归结的一般过程,归结过程是从子句集中不断寻找可归结子句对进行归结，直到归结出空子句或没有可归结子句对为止。一般的归结过程如下：设初始子句集S0=S，对中的全部子句作所有可能的归结，得到第一层归结式，把这些归结式的集合记为S1。用S0中的子句和S1中的子句进行所有可能的归结，得到第二层归结式，把这些归结式的集合记为S2。,归结的一般过程-示例,用S0和S1中的子句与S2中的子句进行所有可能的归结，得到第三层归结式，把这些归结式的集合记为S3。重复此过程直到得到空子句或不能继续归结为止。一般称如上的归结策略为广度优先策略。,归结的一般过程-示例,例：设有如下子句集S=I(x)VR(x),I(a),R(y)VL(y),L(a)用广度优先策略证明S不可满足。证明：从S出发，依次构造S1，S2，S3，。直到出现空子句为止。,示例的归结图,I(x)VR(x),R(y)VL(y),I(a),L(a),R(a),=a/x,I(y)VL(y),=x/y,R(a),=a/y,S0,S1,L(a),=a/y,=a/x,L(a),NIL,=a/y,I(a),=a/y,I(a),S2,归结演绎中的策略,盲目全面进行归结，产生许多无用归结式，更严重的是产生组合爆炸问题。常用的归结策略分为两大类：删除策略：通过删除某些无用的子句缩小归结的范围。限制策略：通过对参加归结的子句进行某些限制减少归结的盲目性。,删除策略-纯文字删除,如果某个文字L在子句集中不存在与其互补的文字L，称此文字为纯文字。纯文字删除法是删除子句集中包含纯文字的子句。例：设子句集S=PVQVR，QVR，Q，RP为纯文字，删除子句PVQVR，然后对QVR，Q，R进行归结。,删除策略-重言式删除,如果一个子句中包含有互补文字，称该子句为重言式。子句PVPVQ是一个重言式，显然这个子句的真值是真，在子句集中删除此子句，不影响子句集的不可满足性。重言式删除法是将子句集中的重言式删除。,删除策略-包孕删除,设子句C1和C2，如果存在一个置换，使得C1C2，则称C1包孕于C2。例：P(x)包孕于P(y)VQ(z)=y/x对子句集来说把包孕子句删除，不影响子句集的不可满足性。包孕删除法：从子句集中删除包孕子句。,删除策略的完备性,以上的几种删除策略是否为完备的归结策略？,限制策略-支持集策略,支持集策略是沃斯等人在1965年提出的一种归结策略。它要求参加归结的两个亲本子句中至少有一个是由目标公式的否定所得到的子句或是它们的后裔。可以证明支持集策略是完备的，即子句集不可满足时，使用支持集策略一定可以归结出空子句。,支持集策略-示例,I(x)VR(x),R(y)VL(y),I(a),L(a),R(a),=a/x,I(y)VL(y),=x/y,R(a),=a/y,S0,S1,L(a),=a/y,=a/x,L(a),NIL,=a/y,I(a),=a/y,I(a),S2,NIL,限制策略-单文字子句策略,如果一个子句只包含一个文字，则称此子句是一个单文字子句。单文字子句策略：要求参加归结的两个亲本子句中至少有一个子句是单文字子句。单文字子句策略是不完备的。,单文字子句策略-示例,I(x)VR(x),R(y)VL(y),I(a),L(a),R(a),=a/x,I(y)VL(y),=x/y,R(a),=a/y,S0,S1,L(a),=a/y,=a/x,L(a),NIL,=a/y,I(a),=a/y,I(a),S2,限制策略-线性输入策略,这种策略要求每次参加归结的两个亲本子句中，至少有一个是初始子句集中的子句。线性输入策略是一种不完备的归结策略。例如S=Q(u)VP(u),Q(x)VP(x),Q(y)VP(y),Q(w)VP(w)是不可满足的，但使用线性输入策略无法得到空子句。,线性输入策略-示例,I(x)VR(x),R(y)VL(y),I(a),L(a),R(a),=a/x,I(y)VL(y),=x/y,R(a),=a/y,S0,S1,L(a),=a/y,=a/x,L(a),NIL,=a/y,I(a),=a/y,I(a),S2,NIL,限制策略-祖先过滤策略,要求参加归结的两个亲本子句满足以下两个条件中的任意一个：参加归结的两个亲本子句中，至少有一个是初始子句集中的子句。如果两个亲本子句都不是初始子句集的子句，则一个应是另一个的先辈子句。可以证明，祖先过滤策略是完备的。,祖先过滤策略-示例,P(x)VQ(x),P(y)VQ(y),P(x),P(z)VQ(z),P(a)VQ(a),Q(x),P(a),NIL,基于规则的演绎推理,归结演绎方便了机器推理，但在化子句集时损失了一些控制信息。例如：如下的子句PVQVR其可由下面的几个公式等价得到。PQR、RQP、PRQ、。,基于规则的正向演绎推理,定理证明问题：已知一组事实，以及相关的领域知识，证明目标。一般情况下，已知事实和目标是用谓词公式表达，而相关领域的知识是由一组蕴含式表达，我们将这组蕴含式称为规则。从事实出发，正向使用规则（F规则），直接进行演绎，直至达到目标为止的一种证明方法。,基于规则的正向演绎推理,为了实现正向推理，需要对定理证明问题的已知事实、规则和证明目标按一定的形式表示出来。下面讨论表示形式的转换。,基于规则的正向演绎推理,事实表达式的与/或形变换：基于规则的正向演绎推理通常将已知事实化为与/或形，化与/或形的基本步骤如下：利用规则PQPVQ消去蕴含符号。利用狄。摩根定律及量词转换律把移到紧靠谓词，使否定连接词的辖域只含一个谓词。化为前束范式。变元标准化。消去全称量词。,基于规则的正向演绎推理,例：将公式化为与或形(x)(y)(Q(y,x)(R(y)VP(y)S(x,y)解：(x)(y)(Q(y,x)(R(y)VP(y)S(x,y)(x)(y)(Q(y,x)(R(y)VP(y)VS(x,y)(x)(y)(Q(y,x)(R(y)P(y)VS(x,y)(x)(y)(Q(y,x)(R(y)P(y)VS(x,y)(y)(Q(y,a)(R(y)P(y)VS(a,y)Q(y,a)(R(y)P(y)VS(a,y),基于规则的正向演绎推理,事实表达式的与/或树：为了推理过程直观将事实表达式的与/或形表示为一棵与/或树。,基于规则的正向演绎推理,与/或树中的结点表示与/或形中的一个子表达式，表达式间的关系规定如下：表达式E为k个子表达式析取时即E=E1VE2VVEk,每个子表达式Ei均被表示为的后继结点，并由一个k连接符将这些后继结点连接到父结点，即表示成与的关系。表达式E为k个子表达式合取时即E=E1E2Ek,每个子表达式Ei均被表示为的后继结点，并由一个单一连接符将这些后继结点连接到父结点，即表示成或的关系。,基于规则的正向演绎推理,例：将Q(y,a)(R(y)P(y)VS(a,y)表示为与/或树。,Q(y,a)(R(y)P(y)VS(a,y),Q(y,a),(R(y)P(y)VS(a,y),R(y)P(y),S(a,y),R(y),P(y),基于规则的正向演绎推理,与/或树的特点根结点是事实表达式的与/或形，端结点是事实表达式中的一个文字。解树集对应着子句集。例中的三个解树对应着三个子句，Q(y,a)，R(y)VS(a,y)，P(y)VS(a,y),基于规则的正向演绎推理,规则的与/或形变换：基于规则的正向演绎推理中要求规则要具有LW的形状，其中L为单文字，W为与/或形。规则的变换步骤：利用规则PQPVQ暂时消去蕴含符号。利用狄。摩根定律及量词转换律把移到紧靠谓词，使否定连接词的辖域只含一个谓词。引入Skolem函数，消去存在量词。化为前束范式，消去全称量词。恢复蕴含式表示。,基于规则的正向演绎推理,例：(x)(y)(z)(P(x,y,z)(u)Q(x,u)(x)(y)(z)(P(x,y,z)V(u)Q(x,u)(x)(y)(z)(P(x,y,z)V(u)Q(x,u)(x)(y)(P(x,y,f(x,y)V(u)Q(x,u)P(x,y,f(x,y)VQ(x,u)P(x,y,f(x,y)Q(x,u),基于规则的正向演绎推理,若出现规则前件非单文字时，如1V2将其等价为两个规则：L1WL2W,基于规则的正向演绎推理,目标公式的表示形式：基于规则的正向演绎推理要求将目标公式表达为子句集的形式。,基于规则的正向演绎推理过程,命题逻辑：设已知事实表示为如下的与/或形(PVQ)R)V(S(TVU)规则为(XY)VZ,基于规则的正向演绎推理过程,(PVQ)R)V(S(TVU),(PVQ)R,S(TVU),PVQ,R,TVU,S,T,U,P,Q,S,XVY,Z,Y,X,基于规则的正向演绎推理过程,已知事实的四个子句VVVVVVVV规则化为子句的两个子句VXVZVYVZ,基于规则的正向演绎推理过程,应用规则后的与/或树的子句（解图）有六个XVZVYVZVXVZVVYVZVVVVVVV,基于规则的正向演绎推理过程,前面的四个子句是已知事实和规则表示的子句进行归结得到的所有归结式。既有规则应用结果，就是归结式的完备集，即规则的应用演绎出所有的逻辑推论。基于规则的正向演绎系统的演绎过程就是不断地调用匹配的规则，对与/或树进行变换，直到生成的与/或树含有目标表达式为止。,基于规则的正向演绎推理-示例,已知事实表达式：AVB规则集：ACDBEF目标公式：CVF,基于规则的正向演绎推理-示例,AVB,A,B,A,B,C,D,E,F,C,F,CVF,基于规则的正向演绎推理过程,谓词逻辑：与命题逻辑的推理过程的主要区别在于，已知事实、规则和目标公式的标准化时要考虑变元和Skolem函数，使用规则匹配时需要合一处理。,基于规则的正向演绎推理-示例,事实：Fidobarksandbites,orFidoisnotadog.DOG(Fido)V(BARKS(Fido)BITES(Fido)规则：ALLterriersaredogs.(x)(DOG(x)TERRIES(x)Anyonewhobarksisnoisy(y)(BARKS(y)NOISY(y)目标:Thereexistssomeonewhoisnotaterrierorwhoisnoisy.(z)(TERRIER(z)VNOISY(z),基于规则的正向演绎推理-示例,DOG(Fido)V(BARKS(Fido)BITES(Fido),DOG(Fido),BARKS(Fido)BITES(Fido),BARKS(Fido),BITES(Fido),DOG(Fido),Fido/x,TERRIER(Fido),BARKS(Fido),Fido/y,NOISY(Fido),目标,规则1,规则2,基于规则的逆向演绎推理,逆向演绎系统：是从目标出发，反方向使用规则（B规则）对目标表达式的与/或树进行变换