人工智能及应用ch33.ppt

经典逻辑推理归结反演求取问题的答案 归结演绎推理的策略 基于规则的演绎推理归结反演求取问题的答案l归结原理还可以用于求取问题答案，其思想与定理 证明相似，求解步骤为；l把已知前提用谓词公式表示，并化为子句集S；l把待求解的问题用谓词公式表示，然后把它的否定 与谓词ANWSER析取构成析取式，ANWSER的变 元与问题谓词的变元完全一致；l把此析取式化为子句集，并添加到S中，构成新的子 句集S1；l对S1使用归结原理，直到得到归结式ANWSER，则 问题答案在谓词ANWSER中归结反演求取问题的答案-示例例：已知王先生是小李的老师，小李与小张是 同班同学，如果x与y是同班同学，则x的老 师也是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)l¬C(x,y)V¬T(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)V¬T(Wang,y)4⊕ 5→ 6 ¬C(li,Zhang)VANWSER(Wang)2⊕ 6→ ANWSER(Wang)归结树T(Wang,Li)¬C(x,y)V¬T(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)归结演绎推理的策略l用产生式系统表示归结过程–综合数据库：子句集Ｓ–规则集：IF C1和C2有归结式C12 THEN S=S∪{C12}–目标条件：NIL∈S归结演绎推理的策略l产生式系统基本算法l初始化综合数据库，把问题的已知事实送入综合数据库。

l若规则库中存在尚未使用过的规则，若有则执行3；否则转7l检查规则库中未使用的规则前件能否与综合数据库中的事实匹配，若 有从中选择一个；否则转6l执行当前选中的规则，并标记，将结论加入综合数据库，若结论是操 作，则执行操作l检查综合数据库中是否包含了问题的解，若包含，问题解决，求解过 程结束；否则转2l当规则库有未使用的规则，但均不能与已知事实匹配，要求用户提供 新的事实，若提供，则转2；否则，问题无解停止求解过程l若规则库中不再有未使用过的规则，问题无解，停止求解过程归结演绎推理的策略l初始化综合数据库DB=S；l若NIL∈DB，停止问题得证；lDB中是否有可归结的子句，若有执行下一步 ，否则转7；l从DB中选择两个不同的可归结子句C1和C2 ；l求C1和C2的归结式C12；lDB=DB∪{C12}，返回2；l停止，无法证明问题归结的一般过程l归结过程是从子句集中不断寻找可归结子句 对进行归结，直到归结出空子句或没有可归 结子句对为止一般的归结过程如下：l设初始子句集S0 =S，对中的全部子句作所有 可能的归结，得到第一层归结式，把这些归 结式的集合记为S1l用S0中的子句和S1 中的子句进行所有可能的 归结，得到第二层归结式，把这些归结式的 集合记为S2。

归结的一般过程-示例l用S0和S1中的子句与S2中的子句进行所有可 能的归结，得到第三层归结式，把这些归结 式的集合记为S3l重复此过程直到得到空子句或不能继续归结 为止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/x}¬I(y)VL(y)σ={x/y}¬R(a)σ={a/y}S0S1L(a)σ={a/y}σ={a/x}L(a)NILσ={a/y}¬I(a)σ={a/y} ¬I(a)S2归结演绎中的策略l盲目全面进行归结，产生许多无用归结式， 更严重的是产生组合爆炸问题l常用的归结策略分为两大类：–删除策略：通过删除某些无用的子句缩小 归结的范围–限制策略：通过对参加归结的子句进行某 些限制减少归结的盲目性删除策略-纯文字删除l如果某个文字L在子句集中不存在与其互补的 文字¬L，称此文字为纯文字l纯文字删除法是删除子句集中包含纯文字的 子句。

例：设子句集 S={PVQVR，¬QVR，Q，¬R}P为纯文字，删除子句PVQVR，然后对 {¬QVR，Q，¬R}进行归结删除策略-重言式删除l如果一个子句中包含有互补文字，称该子句 为重言式l子句PV¬PVQ是一个重言式，显然这个子句 的真值是真，在子句集中删除此子句，不影 响子句集的不可满足性l重言式删除法是将子句集中的重言式删除删除策略-包孕删除l设子句C1和C2，如果存在一个置换σ， 使得C1σ⊆C2，则称C1包孕于C2l例：P(x) 包孕于 P(y)VQ(z) σ={y/x}l对对子句集来说说把包孕子句删删除，不影响子句 集的不可满满足性l包孕删除法：从子句集中删除包孕子句删除策略的完备性l以上的几种删除策略是否为完备的归结策略 ？限制策略-支持集策略l支持集策略是沃斯等人在1965年提出的一种 归结策略它要求参加归结的两个亲本子句 中至少有一个是由目标公式的否定所得到的 子句或是它们的后裔l可以证明支持集策略是完备的，即子句集不 可满足时，使用支持集策略一定可以归结出 空子句支持集策略-示例¬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}S0S1L(a)σ={a/y}σ={a/x}L(a)NILσ={a/y}¬I(a)σ={a/y} ¬I(a)S2NIL限制策略-单文字子句策略l如果一个子句只包含一个文字，则称此子句 是一个单文字子句。

