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

ArtificialIntelligence(AI)

人工智能主讲：戚玉涛Email：qi_yutao@163.com第三章：确定性推理内容提要要第三章：：确定性性推理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：删除策策略主要思想想：归结过程程在寻找找可归结结子句时时，子句句集中的的子句越越多，需需要付出出的代价价就会越越大。如如果在归归结时能能把子句句集中无无用的子子句删除除掉，这这就会缩缩小搜索索范围，，减少比比较次数数，从而而提高归归结效率率。常用的删删除方法法有以下下几种纯文字删删除法重言式删删除法包孕删除除法归结反演演推理的的归结策策略纯文字删删除法如果某文文字L在子句集集中不存存在可与与其互补补的文字字﹁L，则称该该文字为为纯文字。显然，在在归结过过程中纯纯文字不不可能被被消除，，用包含含纯文字字的子句句进行归归结也不不可能得得到空子子句。因因此，对对包含纯文文字的子子句进行归结结是没有有意义的的，应该该把它删删除。对子句集集而言，，删除包包含纯文文字的子子句，是是不影响响其不可可满足性性的。如：子句句集S={P∨Q∨R,,﹁Q∨R,,Q,﹁﹁R}，P是纯文字字，可以将将子句P∨Q∨∨R从子句集集S中删除。。归结反演演推理的的归结策策略重言式删删除法如果一个个子句中中包含有有互补的的文字对对，则称称该子句句为重言式。例如：P(x))∨﹁P(x),P(x))∨Q((x)∨∨﹁P((x)都是重言言式，不不管P(x)的真值为为真还是是为假，，P(x))∨﹁P(x)和P(x))∨Q((x)∨∨﹁P((x)都均为真真。重言式是是真值为为真的子子句。对一个个子句集集来说，，不管是是增加还还是删除除一个真真值为真真的子句句，都不不会影响响该子句句集的不不可满足足性。因因此，可可从子句句集中删删去重言言式。归结反演演推理的的归结策策略包孕删除除法设有子句句C1和C2，若存在在一个置置换σ，使C1σ⊆C2，则称C1包孕于C2。例如：P(x)包孕于P(y))∨Q((z)σ={y/x}P(x)包孕于P(a)σ={a/x}}P(x)包孕于P(a))∨Q((z)σ={a/x}}P(x)∨Q(a)包孕于P(f((a)))∨Q((a)∨∨R(y)σ={f(a))/x}P(x)∨Q(y)包孕于P(a))∨Q((u)∨∨R(w)σ={a/x,,u/y}可从子句句集中删删除那些些包孕的的子句。。归结反演演推理的的归结策策略策略3：单文字字子句策策略如果一个个子句只包含一一个文字字，则称此此子句为为单文字子子句。单文字子子句策略略要求每次参加加归结的的两个亲亲本子句句中至少少有一个个子句是是单文字字子句。采用单文文字子句句策略，，归结式式包含的的文字数数将少于于其亲本本子句中中的文字字数，这这将有利利于向空空子句的的方向发发展，因因此会有有较高的的归结效效率。但这种策策略是不完备的，即当当子句集集为不可可满足时时，用这这种策略略不一定定能归结结出空子子句。归结反演演推理的的归结策策略例：设有如下下子句集集：S={﹁﹁I(x))∨R((x),I(a),﹁﹁R(y))∨L((y),﹁﹁L(a)}用单文字字子句策策略证明明S为不可满满足。﹁I(x)∨R(x)I(a)﹁R(y)∨L(y)﹁L(a)R(a)﹁R(a)NIL归结反演演推理的的归结策策略策略4：线性输输入策略略这种策略略要求每每次参加加归结的的两个亲亲本子句句中，至少应该该有一个个是初始始子句集集中的子子句。所谓初初始子句句集是指指开始归归结时所所使用的的子句集集。线性输入入策略可可限制生生成归结结式的数数目，具具有简