L4谓词逻辑1 离散数学ppt课件

,谓词逻辑,一,1,LuChaojun,SJTU,2,LuChaojun,SJTU,主要内容,谓词与量词谓词公式等值演算范式谓词逻辑推理归结法推理,LuChaojun,SJTU,3,LuChaojun,SJTU,谓词逻辑与命题逻辑的区别,命题逻辑:简单命题是分析的基本单元,不再对简单命题的内部结构进行分析.例如a:“柏拉图是人”和b:“亚里士多德是人”是两个相互独立的命题,看不出a和b有什么联系.谓词逻辑(predicatelogic):深入到简单命题的内部进行更精细的分析,即其主谓结构.例如用谓词Man(x)表示“x是人”,则上述命题a和b可表示为Man(Plato)和Man(Aristotle).这样能看出两命题有联系.,LuChaojun,SJTU,4,LuChaojun,SJTU,对命题的进一步分析,日常语言的陈述句包含主语和谓语.例如:“亚里士多德是人”,主语(“亚里士多德”)是述说的对象,谓语(“是人”)描述主语的属性或关系.谓词逻辑用个体词描述对象,用谓词表达谓语:如Man(Aristotle),Man(Plato).又如:“人是动物”,主语“人”就不适合看成个体了,因为“人”是类概念.适合理解成:“对任何个体x:若x是人,则x是动物”.所以这个命题涉及两个谓词Man()和Animal()间的蕴涵.,LuChaojun,SJTU,5,LuChaojun,SJTU,为什么需要谓词逻辑?,可描述更丰富的推理形式.例如下面这个推理用命题逻辑无法描述.人皆有死.a苏格拉底是人.b苏格拉底会死.c用谓词逻辑可以很好地描述.我们介绍的是一阶谓词逻辑(FOL),它基本上覆盖了人们在数学和日常生活中用到的推理.,LuChaojun,SJTU,6,LuChaojun,SJTU,个体,个体(individual)是指独立存在的客体,可以是具体事物,也可以是抽象概念.个体常元:确定的个体,如Socrates,Plato.个体变元:不确定的个体.所有个体构成论域(domainofdiscourse).也叫个体域.不特别指明的话,论域囊括一切事物.当讨论真假性时,往往指明特定论域.论域是所有个体变元的变化范围.,LuChaojun,SJTU,7,LuChaojun,SJTU,谓词,谓词(predicate)描述个体的属性以及个体之间的关系.例如:柏拉图是人.Man(Plato)亚当喜欢夏娃.Likes(Adam,Eve)A在B和C之间.Between(A,B,C),LuChaojun,SJTU,8,LuChaojun,SJTU,谓词的变目个数,用一元谓词描述个体的属性.如前面的Man(x)用多元谓词描述个体间的关系.关于n个个体的谓词称为n元谓词.如前面的二元谓词Likes(x,y)有0元谓词?命题可视为0元谓词!是独立于任何个体变元的陈述句.故谓词逻辑是命题逻辑的推广.,Arity/Adicitynullary/medadicunary/monadicbinary/dyadicternary/triadicn-arymultary/polyadic,LuChaojun,SJTU,9,LuChaojun,SJTU,谓词是命题函数,一元谓词P可视为从个体域D到集合1,0上的映射:P:D1,0n元谓词也是一样:P:Dn1,0注意:P(x)是命题形式但不是命题,因为其真值不确定.仅当x取定为个体常元时,P(x)才成为命题.,LuChaojun,SJTU,10,个体函数,个体函数是将个体映射到个体的函数f:DnD不同于谓词(将个体映射到真假值).个体函数可当作个体使用,但不能单独使用例如:若函数father(x)表示x的父亲,谓词P(x)表示x是教师,则P(father(x)就表示x的父亲是教师.,LuChaojun,SJTU,LuChaojun,SJTU,11,量词,量词(quantifier)用来对论域中参与判断的个体数量进行约束.常用两个量词(全称量词):表示所有个体都参与判断(存在量词):表示存在某个个体参与判断,LuChaojun,SJTU,LuChaojun,SJTU,12,全称量词,全称量词表达“对所有个体都.”“所有”是对个体数量的一种约束.与此同义的还有“凡是”,“一切”,“任一”,“每个”等.基本形式为(x)P(x)(x)P(x)为真iff对论域中所有个体x,P(x)都为真P也可以是n元谓词,如(x)P(x,y,z)量词(x)后面也可以是任意公式(见后),LuChaojun,SJTU,12,LuChaojun,SJTU,13,存在量词,存在量词表达“存在个体使得”.“存在”也是对个体数量的一种约束,即至少有一个.与此同义的还有“有”,“某个”,“某些”等.基本形式为(x)P(x)(x)P(x)为真iff论域中至少存在一个个体x0使P(x0)为真P也可以是n元谓词,如(x)P(x,y,z)量词(x)后面可以是任意公式(见后),LuChaojun,SJTU,13,LuChaojun,SJTU,14,有限论域下的量词,此前我们约定论域是包含一切事物的集合.论域的无限性给公式真值的讨论带来了复杂性.若论域是有限的,假设用1,2,k表示.则(x)P(x)=P(1)P(2)P(k)(x)P(x)=P(1)P(2)P(k)谓词公式转化成了命题公式,LuChaojun,SJTU,14,LuChaojun,SJTU,15,LuChaojun,SJTU,主要内容,谓词与量词谓词公式等值演算范式谓词逻辑推理归结法推理,LuChaojun,SJTU,16,一阶谓词逻辑,一阶(first-order)谓词逻辑:量词仅作用于个体变元.简称一阶逻辑,记作FOL意即:一阶逻辑只研究刻画个体的谓词,而二阶逻辑则可刻画谓词的谓词.,符号约定个体常元:a,b,c,个体变元:x,y,z,命题变元:p,q,r,函数:f,g,h,谓词:P,Q,R,量词:,联结词:,辅助符号:“(”,“)”,“,”,LuChaojun,SJTU,16,LuChaojun,SJTU,17,项,谓词逻辑的项递归定义如下:(1)个体常元和个体变元是项;(2)若f是n元个体函数,t1,tn是n个项,则f(t1,tn)是项;(3)所有项都是通过有限次使用(1)(2)而生成.,LuChaojun,SJTU,18,合式公式,谓词逻辑的wff递归定义如下:(0)命题变元是wff;(1)若P是n元谓词,t1,tn是n个项,则P(t1,tn)是wff.此类wff称为原子公式;(2)若A,B是wff,则(A),(AB),(AB),(AB),(AB)也是wff;(3)若A是wff,而x是A中的个体变元,则(x)A,(x)A也是wff;(4)所有wff都是通过有限次使用(1)(2)(3)而生成.注wff简称公式.常用符号A,B,C,表示公式.这是元语言符号!约定公式的最外层括号省略.,LuChaojun,SJTU,18,LuChaojun,SJTU,19,例:合式公式,合式公式:p(P(x,y)Q(x,y)(x)(P(x)Q(x)(x)(P(x)(y)Q(x,y)非合式公式(?):(x)(x)P(x)(x)P(y),LuChaojun,SJTU,19,LuChaojun,SJTU,20,约束变元和自由变元,一公式中形如(x)A或(x)A的部分称为对x的约束部分(这里A是公式部分),称A为量词的辖域,称x为约束变元,称x在(x)A或(x)A中的出现为约束出现.若x在公式中的某个出现不处于x或x的辖域中,则称x的这个出现为自由出现,x是自由变元.没有自由变元的公式称为闭公式.,LuChaojun,SJTU,20,LuChaojun,SJTU,21,约束变元和自由变元(续),在公式中x可能出现多次,可能既有约束出现又有自由出现.例如:(x)P(x)Q(x)中,变元x的前两个出现是约束出现,第三个出现是自由出现.约束变元的名字不重要(后文有约束变元更名规则).因此上面的公式与(y)P(y)Q(x)等值.包含自由变元的公式一般不能计算出真值,必须对自由变元作出解释(赋值)后才可.而约束变元则无需解释.,LuChaojun,SJTU,22,自然语句表示为谓词公式,使用FOL表示自然语句,首先分解出谓词,进而使用量词、函数、联结词来构成合式公式.,LuChaojun,SJTU,22,LuChaojun,SJTU,23,例:自然语句形式表示,(1)所有有理数都是实数.(x)(Rational(x)Real(x)(2)有些实数是有理数.(x)(Real(x)Rational(x)(3)没有无理数是有理数./无理数都不是有理数.(x)(Irrational(x)Rational(x)(x)(Irrational(x)Rational(x)注:公式的真假依赖于论域.,LuChaojun,SJTU,23,LuChaojun,SJTU,24,例:自然语句形式表示(续),(4)设论域是自然数集:令Eq(x,y)表示=,s(x)表示x的后继x+1,p(x)表示x的前驱x-1.i.对每个数,有且仅有一个后继(x)(y)(Eq(y,s(x)(z)(Eq(z,s(x)Eq(y,z)ii.没有这样的数,0是其后继(x)(Eq(0,s(x)iii.除0之外的数,有且仅有一个前驱(x)(Eq(x,0)(y)(Eq(y,p(x)(z)(Eq(z,p(x)Eq(y,z),LuChaojun,SJTU,24,LuChaojun,SJTU,25,例:自然语句形式表示(续),(5)积木世界的形式描述桌上有三块积木A,B,C.其相对位置可描述为:On(C,A)OnTable(A)OnTable(B)Clear(C)Clear(B)则“若x上方空,则不存在y在x上”可表示为(x)(Clear(x)(y)On(y,x),LuChaojun,SJTU,25,LuChaojun,SJTU,26,例:自然语句形式表示(续),(6)“函数f(x)在a,b上的点x0处连续”的-定义.()(0()(0(x)(|x-x0|f(x)f(x0)|),LuChaojun,SJTU,26,LuChaojun,SJTU,27,例:自然语句形式表示(续),(7)多次量化:如对P(x,y)有四种多次量化情形:(x)(y)P(x,y)=(x)(y)P(x,y)=(y)(x)P(x,y)人人爱人人=人人被人人爱(x)(y)P(x,y)=(x)(y)P(x,y)(y)(x)P(x,y)人人都有所爱之人有人被人人爱(x)(y)P(x,y)=(x)(y)P(x,y)(y)(x)P(x,y)某人爱人人人人都有人爱(x)(y)P(x,y)=(x)(y)P(x,y)=(y)(x)P(x,y)某人爱某人=某人被某人爱,LuChaojun,SJTU,27,LuChaojun,SJTU,28,谓词公式的解释,谓词公式的真假与论域、自由个体变元、命题变元、谓词和函数有关.对谓词公式的解释I包括五个部分:非空论域D对命题变元指派为0,1对个体常元和(自由)个体变元指派为D中元素对谓词指派为D上的谓词(关系)对函数指派为D上的函数公式A在解释I下是一个命题AI,即有确定的真值.称AI的真值为A在解释I下的真值.,LuChaojun,SJTU,28,LuChaojun,SJTU,29,例:谓词公式的解释,考虑对(x)(P(x)Q(f(x),a)的解释I:论域D指派为1,2;个体常元a指派为1;f指派为D上函数fI:fI(1)=2,fI(2)=1.P指派为D上一元关系PI=Q指派为D上二元关系QI=,此外,若x指派为1:PI(1)QI(fI(1),1)=T若x指派为2:PI(2)QI(fI(2),1)=T所以(x)(P(x)Q(f(x),a)在I下为真.,LuChaojun,SJTU,29,LuChaojun,SJTU,30,谓词公式的分类,谓词逻辑的公式按真假性分为三类永真式(重言式,普遍有效式)永假式(矛盾式,不可满足式)可满足式,LuChaojun,SJTU,LuChaojun,SJTU,31,普遍有效式,如果一个公式在任一解释下都为真,则称为普遍有效的(universallyvalid).普遍有效公式反映了一般逻辑规律.例如:(x)(P(x)P(x)(x)P(x)P(y)(x)P(x)(x)Q(x)