《离散数学-31-2一阶逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学-31-2一阶逻辑.ppt（38页珍藏版）》请在三一办公上搜索。
1、课件,1,第3章 一阶逻辑,课件,2,第3章 一阶逻辑,3.1 一阶逻辑基本概念3.2 一阶逻辑等值演算,课件,3,3.1 一阶逻辑基本概念,3.1.1 命题逻辑的局限性3.1.2 个体词、谓词与量词个体常项、个体变项、个体域、全总个体域谓词常项、谓词变项全称量词、存在量词3.1.3 一阶逻辑命题符号化,课件,4,3.1 一阶逻辑基本概念(续),3.1.4 一阶逻辑公式与分类一阶语言L（字母表、项、原子公式、合式公式）辖域和指导变元、约束出现和自由出现闭式一阶语言L 的解释永真式、矛盾式、可满足式代换实例,课件,5,命题逻辑的局限性,苏格拉底三段论（1）所有的人都是要死的。P（2）苏格拉底是人
2、。Q（3）苏格拉底是要死的。R应当有：PQR但当P,Q取1，而R取0时，真值为0,课件,6,个体词与个体域,个体词:所研究对象中可以独立存在的具体或抽象的客体 个体常项:表示具体事物的个体词,用a,b,c等表示 个体变项:表示抽象事物的个体词,用x,y,z等表示 个体域:个体变项的取值范围 全总个体域:宇宙间一切事物例如“若x是偶数,则x能被2整除.”x、偶数和2是个体词,偶数和2是个体常项,x是个体变项 个体域可以是自然数集N,整数集Z,也可以是全总个 体域,课件,7,谓词,谓词:表示个体词性质或相互之间关系的词 谓词常项:表示具体性质或相互之间关系的谓词 谓词变项:表示抽象性质或相互之间关
3、系的谓词 谓词用F,G,H,P等表示 n元谓词P(x1,x2,xn):含n个命题变项的谓词,是定义在个体域上,值域为0,1的n元函数 一元谓词:表示事物的性质 多元谓词(n2):表示事物之间的关系 0元谓词:不含个体变项的谓词,即命题常项或命题变项,课件,8,实例,例1(1)4是偶数 4是个体常项,“是偶数”是谓词常项,符号化为:F(4)(2)小王和小李同岁 小王,小李是个体常项,同岁是谓词常项.记a:小王,b:小李,G(x,y):x与y同岁,符号化为:G(a,b)(3)x y x,y是命题变项,是谓词常项,符号化为:L(x,y)(4)x具有某种性质P x是命题变项,P是谓词变项,符号化为:P
4、(x),课件,9,实例,例2 将下述命题用0元谓词符号化,并讨论它们的真值:(1)是无理数,而 是有理数(2)如果23，则3y,G(x,y):xy,符号化为 F(2,3)G(3,4)真值为1,课件,10,量词,量词:表示数量的词 全称量词:表示任意的,所有的,一切的等 如 x 表示对个体域中所有的x x F(x)表示所有的x具有性质F 存在量词:表示存在,有的,至少有一个等 如 x 表示在个体域中存在x x F(x)表示存在x具有性质F,课件,11,一阶逻辑命题符号化,例3 在一阶逻辑中将下面命题符号化:(1)人都爱美;(2)有人用左手写字个体域分别取(a)人类集合,(b)全总个体域.解:(a
5、)(1)设F(x):x爱美,符号化为 x F(x)(2)设G(x):x用左手写字,符号化为 x G(x)(b)设M(x):x为人，F(x),G(x)同(a)中(1)x(M(x)F(x)(2)x(M(x)G(x)M(x)称作特性谓词,课件,12,实例,例4 将下列命题符号化,并讨论其真值:(1)对任意的x,均有x2-3x+2=(x-1)(x-2)(2)存在x,使得x+5=3分别取(a)个体域D1=N,(b)个体域D2=R解 记F(x):x2-3x+2=(x-1)(x-2),G(x):x+5=3(a)(1)x F(x)真值为1(2)x G(x)真值为0(b)(1)x F(x)真值为1(2)x G(
6、x)真值为1,课件,13,实例,例5 将下面命题符号化:(1)兔子比乌龟跑得快(2)有的兔子比所有的乌龟跑得快(3)并不是所有的兔子都比乌龟跑得快(4)不存在跑得一样快的兔子和乌龟解 用全总个体域,令F(x):x是兔子,G(y):y是乌龟,H(x,y):x比y跑得快,L(x,y):x和y跑得一样快(1)xy(F(x)G(y)H(x,y)(2)x(F(x)(y(G(y)H(x,y)(3)xy(F(x)G(y)H(x,y)(4)xy(F(x)G(y)L(x,y),课件,14,注意,(1)一元谓词和多元谓词的使用(2)全称量词和存在量词的区别(3)多个量词出现时,不能随意交换顺序如 在个体域R中,记
7、H(x,y):x+y=10 xy H(x,y)真值为1 yx H(x,y)真值为0(4)命题的符号化不惟一如例5(1)x(F(x)y(G(y)H(x,y)(3)xy(F(x)G(y)H(x,y)(4)xy(F(x)G(y)L(x,y),课件,15,一阶语言L,定义3.1 一阶语言L 的字母表定义如下：(1)个体常项：a,b,c,ai,bi,ci,i 1(2)个体变项：x,y,z,xi,yi,zi,i 1(3)函数符号：f,g,h,fi,gi,hi,i 1(4)谓词符号：F,G,H,Fi,Gi,Hi,i 1(5)量词符号：,(6)联结词符号：,(7)括号与逗号：(),，,课件,16,一阶语言L(
8、续),定义3.2 L 的项的定义如下：(1)个体常项和个体变项是项.(2)若(x1,x2,xn)是任意的n元函数，t1,t2,tn是任意 的n个项，则(t1,t2,tn)是项.(3)所有的项都是有限次使用(1),(2)得到的.定义3.3 设R(x1,x2,xn)是L 的任意n元谓词，t1,t2,tn是L 的任意n个项，则称R(t1,t2,tn)是原子公式,课件,17,一阶语言L(续),定义3.4 L 的合式公式定义如下：(1)原子公式是合式公式(2)若A是合式公式,则(A)也是合式公式(3)若A,B是合式公式,则(AB),(AB),(AB),(AB)也 是合式公式(4)若A是合式公式,则xA,
9、xA也是合式公式(5)只有有限次地应用(1)(4)形成的符号串才是合式公式.合式公式又称谓词公式,简称公式,课件,18,量词的辖域,定义3.5 在公式xA和xA中,称x为指导变元,A为相应量词的辖域.在x和x的辖域中,x的所有出现称为约束出现，A中不是约束出现的其他变项称为自由出现例6 公式 x(F(x,y)yG(x,y,z)x的辖域:(F(x,y)yG(x,y,z)，指导变元为x y的辖域:G(x,y,z)，指导变元为y x的两次出现均为约束出现 y的第一次出现为自由出现,第二次出现为约束出现z为自由出现.,课件,19,实例,例7 公式 x(F(x)xG(x)x的辖域:(F(x)xG(x)，
10、指导变元为xx的辖域:G(x)，指导变元为xx的两次出现均为约束出现.但是,第一次出现的x是x中的x,第二次出现的x是x中的x.闭式:不含自由出现的个体变项的公式.,课件,20,解释的直观涵义,例 公式x(F(x)G(x)指定1 个体域:全总个体域,F(x):x是人,G(x):x是黄种人 假命题指定2 个体域:实数集,F(x):x10,G(x):x0 真命题,课件,21,解释,定义3.7 设一阶语言L 的个体常项集ai|i1,函数符号集fi|i1,谓词符号集Fi|i1,L 的解释I由下面4部分组成:(1)非空个体域DI(2)对每一个个体常项ai,DI,称作ai在I中的解释(3)对每一个函数符号
11、fi,设其为m元的,是DI上的m元函数,称作fi在I中的解释(4)对每一个谓词符号Fi,设其为n元的,是一个n元谓词,称作Fi在I中的解释,课件,22,实例,例8 给定解释I 如下:(a)个体域 D=N(b)(c)(d)谓词说明下列公式在 I 下的含义,并讨论其真值(1)xF(g(x,a),x),x(2x=x)假命题,(2)xy(F(f(x,a),y)F(f(y,a),x),xy(x+2=yy+2=x)假命题,课件,23,实例(续),(3)xyzF(f(x,y),z),(5)F(f(x,a),g(x,a),(4)xF(f(x,x),g(x,x),x(2x=x2)真命题,xyz(x+y=z)真命
12、题,(6)x(F(x,y)F(f(x,a),f(y,a),x(x=yx+2=y+2)真命题,x+2=2x 不是命题,课件,24,闭式的性质,定理3.1 闭式在任何解释下都变成命题.例8(1)(4)都是闭式,在I下全是命题.(5)和(6)不是闭式,在I下(5)不是命题,(6)是命题,课件,25,一阶逻辑公式的分类,永真式(逻辑有效式):无成假解释矛盾式(永假式):无成真解释可满足式:至少有一个成真解释在一阶逻辑中,公式的可满足性(永真性,永假性)是不可判定的,即不存在算法能在有限步内判断任给的公式是否是可满足式(永真式,矛盾式),课件,26,代换实例,定义3.9 设A0是含命题变项p1,p2,p
13、n的命题公式,A1,A2,An是n个谓词公式,用Ai处处代替A0中的pi(1in),所得公式A称为A0的代换实例.例如 F(x)G(x),xF(x)yG(y)等都是pq的代换实例 定理3.2 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式.,课件,27,实例,例9 判断下列公式的类型:(1)x(F(x)G(x),非永真式的可满足式,(2)(xF(x)(xF(x),这是 pp 的代换实例,pp是重言式,取解释I1,D1=R,:x是整数,:x是有理数,真命题,永真式,(3)(xF(x)yG(y)yG(y),这是(pq)q的代换实例,(pq)q是矛盾式,矛盾式,取解释I2,D2=R,:x是整
14、数,:x是自然数,假命题,课件,28,3.2 一阶逻辑等值演算,3.2.1 一阶逻辑等值式与置换规则基本等值式置换规则、换名规则、代替规则3.2.2 一阶逻辑前束范式,课件,29,等值式,定义3.10 若AB是永真式,则称A与B是等值的,记作 AB,并称AB为等值式,基本等值式命题逻辑中基本等值式的代换实例如，xF(x)yG(y)xF(x)yG(y)(xF(x)yG(y)xF(x)yG(y)等 消去量词等值式 设D=a1,a2,an xA(x)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an),课件,30,基本等值式(续),量词辖域收缩与扩张等值式 设A(x)是含x自由出现
15、的公式，B中不含x的出现关于全称量词的：x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x),关于存在量词的:x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x),课件,31,基本等值式(续),量词否定等值式设A(x)是含x自由出现的公式 xA(x)x A(x)xA(x)x A(x)量词分配等值式 x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)注意：对无分配律，对无分配律,课件,32,置换规则、换名规则、代替规则,置换规则 设(A)是
16、含公式A的公式,(B)是用公式B取代(A)中的所有A得到的公式,则(A)(B)换名规则 将公式A中某量词的指导变元及其在辖域内的所有约束出现改成该量词辖域内未曾出现的某个个体变项,其余部分不变,记所得公式为A,则AA 代替规则 将公式A中某个自由出现的个体变项的所有自由出现改成A中未曾出现的某个个体变项,其余部分不变,记所得公式为A,则AA,课件,33,实例,例1 消去公式中既约束出现、又自由出现的个体变项(1)xF(x,y,z)yG(x,y,z),uF(u,y,z)yG(x,y,z)换名规则 uF(u,y,z)vG(x,v,z)换名规则,或者 xF(x,u,z)yG(x,y,z)代替规则 x
17、F(x,u,z)yG(v,y,z)代替规则,(2)x(F(x,y)yG(x,y,z),x(F(x,y)tG(x,t,z)换名规则,或者 x(F(x,t)yG(x,y,z)代替规则,课件,34,实例,例2 设个体域D=a,b,c,消去下面公式中的量词:(1)x(F(x)G(x),(F(a)G(a)(F(b)G(b)(F(c)G(c),(2)x(F(x)yG(y),xF(x)yG(y)量词辖域收缩(F(a)F(b)F(c)(G(a)G(b)G(c),x(F(x,a)F(x,b)F(x,c),(3)xyF(x,y),(F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(c
18、,a)F(c,b)F(c,c),课件,35,实例,解(F(f(2)G(2,f(2)(F(f(3)G(3,f(3),例3 给定解释I:(a)D=2,3,(b)(c):x是奇数,:x=2 y=2,:x=y.在I下求下列各式的真值:(1)x(F(f(x)G(x,f(x),(2)xyL(x,y),(11)(01)1,解 yL(2,y)yL(3,y),(L(2,2)L(2,3)(L(3,2)L(3,3),(10)(01)0,课件,36,实例,例4 证明下列等值式:x(M(x)F(x)x(M(x)F(x),证 左边 x(M(x)F(x)量词否定等值式,x(M(x)F(x),x(M(x)F(x),课件,37
19、,前束范式,定义3.11 设A为一个一阶逻辑公式,若A具有如下形式 Q1x1Q2x2Qkxk B则称A为前束范式,其中Qi 为或,1ik,B为不含量词的公式.例如 xy(F(x)(G(y)H(x,y)x(F(x)G(x)是前束范式 x(F(x)y(G(y)H(x,y)x(F(x)G(x)不是前束范式,课件,38,公式的前束范式,定理3.3(前束范式存在定理)一阶逻辑中的任何公式都存在与之等值的前束范式,例5 求公式的前束范式(1)xF(x)xG(x),解 xF(x)xG(x)量词否定等值式,x(F(x)G(x)量词分配等值式,解2 xF(x)yG(y)换名规则,xF(x)yG(y)量词否定等值式,x(F(x)yG(y)量词辖域扩张,xy(F(x)G(y)量词辖域扩张,
