离散数学谓词逻辑.ppt

《离散数学谓词逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学谓词逻辑.ppt（64页珍藏版）》请在三一办公上搜索。

1、1,第二章 谓词逻辑,2,在命题逻辑中,原子命题是进行演算的基本单位,不研究命题的内部结构以及命题之间的内在联系,因而,命题逻辑中的推理有很大的局限性。例如,著名的苏格拉底三段论：所有的人都是要死的,苏格拉底是人,所以苏格拉底是要死的。符号化：分别用P、Q、R表示以上三个命题,则PQR表示这一推理过程。蕴含式PQR不是重言式,虽然凭我们的直觉这个论断正确,在内部逻辑中却无法证明。谓词逻辑的任务就是对原子命题作进一步的分析,研究其内部的逻辑结构,并在此基础上更深入地刻画推理。,3,谓词逻辑：原子命题客体词谓词命题所陈述的对象称为客体词。它可以是一个具体的事物,也可以是一个抽象的概念。例如,李明、

2、自然数、思想等都可以作为客体词。定义用来刻画客体词的性质或客体词之间的关系的词称为谓词。例如：是无理数。小李是计算机系的学生。李明比王宏高2厘米。“”、“小李”、“李明”、“王宏”都是客体词；“是无理数”“是计算机系的学生”“高2厘米”都是谓词。前两个谓词表示客体词的性质,而后一个谓词描述客体词之间的关系。,2.1谓词的概念与表示,4,谓词的表示,客体词有两种：客体常元和客体变元。客体常元表示具体的或特定的客体,一般用小写字母a、b、c等表示；表示抽象的或泛指的客体的词称为客体变元,常用小写字母x、y、z等表示。谓词,通常用大写的字母A、B、C等表示。谓词填式：单独一个谓词不是完整的命题,把谓

3、词字母后填以客体所得的式子。,5,例子,例2-1.1 张明是位大学生。解：设S(x)：x是大学生,c：张明,则原句的谓词形式为S(c)。例2-1.2我坐在张三和李四中间。解：设S(x,y,z)：x坐在y和z之间,i：我,z：张三,l：李四,则原句的谓词形式为S(i,z,l)。,一元谓词：表示客体性质,多元谓词：表示客体间关系,6,一般来说,谓词P(x1,xn)不是命题,真值无法确定,只有当n 个客体常元代替 x1,x2,xn 这n个客体变元之后,才有了确定的真值,因而也就成了命题。例如,L(x,y)是表示x小于y的二元谓词,它的真值不能确定,当以2(用a 表示)、3(用b表示)替换x和y之后,

4、L(a,b)成为真命题。,7,2.2命题函数与量词,例子：假设 谓词H表示“能够到达山顶”,客体p表示李四,q表示老虎,r表示汽车。那么 H(p),H(q),H(r)表示三个不同的命题相同点：H(x)定义 由一个谓词,一些客体变元组成的表达式称为简单命题函数。由一个或者n个简单命题函数以及逻辑联结词组合而成的表达式称为复合命题函数。,8,客体变元的取值范围称为个体域(或论述域)。个体域可以是有限客体的集合,如：a、b、c、计算机系的学生；也可以是无限客体的集合,如实数几何、自然数集合等。特别是,当没有特别声明时,可以将宇宙间的一切事物和概念构成的集合作为个体域,称为全总个体域。,9,量 词 1

5、.所有的人都是要死的。2.有些人是要死的。这两个命题中的客体词和谓语均相同,区别在于“所有的”和“有些”这两个表示数量的词。表示数量的词在谓词逻辑中称为量词,量词包括全称量词和存在量词两种。全称量词对应日常语言中的“一切”、“所有的”、“任意的”等词,表示对个体域的所有客体,用符号“”表示。存在量词对应对应日常语言中的“存在着”、“至少有一个”、“有些”等词,表示存在着个体域的客体,用符号“”表示.,10,例如：xF(x)表示个体域中的所有客体都有性质F；xF(x)表示存在着个体域中的客体具有性质F。当个体域有限时,设个体域为a1,a2,an,则 x F(x)F(a1)F(a2)F(an)x

