资源预览内容
第1页 / 共44页
第2页 / 共44页
第3页 / 共44页
第4页 / 共44页
第5页 / 共44页
第6页 / 共44页
第7页 / 共44页
第8页 / 共44页
第9页 / 共44页
第10页 / 共44页
亲,该文档总共44页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
3.2 谓词逻辑基础,一阶逻辑 基本概念 个体词:表示主语的词 谓词:刻画个体性质或个体之间关系的词 量词:表示数量的词,小王是个工程师。 8是个自然数。 我去买花。 小丽和小华是朋友。 其中,“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词,而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质,第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系,最后一个谓词“是朋友”表示两个个体词之间的关系。,3.2 谓词逻辑基础,3.2 谓词逻辑基础,例如:(1)所有的人都是要死的。 (2) 有的人活到一百岁以上。 在个体域D为人类集合时,可符号化为: (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) ( 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标准形 前束范式 定义:说公式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定理: 谓词逻辑的任意公式都可以化为与之等价的前束范式,但其前束范式不唯一。 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(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 谓词逻辑归结原理,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的祖父。又知每个人都有父亲,试问对某个人来说谁是它的祖父? 求:用一阶逻辑表示这个问题,并建立子句集。 解:这里我们首先引入谓词: 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) 否定后得到子句: ( (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不能循环地出现在另一个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/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是可合一的。 例: 设有公式集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 谓词逻辑归结原理,归结的过程 写出谓词关系公式 用反演法写出谓词表达式 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) R3:“张不肯学习但他是幸运的” 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)(结论的否定) (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 谓词逻辑归结原理,归结过程的控制策略,要解决的问题: 归结方法的知识爆炸。 控制
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号