L4谓词逻辑1 离散数学

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

2、jun, sjtu,对命题的进一步分析,日常语言的陈述句包含主语和谓语. 例如:“亚里士多德是人”,主语(“亚里士多德”)是述说的对象,谓语(“是人”)描述主语的属性或关系. 谓词逻辑用个体词描述对象,用谓词表达谓语:如man(aristotle), man(plato). 又如:“人是动物”,主语“人”就不适合看成个体了,因为“人”是类概念. 适合理解成:“对任何个体x:若x是人,则x是动物”.所以这个命题涉及两个谓词man( )和animal( )间的蕴涵.,lu chaojun, sjtu,为什么需要谓词逻辑?,可描述更丰富的推理形式. 例如下面这个推理用命题逻辑无法描述. 人皆有死.

3、a 苏格拉底是人. b 苏格拉底会死. c 用谓词逻辑可以很好地描述. 我们介绍的是一阶谓词逻辑(fol),它基本上覆盖了人们在数学和日常生活中用到的推理.,lu chaojun, sjtu,个体,个体(individual)是指独立存在的客体,可以是具体事物,也可以是抽象概念. 个体常元:确定的个体,如socrates, plato. 个体变元:不确定的个体. 所有个体构成论域(domain of discourse). 也叫个体域. 不特别指明的话,论域囊括一切事物. 当讨论真假性时,往往指明特定论域. 论域是所有个体变元的变化范围.,lu chaojun, sjtu,谓词,谓词(pred

4、icate)描述个体的属性以及个体之间的关系. 例如: 柏拉图是人. man(plato) 亚当喜欢夏娃. likes(adam,eve) a在b和c之间. between(a,b,c),lu chaojun, sjtu,谓词的变目个数,用一元谓词描述个体的属性. 如前面的man(x) 用多元谓词描述个体间的关系. 关于n个个体的谓词称为n元谓词. 如前面的二元谓词likes(x,y) 有0元谓词? 命题可视为0元谓词! 是独立于任何个体变元的陈述句. 故谓词逻辑是命题逻辑的推广.,arity/adicity nullary/medadic unary/monadic binary/dyadi

5、c ternary/triadic n-ary multary/polyadic,lu chaojun, sjtu,谓词是命题函数,一元谓词p可视为从个体域d到集合1,0上的映射: p: d 1,0 n元谓词也是一样: p: dn 1,0 注意:p(x)是命题形式但不是命题,因为其真值不确定. 仅当x取定为个体常元时, p(x)才成为命题.,lu chaojun, sjtu,个体函数,个体函数是将个体映射到个体的函数 f : dn d 不同于谓词(将个体映射到真假值). 个体函数可当作个体使用,但不能单独使用 例如:若函数father(x)表示x的父亲,谓词p(x)表示x是教师,则p(fath

6、er(x)就表示x的父亲是教师.,lu chaojun, sjtu,量词,量词(quantifier)用来对论域中参与判断的个体数量进行约束. 常用两个量词 (全称量词):表示所有个体都参与判断 (存在量词):表示存在某个个体参与判断,lu chaojun, sjtu,12,全称量词,全称量词表达“对所有个体都.” “所有”是对个体数量的一种约束.与此同义的还有“凡是” ,“一切”, “任一”, “每个”等. 基本形式为 (x) p(x) (x) p(x)为真 iff 对论域中所有个体x, p(x)都为真 p也可以是n元谓词,如 (x) p(x , y , z) 量词(x)后面也可以是任意公式

7、(见后),lu chaojun, sjtu,13,存在量词,存在量词表达“存在个体使得”. “存在”也是对个体数量的一种约束,即至少有一个.与此同义的还有“有” ,“某个”, “某些”等. 基本形式为 (x) p(x) (x) p(x)为真 iff 论域中至少存在一个个体x0使p(x0)为真 p也可以是n元谓词,如 (x)p(x , y , z) 量词(x)后面可以是任意公式(见后),有限论域下的量词,此前我们约定论域是包含一切事物的集合.论域的无限性给公式真值的讨论带来了复杂性. 若论域是有限的,假设用1,2,k表示.则 (x)p(x) = p(1) p(2) p(k) (x)p(x) =

8、p(1) p(2) p(k) 谓词公式转化成了命题公式,lu chaojun, sjtu,14,lu chaojun, sjtu,主要内容,谓词与量词 谓词公式 等值演算 范式 谓词逻辑推理 归结法推理,lu chaojun, sjtu,16,一阶谓词逻辑,一阶(first-order)谓词逻辑:量词仅作用于个体变元. 简称一阶逻辑,记作fol 意即:一阶逻辑只研究刻画个体的谓词,而二阶逻辑则可刻画谓词的谓词.,符号约定 个体常元: a,b,c, 个体变元: x,y,z, 命题变元: p,q,r, 函数: f,g,h, 谓词: p,q,r, 量词: , 联结词: , 辅助符号: “(”, “)

9、”,“,”,项,谓词逻辑的项递归定义如下: (1)个体常元和个体变元是项; (2)若f是n元个体函数,t1,tn是n个项,则f(t1,tn)是项; (3)所有项都是通过有限次使用(1)(2)而生成.,lu chaojun, 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都是通

10、过有限次使用(1)(2)(3)而生成. 注 wff简称公式. 常用符号a, b, c,表示公式.这是元语言符号! 约定公式的最外层括号省略.,lu chaojun, 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),约束变元和自由变元,一公式中形如(x)a或(x)a的部分称为对x的约束部分(这里a是公式部分),称a为量词的辖域,称x为约束变元,称 x在(x)a或(x)a中的出现为约束出现. 若x在公式中的某个出现不处于x或x的辖域中,则称x的这个出现

