谓词逻辑与归结原理2

1,人工智能基础,谓词逻辑与谓词逻辑的归结原理,2/57,3/57,谓词逻辑苏格拉底三段论:“所有的人都是要死的,苏格拉底是人,所以苏格拉底是要死的”。论证应该是成立的,但是不能用命题逻辑来论证。若设P:所有的人都是要死的,Q:苏格拉底是人,R:苏格拉底是要死的。但是(PQ)R不是永真式。P:张三是大学生,Q:李四是大学生都是原子命题,只能用不同的符号来表示,这样就不能揭示出这两个命题的共同特性。,4/57,谓词的概念和表示命题是一个陈述句，它一般可分成主语和谓语两部分。有时还需要用到量词。主语一般是可以独立存在的物体,称为个体(客体),用来刻划个体的性质或关系的词称为谓语(谓词)。通常用大写字母表示谓词，而用小写字母表示客体。,5/57,例.设有下列命题:(1)张三是大学生;李四是大学生;(2)地球绕着太阳转;(3)上海在北京与广州之间。用谓词表示之。(1)设P:张三是大学生,Q:李四是大学生。这是两个不同的命题,但有相同的谓语_是大学生。若设A:是大学生，a:张三,b:李四,则A(a)(或A(张三):张三是大学生,A(b)(或A(李四):李四是大学生。,6/57,(2)地球绕着太阳转;若设B:绕着转,x:地球,y:太阳,则B(x,y):地球绕着太阳转#注意:B(y,x):太阳绕着地球转。B(y,x)与B(x,y)是不同的命题。(3)上海在北京与广州之间。若设Z:在与之间,s:上海,b:北京,g:广州,则Z(s,b,g):上海在北京与广州之间。,7/57,刻划一个个体的性质的谓词A(c)称为一元谓词，刻划二个个体间关系的谓词A(a,b)称为二元谓词,刻划n个个体间关系的谓词A(a1,a2,an,)称为n元谓词。通常，一元谓词表示客体的性质，而多元谓词表示客体之间的关系。n元谓词中个体出现的次序一经约定，就是完全确定的,不可以随意改变。谓词也分谓词常量和谓词变元,这里仅讨论谓词常量。当谓词A(a1,a2,an,)中的个体名称用具体的n个个体替代得到的式子称为谓词填式。,8/57,引入符号“”称为全称量词,“”称为存在量词,统称为量词(Quantifier),全称量词表示“凡是”,“一切”,“所有”,“任一个”等意义;存在量词表示“至少有一个”等意义;现在用量词来表达上面几个命题。(a)若设M(x):x是人,H(x):x要呼吸,则原命题可写成:(x)(M(x)H(x)(b)若设P(x):x是学生,Q(x):x要参加考试,则原命题可写成:(x)(P(x)Q(x)(c)若设Z(x):x是整数,R(x):x是正数,N(x):x是负数,则原命题可写成:(x)(Z(x)(R(x)N(x)#,9/57,例.不管黑猫白猫,抓住老鼠就是好猫。解:设C(x):x是猫,B(x):x黑的,W(x):x是白的,G(x):x是好的,M(x):x是老鼠,K(x,y):x抓住y,则原命题可表示为:(x)(y)(C(x)M(y)(B(x)W(x)K(x,y)G(x).,10/57,谓词归结原理基础,一阶逻辑基本概念个体词：表示主语的词谓词：刻画个体性质或个体之间关系的词量词：表示数量的词,11/57,谓词归结原理基础,一阶逻辑公式及其解释个体常量：a,b,c个体变量：x,y,z谓词符号：P,Q,R量词符号：,12/57,谓词归结原理基础,量词否定等值式：(x）M（x）（y）M（y）(x）M（x）（y）M（y）量词分配等值式：(x）(P（x）Q（x）)(x）P（x）(x）Q（x）(x）(P（x）Q（x）)(x）P（x）(x）Q（x）消去量词等值式：设个体域为有穷集合（a1,a2,an）(x）P（x）P（a1）P（a2）P（an）(x）P（x）P（a1）P（a2）P（an）,13/57,谓词归结原理基础,量词辖域收缩与扩张等值式：(x）(P（x）Q)(x）P（x）Q(x）(P（x）Q)(x）P（x）Q(x）(P（x）Q)(x）P（x）Q(x）(QP（x）)Q(x）P（x）(x）(P（x）Q)(x）P（x）Q(x）(P（x）Q)(x）P（x）Q(x）(P（x）Q)(x）P（x）Q(x）(QP（x）)Q(x）P（x）,14/57,谓词归结子句形(Skolem标准形),SKOLEM标准形()前束范式定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。,15/57,谓词归结子句形(Skolem标准形),即：把所有的量词都提到前面去，然后消掉所有量词(Q1x1)(Q2x2)(Qnxn)M(x1,x2,xn)约束变项换名规则：(Qx）M（x）（Qy）M（y）(Qx）M（x,z）（Qy）M（y,z）,16/57,字句集的求解：共9步,将下列谓词演算公式化为一个子句集(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y),开始：消去蕴涵符号只应用和符号，以AB替换AB。,(1)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y),17/57,(2)减少否定符号的辖域每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。(3)对变量标准化对哑元（虚构变量）改名，以保证每个量词有其自己唯一的哑元。,(2)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y),(3)(x)P(x)(y)P(y)P(f(x,y)(w)Q(x,w)P(w),18/57,(4)消去存在量词以Skolem函数代替存在量词内的约束变量，然后消去存在量词化为前束形把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形=前缀母式全称量词串无量词公式,(4)(x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)）P(g(x)式中，w=g(x)为一Skolem函数。,(5)(x)(y)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x),19/57,把母式化为合取范式任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。(7)消去全称量词所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。,(6)(x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x),(7)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x),20/57,(8)消去连词符号用A,B代替(AB)，消去符号。最后得到一个有限集，其中每个公式是文字的析取。(9)更换变量名称可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。,(8)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x),(9)P(x1)P(y)Pf(x1,y)P(x2)Qx2,g(x2)P(x3)Pg(x3),21/57,谓词归结子句形(Skolem标准形),量词消去原则：消去存在量词“”，略去全程量词“”。注意：左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；如没有，改写成为常量。,22/57,谓词归结子句形(Skolem标准形),Skolem定理：谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。SKOLEM标准形定义：消去量词后的谓词公式。注意：谓词公式G的SKOLEM标准形同G并不等值。,23/57,谓词归结子句形,子句与子句集文字：不含任何连接词的谓词公式。子句：一些文字的析取（谓词的和）。子句集S的求取：GSKOLEM标准形消去存在变量以“，”取代“”，并表示为集合形式。,24/57,谓词归结子句形,G是不可满足的S是不可满足的G与S不等价，但在不可满足的意义下是一致的。定理：若G是给定的公式，而S是相应的子句集，则G是不可满足的S是不可满足的。注意：G真不一定S真，而S真必有G真。即：S=G,25/57,谓词归结子句形,G=G1G2G3Gn的子句形G的字句集可以分解成几个单独处理。有SG=S1US2US3UUSn则SG与S1US2US3UUSn在不可满足得意义上是一致的。即SG不可满足S1US2US3UUSn不可满足,26/57,求取子句集例(1),例：对所有的x,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：P(x,y)表示x是y的父亲Q(x,y)表示x是y的祖父ANS(x)表示问题的解答,27/57,求取子句集例(2),对于第一个条件，“如果x是y的父亲，y又是z的父亲，则x是z的祖父”，一阶逻辑表达式如下：A1：(x)(y)(z)(P(x,y)P(y,z)Q(x,z)SA1：P(x,y)P(y,z)Q(x,z)对于第二个条件：“每个人都有父亲”，一阶逻辑表达式：A2：(y)(x)P(x,y)SA2：P(f(y),y)对于结论：某个人是它的祖父B：(x)(y)Q(x,y)否定后得到子句：（(x)(y)Q(x,y)）ANS(x)SB：Q(x,y)ANS(x)则得到的相应的子句集为：SA1，SA2，SB,28/57,归结原理,也叫消解原理消解反演（过程）Resolutionprinciple化为与、或、非来表示,29/57,谓词逻辑的归结原理,在谓词逻辑中，要考虑变量的约束问题，在应用归结法时，要对公式作变量置换和合一等处理，才能得到互补的基本式，以使进行归结。,归结过程：若S中两子句间有相同互补文字的谓词，但它们的项不同，则必须找出对应的不一致项；进行变量置换，使它们的对应项一致;求归结式看能否导出空子句。,30/57,归结原理,归结原理正确性的根本在于，找到矛盾可以肯定不真。方法：和命题逻辑一样。但由于有函数和量词，所以要考虑置换和合一。,31/57,置换,置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。定义：置换是形如t1/x1,t2/x2,tn/xn的有限集合。其中，x1,x2,xn是互不相同的变量，t1,t2,tn是不同于xi的项（常量、变量、函数）；ti/xi表示用ti置换xi，并且要求ti与xi不能相同，而且xi不能循环地出现在另一个ti中。例如a/x，c/y，f(b)/z是一个置换。g(y)/x，f(x)/y不是一个置换，,32/57,例如表达式Px,f(y)，B，对应于不同的变换si，可得到不同的例:置换置换的例sl=z/x,w/y，Px,f(y)，Bs1=Pz,f(w),Bs2=A/y，Px,f(y)，Bs2=Px,f(A),Bs3=g(z)/x,A/y，Px,f(y)，Bs3=Pg(z),f(A),Bs4=C/x,A/y，Px,f(y)，Bs4=PC,f(A),B,33/57,置换置换的例sl=z/x,w/y，Px,f(y)，Bs1=Pz,f(w),Bs2=A/y，Px,f(y)，Bs2=Px,f(A),Bs3=g(z)/x,A/y，Px,f(y)，Bs3=Pg(z),f(A),Bs4=C/x,A/y，Px,f(y)，Bs4=PC,f(A),B,第一个例叫做原始文字的初等变式，实际上置换后只是对变量作了换名。第四个例称作基例，即置换后项中不再含有变量。用s=t1/v1,t2/v2,.,tn/vn来表示任一置换，用s对表达式E作置换后的例简记为Es。,34/57,置换集的元素ti/vi的含义是表达式中的变量vi处以项ti来替换，但不允许vi用与vi有关的项ti(vi)作置换。对表达式多次置换，如用s1，s2依次进行置换(即(Es1)s2)，可以将这两个置换合成为一个置换(记为s1s2)。,35/57,合成置换s1s2是由两部分的置换对组成:一部分仍是s1的置换对，只是s1的项被s2作了置换;另一部分是s2中与s1变量不同的那些变量对。如s1=g(x,y)/z，s2=A/x,B/y,C/w,D/zs1s2=g(A,B)/z,A/x,B/y,C/w,36/57,置换的合成,设t1/x1,t2/x2,tn/xn，u1/y1,u2/y2,un/yn，是两个置换。与的合成也是一个置换，记作。从集合t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,un/yn中删去以下两种元素：当ti=xi时，删去ti/xi(i=1,2,n);当yix1,x2,xn时，删去uj/yj(j=1,2,m)最后剩下的元素所构成的集合合成即是对ti先做置换然后再做置换，置换xi,37/57,置换的合成,例：设：f(y)/x,z/y，a/x,b/y,y/z，求与的合成。解：先求出集合f(b/y)/x,(y/z)/y,a/x,b/y,y/zf(b)/x,y/y,a/x,b/y,y/z其中，f(b)/x中的f(b)是置换作用于f(y)的结果；y/y中的y是置换作用于z的结果。在该集合中，y/y满足定义中的条件i，需要删除；a/x，b/y满足定义中的条件ii，也需要删除。最后得f(b)/x，y/z,38/57,这样的合成法可使(Es1)s2=E(s1s2)，(可结合)但置换是不可交换的即s1s2s2s1,若存在一个置换s使得表达式集Ei中每个元素经置换后的例有:E1s=E2s=E3s=，则称表达式集Ei是可合一的，这个置换s称作Ei的合一者。i2时很简单,39/57,合一,合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。定义：设有公式集FF1，F2，Fn，若存在一个置换，可使F1F2=Fn，则称是F的一个合一。同时称F1，F2，.，Fn是可合一的。例：设有公式集FP(x,y,f(y),P(a,g(x),z)，则a/x,g(a)/y,f(g(a)/z是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的。,40/57,如有子句集P(x，f(y)，B)，P(x，f(B)，B),作置换s=A/x，B/y，得P(A,f(B),B)，该子句集是可合一的。,s并不是最简单的合一者，因为s1=B/y，使子句集合一为Px，f(B)，B。要求找的是最一般或最普通的合一者(mostgeneralunifier)g，记为mgug。,41/57,任一合一者s与g之间的关系是:存在一个置换s，使得Eis=Eigs。再比较上例的两个合一者，有A/x,B/y=B/yA/x，因此mgug=B/y。mgug的置换限制最少，所产生的例更一般化，有利于归结过程的灵活使用。,42/57,例:Cl=P(x,f(A)P(x,f(y)Q(y)C2=P(z,f(A)Q(z)(1)取L11=P(x,f(A)，L21=P(z，f(A)则s=z/x使L11和L21合一，归结式为P(z，f(y)Q(y)Q(z),(2)取L11=P(x,f(y)，L21=P(z，f(A)则s=z/x，A/y，归结式为Q(A)Q(z)(3)取L11=Q(y)，L21=Q(z),则s=y/z，归结式为P(x，f(A)P(x，f(y)P(y,f(A),43/57,归结原理,归结的注意事项：谓词的一致性，P()与Q()，不可以常量的一致性，P(a,)与P(b,.)，不可以变量，P(a,.)与P(x,)，可以变量与函数，P(a,x,.)与P(x,f(x),)，不可以；是不能同时消去两个互补对，PQ与PQ的空，不可以先进行内部简化（置换、合并）,44/57,归结原理,归结的过程写出谓词关系公式用反演法写出谓词表达式SKOLEM标准形子句集S对S中可归结的子句做归结归结式仍放入S中，反复归结过程得到空子句得证,45/57,例：已知：（1）会朗读的人是识字的，（2）海豚都不识字，（3）有些海豚是很机灵的。证明：有些很机灵的东西不会朗读。,解：把问题用谓词逻辑描述如下，已知：（1）(x)(R(x)L(x)(2)(x)(D(x)L(x)(3)(x)(D(x)I(x)求证:(x(I(x)R(x),46/57,前提化简，待证结论取反并化成子句形，求得子句集:(1)R(x)L(x)(2)D(y)L(y)(3a)D(A)(3b)I(A)(4)I(z)R(z),一个可行的证明过程:(5)R(A)(3b)和(4)的归结式(6)L(A)(5)和(1)的归结式(7)D(A)(6)和(2)的归结式(8)NIL(7)和(3a)的归结式,47/57,例题“快乐学生”问题,假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。解：先将问题用谓词表示如下：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),48/57,例题“快乐学生”问题,由R1及逻辑转换公式:PWH=（PW）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)(11)(5),49/57,归结原理,归结法的实质：归结法是仅有一条推理规则的推理方法。归结的过程是一个语义树倒塌的过程。归结法的问题子句中有等号或不等号时，完备性不成立。Herbrand定理的不