谓词逻辑基础精.pptx

《谓词逻辑基础精.pptx》由会员分享，可在线阅读，更多相关《谓词逻辑基础精.pptx（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、 y）(x x ）P P（x x）（y y ）P P（y y）量词分配等值式：(x x ）(P P（x x）Q Q（x x）)()(x x ）P P（x x）(x x ）Q Q（x x）(x x ）(P P（x x）Q Q（x x）)()(x x ）P P（x x）(x x ）Q Q（x x）消去量词等值式：设个体域为有穷集合（a a1 1,a,a2 2,a an n）(x x ）P P（x x）P P（a a1 1 ）P P（a a2 2 ）P P（a an n ）(x x ）P P（x x）P P（a a1 1 ）P P（a a2 2 ）P P（a an n ）3.2谓词逻辑基础第4页/共

4、43页量词辖域收缩与扩张等值式：(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Q(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Q (x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Q (x x ）(Q Q P P（x x）)Q Q (x x ）P P（x x）(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Q(x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Q (x x ）(P P（x x）Q Q)()(x x ）P P（x x）Q Q (x x ）(Q Q P P

5、（x x）)Q Q (x x ）P P（x x）3.2谓词逻辑基础第5页/共43页3.2谓词逻辑基础第6页/共43页SKOLEMSKOLEM标准形前束范式定义：说公式A A是一个前束范式，如果A A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。3.3谓词逻辑归结原理第7页/共43页即：把所有的量词都提到前面去，然后消掉所有量词(Q(Q1 1x x1 1)(Q)(Q2 2x x2 2)(Q(Qn nx xn n)M(x)M(x1 1,x,x2 2,x,xn n)约束变项换名规则：(Qx(Qx ）MM（x x）（QyQy ）MM（y y）(Qx(Qx ）MM（

6、x,zx,z）（QyQy ）MM（y,zy,z）3.3谓词逻辑归结原理第8页/共43页 量词消去原则：消去存在量词“”，略去全程量词“”。注意：左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；如没有，改写成为常量。3.3谓词逻辑归结原理第9页/共43页 SkolemSkolem定理：谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。SKOLEMSKOLEM标准形定义：消去量词后的谓词公式。注意：谓词公式G G的SKOLEMSKOLEM标准形同G G并不等值。3.3谓词逻辑归结原理第10页/共43页例：将下式化为Skolem标准形：(x)(y)P(a,x,y)(x

7、)(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)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(v,b)R(u)由此得到前述范式第11页/共43页第五步，消去“”（存在量词），略去“”全称量词消去(y)，因为它左边只有(x)，所以使用x的函数f(x)代替之，这样得到：(x)(u)(v)(P(a,x,f(x)Q(v,

8、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)第12页/共43页子句与子句集文字：不含任何连接词的谓词公式。子句：一些文字的析取（谓词的和）。子句集S S的求取：G G SKOLEM SKOLEM标准形 消去存在变量 以“，”取代“”，并表示为集合形式 。3.3谓词逻辑归结原理第13页/共43页 G是不可满足的S是不可满足的G与S不等价，但在不可满足得意义下是一致的。定理：若G是给定的公式，而S是相应的子句集，则G是不可满足的S是不可满

9、足的。注意：G真不一定S真，而S真必有G真。即：S=G3.3谓词逻辑归结原理第14页/共43页G=GG=G1 1 G G2 2 G G3 3 G Gn n的子句形G G的字句集可以分解成几个单独处理。有 S SG G=S=S1 1 U SU S2 2 U S U S3 3 U U U SU Sn n则S SG G 与 S S1 1 U SU S2 2 U S U S3 3 U U U SU Sn n在不可满足得意义上是一致的。即S SG G 不可满足 S S1 1 U SU S2 2 U S U S3 3 U U U SU Sn n不可满足3.3谓词逻辑归结原理第15页/共43页例：对所有的x

10、,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：P(x,y)表示x是y的父亲Q(x,y)表示x是y的祖父ANS(x)表示问题的解答3.3谓词逻辑归结原理第16页/共43页对于第一个条件，“如果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

11、),y)对于结论：某个人是它的祖父B：(x)(y)Q(x,y)否 定 后 得 到 子 句：（(x)(y)Q(x,y)）ANS(x)SB：Q(x,y)ANS(x)则得到的相应的子句集为：SA1，SA2，SB3.3谓词逻辑归结原理第17页/共43页归结原理正确性的根本在于，找到矛盾可以肯定不真。方法：和命题逻辑一样。但由于有函数，所以要考虑合一和置换。3.3谓词逻辑归结原理第18页/共43页置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。定义：置换是形如t1/x1,t2/x2,tn/xn的有限集合。其中，x1,x2,xn是互不相同的变量，t1,t2,tn是不同于xi的项（常量、变量、函

12、数）；ti/xi表示用ti置换xi，并且要求ti与xi不能相同，而且xi不能循环地出现在另一个ti中。例如a/x，c/y，f(b)/z是一个置换。g(y)/x，f(x)/y不是一个置换，3.3谓词逻辑归结原理置换第19页/共43页置换的合成设 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.当yi x1,x2,xn时，删去uj/yj(j=1,2,m)最后剩下的元素所

13、构成的集合。合成即是对ti先做 置换然后再做 置换，置换xi3.3谓词逻辑归结原理第20页/共43页例：设：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/z3.3谓词逻辑归结原理第21页/共43页合一合一可以简单地理解为“寻找相对变量的置换，使两个谓词

14、公式一致”。定义：设有公式集FF1，F2，Fn，若存在一个置换，可使F1 F2=Fn，则称 是F的一个合一。同时称F1，F2，.，Fn是可合一的。例：设 有 公 式 集 F P(x,y,f(y),P(a,g(x),z)，则 a/x,g(a)/y,f(g(a)/z是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的。3.3谓词逻辑归结原理第22页/共43页3.3谓词逻辑归结原理第23页/共43页3.3谓词逻辑归结原理第24页/共43页3.3谓词逻辑归结原理第25页/共43页归结原理归结的注意事项：1.1.谓词的一致性，P()P()与Q()Q()，不可以2.2.常量的一致性，P(a,P(a,

15、)与P(b,P(b,.).)，不可以 变量，P(a,P(a,.).)与P(x,P(x,)，可以3.3.变量与函数，P(a,x,P(a,x,.).)与P(x,f(x),P(x,f(x),)，不可以；4.4.是不能同时消去两个互补对，PQPQ与PPQ Q的空，不可以5.5.先进行内部简化（置换、合并）3.3谓词逻辑归结原理第26页/共43页归结的过程写出谓词关系公式 用反演法写出谓词表达式 SKOLEMSKOLEM标准形 子句集S S 对S S中可归结的子句做归结 归结式仍放入S S中，反复归结过程 得到空子句 得证3.3谓词逻辑归结原理第27页/共43页例题“快乐学生”问题假假设设任任何何通通过

16、过计计算算机机考考试试并并获获奖奖的的人人都都是是快快乐乐的的，任任何何肯肯学学习习或或幸幸运运的的人人都都可可以以通通过过所所有有的的考考试试，张张不不肯肯学学习习但但他他是是幸幸运运的的，任任何何幸幸运运的的人人都都能能获获奖奖。求证：张是快乐的。求证：张是快乐的。解：先将问题用谓词表示如下：R1:“任何通过计算机考试并获奖的人都是快乐的”(x)(Pass(x,computer)Win(x,prize)Happy(x)R2:“任何肯学习或幸运的人都可以通过所有考试”(x)(y)(Study(x)Lucky(x)Pass(x,y)R3:“张不肯学习但他是幸运的”Study(zhang)Luc

17、ky(zhang)R4:“任何幸运的人都能获奖”(x)(Luck(x)Win(x,prize)结论：“张是快乐的”的否定Happy(zhang)第28页/共43页例题“快乐学生”问题由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,comput

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

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

20、略的归结过程。3.3谓词逻辑归结原理第32页/共43页主要思想：归结过程在寻找可归结子句时，子句集中的子句越多，需要付出的代价就会越大。如果在归结时能把子句集中无用的子句删除掉，就会缩小搜索范围，减少比较次数，从而提高归结效率。删除策略对阻止不必要的归结式的产生来缩短归结过程是有效的。然而要在归结式C Cj j产生后方能判别它是否可被删除，这部分计算量是要花费的，只是节省了被删除的子句又生成的归结式。尽管使用删除策略的归结，少做了归结但不影响产生空子句，就是说删除策略的归结推理是完备的。3.3谓词逻辑归结原理第33页/共43页采用支撑集完备 支撑集：设有不可满足子句集S S的子集T T，如果S

21、-TS-T是可满足的，则T T是支持集。采用支撑集策略时，从开始到得到 的整个归结过程中，只选取不同时属于S-TS-T的子句，在其间进行归结。就是说，至少有一个子句来自于支撑集T T或由T T导出的归结式。3.3谓词逻辑归结原理第34页/共43页例如：A A1 1AA2 2AA3 3B B中的B B可以作为支撑集使用。要求每一次参加归结的亲本子句中，只要应该有一个是有目标公式的否定（B B）所得到的子句或者它们的后裔。支撑集策略的归结是完备的，同样，所有可归结的谓词公式都可以用采用支撑集策略达到加快归结速度的目的。问题是如何寻找合适的支撑集。一个最容易找到的支撑集是目标子句的非，即S SB B

22、。3.3谓词逻辑归结原理第35页/共43页ST可满足支撑集示意图3.3谓词逻辑归结原理第36页/共43页 语义归结 完备 语义归结策略是将子句S S按照一定的语义分成两部分，约定每部分内的子句间不允许作归结。同时还引入了文字次序，约定归结时其中的一个子句的被归结文字只能是该子句中“最大”的文字。语义归结策略的归结是完备的，同样，所有可归结的谓词公式都可以用采用语义归结策略达到加快归结速度的目的。问题是如何寻找合适的语义分类方法，并根据其含义将子句集两个部分中的子句进行排序。3.3谓词逻辑归结原理第37页/共43页线性归结 完备 线性归结策略首先从子句集中选取一个称作顶子句的子句C C0 0开始

23、作归结。归结过程中所得到的归结式C Ci i立即同另一子句B Bi i进行归结得归结式C Ci+1i+1。而B Bi i属于S S或是已出现的归结式C Cj j(ji)(j=完备 单元归结策略要求在归结过程中，每次归结都有一个子句是单元子句（只含一个文字的子句）或单元因子。显而易见，词中方法可以简单地削去另一个非单子句中的一个因子，使其长度减少，构成简单化，归结效率较高。初始子句集中没有单元子句时，单元归结策略无效。所以说“反之不成立”，即此问题不能采用单元归结策略。3.3谓词逻辑归结原理第40页/共43页输入归结 =完备 与单元归结策略相似，输入归结策略要求在归结过程中，每一次归结的两个子句中必须有一个是S S的原始子句。这样可以避免归结出的不必要的新子句加入归结，造成恶性循环。可以减少不必要的归结次数。3.3谓词逻辑归结原理第41页/共43页如同单元归结策略，不是所有的可归结谓词公式的最后结论都是可以从原始子句集中的得到的。简单的例子，归结结束时，即最后一个归结式为空子句的条件是，参加归结的双方必须是两个单元子句。原始子句集中没有单元子句的谓词公式一定不能采用输入归结策略。3.3谓词逻辑归结原理第42页/共43页感谢您的观看！第43页/共43页