11、为自由出现,x是自由变元. 没有自由变元的公式称为闭公式.,lu chaojun, sjtu,20,约束变元和自由变元(续),在公式中x可能出现多次,可能既有约束出现又有自由出现. 例如: (x)p(x)q(x)中,变元x的前两个出现是约束出现,第三个出现是自由出现. 约束变元的名字不重要(后文有约束变元更名规则).因此上面的公式与(y)p(y)q(x)等值. 包含自由变元的公式一般不能计算出真值,必须对自由变元作出解释(赋值)后才可.而约束变元则无需解释.,lu chaojun, sjtu,22,自然语句表示为谓词公式,使用fol表示自然语句,首先分解出谓词, 进而使用量词、函数、联结词来构

12、成合式公式.,lu chaojun, 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) 注:公式的真假依赖于论域.,lu chaojun, sjtu,24,例:自然语句形式表示(续),(4)设论域是自然数集:令eq(x,y)表示=,s(x)表示x的后继x+1,p(x)表示x的前驱x-1. i.对

13、每个数,有且仅有一个后继 (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),lu chaojun, sjtu,25,例:自然语句形式表示(续),(5)积木世界的形式描述 桌上有三块积木a,b,c.其相对位置可描述为: on(c,a) ontable(a) ontable(b) clear(c) clear(b) 则“若x上方空,则不存在y在x上”可表示为 (x)(clear

14、(x) (y)on(y,x),lu chaojun, sjtu,26,例:自然语句形式表示(续),(6) “函数f (x)在a,b上的点x0处连续”的-定义. ()( 0 ( )( 0 (x)( |x - x0 | |f (x) f (x0)| ),lu chaojun, 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) 人人都有所爱之人 有人被人人爱

15、 (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) 某人爱某人 = 某人被某人爱,lu chaojun, sjtu,28,谓词公式的解释,谓词公式的真假与论域、自由个体变元、命题变元、谓词和函数有关. 对谓词公式的解释i包括五个部分: 非空论域d 对命题变元指派为0,1 对个体常元和(自由)个体变元指派为d中元素 对谓词指派为d上的谓词(关系) 对函数指派为d上的函数 公式a在解释i下是一个命题ai,即有确定的真值.称ai的真值为a在解释i下的真值.,

16、lu chaojun, sjtu,29,例:谓词公式的解释,考虑对(x) (p(x) q(f (x),a)的解释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下为真.,lu chaojun, sjtu,谓词公式的分类,谓词逻辑的公式按真假性分为三类 永真式(重言式,普遍有效式) 永假式(矛盾式,不可满足式) 可满足式,lu chaojun, sjtu,31,普遍有效式,如果一个公式在任一解释下都为真,则称为普遍有效的(universally valid). 普遍有效公式反映了一般逻辑规律. 例如: (x)(p(x) p(x) (x)p(x) p(