人工智能导论

3-4-2鲁宾逊归结原理基本思想在谓词公式转化为子句集的过程中，子句集中子句间的关系是合取。因此，只要有一个子句为不可满足（永假），则整个子句集就是不可满足的。另一方面，空子句是不可满足的，所以，一个子句集中如果包含空子句，则该子句集就一定是不可满足的。鲁滨逊归结原理就是通过对子句集中的子句做逐次归结，直至导出空子句或不能继续归结为止，来证明子句集的不可满足性。这是定理自动证明的一个重大突破。鲁滨逊归结原理分为命题逻辑归结原理和谓词逻辑归结原理。命题逻辑的归结原理命题逻辑的归结若P是原子谓词公式，则称P与﹁P为互补文字。归结：设C1和C2是两个子句，如果C1中的文字L1与C2中的文字L2互补，则(C1-L1)∨(C2-L2)称为C1和C2的归结式，C1和C2是它的亲本。例3-7设C1=P∨Q∨R,C2=﹁P∨S,求C1和C2的归结式。L1=P，L2=﹁P，C1和C2的归结式是Q∨R∨S例3-8设C1=﹁Q,C2=Q,求C1和C2的归结式。L1=﹁Q，L2=Q，C1和C2的归结式是NIL例3-9设C1=﹁P∨Q,C2=﹁Q,C3=P,求C1、C2和C3的归结式。C1和C2的归结式C12是﹁PC12和C3的归结式C123是NIL﹁P∨Q﹁QP﹁PNIL定理3-2C1和C2的归结式C12是C1和C2的逻辑结论。证明：设C1=L∨C1′,C2=﹁L∨C2′关于解释I为真，证明C12=C1′∨C2′在解释I下也为真。L∨C1′T﹁L∨C2′TLTFC1′T﹁LFC2′TC1′∨C2′TT推论1：设S={C1,C2,C3,…,Cn},C12是C1和C2的归结式,S1={C12,C3,…,Cn},若S1不可满足，则S不可满足。证明：设C1=L∨C1′,C2=﹁L∨C2′,C1和C2的归结式C12=C1′∨C2′,S1关于解释I为假，证明S在解释I下也为假。S1FC12=C1′∨C2′TFC3或，…，或CnFC1′FLT(F)C1=L∨C1′T(F)C2′F﹁LF(T)C2=﹁L∨C2′F(T)SFF推论2：设S={C1,C2,C3,…,Cn},C12是C1和C2的归结式,S2={C12,C1,C2,C3,…,Cn},则S2不可满足当且仅当S不可满足。证明：设C1=L∨C1′,C2=﹁L∨C2′,C1和C2的归结式C12=C1′∨C2′,S2关于解释I为假，证明S在解释I下也为假。S2FC12=C1′∨C2′TFC1或，…，或CnFC1′FLT(F)C1=L∨C1′T(F)C2′F﹁LF(T)C2=﹁L∨C2′F(T)SFF定理3-3子句集S是不可满足的当且仅当存在一个从S到空子句的归结过程。（证明要用海伯伦原理，因此，鲁滨逊归结原理是建立在海伯伦原理上的。）命题逻辑的归结反演若G是F的逻辑结论，则F→G永真，从而﹁(F→G)永假，于是F∧﹁G永假。因此，已知F，证明G为真的归结反演过程如下：（1）否定G，得﹁G；（2）把{F，﹁G}化为子句集S；（3）对S归结，并将归结式放入S，若出现空子句，则G为真，否则G为假。例3-10已知{P,(P∧Q)→R,(S∨T)→Q,T},求证R。否定结论：﹁R{P,(P∧Q)→R,(S∨T)→Q,T,﹁R}子句集：{P,﹁P∨﹁Q∨R,﹁S∨Q,﹁T∨Q，T,﹁R}﹁P∨﹁Q∨R﹁RP﹁P∨﹁Q﹁Q﹁T∨Q﹁TTNIL例：若公司拒绝工人的要求，则罢工不会停止，除非罢工超过一年且公司经理辞职。问：如果公司拒绝工人的要求，而罢工又刚刚开始，罢工是否能停止？解：定义命题：P公司拒绝工人的要求；Q罢工停止;R公司经理辞职;S罢工超过一年。)QQ?(SPQ))SR(P(或待求问题：已知事实：用命题公式表示：把已知事实及待求问题事实子句集{﹁P∨﹁Q∨R，﹁P∨﹁Q∨S,P,﹁S}﹁P∨﹁Q∨S﹁S﹁P∨﹁QP﹁Q因此，结论是罢工不会停止（﹁Q）。因为，Q添加到子句集后，有﹁P∨﹁Q∨S﹁S﹁P∨﹁QP﹁QQNIL谓词逻辑的归结由于谓词逻辑中一般都含有变元，需要先用一个最一般合一对变元进行代换，才能使用归结。置换（3.2.5）置换是形如{t1/x1,t2/x2,…,tn/xn}的有限集合，其中：t1,t2,…,tn是项（常量、变量、函数）；x1,x2,…,xn是互不相同的变元；ti/xi表示用ti置换xi。并且要求ti与xi不能相同，xi不能循环地出现在另一个ti中。例：{a/x,c/y,f(b)/z}是置换，{g(y)/x,f(x)/y}不是置换。而{g(a)/x,f(x)/y}是置换。设Ɵ={t1/x1,t2/x2,…,tn/xn}是置换，F是谓词公式，把F中出现的所有xi换成ti,得到一个新的谓词公式G,称G为F在该置换下的例示，记为G=FƟ。例：P(x,y,z)在置换{a/x,f(b)/y,u/z}下的例示是P(a,f(b),u)。函数g(x,y)在置换{a/x,f(b)/y}下得g(a,f(b))。谓词公式的例示是该谓词公式的逻辑结论（全称固化和存在固化）。置换的合成：设p={t1/x1,t2/x2,…,tn/xn},q={u1/y1,u2/y2,…,um/ym}是两个置换，则p与q的合成也是一个置换，记为p·q。它是从集合{t1q/x1,t2q/x2,…,tnq/xn,u1/y1,u2/y2,…,um/ym}中删去以下两种元素：（1）当yi∈{x1,x2,…,xn}时，删去ui/yi；（2）当tiq=xi时，删去tiq/xi。剩下的元素。例：p={f(y)/x,z/y},q={a/x,b/y,y/z}，确定置换p·q。{f(y)q/x,zq/y,a/x,b/y,y/z}（删去a/x和b/y）{f(y)q/x,zq/y,y/z}{f(b)/x,y/y,y/z}（删去y/y）置换p·q是{f(b)/x,y/z}置换合成不满足交换律，但满足结合律。例：E=P(x,y,z),p={f(y)/x,z/y},q={a/x,b/y,y/z}，Ep=P(f(y),z,z),(Ep)q=P(f(b),y,y),Ep·q=P(f(b),y,y),于是Ep·q=(Ep)q合一设有公式集F={F1,F2,…,Fn},若存在一个置换p使F1p=F2p=…=Fnp,则称p是F的一个合一。称F1,F2,…,Fn是可合一的。例：F={P(x,y,f(y)),P(a,g(x),z)}p={a/x,g(a)/y,f(g(a))/z}F1p=P(a,g(a),f(g(a)))F2p=P(a,g(a),f(g(a)))从上例中可以看出两个谓词是可合一的，就必须具有相同的谓词符号。例：F={P(x,y,f(y)),P(a,g(x),z)}p={a/x,g(a)/y,f(g(a))/z}F1p=P(a,g(a),f(g(a)))F2p=P(a,g(a),f(g(a)))而合一置换的构造如下：比较第一变元：x,ax是变元，a是常量，用a替换x，即a/x;比较第二变元：y,g(x)y是变元，g(x)是函数，用g(x)替换y，即g(x)/y;比较第三变元：f(y),zz是变元，f(y)是函数，用f(y)替换z，即f(y)/z.例：F={P(x,y,f(y)),P(a,g(x),z)}p={a/x,g(a)/y,f(g(a))/z}比较第一变元：x,ax是变元，a是常量，用a替换x，即a/x;比较第二变元：y,g(x)y是变元，g(x)是函数，用g(x)替换y，即g(x)/y;比较第三变元：f(y),zz是变元，f(y)是函数，用f(y)替换z，即f(y)/z.得到置换{a/x,g(x)/y,f(y)/z}也就是{a/x,g(a)/y,f(g(a))/z}例：F={P(x,y,z),P(x,f(a),h(b))}比较第一变元：x,xx是变元，x是变元，用x替换x，即x/x;比较第二变元：y,f(a)y是变元，f(a)是常量，用f(a)替换y，即f(a)/y;比较第三变元：z,h(b)z是变元，h(b)是常量，用h(b)替换z，即h(b)/z.得到合一置换{x/x,f(a)/y,h(b)/z}也就是{f(a)/y,h(b)/z}F{f(a)/y,h(b)/z}={P(x,f(a),h(b)),P(x,f(a),h(b))}例：F={P(a,x,f(g(y))),P(z,h(z,u),f(u))}比较第一变元：a,zz是变元，a是常量，用a替换z，即a/z;比较第二变元：x,h(z,u)x是变元，h(z,u)是函数，用h(z,u)替换x，即h(z,u)/x;比较第三变元：f(g(y)),f(u)g(y)(函数)是f(g(y))的变元(对f来说)，u是f(u)的变元(对f来说)，用g(y)替换u，即g(y)/u.得到合一置换{a/z,h(z,u)/x,g(y)/u}也就是{a/z,h(a,g(y))/x,g(y)/u}F{a/z,h(a,g(y))/x,g(y)/u}={P(a,h(a,g(y)),f(g(y))),P(a,h(a,g(y)),f(g(y)))}例：F={P(a,b,c),P(d,b,c)}比较第一变元：a,da是常量，d是常量，常量不能替换常量。因此，不可合一。例：F={P(a,b),P(x,y,z)}P(a,b)是二元谓词，P(x,y,z)是三元谓词。因此，不可合一。总结如下：（1）同元谓词才可能；（2）对应位置元相比较；（3）常量、变量替换变量；（4）函数替换变量；（5）函数相逢也一样。例：F={R(g(x),y,g(g(z))),﹁R(u,g(u),g(v))}比较第一变元：g(x),ug(x)是函数，u是变元，用g(x)替换u，即g(x)/u;比较第二变元：y,g(u)y是变元，g(u)是函数，用g(u)替换y，即g(u)/y;比较第三变元：g(g(z)),g(v)g(z)(函数)是g(g(z))的变元(对前g来说)，v是g(v)的变元(对g来说)，用g(z)替换v，即g(z)/v.得到合一置换{g(x)/u,g(u)/y,g(z)/v}也就是{g(x)/u,g(g(x))/y,g(z)/v}F{g(x)/u,g(g(x))/y,g(z)/v}={R(g(x),g(g(x)),g(g(z))),﹁R(g(x),g(g(x)),g(g(z)))}作业p.1003-8谓词逻辑的归结原理若P是原子谓词公式，则称P与﹁P为互补文字。归结：设C1和C2是两个没有公共变元的子句，如果C1中的文字L1与C2中的文字L2互补，且p是L1与L2的合一置换，则(C1p-L1p)∨(C2p-L2p)称为C1和C2的归结式，C1和C2是它的亲本。例3-11设C1=P(a)∨R(x),C2=﹁P(y)∨Q(b),求C1和C2的归结式。L1=P(a)，L2=﹁P(y)，L1与L2的合一置换是p={a/y}C2p=﹁P(a)∨Q(b)C1和C2归结是R(x)∨Q(b)例3-12设C1=P(x)∨Q(a),C2=﹁P(b)∨R(x),求C1和C2的归结式。变元变名C2=﹁P(b)∨R(y)L1=P(x)，L2=﹁P(b)，L1与L2的合一置换是p={b/x}C1p=P(b)∨Q(a)C1和C2归结是Q(a)∨R(x)例3-13设C1=P(x)∨﹁Q(b),C2=﹁P(a)∨Q(y)∨R(z),求C1和C2的归结式。归结时一次只能消去一个互补对。L1=P(x)，L2=﹁P(a)，L1与L2的合一置换是p={a/x}C1p=P(a)∨﹁Q(b)C1和C2归结是﹁Q(b)∨Q(y)∨R(z)例3-14设C1=P(x)∨P(f(a))∨Q(x),C2=﹁P(y)∨R(b),求C1和C2的归结式。子句内部有可合一的文字时，归结前应先对这些文字合一。C1中P(x)与P(f(a))的合一置换q={f(a)/x}C1q=P(f(a))∨P(f(a))∨Q(f(a))=P(f(a))∨Q(f(a))L1=P(f(a))，L2=﹁P(y)，L1与L2的合一置换是p={f(a)/y}C2p=﹁P(f(a))∨R(b)C1和C2归结是Q(f(a))∨