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

西安电子科技大学ArtificialIntelligence(AI)人工智能主讲：戚玉涛Email：[e-mail]第三章：确定性推理西安电子科技大学内容提要第三章：确定性推理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}化成子句集，得到西安电子科技大学谓词逻辑的归结(1)﹁A(x,y)∨﹁B(y)∨C(f(x))(2)﹁A(u,v)∨﹁B(v)∨D(u,f(u))(3)﹁C(z)(4)A(m,n)(5)B(k)最后应用谓词逻辑的归结原理对上述子句集进行归结，其过程为：(6)﹁A(x,y)∨﹁B(y)(7)﹁B(n)(8)NILF﹁G(1)和(3)归结，取σ={f(x)/z}(4)和(6)归结，取σ={m/x,n/y}(5)和(7)归结，取σ={n/k}西安电子科技大学谓词逻辑的归结因此，G是F的逻辑结论。上述归结过程可用如下归结树来表示﹁A(x,y)∨﹁B(y)∨C(f(x))﹁C(z)﹁A(x,y)∨﹁B(y)A(m,n)﹁B(n)B(k)NIL{f(x)/z}{m/x,n/y}{n/k}西安电子科技大学谓词逻辑的归结例：“快乐学生”问题假设：任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。解：先定义谓词：Pass(x,y)：x可以通过y考试Win(x,prize)：x能获得奖励Study(x)：x肯学习Happy(x)：x是快乐的Lucky(x)：x是幸运的西安电子科技大学谓词逻辑的归结再将问题用谓词表示如下：“任何通过计算机考试并奖的人都是快乐的”(∀x)(Pass(x,computer)∧Win(x,prize)→Happy(x))“任何肯学习或幸运的人都可以通过所有考试”(∀x)(∀y)(Study(x)∨Lucky(x)→Pass(x,y))“张不肯学习但他是幸运的”﹁Study(zhang)∧Lucky(zhang)“任何幸运的人都能获奖”(∀x)(Lucky(x)→Win(x,prize))结论“张是快乐的”的否定﹁Happy(zhang)西安电子科技大学谓词逻辑的归结将上述谓词公式转化为子句集如下：(1)﹁Pass(x,computer)∨﹁Win(x,prize)∨Happy(x)(2)﹁Study(y)∨Pass(y,z)(3)﹁Lucky(u)∨Pass(u,v)(4)﹁Study(zhang)(5)Lucky(zhang)(6)﹁Lucky(w)∨Win(w,prize)(7)﹁Happy(zhang)(结论的否定)按归结原理进行归结，归结树如下：西安电子科技大学谓词逻辑的归结﹁Pass(x,computer)∨﹁Win(x,prize)∨Happy(x)﹁Lucky(w)∨Win(w,prize)﹁Pass(w,Computer)∨Happy(w)∨﹁Lucky(w)﹁Happy(zhang)Lucky(zhang)﹁Pass(zhang,Computer)∨﹁Lucky(zhang)﹁Pass(zhang,Computer)﹁Lucky(u)∨Pass(u,v)﹁Lucky(zhang)Lucky(zhang)NIL{w/x}{zhang/w}{zhang/u,computer/v}西安电子科技大学归结演绎推理归结演绎推理子句集及其化简鲁滨逊归结原理归结反演推理的归结策略用归结反演求取问题的答案西安电子科技大学归结反演推理的归结策略在归结演绎推理中，由于事先并不知道哪些子句对可进行归结，更不知道通过对哪些子句对的归结能尽快得到空子句，因此就需要对子句集中的所有子句逐对进行比较，直到得出空子句为止。这种盲目的全面进行归结的方法，不仅会产生许多无用的归结式，更严重的是会产生组核爆炸问题。因此，需要研究有效的归结策略来解决这些问题。常用的归结策略可分为两大类：限制策略：通过限制参加归结的子句减少盲目性删除策略：通过删除某些无用的子句缩小归结范围西安电子科技大学归结反演推理的归结策略归结的一般过程设初始子句集为S0，对子句集进行归结的一般过程如下：(1)从S0出发，对S0中的全部子句作所有可能的归结，得到第一层归结式，记为S1;(2)用S0中的子句与S1中的子句进行所有可能的归结，得到第二层归结式，记为S2;(3)用S0和S1中的子句与S2中的子句进行所有可能的归结，得到第三层归结式，记为S3;如此继续，知道得出空子句或不能再继续归结为止。西安电子科技大学归结反演推理的归结策略例：设有如下子句集：S={﹁I(x)∨R(x),I(a),﹁R(y)∨L(y),﹁L(a)}归结的一般过程如下﹁I(x)∨R(x)I(a)﹁R(y)∨L(y)﹁L(a)R(a)﹁I(x)∨L(x)﹁R(a)L(a)L(a)﹁I(a)﹁I(a)NILSS1S2西安电子科技大学归结反演推理的归结策略可以看出，按照一般过程进行归结时，不仅归结出了许多无用的子句，而且有一些归结式还是重复的，既浪费时间，又多占空间。但是，这种策略当问题有解时保证能找到最短归结路径。因此，它是一种完备的归结策略。策略1：支持集策略支持集策略是沃斯(Wos)等人在1965年提出的一种归结策略。支持集策略要求每次参加归结的两个亲本子句中，至少有一个是由目标公式的否定得到的子句或它们的后裔。可以证明支持集策略是完备的，即当子句集为不可满足时，则由支持集策略一定能够归结出一个空子句。西安电子科技大学归结反演推理的归结策略例：设有如下子句集：S={﹁I(x)∨R(x),I(a),﹁R(y)∨L(y),﹁L(a)}其中，﹁I(x)∨R(x)为目标公式的否定。用支持集策略证明S为不可满足。﹁I(x)∨R(x)I(a)﹁R(y)∨L(y)﹁L(a)R(a)﹁I(x)∨L(x)L(a)L(a)﹁I(a)NIL支持集策略限制了子句集元素剧增，但会增加空子句所在的深度西安电子科技大学归结反演推理的归结策略策略2：删除策略主要思想：归结过程在