《谓词逻辑基础》PPT课件.ppt

《《谓词逻辑基础》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《谓词逻辑基础》PPT课件.ppt（43页珍藏版）》请在三一办公上搜索。

1、3.2 谓词逻辑基础,一阶逻辑基本概念个体词：表示主语的词谓词：刻画个体性质或个体之间关系的词量词：表示数量的词,小王是个工程师。8是个自然数。我去买花。小丽和小华是朋友。其中，“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词，而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质，第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系，最后一个谓词“是朋友”表示两个个体词之间的关系。,3.2 谓词逻辑基础,3.2 谓词逻辑基础,例如：（1）所有的人都是要死的。（2）有的人活到一百岁以上。在个体域D为人类集合时，可符号

2、化为：（1）xP(x)，其中P(x)表示x是要死的。（2）x Q(x),其中Q(x)表示x活到一百岁以上。在个体域D是全总个体域时，引入特殊谓词R(x)表示x是人，可符号化为：（1）x（R(x)P(x)）,其中，R(x)表示x是人；P(x)表示x是要死的。（2）x（R(x)Q(x)），其中，R(x)表示x是人；Q(x)表示x活到一百岁以上。,一阶逻辑公式及其解释个体常量：a,b,c个体变量：x,y,z谓词符号：P,Q,R量词符号：,3.2 谓词逻辑基础,量词否定等值式：(x）P（x）（y）P（y）(x）P（x）（y）P（y）量词分配等值式：(x）(P（x）Q（x）)(x）P（x）(x）Q（x）

3、(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）,3.2 谓词逻辑基础,量词辖域收缩与扩张等值式：(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）(Q P（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）(Q P（x）)Q(x）P（x）,3.2 谓词逻辑基础,3.2 谓词逻辑基础,SKOLEM标准

4、形前束范式定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。,3.3 谓词逻辑归结原理,即：把所有的量词都提到前面去，然后消掉所有量词(Q1x1)(Q2x2)(Qnxn)M(x1,x2,xn)约束变项换名规则：(Qx）M（x）（Qy）M（y）(Qx）M（x,z）（Qy）M（y,z）,3.3 谓词逻辑归结原理,量词消去原则：消去存在量词“”，略去全程量词“”。注意：左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；如没有，改写成为常量。,3.3 谓词逻辑归结原理,Skolem定理：谓词逻辑的任意公式都可以化为与之等

5、价的前束范式，但其前束范式不唯一。SKOLEM标准形定义：消去量词后的谓词公式。注意：谓词公式G的SKOLEM标准形同G并不等值。,3.3 谓词逻辑归结原理,例：将下式化为Skolem标准形：,(x)(y)P(a,x,y)(x)(y)Q(y,b)R(x)解：第一步，消去号，得：(x)(y)P(a,x,y)(x)(y)Q(y,b)R(x)第二步，深入到量词内部，得：(x)(y)P(a,x,y)(x)(y)Q(y,b)R(x)第三步，变元易名，得(x)(y)P(a,x,y)(u)(v)(Q(v,b)R(u)第四步，存在量词左移，直至所有的量词移到前面，(x)(y)(u)(v)(P(a,x,y)(Q

6、(v,b)R(u)由此得到前述范式,第五步，消去“”（存在量词），略去“”全称量词消去(y)，因为它左边只有(x)，所以使用x的函数f(x)代替之，这样得到：(x)(u)(v)(P(a,x,f(x)Q(v,b)R(u)消去(u)，同理使用g(x)代替之，这样得到：(x)(v)(P(a,x,f(x)Q(v,b)R(g(x)则，略去全称变量，原式的Skolem标准形为：P(a,x,f(x)Q(v,b)R(g(x),子句与子句集文字：不含任何连接词的谓词公式。子句：一些文字的析取（谓词的和）。子句集S的求取：G SKOLEM标准形 消去存在变量 以“，”取代“”，并表示为集合形式。,3.3 谓词逻辑

7、归结原理,G是不可满足的 S是不可满足的G与S不等价，但在不可满足得意义下是一致的。定理：若G是给定的公式，而S是相应的子句集，则G是不可满足的 S是不可满足的。注意：G真不一定S真，而S真必有G真。即：S=G,3.3 谓词逻辑归结原理,G=G1 G2 G3 Gn 的子句形G的字句集可以分解成几个单独处理。有 SG=S1 U S2 U S3 U U Sn则SG 与 S1 U S2 U S3 U U Sn在不可满足得意义上是一致的。即SG 不可满足 S1 U S2 U S3 U U Sn不可满足,3.3 谓词逻辑归结原理,例：对所有的x,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖

8、父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：P(x,y)表示x是y的父亲Q(x,y)表示x是y的祖父ANS(x)表示问题的解答,3.3 谓词逻辑归结原理,对于第一个条件，“如果x是y 的父亲，y又是z 的父亲，则x是z 的祖父”，一阶逻辑表达式如下：A1：(x)(y)(z)(P(x,y)P(y,z)Q(x,z)S A1：P(x,y)P(y,z)Q(x,z)对于第二个条件：“每个人都有父亲”，一阶逻辑表达式：A2：(y)(x)P(x,y)S A2：P(f(y),y)对于结论：某个人是它的祖父B：(x)(y)Q(x,y)

9、否定后得到子句：（(x)(y)Q(x,y)）ANS(x)SB：Q(x,y)ANS(x)则得到的相应的子句集为：S A1，S A2，SB,3.3 谓词逻辑归结原理,归结原理正确性的根本在于，找到矛盾可以肯定不真。方法：和命题逻辑一样。但由于有函数，所以要考虑合一和置换。,3.3 谓词逻辑归结原理,置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。定义：置换是形如t1/x1,t2/x2,tn/xn的有限集合。其中，x1,x2,xn是互不相同的变量，t1,t2,tn是不同于xi的项（常量、变量、函数）；ti/xi表示用ti置换xi，并且要求ti与xi不能相同，而且xi不能循环地出现在另一个

10、ti中。例如a/x，c/y，f(b)/z是一个置换。g(y)/x，f(x)/y不是一个置换，,3.3 谓词逻辑归结原理,置换,置换的合成,设t1/x1,t2/x2,tn/xn，u1/y1,u2/y2,un/yn，是两个置换。则与的合成也是一个置换，记作。它是从集合t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,un/yn 中删去以下两种元素：i.当ti=xi时，删去ti/xi(i=1,2,n);Ii.当yix1,x2,xn时，删去uj/yj(j=1,2,m)最后剩下的元素所构成的集合。合成即是对ti先做置换然后再做置换，置换xi,3.3 谓词逻辑归结原理,例：设：f(y)/x,z/

11、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,3.3 谓词逻辑归结原理,合一,合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。定义：设有公式集FF1，F2，Fn，若存在一个置换，可使F1F2=Fn，则称是F的一个合一。同时称F1，F2，.，Fn是可合一的。例：

12、设有公式集FP(x,y,f(y),P(a,g(x),z)，则a/x,g(a)/y,f(g(a)/z是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的。,3.3 谓词逻辑归结原理,3.3 谓词逻辑归结原理,3.3 谓词逻辑归结原理,3.3 谓词逻辑归结原理,归结原理,归结的注意事项：谓词的一致性，P()与Q()，不可以常量的一致性，P(a,)与P(b,.)，不可以 变量，P(a,.)与P(x,)，可以变量与函数，P(a,x,.)与P(x,f(x),)，不可以；是不能同时消去两个互补对，PQ与PQ的空，不可以先进行内部简化（置换、合并）,3.3 谓词逻辑归结原理,归结的过程写出谓词关系公式

13、 用反演法写出谓词表达式 SKOLEM标准形 子句集S 对S中可归结的子句做归结 归结式仍放入S中，反复归结过程 得到空子句 得证,3.3 谓词逻辑归结原理,例题“快乐学生”问题,假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。解：先将问题用谓词表示如下：R1:“任何通过计算机考试并获奖的人都是快乐的”(x)(Pass(x,computer)Win(x,prize)Happy(x)R2:“任何肯学习或幸运的人都可以通过所有考试”(x)(y)(Study(x)Lucky(x)Pass(x,y)R

14、3:“张不肯学习但他是幸运的”Study(zhang)Lucky(zhang)R4:“任何幸运的人都能获奖”(x)(Luck(x)Win(x,prize)结论：“张是快乐的”的否定Happy(zhang),例题“快乐学生”问题,由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)

15、（结论的否定）(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),归结法的实质：归结法是仅有一条推理规则的推理方法。归结的过程是一个语义树倒塌的过程。归结法的问题子句中有等号或不等号时，完备性不成立。Herbrand定理的不实用性引出了可实用的归结法。,3.3 谓词逻辑归结原理,归结过程的控制策略

16、,要解决的问题：归结方法的知识爆炸。控制策略的目的归结点尽量少控制策略的原则给出控制策略，以使仅对选择合适的子句间方可做归结。避免多余的、不必要的归结式出现。或者说，少做些归结仍能导出空子句。,3.3 谓词逻辑归结原理,删除策略=完备名词解释：归类：设有两个子句C和D，若有置换使得C D成立，则称子句C把子句D归类。由于小的可以代表大的，所以小的吃掉大的了。若对S使用归结推理过程中，当归结式Cj是重言式（永真式）和Cj被S中子句和子句集的归结式Ci(ij)所归类时，便将Cj删除。这样的推理过程便称做使用了删除策略的归结过程。,3.3 谓词逻辑归结原理,主要思想：归结过程在寻找可归结子句时，子句

17、集中的子句越多，需要付出的代价就会越大。如果在归结时能把子句集中无用的子句删除掉，就会缩小搜索范围，减少比较次数，从而提高归结效率。删除策略对阻止不必要的归结式的产生来缩短归结过程是有效的。然而要在归结式Cj产生后方能判别它是否可被删除，这部分计算量是要花费的，只是节省了被删除的子句又生成的归结式。尽管使用删除策略的归结，少做了归结但不影响产生空子句，就是说删除策略的归结推理是完备的。,3.3 谓词逻辑归结原理,采用支撑集完备 支撑集：设有不可满足子句集S的子集T，如果S-T是可满足的，则T是支持集。采用支撑集策略时，从开始到得到的整个归结过程中，只选取不同时属于S-T的子句，在其间进行归结。

18、就是说，至少有一个子句来自于支撑集T或由T导出的归结式。,3.3 谓词逻辑归结原理,例如：A1A2A3B中的B可以作为支撑集使用。要求每一次参加归结的亲本子句中，只要应该有一个是有目标公式的否定（B）所得到的子句或者它们的后裔。支撑集策略的归结是完备的，同样，所有可归结的谓词公式都可以用采用支撑集策略达到加快归结速度的目的。问题是如何寻找合适的支撑集。一个最容易找到的支撑集是目标子句的非，即SB。,3.3 谓词逻辑归结原理,3.3 谓词逻辑归结原理,语义归结完备 语义归结策略是将子句S按照一定的语义分成两部分，约定每部分内的子句间不允许作归结。同时还引入了文字次序，约定归结时其中的一个子句的被

19、归结文字只能是该子句中“最大”的文字。语义归结策略的归结是完备的，同样，所有可归结的谓词公式都可以用采用语义归结策略达到加快归结速度的目的。问题是如何寻找合适的语义分类方法，并根据其含义将子句集两个部分中的子句进行排序。,3.3 谓词逻辑归结原理,线性归结 完备 线性归结策略首先从子句集中选取一个称作顶子句的子句C0开始作归结。归结过程中所得到的归结式Ci立即同另一子句Bi进行归结得归结式Ci+1。而Bi属于S或是已出现的归结式Cj(ji)。即，如下图所示归结得到的新子句立即参加归结。线性归结是完备的，同样，所有可归结的谓词公式都可以采用线性归结策略达到加快归结速度的目的。如果能搞找到一个较好

20、的顶子句，可以式归结顺利进行。否则也可能事与愿违。,3.3 谓词逻辑归结原理,3.3 谓词逻辑归结原理,单元归结=完备 单元归结策略要求在归结过程中，每次归结都有一个子句是单元子句（只含一个文字的子句）或单元因子。显而易见，词中方法可以简单地削去另一个非单子句中的一个因子，使其长度减少，构成简单化，归结效率较高。初始子句集中没有单元子句时，单元归结策略无效。所以说“反之不成立”，即此问题不能采用单元归结策略。,3.3 谓词逻辑归结原理,输入归结=完备 与单元归结策略相似，输入归结策略要求在归结过程中，每一次归结的两个子句中必须有一个是S的原始子句。这样可以避免归结出的不必要的新子句加入归结，造成恶性循环。可以减少不必要的归结次数。,3.3 谓词逻辑归结原理,如同单元归结策略，不是所有的可归结谓词公式的最后结论都是可以从原始子句集中的得到的。简单的例子，归结结束时，即最后一个归结式为空子句的条件是，参加归结的双方必须是两个单元子句。原始子句集中没有单元子句的谓词公式一定不能采用输入归结策略。,3.3 谓词逻辑归结原理,