人工智能导论课件人工智能导论——第五章_201001851章节幻灯片.pptVIP

形式上的要求 目标为任意表达式 事实表达式是文字的合取 规则形式： L ? W, 其中W为单文字， 如形为： L? W1 ?W2，则变换为： L? W1 和 L? W2 变量收全称量词约束 对目标逆向使用规则 * 目标用Skolem 化的对偶形式，即 消去全称量词，用Skolem函数代替 保留存在量词 对主析取元作变量换名 例：(?y)(?x)(P(x, y) ? Q(x, y)) = (?y)(P(f(y), y) ? Q(f(y), y)) = P(f(y1), y1) ? Q(f(y2), y2) 换名 * 对目标表达式的处理 目标的与或树表示 * 例： 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) * 对规则的处理 对规则的形式： L ? W 其中，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) 换名 应用规则对与或图做变换 * 例： 目标： Q(w, A) ?((~R(v) ? ~P(v)) ? ~S(A, v)) 规则： P(u)? Q(v, A) ? ~S(u, B) 假设w, u, v是变量，A、B是常量 * 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) ~S(u, B) {A/u, B/v} P(A) Q(B,A) * 一致解图 如果一个解图中所涉及的置换是一致的，则该解图称为一致解图。 设有置换集{u1, u2, …, un}, 其中: ui={ti1/vi1, …, tin/vin}，定义表达式： U1=(v1,1, …, v1,m1, …, vn,1, …, vn,mn) U2=(t1,1, …, t1,m1, …, tn,1, …, tn,mn) 置换集{u1, u2, …, un}称为一致的，当且仅当U1和U2是可合一的。 U1、U2的mgu是{u1, u2, …, un}的合一复合。 置换集的合一复合运算是可结合和可交换的。 * 一致置换举例 * 例： 事实： D(F) ~B(F) W(F) M(N) 规则： R1: (W(x1) ? D(x1)) ? F(x1) R2: (F(x2) ? ~B(x2)) ? ~A(y2, x2) R3: D(x3) ? A(x3) R4: C(x4) ? A(x4) R5: M(x5) ? C(x5) 目标： C(x) ? D(y) ? ~A(x, y) C(x) ? D(y) ? ~A(x, y) C(x) D(y) ~A(x, y) C(x5) {x/x5} M(x) R5 M(N) {N/x} D(F) {F/y} ~A(y2, x2) {x/y2,y/x2} F(y) ~B(y) R2 ~B(F) {F/y} F(x1) {y/x1} W(y) D(y) R1 W(F) {F/y} D(F) {F/y} * 一致性检查 置换集 {{x/x5}, {N/x}, {F/y}, {x/y2, y/x2}, {F/y}, {y/x1}, {F/y}, {F/y}} U1=(x5, x, y, y2, x2, y, x1, y, y) U2=(x, N, F, x, y, F, y, F, F) 合一复合 {N/x5, N/x, F/y, N/y2, F/x2, F/x1} 目标得到的解答 C(x) ? D(y) ? ~A(x, y) = C(