浙大版人工智能chp2.ppt

第三章 人工智能中的谓词演算及应用 一致化算法(Unify(E1…Em))：设W={E1…Em} (1) 置K=0，Wk=W,σk=ε(ε表示空置换) (2) 如果Wk只含单独一个原子命题公式，则结束，σk就是W的最一般的一致置换，否则寻找Wk的不一致集合Dk. (3) 如果Dk中存在元素Vk,tk, 且Vk是一个tk中不出现的变换，则作(4)，否则结束，W不可合一。 (4) 令σk+1 = σk · (tk/Vk), 并且作 Wk+1 = Wk(tk/Vk)。 (5) 置K=K+1,转(2)。 可以证明算法在有限步结束，且W可合一时是最一般的一直置换。 第三章 人工智能中的谓词演算及应用 例子：W={P(a,x,f(g(y))),P(z,f(z),f(u))}求W的最一般一致置换。 (1) σ0=ε,W0=W, W0不是单个原子公式,σ0不是一般一直置换。 (2) 求得不一致集D0={a,z},在D0中存在V0=z,且不在t0=a中出现。 (3) 令σ1=σ0{t0/V0}={a/z}, W1=W0{a/z} ={P(a,x,f(g(y))),P(a,f(a),f(u))} (4) D1={x,f(a)} (5) D1中，V1=x, t1=f(a) (6) σ2=σ1{t1/V1}={a/z}·{f(a)/x}={a/z,f(a)/x}, W2=W1{f(a)/x}={P(a,f(a),f(g(y))),P(a,f(a),f(u))} 第三章 人工智能中的谓词演算及应用 (7) D2={g(y),u}, V2=u, t2=g(y) (8) 令σ3=σ2·{t2/V2}={a/z,f(a)/x,g(y)/u} W3=W2{g(y)/u} ={P(a,f(a),f(g(y))),P(a,f(a),f(g(y)))} ={P(a,f(a),f(g(y)))} (9) 所得σ3={a/z,f(a)/x,g(y)/u}为所求的最一般一致置换。 例：W={Q(f(a),g(x)),Q(y,y)}判定W是否可合一。 1. 令σ0=ε,W0=W; 2. D0={f(a),y}, σ1={f(a)/y}, W1 = W{f(a)/y} = {Q(f(a),g(x)),Q(f(a),f(a))} 3. D1中没有一个元素是变量，故W不可合一。 第三章 人工智能中的谓词演算及应用 谓词逻辑的归结过程：设C1和C2为不具有完全相同变元的两个子句，子句中的变量已标准化。采用文字集形式表示子句(即文字之间理解为析取关系)，则 C1={C1i} (i=1,…,n), C2={C2j} (j=1,…,m) 再设{L1k}和{L2k}分别为C1和C2的两个子集。若{L1k}和{～L2k}的并集存在一个mgu s, 则两个子集归结式为： C={{C1i}-{L1k}}s∪{{C2i}-{L2k}}s 可以看出这两个子句归结时由于有多种方式选取{L1k}、{L2k}，因此归结式不是唯一的。 第三章 人工智能中的谓词演算及应用 例：C1=P(x,f(A))∨P(x,f(y))∨Q(y) C2=～P(z,f(A))∨～Q(z) 1. 取 L11=P(x,f(A)),L21=～P(z,f(A)),存在s={z/x}使L11和～L21合一，所以归结式为 (P(z,f(y))∨Q(y)∨～Q(z) 2. 取 L11=P(x,f(y)),L21=～P(z,f(A)),则s={z/x,A/y},归结式为 Q(A)∨～Q(z) 3. 取 L11=Q(y),L21=～Q(z), 则s={y/z}, 归结式为 P(x,f(A))∨P(x,f(y))∨P(y,f(A)) 例子表明选不同文字对做归结时得到不同的归结式，但由于都是用最一般合一做置换，所以归结式仍是最一般归结式，而若某文字不用mgu合一，结果会有许多限制。 第三章 人工智能中的谓词演算及应用 例：已知 1.会朗诵的人是识字的；2.海豚都不识字；3. 有些海豚是很机灵的。证明：有些很机灵的东西不会朗诵。 首先将问题的描述用谓词逻辑表示： 已知：1.( x)(R(x)→L(x)); 2. ( x)(D(x)→～L(x)); 3.(ョx)(D(x)∧I(x))。 求证：(ョx)(I(x)∧～R(x)) 将条件的谓词公式化简,要证明的结论取非,化成子句形,得子句集: 1. ～R(x)∨L(x); 2. ～D(y)∨～L(y); 3a. D(A); 3b. I(A); 4. ～I(z)∨R(z).归结(证明): 5. R(A); (3b)和(4)的归结式 6. L(