L4谓词逻辑1 离散数学

1、整理课件谓词逻辑一整理课件主要内容 谓词与量词 谓词公式 等值演算 范式 谓词逻辑推理 归结法推理整理课件谓词逻辑与命题逻辑的区别 命题逻辑:简单命题是分析的基本单元,不再对简单命题的内部结构进行分析. 例如a:“柏拉图是人”和b:“亚里士多德是人”是两个相互独立的命题,看不出a和b有什么联系. 谓词逻辑谓词逻辑(predicate logic):深入到简单命题的内部进行更精细的分析,即其主谓结构. 例如用谓词Man(x)表示“x是人”,则上述命题a和b可表示为Man(Plato)和Man(Aristotle).这样能看出两命题有联系.整理课件对命题的进一步分析 日常语言的陈述句包含主语和谓语

2、. 例如:“亚里士多德是人”,主语(“亚里士多德”)是述说的对象,谓语(“是人”)描述主语的属性或关系.谓词逻辑用个体词描述对象,用谓词表达谓语:如Man(Aristotle), Man(Plato). 又如:“人是动物”,主语“人”就不适合看成个体了,因为“人”是类概念.适合理解成:“对任何个体x:若x是人,则x是动物”.所以这个命题涉及两个谓词Man( )和Animal( )间的蕴涵.整理课件为什么需要谓词逻辑? 可描述更丰富的推理形式. 例如下面这个推理用命题逻辑无法描述. 人皆有死.a 苏格拉底是人.b苏格拉底会死.c 用谓词逻辑可以很好地描述. 我们介绍的是一阶谓词逻辑(FOL),它

3、基本上覆盖了人们在数学和日常生活中用到的推理.整理课件个体 个体个体(individual)是指独立存在的客体,可以是具体事物,也可以是抽象概念. 个体常元:确定的个体,如Socrates, Plato. 个体变元:不确定的个体. 所有个体构成论域论域(domain of discourse). 也叫个体域个体域. 不特别指明的话,论域囊括一切事物.当讨论真假性时,往往指明特定论域. 论域是所有个体变元的变化范围.整理课件谓词 谓词谓词(predicate)描述个体的属性以及个体之间的关系. 例如:柏拉图是人是人. Man(Plato)亚当喜欢喜欢夏娃. Likes(Adam,Eve)A在在B

4、和C之间之间. Between(A,B,C)整理课件谓词的变目个数 用一元谓词描述个体的属性. 如前面的Man(x) 用多元谓词描述个体间的关系. 关于n个个体的谓词称为n元谓词. 如前面的二元谓词Likes(x,y) 有0元谓词? 命题可视为0元谓词!是独立于任何个体变元的陈述句. 故谓词逻辑是命题逻辑的推广.Arity/Adicitynullary/medadicunary/monadicbinary/dyadicternary/triadicn-arymultary/polyadic整理课件谓词是命题函数 一元谓词P可视为从个体域D到集合1,0上的映射:P: D 1,0 n元谓词也是一样

