第十四讲_人工智能（AI）.ppt

2007-09-26 人工智能（AI） 郑 wpzheng@sxu.edu.cn 4.1.2 消解推理规则 消解： E1∨E2, ﹁E2∨E3 E1∨E3 消解式 找互补对 4.1.4 消解反演求解过程 公式集 S，目标公式 L： 否定L, ﹁L ﹁L 加到 S 中：{﹁L, S} 化{﹁L, S}为子句集 应用消解原理，力图推出空子句NIL 4.1.4 消解反演求解过程 三人中至少录取一人。 如果录取A而不录取B, 则一定录取C。 如果录取B，则一定录取C。 求证：公司一定录取C。 证明：设用 P(x) 表示录取 x。 4.1.4 消解反演求解过程 S={P(A)∨P(B)∨P(C), P(A)∧﹁P(B) P(C), P(B) P(C)}, L={P(C)} 否定L，﹁L={﹁P(C)}； 加﹁L到S: {S, ﹁L} {P(A)∨P(B)∨P(C), (P(A)∧﹁P(B)) P(C), P(B) P(C), ﹁P(C)} 化为子句集 应用消解原理，力图推出空子句NIL 4.1.4 消解反演求解过程 {P(A)∨P(B)∨P(C), (P(A)∧﹁P(B)) P(C), P(B) P(C), ﹁P(C)} 化为子句集 (1) P(A)∨P(B)∨P(C) (2) ?P(A)∨P(B)∨P(C) (3) ?P(B)∨P(C) (4) ?P(C) 4.1.4 消解反演求解过程 {P(A)∨P(B)∨P(C), (P(A)∧﹁P(B)) P(C), P(B) P(C), ﹁P(C)} 化为子句集 (1) P(A)∨P(B)∨P(C) (2) ?P(A)∨P(B)∨P(C) (3) ?P(B)∨P(C) (4) ?P(C) 4.1.4 消解反演求解过程 利用消解反演求问题答案 已知前提化为子句集S 待求解问题W(x);新设谓词Answer(x) {?W(x)∨Answer(x)},化为子句集T S’={S,L}，归结 若得到归结式Answer，得解 4.1.4 消解反演求解过程 例：F1:王(wang)先生是小李(li)的老师 F2: 小李与小张(Zhang)是同班同学 F3: 如果x和y是同班同学，则x的老师也是y的老师 求：小张的老师是谁？ 定义谓词：T(x,y): x是y的老师 C(x,y): x和y是同班同学 4.1.4 消解反演求解过程 F1: T(wang, li) F2: C(Li, Zhang) F3: 求：T(u, Zhang) 4.1.4 消解反演求解过程 F1: T(wang, li) F2: C(Li, Zhang) F3: ?T(u, Zhang) ∨ Answer(u) 4.1.4 消解反演求解过程 4.1 消解原理 把知识和目标的否定化成子句形式 根据消解反演原则，进行推理。 从子句集中找可进行归结的子句对 哪两个可进行归结? 哪些子句对的归结可以尽快得到解? 4.1 消解原理 归结的一般过程S={C1,C2,C3,C4} S中子句两两比较归结——第一级归结式 S中子句与第一级归结式中子句逐一比较——第二级归结式 ……….. 停止：出现NIL,或ANSWER, 或无法归结 4.1 消解原理 子句形定理证明方法 效率低 丢失重要信息 4.2 规则演绎系统 非子句定理证明 规则: IF……THEN…… 前项 后项 运用规则进行推理－规则演绎系统 (与或形演绎推理) THEN规定动作－产生式系统 4.2 规则演绎系统 基于规则的推理系统 IF……THEN…… 规则演绎系统 产生式系统 推理方向 正向推理：IF THEN, 从事实或状况到目标或动作 逆向推理: THEN IF，从目标或动作到事实或状况 双向推理 4.2 规则演绎系统 消解原理: 子句形推理 规则演绎：与或形推理 4.2 规则演绎系统 推理三要素 事实或状态 规则 目标或动作 4.2.1 规则正向演绎系统 正向推理：从事实向目标进行操作 从 if 到 then 的推理 事实: 非蕴涵式的与或形——总数据库 把事实表示成谓词演算公式， 把公式变换为与或形 规则: F规则 目标：文字析取－子句 4.2.1.1 事实表达式的与或形变换 4.2.1.1 事实表达式的与或形变换 4.2.1.1 事实表达式的与或形变换 4.2.1.1 事实表达式的与或形变换 4.2.1.2 事实表达式的与或图表示 4.2.1.2 事实表达式的与或图表示 4.2.1.2 事实