6、F(x)F(a1)F(a2)F(an),11,符号化:谓词F(x)表示是要死的。当个体域为人类集合时,上述两命题可分别符号化为 x F(x)x F(x)。(所有的人都是要死的。有些人是要死的。)引入新的谓词M(x),将人类分离出来。在全总个体域下,以上两命题可分别叙述为：x(M(x)F(x)x(M(x)F(x)从以上两命题的符号化可以看出,同一命题在不同个体域下符号化的形式可能不同。,12,这里,M(x)称为特性谓词。应该注意的是,全称量词和存在量词符号化时,引入特性谓词时的形式是不同的。用全称量词 符号化时,特性谓词作为条件式的前件；用存在量词符号化时则作为合取式的一项。,13,对于任一给定

7、的实数x,都存在着一个实数y,使得x+y=0。如果取个体域为实数集合 x y H(x,y)然而 y x H(x,y)：存在着一个少数y,对于任一实数x,使得x+y=0 由此可见,量词出现的不同顺序表达了不同的含义,量词的顺序不能随意颠倒。我们约定,量词按从左到右的顺序读出。,14,练习,Page59(1)c.g.Page60(2)a.i.,15,2.3谓词公式与翻译,1.谓词公式 为了使命题的符号化更准确和规范,以及正确进行谓词演算和推理,我们介绍谓词演算合式公式的概念。定义 2.3.1 设R(x1,x2,xn)是n元谓词,其中x1,x2,xn 是客体变元,则R(x1,x2,xn)称为谓词演算

8、的原子公式。,16,定义2.3.2 谓词演算的合式公式定义如下：(1)原子公式是合式公式；(2)若A是合式公式,则(A)是合式公式；(3)若A、B是合式公式,则(AB)、(AB)、(AB)、(AB)是合式公式；(4)若A是合式公式,则(x)A、(x)A是合式公式；(5)只要有限次地应用(1)(4)构成的符号串才是合式公式。谓语演算的合适公式简称为谓词公式。与命题公式类似,谓词公式最外层的括号也可以省略。,17,例 1 在谓词逻辑中将下列命题符号化。(1)没有不死的人。(2)不存在最小数。(3)教育技术系的学生都学离散数学。解 题目中没有指定个体域,取个体域为全总个体域。(1)假设,M(x)：x

9、是人,F(x)：x是要死的，那么x(M(x)F(x)(2)假设,N(x)：x是数,L(x,y)：x小于y，那么x(N(x)y(N(y)L(x,y)(3)假设,S(x)：x是教育技术系的学生,F(x)：x要学离散数学，那么(x)(S(x)F(x)本题也可以引入二元谓词G(x,y)：x是学习y,以及客体常元a：离散数学,进行如下符号化：(x)(S(x)G(x,a),18,练习,Page62(1)a.c.e.Page62(2),A:5是质数。C:对所有的x,若x被2除尽,则x是偶数.E:对所有的x,若x不是偶数,则x不能被2除尽.,19,2.4变元的约束,定义 2.4.1 在谓词公式(x)A(x)和

10、(x)A(x),x 称为量词的指导变元或作用变元,A(x)称为量词的辖域或作用域。辖域中x的所有出现称为约束出现,也称x受相应量词指导变元的约束,A(x)中不是约束出现的其他变元的出现成为自由出现(也称自由变元、参数)。,20,例1 指出下列谓词公式中各量词的指导变元、辖域以及客体变元的出现情况。(1)(x)P(x)P(y)(2)(x)(P(x)Q(x)(x)R(x)(3)(x)(P(x,y)(x)Q(x)(y)R(y,s)解(1)在(x)P(x)中,(x)的辖域是P(x),指导变元是x。整个公式中,x是约束出现,受(x)的约束,y是自由出现。(2)在(x)(P(x)Q(x)中(x)的指导变元

11、是x,辖域是P(x)Q(x),x是约束出现,受(x)的约束。(x)R(x)中(x)的指导变元是x,辖域是R(x),x是约束出现,受(x)的约束。整个公式中,x是约束出现。,21,(3)(x)(P(x,y)(x)Q(x)(y)R(y,s)(x)Q(x)中的指导变元是x,辖域是Q(x),x的出现是约束出现；(x)(P(x,y)(x)Q(x)中的辖域是P(x,y)(x)Q(x),指导变元是x,x的第2个是约束出现,但受x的约束,y自由出现；yR(y,s)中的指导变元是y,辖域是R(y,s),y的出现是约束出现,s自由出现；整个公式中,x约束出现,y既有自由出现又有约束出现,s自由出现。,22,从前面

12、的讨论可以看出,一个谓词公式中,有的客体变元既有自由出现又有约束出现(从例2中的(3)、(4)式的y),这样就容易引起概念上的混乱。为了避免这种混乱可以采用如下的两条规则：约束变元的改名规则 将量词辖域中出现的某个约束变元及相应的指导变元换成一个辖域中未曾出现过的客体变元名,公式的其余部分不变。,23,自由变元的代入规则 对某个自由出现的客体变元,用与原公式中所有变元名不同的变元名每一处代入。这两条规则之所以正确,是由于在构造一个公式时,变元的名称是无关紧要的。例如,我们想将如下如下命题符号化：所有的人都是要死的。设当前的个体域是人类集合,如果用P(x)表示x是要死的,则命题可符号化为(x)P

13、(x);如果用P(y)表示y是要死的,则(y)P(y)同样表达该命题。P(x)和P(y)在表达“是要死的”这个意义上是相同的,变量的名称无关紧要。,24,例3 对例2中的公式实施改名或代入规则。(1)xP(x)P(y)显然没有必要进行改名或代入。(2)对xR(x)实施改名规则,得xR(y),这样原公式就化为x(P(x)Q(x)yR(y)(3)对(x)Q(x)中x的约束出现实施改名规则,得()Q(),同时对(y)R(y,s)实施改名规则,得(t)R(t,s),这时原公式化为(x)P(x,y)()Q()(t)R(t,s),25,2.5 谓词演算的等价式与蕴含式,一个谓词公式中一般有客体常元、客体变

14、元以及命题变元等,对各种变元指定特定的常元代替,就构成了对公式的解释(赋值)，即可以判断其逻辑真值T或F。定义2.5.1 一个解释(赋值)I由下面几部分构成：(1)非空个体域D；(2)D中一部分特定元素；(3)D上一些特定谓词。,用一个解释I解释一个谓词公式A包括：将I的个体域D作为A的个体域,A中的客体常元用I中的特定元素代替,谓词用I上的特定谓词代替。,26,例1 给定解释I1如下：(1)个体域为自然数集合N；(2)N中的特定元素a=0；（3）F(x,y):x大于或等于y.在解释I1下,求下列各式的真值：(1)(x)F(x,a)；(2)(xy)F(x,y)解 在解释I1下,公式分别解释为：

15、,(1)任何自然数都大于或等于零,为真命题.(2)对任一自然数x,都存在一自然数y使得xy,为真命题.,27,例2 考虑以下解释I2：(1)个体域D=0,1；(2)D中的特定元素a=0；(3)D上的特定谓词P：,在解释I2下,下列那些公式为真？那些为假？(1)(x)(y)P(x,y)(2)(x)(y)(P(x,y)P(y,x)(3)(x)P(x,a)解 在解释I2下,原公式分别化为：(1)(x)(y)P(x,y)(y)P(0,y)(y)P(1,y)(P(0,0)P(0,1)(P(1,0)P(1,1)(FT)(T F)(TT)T,28,(2)(xy)(P(x,y)P(y,x)(P(0,0)P(0

16、,0)(P(0,1)P(1,0)(P(1,0)P(0,1)(P(1,1)P(1,1)(F F)(T T)(T T)(F F)T T T T T(3)(x)P(x,a)P(0,0)P(1,0)FT F,29,从上述两个例子可以看出，有的公式在具体解释下真值确定，是命题。但是，如果公式不含自由变元，由于每个客体变元都受量词的约束,因而在具体解释下总表达一个意义确定的语句，即一个真命题或假命题。例2中的(1)(3)都是，它们在各种解释下均是命题。,30,定义2.5.2 设A为一谓词公式,如果A在任何解释下都是真的,则称A是重言式(永真式)；如果A在任何解释下都是假的,则称A是矛盾式(永假式)；若至少

17、存在一种解为真,则称A是可满足式。由定义可知,重言式也称可满足式。定义2.5.3 设A、B是两个谓词公式,若AB是永真式,则称A和B等价或A等价于B,记作AB,这个式子称为等价式。定义2.5.4 设A、B为两个谓词公式,若AB是永真式,则称A蕴含B,记作AB。,31,等价式和永真蕴含式 首先,命题演算的永真式也是谓词演算的永真式。例如:x(P(x)Q(x)x(P(x)Q(x)(蕴含表达式)(xP(x)yQ(y)xP(x)yQ(y)(德.摩根定律)xP(x)(xP(x)yQ(y)yQ(y)(假言推理),32,特有的等价式和永真蕴含式(1)对的永真蕴含关系 xP(x)xP(x)(对的永真蕴含式)这

18、个式子显然成立。因为“对个体域中的任何客体P(x)成立”当然能推出“存在个体域中的某个使P(x)成立”。(2)量词的否定(量词的转化律)xP(x)x P(x)x P(x)x P(x)这里约定,出现在量词前面的否定,不是否定该量词本身,而是否定被量化了的整个公式。,？,33,有限个体域上证明 设个体域为a1,a2,an,则 xP(x)(P(a1)P(a2)P(an)P(a1)P(a2)P(an)xP(x)xP(x)(P(a1)P(a2)P(an)P(a1)P(a2)P(an)(x)P(x),34,(3)量词辖域的扩张与收缩 xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(

19、A(x)B)xA(x)Bx(A(x)B),xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)BxA(x)x(BA(x)BxA(x)x(BA(x),35,例3 证明xA(x)B x(A(x)B)证明：xA(x)B xA(x)B(蕴含表达式)xA(x)B(量词转化率)x(A(x)B)(量词辖域扩张)x(A(x)B)(蕴含表达式)(4)量词的分配形式 x(A(x)B(x)xA(x)xB(x)(对的分配率)“对于任意的x,A(x)和B(x)都成立”,当然等价于“对于任意的x,A(x)成立,并且对于任意的x,B(x)成立”。x(A(x)B(x)xA(x)xB(x)(对的分配率),？,36,但是,下

20、面的式子却不成立：x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)要证明这两个等价式不成立,只要给出一种解释,使得等价式在该解释下不成立既可。,虽然如此,却有如下的永真蕴含式：x(A(x)B(x)xA(x)xB(x)(对的永真蕴含式)分别以A(x)、B(x)代入上式的A(x)、B(x)得 xA(x)xB(x)x(A(x)B(x)(对的永真蕴含式),37,(5)关于多个量词的永真式 从前面的叙述我们知道,多个量词同时出现时,其顺序不能随意颠倒。但是,按特定顺序出现的多量词公式之间却存在着等价式和永真蕴含式。在此,我们只举2个量词的情况,更多量词的情况与之类似。xy

21、A(x,y);yxA(x,y);xyA(x,y);yxA(x,y);xyA(x,y);yxA(x,y);,38,xyA(x,y)yxA(x,y)xyA(x,y)yxA(x,y)xyA(x,y)yxA(x,y),39,现将常用的谓词演算等价式和永真蕴含式归纳如下：(1)对的永真蕴含式 xP(x)xP(x)(2)量词的转化律xP(x)xP(x)xP(x)xP(x),40,(3)量词辖域的扩张与收缩xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)(4)对A的分配律 x(A(x)B(x)xA(x)xB(x),41,(5)对的分配律 x(A

22、(x)B(x)xA(x)xB(x)(6)对的永真蕴含式 xA(x)xB(x)x(A(x)B(x)(7)对的永真蕴含式 x(A(x)B(x)xA(x)xB(x),42,例5 判断下面的证明是否正确。x(A(x)B(x)x(A(x)B(x)x(A(x)B(x)x(A(x)B(x)(xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)xA(x)xB(x),43,解 这个推证错误。错误在于下面的一步：x(A(x)B(x)(xA(x)xB(x)由对的永真蕴含式(7)可得 x(A(x)B(x)xA(x)xB(x)又由逆反律得(xA(x)xB(x)x(A(x)B(x)而反向的永真蕴含式却不一定成立,

23、而且通常不成立。,44,2.6 前束范式,在命题演算中,常将公式化为规范形式。对于谓词演算也有类似情况。定义2.6.1 一个谓词公式,如果量词均在全式的开头,且其辖域延伸到公式的末尾,则该公式称为前束范式。也就是说,前束范式有如下形式：v1v2vnA其中,可以是或,vi(I=1,n)是客体变元,A是不含量词的谓词公式。例如,xyz(P(x,y)Q(z)R(x,z),xz(P(x,y)Q(z)等都是前束式。,45,定理 2.6.1 任意一个谓词公式均可化为与之等价的前束范式。证明 首先利用量词的转化律将量词前面的否定深入到谓词前面,再利用改名和代入规则以及量词辖域扩张的公式将量词移到全式的最前面

24、,便得到前束范式。这个定理的证明实际上提供了求一个谓词公式的前束范式的方法和步骤。下面我们举例说明。,46,例1 求下面谓词公式的前束范式。(1)xy(zP(x,z)P(y,z)uQ(x,y,u)(2)x(yA(x,y)xy(B(x,y)y(A(x,y)B(x,y)解(1)xy(zP(x,z)P(y,z)uQ(x,y,u)xy(zP(x,z)P(y,z)uQ(x,y,u)(蕴含表达式)xy(zP(x,z)P(y,z)uQ(x,y,u)(量词转化律)xy(wP(x,w)P(y,z)uQ(s,t,u)(改名及代入规则)xywu(P(x,w)P(y,z)Q(s,t,u)(量词辖域扩张),47,(2)

25、x(yA(x,y)xy(B(x,y)y(A(x,y)B(x,y)x(yA(x,y)xy(B(x,y)y(A(x,y)B(x,y)(蕴含表达式)x(yA(x,y)xy(B(x,y)y(A(y,x)B(x,y)(量词转化律、德.摩根定律)x(yA(x,y)xy(B(x,y)z(A(z,x)B(x,z)(改名规则)x(yA(x,y)xyz(B(x,y)(A(z,x)B(x,z)(量词辖域扩张)x(yA(x,y)stz(B(s,t)(A(z,s)B(s,z)(改名规则)xyzstz(A(x,y)(B(s,t)(A(z,s)B(s,z)(量词辖域扩张),48,注意 由于进行演算时所用的方法不同,对于同一

26、公式可能得到不同的前束范式,因此,给定公式的前束范式并不是惟一的。但是,所有前束范式的各指导变元应各不相同,原公式中自由出现的客体变元在前束范式中也应自由出现；否则就应该检查纠正演算中的错误。,49,前束范式中量词的个数必须等于原公式中量词的个数吗?答案是否定的。原因是由于下面的等价式：xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)当然,如果你愿意,也可以保持原公式中量词的数目：xA(x)xB(x)xA(x)yB(y)(改名规则)xy(A(x)B(y)(量词辖域扩张),50,定义2.6.2 若一个谓词公式A有如下形式,则称之为前束析取范式。v1v2vn(A11

27、A12A1k1)(A21A22A2k2)(Am1Am2Amkm)其中是量词,vi(I=1,2,n)是客体变元,Aikj(I,j=1,m)是原子公式或其否定。定理2.6.3 任一谓词公式均可化为与之等价的前束析取范式(证明从略)。,51,定义 一谓词公式A如果有如下形式,则称之为前束合取范式。v1 v2 vn(A11A12 A1k1)(A21 A22 A2k2)(Am1 Am2 Amkm)其中,、vi、Aiki的概念与定义中相同。定理2.6.4 任一谓词公式均可化为与之等价的前束合取范式(证明从略)。,52,作业,P72(2)cP75(1)b,53,2.7 谓词逻辑的推理理论,谓词逻辑的推理可以

28、看作是对命题逻辑推理的扩充。谓词逻辑中,前提、结论、推理等概念与命题逻辑中相同,只不过参加推理的是谓词公式而非命题公式。命题逻辑的推理规则均可在谓词逻辑推理中应用。但是,谓词逻辑的推理有着自己的特点。看两个谓词逻辑推理的例子,第一个是苏氏三段论：所有的人都是要死的,苏格拉底是人,所以苏格拉底是要死的。,54,第二个是实数域上的推理：所有的有理数是实数,某些有理数是整数,因此某些实数是整数。我们看到,前提和结论中均有量词出现。只有消去前提中的量词,才能应用命题逻辑中的推理规则；而推导出的结论又必须适当加上量词,才能得到含有量词的最后结论。因此有如下消去和添加量词的规则。在下面的叙述中,AB中的A

29、、B可分别看作前提和结论。,55,消去量词的规则有两类：全称规则和存在指定规则。1.全称指定规则(简称US规则)这条规则有如下两中形式：(1)xP(x)P(y)(2)xP(x)P(c)其中,(1)中y为任意不在P(x)中约束出现的客体变元(因而可以是x本身)；(2)中c为个体域中的任一客体常元。这两个式子表达的含义分别是：如果对个体域中的任意客体x,A(x)成立,则当然对可以取任何值的客体变元y、A(y)成立；对任意的客体常元c、A(c)成立。,56,2.存在指定规则(简称ES规则)xP(x)P(c)其中,c是使P成立的特定客体常元。看下面的推理过程：(1)xF(x)P(2)F(c)ES1(3

30、)xG(x)P(4)G(c)ES3(5)F(c)G(c)T(2),(4),有问题吗？,57,推理的第(4)步是错误的。使F成立的特定客体不一定能使G成立,因此,一般地,对xG(x)运用ES规则,只能得到G(d)。添加量词的规则也有两条：全称推广规则和存在推广规则。3.全称推广规则(简称UG规则)P(y)xP(x)如果能够证明,y取任何值时P均为真,则可得结论xP(x)。,58,4.存在推广规则(简称EG规则)P(c)xP(x)上式中,c是使P成立的特定客体常元。如果能够证明,存在着个体域中的客体c,使P成立,当然就能得出一般性的结论xP(x)。虽然这4条规则的本身表达的含义非常简单、清晰,但是

31、推理过程中应用时要特别注意,尤其是当谓词是多元谓词时。,59,下面用本节开头的两个例子说明如何在谓词逻辑中构造证明。,60,例1 构造苏格拉底三段论的证明。解 由于题目中没有指定个体域,取全总个体域为个体域。首先将命题符号化。M(x):x是人,F(x):x是要死的,a：苏格拉底。前提：x(M(x)F(x),M(a)结论：F(a)证明(1)x(M(x)F(x)P(2)M(a)F(a)US(1)(3)M(a)P(4)F(a)T(2)、(3),61,例2 证明下列推理。所有的有理数是实数,某些有理数是整数,因此某些实数是整数。解 在此仍取全总个体域作个体域。首先符号化各命题。Q(x)：x是有理数,R

32、(x)：x是实数,Z(x)：x是整数 前提：x(Q(x)R(x),x(Q(x)Z(x)结论：x(R(x)Z(x),62,(1)x(Q(x)Z(x)P(2)Q(c)Z(c)ES(1)(3)x(Q(x)R(x)P(4)Q(c)R(c)US(3)(5)Q(c)T(2)(6)Z(c)T(2)(7)R(c)T(4)、(5)(8)R(c)Z(c)T(6)、(7)(9)x(R(x)Z(x)EG(8),63,例3 判断下面的推理过程是否正确。(1)xyF(x,y)P(2)yF(z,y)US(1)(3)F(z,c)ES(2)(4)xF(x,c)UG(3)(5)yxF(x,y)EG(4)解：这个推理过程显然是错误的,因为从它可以得出结论：xyF(x,y)yxF(x,y)而由2.1节中的解释我们知道这个式子不成立。它的错误在于第(3)步。xyF(x,y)的含义是：对任一x,存在着与之相应的y,使F(x,y)成立。但是,对yF(z,y)利用ES规则消去存在量词后得到的F(z,c)的含义却是：对任意客体z,有同一客体c,使F(z,c)成立。显然,F(z,c)不是yF(z,y)的有效结论。因此,使用ES规则xP(x)P(c)消去存在量词的条件是：P(x)中除x外没有其他自由出现的客体变元。,64,练习,P79 T(1)-(a)作业：P79 T(3)-(b),