l单文字子句策略：要求参加归结的两个亲本 子句中至少有一个子句是单文字子句l单文字子句策略是不完备的单文字子句策略-示例¬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}S0S1L(a)σ={a/y}σ={a/x}L(a)NILσ={a/y}¬I(a)σ={a/y} ¬I(a)S2限制策略-线性输入策略l这种策略要求每次参加归结的两个亲本子句 中，至少有一个是初始子句集中的子句l线性输入策略是一种不完备的归结策略例 如S={Q(u)VP(u),¬Q(x)VP(x), ¬Q(y)V¬P(y), ¬Q(w)V ¬P(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}S0S1L(a)σ={a/y}σ={a/x}L(a)NILσ={a/y}¬I(a)σ={a/y} ¬I(a)S2NIL限制策略-祖先过滤策略l要求参加归结的两个亲本子句满足以下两个 条件中的任意一个：–参加归结的两个亲本子句中，至少有一个是初始 子句集中的子句。

–如果两个亲本子句都不是初始子句集的子句，则 一个应是另一个的先辈子句l可以证明，祖先过滤策略是完备的祖先过滤策略-示例¬P(x)V¬Q(x)¬P(y)VQ(y)¬P(x)P(z)V¬Q(z)P(a)VQ(a)¬Q(x)P(a)NIL基于规则的演绎推理l归结演绎方便了机器推理，但在化子句集时 损失了一些控制信息例如：如下的子句PVQVR其可由下面的几个公式等价得到¬PΛ¬Q→R、 ¬RΛ¬Q→P、 ¬PΛ¬R→Q、 基于规则的正向演绎推理l定理证明问题：已知一组事实，以及相关的 领域知识，证明目标一般情况下，已知事 实和目标是用谓词公式表达，而相关领域的 知识是由一组蕴含式表达，我们将这组蕴含 式称为规则l从事实出发，正向使用规则（F规则），直接 进行演绎，直至达到目标为止的一种证明方 法基于规则的正向演绎推理l为了实现正向推理，需要对定理证明问题的 已知事实、规则和证明目标按一定的形式表 示出来下面讨论表示形式的转换基于规则的正向演绎推理l事实表达式的与/或形变换：基于规则的正向 演绎推理通常将已知事实化为与/或形，化与/ 或形的基本步骤如下：–利用规则P→Q⇔¬PVQ消去蕴含符号。

–利用狄摩根定律及量词转换律把¬移到紧靠谓 词，使否定连接词的辖域只含一个谓词–化为前束范式–变元标准化–消去全称量词基于规则的正向演绎推理例：将公式化为与／或形 (∃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))V¬S(x,y))) ⇔(∃x)(∀y)(Q(y,x)Λ((¬R(y)Λ¬P(y))V¬S(x,y))) ⇔ (∃x)(∀y)(Q(y,x)Λ((¬R(y)Λ¬P(y))V¬S(x,y))) ⇔(∀y)(Q(y,a)Λ((¬R(y)Λ¬P(y))V¬S(a,y))) ⇔Q(y,a)Λ((¬R(y)Λ¬P(y))V¬S(a,y))基于规则的正向演绎推理l事实表达式的与/或树：为了推理过程直观将 事实表达式的与/或形表示为一棵与/或树基于规则的正向演绎推理l与/或树中的结点表示与/或形中的一个子表达 式，表达式间的关系规定如下：–表达式E为k个子表达式析取时即E=E1VE2V…V Ek,每个子表达式Ei均被表示为Ｅ的后继结点，并 由一个k连接符将这些后继结点连接到父结点，即 表示成与的关系。

–表达式E为k个子表达式合取时即 E=E1ΛE2Λ…ΛEk,每个子表达式Ei均被表示为Ｅ的 后继结点，并由一个单一连接符将这些后继结点 连接到父结点，即表示成或的关系 基于规则的正向演绎推理例：将Q(y,a)Λ((¬R(y)Λ¬P(y))V¬S(a,y))表示为 与/或树Q(y,a)Λ((¬R(y)Λ¬P(y))V¬S(a,y))Q(y,a)(¬R(y)Λ¬P(y))V¬S(a,y)¬R(y)Λ¬P(y)¬S(a,y)¬R(y)¬P(y)基于规则的正向演绎推理l与/或树的特点–根结点是事实表达式的与/或形，端结点是事实表 达式中的一个文字–解树集对应着子句集例中的三个解树对应着三 个子句， Q(y,a)，¬R(y)V¬S(a,y)，¬P(y) V¬S(a,y)基于规则的正向演绎推理l规则的与/或形变换：基于规则的正向演绎推理中要 求规则要具有L→W的形状，其中L为单文字，W为与 /或形l规则的变换步骤：–利用规则P→Q⇔¬PVQ暂时消去蕴含符号–利用狄摩根定律及量词转换律把¬移到紧靠谓词，使否定 连接词的辖域只含一个谓词–引入Skolem函数，消去存在量词–化为前束范式，消去全称量词。

–恢复蕴含式表示基于规则的正向演绎推理例：(∀x)(((∃y)(∀z)(P(x,y,z))→(∀u)Q(x,u)) ⇔(∀x)(¬((∃y)(∀z)(P(x。