人工智能-谓词逻辑43

谓词逻辑基础一阶逻辑基本概念个体词：表示主语的词谓词：刻画个体性质或个体之间关系的词量词：表示数量的词小王是个工程师。8是个自然数。我去买花。小丽和小华是朋友。其中，“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词，而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质，第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系，最后一个谓词“是朋友”表示两个个体词之间的关系。谓词逻辑基础谓词逻辑基础例如：（1）所有的人都是要死的。（2）有的人活到一百岁以上。在个体域D为人类集合时，可符号化为：（1）xP(x)，其中P(x)表示x是要死的。（2）xQ(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量词符号：,谓词逻辑基础量词否定等值式：～(x）P（x）=（y）～P（y）～(x）P（x）=（y）～P（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）谓词逻辑基础量词辖域收缩与扩张等值式：(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）谓词逻辑基础谓词逻辑基础SKOLEM标准形前束范式定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。谓词逻辑归结原理即：把所有的量词都提到前面去，然后消掉所有量词(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)约束变项换名规则：(Qx）M（x）=（Qy）M（y）(Qx）M（x,z）=（Qy）M（y,z）谓词逻辑归结原理量词消去原则：消去存在量词“”，略去全程量词“”。注意：左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；如没有，改写成为常量。谓词逻辑归结原理Skolem定理：谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。SKOLEM标准形定义：消去量词后的谓词公式。注意：谓词公式G的SKOLEM标准形同G并不等值。谓词逻辑归结原理例：将下式化为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(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标准形→消去存在变量→以“，”取代“∧”，并表示为集合形式。谓词逻辑归结原理G是不可满足的=S是不可满足的G与S不等价，但在不可满足得意义下是一致的。定理：若G是给定的公式，而S是相应的子句集，则G是不可满足的=S是不可满足的。注意：G真不一定S真，而S真必有G真。即：S=G谓词逻辑归结原理G=G1ΛG2ΛG3Λ…ΛGn的子句形G的字句集可以分解成几个单独处理。有SG=S1US2US3U…USn则SG与S1US2US3U…USn在不可满足得意义上是一致的。即SG不可满足=S1US2US3U…USn不可满足3.3谓词逻辑归结原理例：对所有的x,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：P(x,y)表示x是y的父亲Q(x,y)表示x是y的祖父ANS(x)表示问题的解答谓词逻辑归结原理对于第一个条件，“如果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)S～B：～Q(x,y)∨ANS(x)则得到的相应的子句集为：{SA1，SA2，S～B}谓词逻辑归结原理归结原理正确性的根本在于，找到矛盾可以肯定不真。方法：和命题逻辑一样。但由于有函数，所以要考虑合一和置换。谓词逻辑归结原理置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。定义：置换是形如{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}不是一个置换，谓词逻辑归结原理置换置换的合成设＝{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)最后剩下的元素所构成的集合。合成即是对ti先做置换然后再做置换，置换xi谓词逻辑归结原理例：设：＝{f(y)/x,z/y}，＝{a/x,b/y,y/z}，求与的合成。解：先求出集合{f(b/y)/x,(y/z)/y,a/x,b/y,y/z}＝{f(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}谓词逻辑归结原理合一合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。定义：设有公式集F＝{F1，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}是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的。谓词逻辑归结原理谓词逻辑归结原理谓词逻辑归结原理谓词逻辑归结原理归结原理归结的注意事项：1.谓词的一致性，P()与Q()，不可以2.常量的一致性，P(a,…)与P(b,….)，不可以变量，P(a,….)与P(x,…)，可以3.变量与函数，P(a,x,….)与P(x,f(x),…)，不可以；4.是不能同时消去两个互补对，P∨Q与～P∨～Q的空，不可以5.先进行内部简化（置换、合并）谓词逻辑归结原理归结的过程写出谓词关系公式→用反演法写出谓词表达式→SKOLEM标准形→子句集S→对S中可归结的子句做归结→归结式仍放入S中，反复归结过程→得到空子句▯得证谓词逻辑归结原理例题“快乐学生”问题假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。解：先将问题用谓词表示如下：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)例题“快乐学生”问题由R1及逻辑转换公式:P∧W→H=～（P∧W）∨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)归结法的实质：归结法是仅有一条推理规则的推理方法。归结的过程是一个语义树倒塌的过程。归结法的问题子句中有等号或不等号时，完备性不成立。※Herbrand定理的不实用性引出了可实用的归结法。谓词逻辑归结原理归结过程的控制策略要解决的问题：归结方法的知识爆炸。控制策略的目的归结点尽量少控制策略的原则给出控制策略，以使仅对选择合适的子句间方可做归结。避免多余的、不必要的归结式出现。或者说，少做些归结仍能导出空子句。谓词逻辑归结原理删除策略=完备名词解释：归类：设有两个子句C和D，若有置换使得CD成立，则称子句C把子句D归类。由于小的可以代表大的，所以小的吃