5、:P: Dn 1,0 注意:P(x)是命题形式但不是命题,因为其真值不确定. 仅当x取定为个体常元时, P(x)才成为命题.整理课件个体函数 个体函数个体函数是将个体映射到个体的函数 f : Dn D 不同于谓词(将个体映射到真假值). 个体函数可当作个体使用,但不能单独使用 例如:若函数father(x)表示x的父亲,谓词P(x)表示x是教师,则P(father(x)就表示x的父亲是教师.整理课件量词 量词量词(quantifier)用来对论域中参与判断的个体数量进行约束. 常用两个量词 (全称量词全称量词):表示所有个体都参与判断 (存在量词存在量词):表示存在某个个体参与判断整理课件12

6、全称量词 全称量词表达“对所有个体都.” “所有”是对个体数量的一种约束.与此同义的还有“凡是” ,“一切”, “任一”, “每个”等. 基本形式为(x) P(x) (x) P(x)为真 iff 对论域中所有个体x, P(x)都为真 P也可以是n元谓词,如 (x) P(x , y , z) 量词(x)后面也可以是任意公式(见后)整理课件13存在量词 存在量词表达“存在个体使得”. “存在”也是对个体数量的一种约束,即至少有一个.与此同义的还有“有” ,“某个”, “某些”等. 基本形式为(x) P(x) (x) P(x)为真 iff 论域中至少存在一个个体x0使P(x0)为真 P也可以是n元谓

7、词,如 (x)P(x , y , z) 量词(x)后面可以是任意公式(见后)有限论域下的量词 此前我们约定论域是包含一切事物的集合.论域的无限性给公式真值的讨论带来了复杂性. 若论域是有限的,假设用1,2,k表示.则(x)P(x) = P(1) P(2) P(k)(x)P(x) = P(1) P(2) P(k) 谓词公式转化成了命题公式Lu Chaojun, SJTU 14Lu Chaojun, SJTU 主要内容谓词与量词 谓词公式 等值演算 范式 谓词逻辑推理 归结法推理整理课件16一阶谓词逻辑 一阶一阶(first-order)谓词谓词逻辑逻辑:量词仅作用于个体变元. 简称一阶逻辑,记作

8、FOL 意即:一阶逻辑只研究刻画个体的谓词,而二阶逻辑则可刻画谓词的谓词. 符号约定个体常元: a,b,c,个体变元: x,y,z,命题变元: p,q,r,函数: f,g,h,谓词: P,Q,R,量词: ,联结词: ,辅助符号: “(”, “)”,“,”项 谓词逻辑的项项递归定义如下:(1)个体常元和个体变元是项;(2)若f是n元个体函数,t1,tn是n个项,则f(t1,tn)是项;(3)所有项都是通过有限次使用(1)(2)而生成.整理课件18合式公式 谓词逻辑的wff递归定义如下:(0)命题变元是wff;(1)若P是n元谓词, t1,tn是n个项,则P(t1,tn)是wff.此类wff称为原

9、子公式;(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,表示公式.这是元语言符号! 约定公式的最外层括号省略.整理课件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)约束变元和自由变元 一公式中形如(x)A或(x)A的部分称为对x的约束部分(这里A是公式

10、部分),称A为量词的辖域辖域,称x为约束变元约束变元,称 x在(x)A或(x)A中的出现为约束出现约束出现. 若x在公式中的某个出现不处于x或x的辖域中,则称x的这个出现为自由出现自由出现,x是自由变元自由变元. 没有自由变元的公式称为闭公式闭公式.Lu Chaojun, SJTU 20约束变元和自由变元(续) 在公式中x可能出现多次,可能既有约束出现又有自由出现. 例如: (x)P(x)Q(x)中,变元x的前两个出现是约束出现,第三个出现是自由出现. 约束变元的名字不重要(后文有约束变元更名规则).因此上面的公式与(y)P(y)Q(x)等值. 包含自由变元的公式一般不能计算出真值,必须对自由

11、变元作出解释(赋值)后才可.而约束变元则无需解释.整理课件22自然语句表示为谓词公式 使用FOL表示自然语句,首先分解出谓词, 进而使用量词、函数、联结词来构成合式公式.整理课件23例:自然语句形式表示(1)所有有理数都是实数.(x)(Rational(x)Real(x)(2)有些实数是有理数.(x)(Real(x) Rational(x)(3)没有无理数是有理数./无理数都不是有理数.(x)(Irrational(x) Rational(x)(x)(Irrational(x)Rational(x)注:公式的真假依赖于论域.整理课件24例:自然语句形式表示(续)(4)设论域是自然数集:令Eq(

12、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)整理课件25例:自然语句形式表示(续)(5)积木世界的形式描述桌上有三块积木A,B,C.其相对位置可描述为:On(C,A)OnTable(A)OnTable(B)Clear(C)Clear(B)则“若x上方空,则不存在y在x上”可表示

13、为(x)(Clear(x) (y)On(y,x)整理课件26例:自然语句形式表示(续)(6) “函数f (x)在a,b上的点x0处连续”的-定义.()( 0 ( )( 0 (x)( |x - x0 | |f (x) f (x0)| )整理课件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,

14、y) (y)(x)P(x,y) 某人爱人人 人人都有人爱(x)(y)P(x,y) = (x)(y)P(x,y) = (y)(x)P(x,y) 某人爱某人 = 某人被某人爱整理课件28谓词公式的解释 谓词公式的真假与论域、自由个体变元、命题变元、谓词和函数有关. 对谓词公式的解释解释I包括五个部分: 非空论域D 对命题变元指派为0,1 对个体常元和(自由)个体变元指派为D中元素 对谓词指派为D上的谓词(关系) 对函数指派为D上的函数 公式A在解释I下是一个命题AI,即有确定的真值.称AI的真值为A在解释I下的真值.整理课件29例:谓词公式的解释考虑对(x) (P(x) Q(f (x),a)的解释

15、I:论域D指派为1,2;个体常元a指派为1;f 指派为D上函数f I: f I(1)=2, f I(2)=1.P指派为D上一元关系PI =Q指派为D上二元关系QI =,此外,若x指派为1: PI(1) QI(f I(1),1) = T 若x指派为2: PI(2) QI(f I(2),1) = T所以(x) (P(x) Q(f (x),a)在I下为真.整理课件谓词公式的分类 谓词逻辑的公式按真假性分为三类 永真式(重言式,普遍有效式) 永假式(矛盾式,不可满足式) 可满足式整理课件31普遍有效式 如果一个公式在任一解释下都为真,则称为普遍有效的普遍有效的(universally valid). 普遍有效公式反映了一般逻辑规律. 例如:(x)(P(x) P(x