西电人工智能13 确定性推理 part 6

Artificial Intelligence (AI)

人工智能第三章：确定 性推理

主讲：戚玉涛Email:qi_yutao@http://doc.guandang.net西安电子科技大学

内容提要第三章：确定性推理1.推理的基本概念

2.搜索策略3.自然演绎推理

4.归结演绎推理5.基于规则的演绎推理

西安电子科技大学

归结演绎推理 归结演绎推理 子句集及其化简 鲁滨逊归结原理 归结反演推理的归结策略 用归结反演求取问题的答案

西安电子科技大学

鲁滨逊归结原理 鲁滨逊归结原理包括

命题逻辑的归结

谓词逻辑的归结

西安电子科技大学

命题逻辑的归结 命题逻辑的归结反演：在命题逻辑中，已知F,证 明G为真的归结反演过程如下： ①否定目标公式G,得﹁G; ②把﹁G并入到公式集F中，得到{F,﹁G}; ③把{F,﹁G}化为子句集S。

④ 应用归结原理对子句集S中的子句进行归结，并 把每次得到的归结式并入S中。如此反复进行，若 出现空子句，则停止归结，此时就证明了G为真。西安电子科技大学

鲁滨逊归结原理 鲁滨逊归结原理包括

命题逻辑的归结

谓词逻辑的归结

西安电子科技大学

谓词逻辑的归结 在谓词逻辑中，由于子句集中的谓词一般都含有变元，因 此不能象命题逻辑那样直接消去互补文字。 对于谓词逻辑，需要先用一个最一般合一对变元进行置换， 然后才能进行归结。

谓词逻辑的归结原理 设C1和C2是两个没有公共变元的子句，L1和L2分别是 C1和C2中的文字。如果 σ 是L1和﹁ L2存在最一般合一， 则称： C12=({C1σ}-{ L1σ})∪({ C2σ}-{ L2σ})

为C1和C2的二元归结式，L1和L2为归结式上的文字。

西安电子科技大学

谓词逻辑的归结 例：设C1=P(a)∨R(x),C2=﹁P(y)∨Q(b),求 C12 解：取L1= P(a), L2=﹁P(y),则L1和﹁L2的最 一般合一是σ={a/y}。因此：C12= ( {C1σ}-{L1σ}) ∪ ({C2σ}-{L2σ})= ({P(a), R(x)}-{P(a)})∪({﹁P(a), Q(b)}-{﹁P(a)}) = ({R(x)})∪({Q(b)}) = { R(x), Q(b) } = R(x)∨Q(b)西安电子科技大学

谓词逻辑的归结 例：设C1=P(x)∨Q(a),C2=﹁P(b)∨R(x) ,求 C12 解：由于C1和C2有相同的变元x,不符合定义的要求。为了进行归结，需要修改C2中变元的名字。令 C2=﹁P(b)∨R(y),此时L1= P(x), L2 =﹁P(b),L1和 ﹁L2的最一般合一是 σ={b/x}。则有:C12= ( {C1σ}-{L1σ})∪ ({C2σ}-{L2σ})

= ({P(b), Q(a)}-{P(b)}) ∪ ({﹁P(b), R(y)}-{﹁P(b)}) = ({Q(a)}) ∪ ({R(y)}) = {Q(a), R(y)} = Q(a)∨R(y)

西安电子科技大学

谓词逻辑的归结 例：设 C1=P(a)∨﹁Q(x) ∨R(x)C2=﹁P(y)∨Q(b) 求C12 对C1和C2通过最一般合一(σ={b/x, a/y})的作用， 可以得到两个互补对。 注意：求归结式不能同时消去两个互补对，这样的 结果不是二元归结式。如在σ

={b/x, a/y}下，若同时 消去两个互补对，所得的R(b)不是C1和C2的二元归 结式。西安电子科技大学

谓词逻辑的归结 例：设 C1=P(a)∨﹁Q(x) ∨R(x)C2=﹁P(y)∨Q(b) 求C12 解1:取L1= P(a), L2=﹁P(y),则σ={a/y}是L1与﹁L2 的最一般合一。此时： C12= ﹁Q(x) ∨ R(x) ∨Q(b) 解2:取L1= ﹁Q(x) L2=Q(b) ,则σ={b/x}是L1与﹁ L2的最一般合一。此时：

C12= P(a)∨ R(b) ∨﹁P(y) 西安电子科技大学

谓词逻辑的归结 例：设 C1=P(x)∨P(f(a))∨Q(x) ,C2=﹁P(y)∨R(b)求C12 解：对参加归结的某个子句，若其内部有可合一的文 字，则在进行归结之前应先对这些文字进行合一。 本例的C1中有可合一的文字P(x)与P(f(a)),若用它们的 最一般合一σ={f(a)/x}进行代换，可得到 ： C1σ=P(f(a))∨Q(f(a)) 此时对C1σ与C2进行归结。选L1= P(f(a)), L2 =﹁P(y), L1和L2的最一般合一是σ={f(a)/y},则可得到C1和C2的 二元归结式为：C12=R(b)∨Q(f(a))

西安电子科技大学

谓词逻辑的归结 例：设 C1=P(y)∨P(f(x))∨Q(g(x))C2=﹁P(f(g(a)))∨Q(b) 求C12 解：对C1 ,取最一般合一 σ={f(x)/y},得C1的因子 C1σ=P(f(x))∨Q(g(x))

对C1的因子和C2归结(σ={g(a)/x }),可得：C12=Q(g(g(a)))∨Q(b)西安电子科技大学

谓词逻辑的归结 我们把C1σ称为C1的因子。一般来说，若子句C中有两个 或两个以上的文字具有最一般合一σ,则称Cσ为子句C的 因子。如果Cσ是一个单文字，则称它为C的单元因子。应 用因子概念，可对谓词逻辑中的归结原理给出如下定义：

若C1和C2是无公共变元的子句，则子句C1和C2的归结 式是下列二元归结式之一： ① C1和C2的二元归结式; ② C1的因子C1σ1和C2的二元归结式； ③ C1和C2的因子C2σ2的二元归结式； ④ C1的因子C1σ1和C2的因子C2σ的二元归结式。

西安电子科技大学

谓词逻辑的归结 谓词逻辑的归结反演 谓词逻辑的归结反演过程与命题逻辑的归结反 演过程相比，其步骤基本相同，但每步的处理 对象不同。 在步骤(3)化简子句集时，谓词逻辑需要把由谓 词构成的公式集化为子句集。 在步骤(4)按归结原理进行归结时，谓词逻辑的 归结原理需要考虑两个亲本子句的最一般合一。西安电子科技大学

谓词逻辑的归结 例：已知F: ( x)(( y)(A(x, y)∧B(y))→( y)(C(y)∧D(x, y))) G: ﹁( x)C(x)→( x)( y)(A(x, y)→﹁B(y))

求证G是F的逻辑结论。 证明：先把G否定，并放入F中，得到的{F, ﹁G}:

{( x)(( y)(A(x,y)∧B(y))→( y)(C(y)∧D(x,y))),﹁(﹁( x)C(x)→( x)( y)(A(x,y)→﹁ B(y)))} 再把{F,﹁G}化成子句集，得到西安电子科技大学