《人工智能及应用ch33》由会员分享，可在线阅读，更多相关《人工智能及应用ch33（55页珍藏版）》请在金锄头文库上搜索。
1、经典逻辑推理归结反演求取问题的答案 归结演绎推理的策略 基于规则的演绎推理归结反演求取问题的答案l归结原理还可以用于求取问题答案，其思想与定理 证明相似，求解步骤为；l把已知前提用谓词公式表示，并化为子句集S；l把待求解的问题用谓词公式表示，然后把它的否定 与谓词ANWSER析取构成析取式，ANWSER的变 元与问题谓词的变元完全一致；l把此析取式化为子句集，并添加到S中，构成新的子 句集S1；l对S1使用归结原理，直到得到归结式ANWSER，则 问题答案在谓词ANWSER中。归结反演求取问题的答案-示例例：已知王先生是小李的老师，小李与小张是 同班同学，如果x与y是同班同学，则x的老 师也是
2、y的老师。求小张的老师是谁？ 解：定义谓词T(x,y):x是y的老师；C(x,y):x与y是同班同学。归结反演求取问题的答案-示例用谓词表示已知条件lT(Wang,Li):王先生是小李的老师;lC(Li,Zhang):小李与小张是同班同学;l(x) (y) (z)(C(x,y)T(z,x)T(z,y):如果x 与y是同班同学，则x的老师也是y的老师。归结反演求取问题的答案-示例化子句集lT(Wang,Li)lC(Li,Zhang)lC(x,y)VT(z,x)VT(z,y) 表达待求解问题(u)T(u,Zhang) (u)T(u,Zhang)VANWSER(u)归结反演求取问题的答案-示例化子句
3、集(u)T(u,Zhang)VANWSER(u) (u)T(u,Zhang)VANWSER(u) T(u,Zhang)VANWSER(u) 进行归结 C(li,y)VT(Wang,y)4 5 6 C(li,Zhang)VANWSER(Wang)2 6 ANWSER(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用产生式系统表示
4、归结过程综合数据库：子句集规则集：IF C1和C2有归结式C12 THEN S=SC12目标条件：NILS归结演绎推理的策略l产生式系统基本算法l初始化综合数据库，把问题的已知事实送入综合数据库。l若规则库中存在尚未使用过的规则，若有则执行3；否则转7。l检查规则库中未使用的规则前件能否与综合数据库中的事实匹配，若 有从中选择一个；否则转6。l执行当前选中的规则，并标记，将结论加入综合数据库，若结论是操 作，则执行操作。l检查综合数据库中是否包含了问题的解，若包含，问题解决，求解过 程结束；否则转2。l当规则库有未使用的规则，但均不能与已知事实匹配，要求用户提供 新的事实，若提供，则转2；否则
5、，问题无解停止求解过程。l若规则库中不再有未使用过的规则，问题无解，停止求解过程。归结演绎推理的策略l初始化综合数据库DB=S；l若NILDB，停止问题得证；lDB中是否有可归结的子句，若有执行下一步 ，否则转7；l从DB中选择两个不同的可归结子句C1和C2 ；l求C1和C2的归结式C12；lDB=DBC12，返回2；l停止，无法证明问题。归结的一般过程l归结过程是从子句集中不断寻找可归结子句 对进行归结，直到归结出空子句或没有可归 结子句对为止。一般的归结过程如下：l设初始子句集S0 =S，对中的全部子句作所有 可能的归结，得到第一层归结式，把这些归 结式的集合记为S1。l用S0中的子句和S
6、1 中的子句进行所有可能的 归结，得到第二层归结式，把这些归结式的 集合记为S2。归结的一般过程-示例l用S0和S1中的子句与S2中的子句进行所有可 能的归结，得到第三层归结式，把这些归结 式的集合记为S3。l重复此过程直到得到空子句或不能继续归结 为止。l一般称如上的归结策略为广度优先策略。归结的一般过程-示例例：设有如下子句集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/xI(y)VL(y)
7、=x/yR(a)=a/yS0S1L(a)=a/y=a/xL(a)NIL=a/yI(a)=a/y I(a)S2归结演绎中的策略l盲目全面进行归结，产生许多无用归结式， 更严重的是产生组合爆炸问题。l常用的归结策略分为两大类：删除策略：通过删除某些无用的子句缩小 归结的范围。限制策略：通过对参加归结的子句进行某 些限制减少归结的盲目性。删除策略-纯文字删除l如果某个文字L在子句集中不存在与其互补的 文字L，称此文字为纯文字。l纯文字删除法是删除子句集中包含纯文字的 子句。 例：设子句集 S=PVQVR，QVR，Q，RP为纯文字，删除子句PVQVR，然后对 QVR，Q，R进行归结。删除策略-重言式删
8、除l如果一个子句中包含有互补文字，称该子句 为重言式。l子句PVPVQ是一个重言式，显然这个子句 的真值是真，在子句集中删除此子句，不影 响子句集的不可满足性。l重言式删除法是将子句集中的重言式删除。删除策略-包孕删除l设子句C1和C2，如果存在一个置换， 使得C1C2，则称C1包孕于C2。l例：P(x) 包孕于 P(y)VQ(z) =y/xl对对子句集来说说把包孕子句删删除，不影响子句 集的不可满满足性。l包孕删除法：从子句集中删除包孕子句。删除策略的完备性l以上的几种删除策略是否为完备的归结策略 ？限制策略-支持集策略l支持集策略是沃斯等人在1965年提出的一种 归结策略。它要求参加归结的
9、两个亲本子句 中至少有一个是由目标公式的否定所得到的 子句或是它们的后裔。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/y I(a)S2NIL限制策略-单文字子句策略l如果一个子句只包含一个文字，则称此子句 是一个单文字子句。l单文字子句策略：要求参加归结的两个亲本 子句中至少有一个子句是单文字子句。l单文字子句策略是不完备的。单文字子句策略-示例I(x)VR
10、(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/y I(a)S2限制策略-线性输入策略l这种策略要求每次参加归结的两个亲本子句 中，至少有一个是初始子句集中的子句。l线性输入策略是一种不完备的归结策略。例 如S=Q(u)VP(u),Q(x)VP(x), Q(y)VP(y), Q(w)V P(w) 是不可满足的，但使用线性 输入策略无法得到空子句。线性输入策略-示例I(x)VR(x)R(y)VL(y)I(a)L(a)R(a)=a/xI(y)VL(y)=x/yR(a)=a/yS0S
11、1L(a)=a/y=a/xL(a)NIL=a/yI(a)=a/y I(a)S2NIL限制策略-祖先过滤策略l要求参加归结的两个亲本子句满足以下两个 条件中的任意一个：参加归结的两个亲本子句中，至少有一个是初始 子句集中的子句。如果两个亲本子句都不是初始子句集的子句，则 一个应是另一个的先辈子句。l可以证明，祖先过滤策略是完备的。祖先过滤策略-示例P(x)VQ(x)P(y)VQ(y)P(x)P(z)VQ(z)P(a)VQ(a)Q(x)P(a)NIL基于规则的演绎推理l归结演绎方便了机器推理，但在化子句集时 损失了一些控制信息。例如：如下的子句PVQVR其可由下面的几个公式等价得到。PQR、 RQ
12、P、 PRQ、 。 。基于规则的正向演绎推理l定理证明问题：已知一组事实，以及相关的 领域知识，证明目标。一般情况下，已知事 实和目标是用谓词公式表达，而相关领域的 知识是由一组蕴含式表达，我们将这组蕴含 式称为规则。l从事实出发，正向使用规则（F规则），直接 进行演绎，直至达到目标为止的一种证明方 法。基于规则的正向演绎推理l为了实现正向推理，需要对定理证明问题的 已知事实、规则和证明目标按一定的形式表 示出来。下面讨论表示形式的转换。基于规则的正向演绎推理l事实表达式的与/或形变换：基于规则的正向 演绎推理通常将已知事实化为与/或形，化与/ 或形的基本步骤如下：利用规则PQPVQ消去蕴含符
13、号。利用狄。摩根定律及量词转换律把移到紧靠谓 词，使否定连接词的辖域只含一个谓词。化为前束范式。变元标准化。消去全称量词。基于规则的正向演绎推理例：将公式化为与或形 (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)基于规则的正向演绎推理l事实
14、表达式的与/或树：为了推理过程直观将 事实表达式的与/或形表示为一棵与/或树。基于规则的正向演绎推理l与/或树中的结点表示与/或形中的一个子表达 式，表达式间的关系规定如下：表达式E为k个子表达式析取时即E=E1VE2VV Ek,每个子表达式Ei均被表示为的后继结点，并 由一个k连接符将这些后继结点连接到父结点，即 表示成与的关系。表达式E为k个子表达式合取时即 E=E1E2Ek,每个子表达式Ei均被表示为的 后继结点，并由一个单一连接符将这些后继结点 连接到父结点，即表示成或的关系。 基于规则的正向演绎推理例：将Q(y,a)(R(y)P(y)VS(a,y)表示为 与/或树。Q(y,a)(R(
15、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)基于规则的正向演绎推理l与/或树的特点根结点是事实表达式的与/或形，端结点是事实表 达式中的一个文字。解树集对应着子句集。例中的三个解树对应着三 个子句， Q(y,a)，R(y)VS(a,y)，P(y) VS(a,y)基于规则的正向演绎推理l规则的与/或形变换：基于规则的正向演绎推理中要 求规则要具有LW的形状，其中L为单文字，W为与 /或形。l规则的变换步骤：利用规则PQPVQ暂时消去蕴含符号。利用狄。摩根定律及量词转换律把移到紧靠谓词，使否定 连接词的辖域只含一个谓词。引入Skolem函数，消去存在量词。化为前束范式，消去全称量词。恢复蕴含式表示。基于规则的正向演绎推理例：(x)(y)(z)(P(x,y,z)(u)Q(x,u) (x)(y)(z)(P(x
