《人工智能及应用_ch3_3(精品).ppt》由会员分享，可在线阅读，更多相关《人工智能及应用_ch3_3(精品).ppt（55页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、经典逻辑推理经典逻辑推理归结反演求取问题的答案归结反演求取问题的答案归结演绎推理的策略归结演绎推理的策略基于规则的演绎推理基于规则的演绎推理归结反演求取问题的答案l归结原理还可以用于求取问题答案，其思想与定理归结原理还可以用于求取问题答案，其思想与定理证明相似，求解步骤为；证明相似，求解步骤为；1.把已知前提用谓词公式表示，并化为子句集把已知前提用谓词公式表示，并化为子句集S；2.把待求解的问题用谓词公式表示，然后把它的否定把待求解的问题用谓词公式表示，然后把它的否定与谓词与谓词ANWSER析取构成析取式，析取构成析取式，ANWSER的变元的变元与问题谓词的变元完全一致；与问题谓词的变元完全一
2、致；3.把此析取式化为子句集，并添加到把此析取式化为子句集，并添加到S中，构成新的子中，构成新的子句集句集S1；4.对对S1使用归结原理，直到得到归结式使用归结原理，直到得到归结式ANWSER，则，则问题答案在谓词问题答案在谓词ANWSER中。中。归结反演求取问题的答案-示例例：已知王先生是小李的老师，小李与小张是同例：已知王先生是小李的老师，小李与小张是同班同学，如果班同学，如果x与与y是同班同学，则是同班同学，则x的老师也的老师也是是y的老师。求小张的老师是谁？的老师。求小张的老师是谁？解：定义谓词解：定义谓词 T(x,y):x是是y的老师；的老师；C(x,y):x与与y是同班同学。是同班
3、同学。归结反演求取问题的答案-示例用谓词表示已知条件用谓词表示已知条件1.T(Wang,Li):王先生是小李的老师王先生是小李的老师;2.C(Li,Zhang):小李与小张是同班同学小李与小张是同班同学;3.(xx)(yy)(z z)(C(x,y)T(z,x)T(z,yT(z,x)T(z,y):):如果如果x与与y是同班同学，则是同班同学，则x的老师也是的老师也是y的老师。的老师。归结反演求取问题的答案-示例化子句集化子句集1.T(Wang,Li)2.C(Li,Zhang)3.C(x,y)V VT(z,x)VT(z,yT(z,x)VT(z,y)表达待求解问题表达待求解问题(u u)T(u,Zh
4、ang)T(u,Zhang)(u u)T(u,Zhang)T(u,Zhang)VANWSER(uVANWSER(u)归结反演求取问题的答案-示例化子句集化子句集(u u)T(u,Zhang)T(u,Zhang)VANWSER(uVANWSER(u)(u u)T(u,Zhang)T(u,Zhang)VANWSER(uVANWSER(u)T(u,Zhang)T(u,Zhang)VANWSER(uVANWSER(u)进行归结进行归结 C(li,y)V VT(Wang,yT(Wang,y)4 54 5 6 6 C(li,Zhang)VANWSER(WangVANWSER(Wang)2 62 6 ANW
5、SER(WangANWSER(Wang)归结树归结树T(Wang,Li)C(x,y)VT(z,x)VT(z,y)C(Li,y)VT(Wang,y)=Wang/z,Li/xT(u,Zhang)VANWSER(u)C(Li,Zhang)VANWSER(Wang)=Wang/u,Zhang/yC(Li,Zhang)ANWSER(Wang)归结演绎推理的策略l用产生式系统表示归结过程用产生式系统表示归结过程综合数据库：子句集综合数据库：子句集规则集：规则集：IF C1和和C2有归结式有归结式C12 THEN S=SC12C12目标条件：目标条件：NILSNILS归结演绎推理的策略l产生式系统基本算法产
6、生式系统基本算法1.初始化综合数据库，把问题的已知事实送入综合数据库。初始化综合数据库，把问题的已知事实送入综合数据库。2.若规则库中存在尚未使用过的规则，若有则执行若规则库中存在尚未使用过的规则，若有则执行3；否则转；否则转7。3.检查规则库中未使用的规则前件能否与综合数据库中的事实匹配，若检查规则库中未使用的规则前件能否与综合数据库中的事实匹配，若有从中选择一个；否则转有从中选择一个；否则转6。4.执行当前选中的规则，并标记，将结论加入综合数据库，若结论是操执行当前选中的规则，并标记，将结论加入综合数据库，若结论是操作，则执行操作。作，则执行操作。5.检查综合数据库中是否包含了问题的解，若
7、包含，问题解决，求解过检查综合数据库中是否包含了问题的解，若包含，问题解决，求解过程结束；否则转程结束；否则转2。6.当规则库有未使用的规则，但均不能与已知事实匹配，要求用户提供当规则库有未使用的规则，但均不能与已知事实匹配，要求用户提供新的事实，若提供，则转新的事实，若提供，则转2；否则，问题无解停止求解过程。；否则，问题无解停止求解过程。7.若规则库中不再有未使用过的规则，问题无解，停止求解过程。若规则库中不再有未使用过的规则，问题无解，停止求解过程。归结演绎推理的策略1.初始化综合数据库初始化综合数据库DB=SDB=S；2.若若NILDBNILDB，停止问题得证；停止问题得证；3.3.D
8、BDB中是否有可归结的子句，若有执行下一步，中是否有可归结的子句，若有执行下一步，否则转否则转7 7；4.4.从从DBDB中选择两个不同的可归结子句中选择两个不同的可归结子句C1C1和和C2C2；5.5.求求C1C1和和C2C2的归结式的归结式C12C12；6.6.DB=DBC12DB=DBC12，返回返回2 2；7.7.停止，无法证明问题。停止，无法证明问题。归结的一般过程归结的一般过程l归结过程是从子句集中不断寻找可归结子句归结过程是从子句集中不断寻找可归结子句对进行归结，直到归结出空子句或没有可归对进行归结，直到归结出空子句或没有可归结子句对为止。一般的归结过程如下：结子句对为止。一般的
9、归结过程如下：1.设初始子句集设初始子句集S0=S=S，对中的全部子句作所有对中的全部子句作所有可能的归结，得到第一层归结式，把这些归可能的归结，得到第一层归结式，把这些归结式的集合记为结式的集合记为S1。2.2.用用S0中的子句和中的子句和S1 中的子句进行所有可能的中的子句进行所有可能的归结，得到第二层归结式，把这些归结式的归结，得到第二层归结式，把这些归结式的集合记为集合记为S2。归结的一般过程归结的一般过程-示例示例3.3.用用S0和和S1中的子句与中的子句与S2中的子句进行所有可中的子句进行所有可能的归结，得到第三层归结式，把这些归结能的归结，得到第三层归结式，把这些归结式的集合记为
10、式的集合记为S3。4.4.重复此过程直到得到空子句或不能继续归结重复此过程直到得到空子句或不能继续归结为止。为止。5.5.一般称如上的归结策略为广度优先策略。一般称如上的归结策略为广度优先策略。归结的一般过程归结的一般过程-示例示例例：设有如下子句集例：设有如下子句集 S=I(x)VR(x),I(a),VR(x),I(a),R(y)VL(y),VL(y),L(a)用广度优先策略证明用广度优先策略证明S不可满足。不可满足。证明：从证明：从S出发，依次构造出发，依次构造S1，S2，S3，。，。直到出现空子句为止。直到出现空子句为止。示例的归结图示例的归结图I(x)VR(x)R(y)VL(y)I(a
11、)L(a)R(a)=a/xI(y)VL(y)=x/yR(a)=a/yS0S1L(a)=a/y=a/xL(a)NIL=a/yI(a)=a/yI(a)S2归结演绎中的策略归结演绎中的策略l盲目全面进行归结，产生许多无用归结式，更盲目全面进行归结，产生许多无用归结式，更严重的是产生组合爆炸问题。严重的是产生组合爆炸问题。l常用的归结策略分为两大类：常用的归结策略分为两大类：删除策略：通过删除某些无用的子句缩小归删除策略：通过删除某些无用的子句缩小归结的范围。结的范围。限制策略：通过对参加归结的子句进行某些限制策略：通过对参加归结的子句进行某些限制减少归结的盲目性。限制减少归结的盲目性。删除策略删除策
12、略-纯文字删除纯文字删除l如果某个文字如果某个文字L L在子句集中不存在与其互补的在子句集中不存在与其互补的文字文字 L L，称此文字为纯文字。，称此文字为纯文字。l纯文字删除法是删除子句集中包含纯文字的子纯文字删除法是删除子句集中包含纯文字的子句。句。例：设子句集例：设子句集 S=PVQVRS=PVQVR，QVRQVR，Q Q，RR P P为纯文字，删除子句为纯文字，删除子句PVQVRPVQVR，然后对然后对 QVRQVR，Q Q，RR进行归结。进行归结。删除策略删除策略-重言式删除重言式删除l如果一个子句中包含有互补文字，称该子句为如果一个子句中包含有互补文字，称该子句为重言式。重言式。l
13、子句子句PVPV P PVQVQ是一个重言式，显然这个子句的是一个重言式，显然这个子句的真值是真，在子句集中删除此子句，不影响子真值是真，在子句集中删除此子句，不影响子句集的不可满足性。句集的不可满足性。l重言式删除法是将子句集中的重言式删除。重言式删除法是将子句集中的重言式删除。删除策略删除策略-包孕删除包孕删除l设子句设子句C1和和C2，如果存在一个置换，如果存在一个置换，使得，使得C1 C2C2，则称则称C1C1包孕于包孕于C2C2。l例：例：P(xP(x)包孕于包孕于 P(y)VQ(zP(y)VQ(z)=y/xl对对子句集来子句集来说说把包孕子句把包孕子句删删除，不影响子句集除，不影响
14、子句集的不可的不可满满足性。足性。l包孕删除法：从子句集中删除包孕子句。包孕删除法：从子句集中删除包孕子句。删除策略的完备性删除策略的完备性l以上的几种删除策略是否为完备的归结策略？以上的几种删除策略是否为完备的归结策略？限制策略限制策略-支持集策略支持集策略l支持集策略是沃斯等人在支持集策略是沃斯等人在1965年提出的一种年提出的一种归结策略。它要求参加归结的两个亲本子句中归结策略。它要求参加归结的两个亲本子句中至少有一个是由目标公式的否定所得到的子句至少有一个是由目标公式的否定所得到的子句或是它们的后裔。或是它们的后裔。l可以证明支持集策略是完备的，即子句集不可可以证明支持集策略是完备的，
15、即子句集不可满足时，使用支持集策略一定可以归结出空子满足时，使用支持集策略一定可以归结出空子句。句。支持集策略支持集策略-示例示例I(x)VR(x)R(y)VL(y)I(a)L(a)R(a)=a/xI(y)VL(y)=x/yR(a)=a/yS0S1L(a)=a/y=a/xL(a)NIL=a/yI(a)=a/yI(a)S2NIL限制策略限制策略-单文字子句策略单文字子句策略l如果一个子句只包含一个文字，则称此子句是如果一个子句只包含一个文字，则称此子句是一个单文字子句。一个单文字子句。l单文字子句策略：要求参加归结的两个亲本子单文字子句策略：要求参加归结的两个亲本子句中至少有一个子句是单文字子句
16、。句中至少有一个子句是单文字子句。l单文字子句策略是不完备的。单文字子句策略是不完备的。单文字子句策略单文字子句策略-示例示例I(x)VR(x)R(y)VL(y)I(a)L(a)R(a)=a/xI(y)VL(y)=x/yR(a)=a/yS0S1L(a)=a/y=a/xL(a)NIL=a/yI(a)=a/yI(a)S2限制策略限制策略-线性输入策略线性输入策略l这种策略要求每次参加归结的两个亲本子句中，这种策略要求每次参加归结的两个亲本子句中，至少有一个是初始子句集中的子句。至少有一个是初始子句集中的子句。l线性输入策略是一种不完备的归结策略。例如线性输入策略是一种不完备的归结策略。例如S=S=
17、Q(u)VP(u),Q(u)VP(u),Q(x)Q(x)VP(xVP(x),),Q(y)VQ(y)V P(yP(y),),Q(w)VQ(w)V P(wP(w)是不可满足的，但使用线性输是不可满足的，但使用线性输入策略无法得到空子句。入策略无法得到空子句。线性输入策略线性输入策略-示例示例I(x)VR(x)R(y)VL(y)I(a)L(a)R(a)=a/xI(y)VL(y)=x/yR(a)=a/yS0S1L(a)=a/y=a/xL(a)NIL=a/yI(a)=a/yI(a)S2NIL限制策略限制策略-祖先过滤策略祖先过滤策略l要求参加归结的两个亲本子句满足以下两个条要求参加归结的两个亲本子句满足
18、以下两个条件中的任意一个：件中的任意一个：参加归结的两个亲本子句中，至少有一个是初始子参加归结的两个亲本子句中，至少有一个是初始子句集中的子句。句集中的子句。如果两个亲本子句都不是初始子句集的子句，则一如果两个亲本子句都不是初始子句集的子句，则一个应是另一个的先辈子句。个应是另一个的先辈子句。l可以证明，祖先过滤策略是完备的。可以证明，祖先过滤策略是完备的。祖先过滤策略祖先过滤策略-示例示例P(x)V VQ(x)P(y)V VQ(y)P(x)P(z)V VQ(z)P(a)V VQ(a)Q(x)P(a)NIL基于规则的演绎推理基于规则的演绎推理l归结演绎方便了机器推理，但在化子句集时损归结演绎方
19、便了机器推理，但在化子句集时损失了一些控制信息。例如：如下的子句失了一些控制信息。例如：如下的子句 PVQVRPVQVR 其可由下面的几个公式等价得到。其可由下面的几个公式等价得到。P P QRQR、R R QPQP、P P RQRQ、。基于规则的正向演绎推理基于规则的正向演绎推理l定理证明问题：已知一组事实，以及相关的领定理证明问题：已知一组事实，以及相关的领域知识，证明目标。一般情况下，已知事实和域知识，证明目标。一般情况下，已知事实和目标是用谓词公式表达，而相关领域的知识是目标是用谓词公式表达，而相关领域的知识是由一组蕴含式表达，我们将这组蕴含式称为规由一组蕴含式表达，我们将这组蕴含式称
20、为规则。则。l从事实出发，正向使用规则（从事实出发，正向使用规则（F规则），直接规则），直接进行演绎，直至达到目标为止的一种证明方法。进行演绎，直至达到目标为止的一种证明方法。基于规则的正向演绎推理基于规则的正向演绎推理l为了实现正向推理，需要对定理证明问题的已为了实现正向推理，需要对定理证明问题的已知事实、规则和证明目标按一定的形式表示出知事实、规则和证明目标按一定的形式表示出来。下面讨论表示形式的转换。来。下面讨论表示形式的转换。基于规则的正向演绎推理基于规则的正向演绎推理l事实表达式的与事实表达式的与/或形变换：基于规则的正向或形变换：基于规则的正向演绎推理通常将已知事实化为与演绎推理通
21、常将已知事实化为与/或形，化与或形，化与/或形的基本步骤如下：或形的基本步骤如下：1.利用规则利用规则PQQPVQVQ消去蕴含符号。消去蕴含符号。2.2.利用狄。摩根定律及量词转换律把利用狄。摩根定律及量词转换律把移到紧靠谓词，移到紧靠谓词，使否定连接词的辖域只含一个谓词。使否定连接词的辖域只含一个谓词。3.化为前束范式。化为前束范式。4.变元标准化。变元标准化。5.消去全称量词。消去全称量词。基于规则的正向演绎推理基于规则的正向演绎推理例例：将公式化为与或形：将公式化为与或形(x)(y)(Q(y,xx)(y)(Q(y,x)(R(y)VP(yR(y)VP(y)S(x,yS(x,y)解：解：(x
22、)(y)(Q(y,xx)(y)(Q(y,x)(R(y)VP(yR(y)VP(y)S(x,yS(x,y)(x)(y)(Q(y,xx)(y)(Q(y,x)(R(y)R(y)VP(y)VVP(y)V S(x,yS(x,y)(x)(y)(Q(y,xx)(y)(Q(y,x)(R(yR(y)P(y)VP(y)V S(x,yS(x,y)(x)(y)(Q(y,xx)(y)(Q(y,x)(R(yR(y)P(y)VP(y)V S(x,yS(x,y)(y)(Q(y,ay)(Q(y,a)(R(yR(y)P(y)VP(y)V S(a,yS(a,y)Q(y,aQ(y,a)(R(yR(y)P(y)VP(y)V S(a,yS
23、(a,y)基于规则的正向演绎推理基于规则的正向演绎推理l事实表达式的与事实表达式的与/或树：为了推理过程直观将或树：为了推理过程直观将事实表达式的与事实表达式的与/或形表示为一棵与或形表示为一棵与/或树。或树。基于规则的正向演绎推理基于规则的正向演绎推理l与与/或树中的结点表示与或树中的结点表示与/或形中的一个子表达或形中的一个子表达式，表达式间的关系规定如下：式，表达式间的关系规定如下：表达式表达式E为为k个子表达式析取时即个子表达式析取时即E=E1V VE2V VV V Ek,每个子表达式每个子表达式Ei均被表示为的后继结点，并均被表示为的后继结点，并由一个由一个k连接符将这些后继结点连接
24、到父结点，即连接符将这些后继结点连接到父结点，即表示成与的关系。表示成与的关系。表达式表达式E为为k个子表达式合取时即个子表达式合取时即E=E1 E2 Ek,每个子表达式每个子表达式Ei均被表示为的后继结点，并由一均被表示为的后继结点，并由一个单一连接符将这些后继结点连接到父结点，即表个单一连接符将这些后继结点连接到父结点，即表示成或的关系。示成或的关系。基于规则的正向演绎推理基于规则的正向演绎推理例：将例：将Q(y,aQ(y,a)(R(yR(y)P(y)VP(y)V S(a,yS(a,y)表示为表示为与与/或树。或树。Q(y,a)(R(y)P(y)VS(a,y)Q(y,a)(R(y)P(y)
25、VS(a,y)R(y)P(y)S(a,y)R(y)P(y)基于规则的正向演绎推理基于规则的正向演绎推理l与与/或树的特点或树的特点根结点是事实表达式的与根结点是事实表达式的与/或形，端结点是事实表或形，端结点是事实表达式中的一个文字。达式中的一个文字。解树集对应着子句集。例中的三个解树对应着三个解树集对应着子句集。例中的三个解树对应着三个子句，子句，Q(y,a)，R(y)VS(a,y)，P(y)VS(a,y)基于规则的正向演绎推理基于规则的正向演绎推理l规则的与规则的与/或形变换：基于规则的正向演绎推理中要或形变换：基于规则的正向演绎推理中要求规则要具有求规则要具有LWW的形状，其中的形状，其
26、中L L为单文字，为单文字，WW为为与与/或形。或形。l规则的变换步骤：规则的变换步骤：1.利用规则利用规则PQQPVQVQ暂时暂时消去蕴含符号。消去蕴含符号。2.2.利用狄。摩根定律及量词转换律把利用狄。摩根定律及量词转换律把移到紧靠谓词，使否定移到紧靠谓词，使否定连接词的辖域只含一个谓词。连接词的辖域只含一个谓词。3.引入引入Skolem函数，消去存在量词。函数，消去存在量词。4.化为前束范式，消去全称量词。化为前束范式，消去全称量词。5.恢复蕴含式表示。恢复蕴含式表示。基于规则的正向演绎推理基于规则的正向演绎推理例例：(x)(y)(z)(P(x,y,z)(u)Q(x,ux)(y)(z)(
27、P(x,y,z)(u)Q(x,u)(x)(x)(y)(z)(P(x,y,z)V(u)Q(x,u(y)(z)(P(x,y,z)V(u)Q(x,u)(x)(y)(z)(x)(y)(z)(P(x,y,z)V(u)Q(x,uP(x,y,z)V(u)Q(x,u)(x)(y)(x)(y)(P(x,y,f(x,y)V(u)Q(x,uP(x,y,f(x,y)V(u)Q(x,u)P(x,y,f(x,y)VQ(x,uP(x,y,f(x,y)VQ(x,u)P(x,y,f(x,y)Q(x,uP(x,y,f(x,y)Q(x,u)基于规则的正向演绎推理基于规则的正向演绎推理l若出现规则前件非单文字时，如若出现规则前件非单
28、文字时，如1V1V22 将其等价为两个规则：将其等价为两个规则：L1WL1W L2W L2W基于规则的正向演绎推理基于规则的正向演绎推理l目标公式的表示形式：基于规则的正向演绎推目标公式的表示形式：基于规则的正向演绎推理要求将目标公式表达为子句集的形式。理要求将目标公式表达为子句集的形式。基于规则的正向演绎推理过程基于规则的正向演绎推理过程命题逻辑：设已知事实表示为如下的与命题逻辑：设已知事实表示为如下的与/或形或形 (PVQ)(PVQ)R)V(SR)V(S(TVU)(TVU)规则为规则为 (X(X Y)VZY)VZ基于规则的正向演绎推理过程基于规则的正向演绎推理过程(PVQ)R)V(S(TV
29、U)(PVQ)RS(TVU)PVQRTVUSTUPQSXVYZYX基于规则的正向演绎推理过程基于规则的正向演绎推理过程l已知事实的四个子句已知事实的四个子句1.1.V V2.2.V VV V3.3.V VV V4.4.V VV VV Vl规则化为子句的两个子句规则化为子句的两个子句1.VXVZVXVZ2.VYVZVYVZ基于规则的正向演绎推理过程基于规则的正向演绎推理过程l应用规则后的与应用规则后的与/或树的子句（解图）有六个或树的子句（解图）有六个1.1.XVZVXVZV2.2.YVZVYVZV3.3.XVZVXVZVV V4.4.YVZVYVZVV V5.5.V VV V6.6.V VV
30、VV V基于规则的正向演绎推理过程基于规则的正向演绎推理过程l前面的四个子句是已知事实和规则表示的子句前面的四个子句是已知事实和规则表示的子句进行归结得到的所有归结式。进行归结得到的所有归结式。l既有规则应用结果，就是归结式的完备集，即既有规则应用结果，就是归结式的完备集，即规则的应用演绎出所有的逻辑推论。规则的应用演绎出所有的逻辑推论。l基于规则的正向演绎系统的演绎过程就是不断基于规则的正向演绎系统的演绎过程就是不断地调用匹配的规则，对与地调用匹配的规则，对与/或树进行变换，直或树进行变换，直到生成的与到生成的与/或树含有目标表达式为止。或树含有目标表达式为止。基于规则的正向演绎推理基于规则
31、的正向演绎推理-示例示例已知事实表达式：已知事实表达式：AVBVB规则集：规则集：ACAC D D BE BE F F目标公式：目标公式：CVFCVF基于规则的正向演绎推理基于规则的正向演绎推理-示例示例AVBABABCDEFCFCVF基于规则的正向演绎推理过程基于规则的正向演绎推理过程l谓词逻辑：与命题逻辑的推理过程的主要区别谓词逻辑：与命题逻辑的推理过程的主要区别在于，已知事实、规则和目标公式的标准化时在于，已知事实、规则和目标公式的标准化时要考虑变元和要考虑变元和Skolem函数，使用规则匹配时函数，使用规则匹配时需要合一处理。需要合一处理。基于规则的正向演绎推理基于规则的正向演绎推理-
32、示例示例事实：事实：FidoFido barks barks andand bites,orbites,or FidoFido is not a dog.is not a dog.DOG(Fido)DOG(Fido)V(BARKS(FidoV(BARKS(Fido)BITES(FidoBITES(Fido)规则：规则：ALL terriers are dogs.ALL terriers are dogs.(x)(x)(DOG(x)DOG(x)TERRIES(xTERRIES(x)Anyone who barks is noisy Anyone who barks is noisy (y)(BA
33、RKS(y)NOISY(yy)(BARKS(y)NOISY(y)目标目标:There exists someone who is not a:There exists someone who is not a terrier or who is noisy.terrier or who is noisy.(z)(z)(TERRIER(z)VNOISY(zTERRIER(z)VNOISY(z)基于规则的正向演绎推理基于规则的正向演绎推理-示例示例DOG(Fido)V(BARKS(Fido)BITES(Fido)DOG(Fido)BARKS(Fido)BITES(Fido)BARKS(Fido)B
34、ITES(Fido)DOG(Fido)Fido/xTERRIER(Fido)BARKS(Fido)Fido/yNOISY(Fido)目标目标规则规则1规则规则2基于规则的逆向演绎推理基于规则的逆向演绎推理l逆向演绎系统：是从目标出发，反方向使用规逆向演绎系统：是从目标出发，反方向使用规则（则（B规则）对目标表达式的与规则）对目标表达式的与/或树进行变或树进行变换，最后得到含有事实结点的图。换，最后得到含有事实结点的图。l逆向演绎系统对已知事实、规则和目标公式的逆向演绎系统对已知事实、规则和目标公式的表示形式要求与正向的形式对偶。表示形式要求与正向的形式对偶。基于规则的逆向演绎推理基于规则的逆向
35、演绎推理l目标公式转换为与目标公式转换为与/或形。或形。lB B规则的形式为规则的形式为W WLL，其中其中W W为与为与/或形，或形，L L为单为单文字。文字。l已知事实表达为文字的合取，即表达为短语。已知事实表达为文字的合取，即表达为短语。基于规则的逆向演绎推理基于规则的逆向演绎推理-示例示例事实：事实：DOG(Fido)Fido是一只狗是一只狗 BARKS(Fido)Fido是不叫的是不叫的 WAGS-TAIL(Fido)Fido摇尾巴摇尾巴 MEOWS(Myrtle)猫咪的名字是猫咪的名字是Myrtle规则：摇尾巴的狗是温顺的狗。规则：摇尾巴的狗是温顺的狗。WAGS-TAIL(x)DO
36、GDOG(x)FRIENDLY(xFRIENDLY(x)温顺不叫的东西不值得害怕。温顺不叫的东西不值得害怕。FRIENDLY(yFRIENDLY(y)BARKS(y)AFRAID(z,y)基于规则的逆向演绎推理基于规则的逆向演绎推理-示例示例 DOG(u)ANIMAL(u)狗是动物狗是动物 CAT(v)ANIMAL(v)猫是动物猫是动物 MEOWS(w)CAT(w)猫咪是猫猫咪是猫目标：存在一只猫和一只狗，这只猫不害怕这只目标：存在一只猫和一只狗，这只猫不害怕这只狗。狗。(x x)(yy)(CAT(x)DOG(yDOG(y)AFRAID(x,y)基于规则的逆向演绎推理基于规则的逆向演绎推理-示例示例CAT(s)DOG(t)AFRAID(s,t)CAT(s)DOG(t)AFRAID(s,t)CAT(w)DOG(Fido)AFRAID(z,y)MEOWS(w)MEOWS(Myrtle)BARKS(y)FRIENDLY(y)BARKS(Fido)FRIENDLY(x)WAGS-TAIL(x)BARKS(x)WAGS-TAIL(Fido)BARKS(Fido)