《人工智能导论-》- 04 推理-0....ppt

(?x)(?y)P(a,x,y)∨(?x)((?y)Q(y,b)∨R(x)) 第三步，变元易名，得 (?x)(?y)P(a,x,y) ∨(?u)(?v)(Q(v,b) ∨R(u)) 第四步，存在量词左移，直至所有的量词移到前面，得： (?x)(?y)(?u)(?v)P(a,x,y) ∨(Q(v,b)∨R(u)) 由此得到前束范式 (?x)(?y)(?u)(?v)P(a,x,y)∨(Q(v,b)∨R(u)) 第五步，消去“?”（存在量词），略去“?”全称量词 消去(?y)，因为它左边只有(?x)，所以使用x的函数f(x)代替之，这样得到： (?x)(?u)(?v)(P(a,x,f(x))∨Q(v, b)∨R(u)) 消去(?u)，同理使用g(x)代替之，这样得到： (?x)(?v)(P(a,x,f(x))∨Q(v,b)∨R(g(x))） 略去全称变量，原式的Skolem标准形为： P(a,x,f(x))∨Q(v,b)∨R(g(x)) 归结的注意事项： 谓词的一致性，P()与Q()，不可以归结 常量的一致性，P(a, …)与P(b,….)，不可以归结 变量，P(a,….)与P(x,…)，可以归结 变量与函数，P(x,….)与P(f(x),…)，不可以归结； 不能同时消去两个互补对 先进行内部简化（置换、合并） 例: c1=P(y)∨Q(x)∨R(g(x)), c2=～P(f(g(a)))∨～Q(b) 归结的过程 写出谓词关系公式 用反演法写出谓词表达式 SKOLEM标准形 子句集S 对S中可归结的子句做归结 归结式仍放入S中，反复归结过程 得到空子句 得证 例题“快乐学生”问题 假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。 ?解：先将问题用谓词表示如下： R1:“任何通过计算机考试并获奖的人都是快乐的” (?x)((Pass(x, computer)∧Win(x, prize))→Happy(x)) R2:“任何肯学习或幸运的人都可以通过所有考试” (?x)(?y)(Study(x)∨Lucky(x)→Pass(x, y)) R3:“张不肯学习但他是幸运的” ～Study(zhang)∧Lucky(zhang) R4:“任何幸运的人都能获奖” (?x)(Luck(x)→Win(x,prize)) 结论：“张是快乐的”的否定 ～Happy(zhang) 由R1及逻辑转换公式:P∧W→H = ～（P∧W）∨ H ，可得 (1)～Pass(x, computer)∨～Win(x, prize)∨Happy(x) 由R2： (2)～Study(y)∨Pass(y,z) (3)～Lucky(u)∨Pass(u,v) 由R3： (4)～Study(zhang) (5)Lucky(zhang) 由R4： (6)～Lucky(w)∨Win(w，prize) 由结论：(7)～Happy(zhang) （结论的否定） (8)～Pass(w, computer)∨Happy(w)∨～Luck(w) (1)(6)，{w/x} (9)～Pass(zhang, computer)∨～Lucky(zhang) (8)(7)，{zhang/w} (10)?～Pass(zhang, computer) (9)(5) (11)??～Lucky(zhang) (10)(3)，{zhang/u, computer/v} (12) Nil (11)(5)? 归结原理 归结法的实质： 归结法是仅有一条推理规则的推理方法。 归结的过程是一个语义树倒塌的过程。 例:储蓄问题 前提：每个储蓄钱的人都获得利息。 结论：如果没有利息，那么就没有人去储蓄钱 证明： (1）规定原子公式： S(x,y) 表示 “x储蓄y” M(x) 表示 “x是钱” I(x) 表示 “x是利息” E(x，y) 表示 “x获得y” (2）用谓词公式表示前提和结论： 前提： (?x)[(?y)(S(x,y) ∧M(y)）? (?y)(I(y)∧E(x,y))] 结论： ～(?x)I(x)? (?x)(?y)(M(y)→～S(x,y)) 1) ～S(x,y)∨～M(y)∨I(f(x)) 2) ～S(x,y)∨～M(y)∨E(x,