人工智能-.ppt

~HB(s5) ~ON(s3) ? ~AT(box, c, s3) ? HB(grasp(s3)) ~ON(s3) ? ~AT(box, c, s3) {grasp(s3)/s5} ON(climb(s2)) {climb(s2)/s3} ~AT(box, c, climb(s2)) ~ON(s0) ON(s1) ? AT(box, x1, push(x1, s1)) {s0/s1} AT(box, x1, push(x1, s0)) ~AT(box, x4, s4) ?AT(box, x4, climb(s4)) {x4/x1,push(x4,s0)/s4} AT(box, x4, climb(push(x4,s0))) NIL {c/x4,push(c,s0)/s2} HB(s5) ? HB(grasp(s3)) ? ? HB(grasp(climb(s2))) HB(grasp(climb(push(c,s0)))) 归结方法小结 求子句集，进行归结，方法简单 通过修改证明树的方法，提取回答 方法通用 求解效率低，不宜引入启发信息 不宜理解推理过程 4.5 基于规则的正向演绎系统 问题： 归结方法不自然 可能会丢失蕴涵关系中所包含的控制信息 例： 以下蕴涵式： ~A ? ~B ? C ~C ? A ? B ~A ? ~C ? B ~A ? C ? B ~B ? ~C ? A ~B ? A ? C 均与子句(A ? B ? C)等价，但显然上面的蕴涵式信息更丰富。 事实表达式的与或形及其表达 与或形 无量词约束 否定符只作用于单个文字 只有“与”、“或” 例： (?u)(?v)(Q(v, u)?~((R(v)?P(v))?S(u, v))) =(?u)(?v) (Q(v, u)?((~R(v)?~P(v))?~S(u, v))) =Q(v, a)?((~R(v) ? ~P(v))?~S(a, v)) Skolem化 = Q(w, a)?((~R(v)?~P(v))?~S(a, v)) 主合取元变量换名 事实的与或树表示 例： Q(w, a)?((~R(v) ? ~P(v)) ? ~S(a, v)) Q(w, a)?((~R(v) ? ~P(v)) ? ~S(a, v)) Q(w, a) (~R(v) ? ~P(v)) ? ~S(a, v) ~R(v) ? ~P(v) ~S(a, v) ~R(v) ~P(v) 解图集：Q(w, a), ~R(v)?~S(a, v), ~P(v)?~S(a, v) 应用规则对与或图作变换 对规则的形式： L ? W 其中，L是单文字，W是与或形，变量受全称量词约束 例：(?x)(((?y)(?z)P(x, y, z)) ? (?u)Q(x, u)) = (?x)(~((?y)(?z)P(x, y, z)) ? (?u)Q(x, u)) = (?x)((?y)(?z)~P(x, y, z) ? (?u)Q(x, u)) = (?x)(?y)(?z) (?u)(~P(x, y, z) ? Q(x, u)) 转化 ~P(x, y, f(x, y)) ? Q(x, u) 转化P(x, y, f(x, y)) ? Q(x, u) 转化P(x1, y1, f(x1, y1)) ? Q(x1, u1) 换名 例：(L1 ? L2) ? W 转化为L1 ? W 和 L2 ? W 命题逻辑的情况 例： 事实：((P ? Q) ? R) ? (S ? (T ? U)) 规则：S ? (X ? Y) ? Z ((P ? Q) ? R) ? (S ? (T ? U)) (P ? Q) ? R S ? (T ? U) P ? Q R S T ? U P Q T U S X ? Y Z X Y 事实子句： P? Q? S P? Q? T? U S? R R? T? U 规则的子句： S ? (X ? Y) ? Z = ~S?(X ? Y) ? Z = ~S ? X ? Z ~S ? Y ? Z 结论：加入规则后得到的解图，是事实与规则对应子句的归结式 得到的结论： P? Q? X? Z P? Q? Y? Z R? X? Z R? Y? Z 例： 事实：A ? B 规则集： A ? C ? D B ? E ? G 目标公式： C ? G A? B A B A C D B E G C G 目标 谓词逻辑的情况 事实表达式化成与或形 规则化成L ? W的形式，其中L为单文字 目标用Skolem 化的对偶形式，即 消去全称量词，用Skolem函数代替 保留存在量词 对析