人工智能及应用_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)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) 归结树 归结演绎推理的策略 用产生式系统表示归结过程 综合数据库：子句集Ｓ 规则集：IF C1和C2有归结式C12 THEN S=S∪{C12} 目标条件：NIL∈S 归结演绎推理的策略 产生式系统基本算法 初始化综合数据库，把问题的已知事实送入综合数据库。 若规则库中存在尚未使用过的规则，若有则执行3；否则转7。 检查规则库中未使用的规则前件能否与综合数据库中的事实匹配，若有从中选择一个；否则转6。 执行当前选中的规则，并标记，将结论加入综合数据库，若结论是操作，则执行操作。 检查综合数据库中是否包含了问题的解，若包含，问题解决，求解过程结束；否则转2。 当规则库有未使用的规则，但均不能与已知事实匹配，要求用户提供新的事实，若提供，则转2；否则，问题无解停止求解过程。 若规则库中不再有未使用过的规则，问题无解，停止求解过程。 归结演绎推理的策略 初始化综合数据库DB=S； 若NIL∈DB，停止问题得证； DB中是否有可归结的子句，若有执行下一步，否则转7； 从DB中选择两个不同的可归结子句C1和C2； 求C1和C2的归结式C12； DB=DB∪{C12}，返回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 ，。。。直到出现空子句为止。 示例的归结图 归结演绎中的策略 盲目全面进行归结，产生许多无用归结式，更严重的是产生组合爆炸问题。 常用的归结策略分为两大类： 删除策略：通过删除某些无用的子句缩小归结的范围。 限制策略：通过对参加归结的子句进行某些限制减少归结的盲目性。 删除策略-纯文字删除 如果某个文字L在子句集中不存在与其互补的文字?L，称此文字为纯文字。 纯文字删除法是删除子句集中包含纯文字的子句。 例：设子句集 S={PVQVR，?QVR，Q，?R} P为纯文字，删除子句PVQVR，然后对{?QVR，Q，?R}进行归结。 删除策略-重言式删除 如果一个子句中包含有互补文字，称该子句为重言式。 子