第三章人工智能蔡自兴.pptx

第三章 归结推理方法;归结 推理;第三章 归结推理方法;概述;第三章 归结推理方法;命题逻辑的归结法;命题逻辑基础;命题逻辑基础;命题逻辑基础;命题举例;命题表示公式（1）;命题表示公式（2）;命题 逻辑的推理规则;利用规则构造证明;命题逻辑的归结法;归谬法证明;命题逻辑的归结法;命题逻辑的归结法;命题逻辑的归结法;命题逻辑归结例题（1）;命题逻辑归结例题（2）;第三章 归结推理方法;谓词归结原理基础;谓词归结原理基础;谓词归结原理基础;谓词归结原理基础;谓词归结原理基础;谓词归结原理基础;谓词归结子句形( Skolem 标准形);谓词归结子句形( Skolem 标准形);谓词归结子句形( Skolem 标准形);谓词归结子句形( Skolem 标准形);谓词归结子句形( Skolem 标准形);谓词归结子句形( Skolem 标准形);谓词归结子句形;谓词归结子句形;谓词归结子句形;求取子句集例(1);求取子句集例(2);第三章 归结推理方法;归结原理; 置 换; 例 {a/x，c/y，f(b)/z}是一个置换 {g(y)/x，f(x)/y}不是一个置换。 原因：它在x和y之间出现了循环置换现象。置换的目的是要将某些变量用另外的变量、常量或函数取代，使其不在公式中出现。这里用g(y)置换x, 用f(g(y))置换y,既没有消去x,也没有消去y. 若改为 {g(a)/x，f(x)/y} 就可以了。;置换的合成;置换的合成;合一;例1：设有置换s={z/x, A/y}，则：P[x, f(y), B]s=P[z, f(A), B]。这里x被换成了z，y被换成了A。设有公式的集合{Ei}(i=1, 2, ..., m)，如果存在一个置换s，使得这m个公式被施以s以后，变得完全一样了，则称这m个公式是可合一的，置换s是它们的合一者。;例2：设有公式集{P(x, f(y), B), P(z, f(B), B)}和置换s1={A/x, B/y, A/z}，由于：P(x, f(y), B)s=P(A, f(B), B)P(z, f(B), B)s=P(A, f(B), B)所以公式集{P(x, f(y), B), P(z, f(B), B)}是可合一的，置换s1={A/x, B/y, A/z}是它们的合一者。;若存在一个置换s使得表达式集{Ei}中每个元素经置换后的例有：E1s=E2s=E3s=… ，则称表达式集{Ei}是可合一的，这个置换s称作{Ei}的合一者。 在归结法中主要是处理可合一的子句集，例如有子句集: {P（x，f（y），B），P（x，f（B），B）}，若对两个子句作置换s＝{A/x，B/y}，则可得{P（A，f（B??，B）}，因而该子句集是可合一的。 仅仅从合一的角度看，s并不是最简单的合一者，因为还存在另一个s1＝{B/y}的合一者，使子句集合一为{P[x，f（B），B]}。因此通常还要求找的是最一般或最普通的合一者（most general unifier）g，记为mgu g。;任一合一者s与g之间的关系是： 存在一个置换s′，使得{Ei}s＝{Ei}gs′。再比较上例的两个合一者，有{A/x，B/y}＝{B/y}{A/x}，因此mgu g＝{B/y}。可见mgu g的置换限制最少，所产生的例更一般化，这有利于归结过程的灵活使用。 ;UNIFY算法;例：公式集如下：{P(x, x, z), P(f(y), f(B), y)}用表的形式表示为：E1=(P x x z)E2=(P (f y) (f B) y) 从左向右按顺序扫描两个谓词。E1和E2的第一项都是P，是一致的，转入第二项。E1的第二项是x，E2的第二项是(f y)，二者不一致。由于其中一个是变量，可以进行置换。选置换{(f y)/x}使得二者成为一致的。该置换同时作用于E1的第三项x。这样有：E1= (P (f y) (f y) z)E2= (P (f y) (f B) B); E1= (P (f y) (f y) z)E2= (P (f y) (f B) B)继续看第三项。E1的第三项是(f y)，E2的第三项是(f, B)。由于两个都是表，需要进入表的内部进行比较。 在表的内部，第一项均是f，是一致的。第二项一个是变量y，一个是常量B。选置换{B/y}使二者成为一致的。该置换不仅使得两个公式中的所有y都被替换为了B，而且也作用于前一个置换{(f y)/x}，使得该置换变成了{(f B)/x}。这样有：E1= (P (f B) (f B) z)E2= (P (f B) (f B) B);E1= (P (f B)