离散数学第三章.

1第3章一阶逻辑2第3章一阶逻辑•3.1一阶逻辑基本概念•3.2一阶逻辑等值演算33.1一阶逻辑基本概念•3.1.1命题逻辑的局限性•3.1.2个体词、谓词与量词–个体常项、个体变项、个体域、全总个体域–谓词常项、谓词变项–全称量词、存在量词•3.1.3一阶逻辑命题符号化43.1一阶逻辑基本概念(续)•3.1.4一阶逻辑公式与分类–一阶语言L（字母表、项、原子公式、合式公式）–辖域和指导变元、约束出现和自由出现–闭式–一阶语言L的解释–永真式、矛盾式、可满足式–代换实例5命题逻辑的局限性考虑下述推理:凡偶数都能被2整除,6是偶数,所以6能被2整除.在命题逻辑中令p:凡偶数都能被2整除,q:6是偶数,r:6能被2整除符号化为(pq)r不能证明其正确性6个体词与个体域个体词:所研究对象中可以独立存在的具体或抽象的客体个体常项:表示具体事物的个体词,用a,b,c等表示个体变项:表示抽象事物的个体词,用x,y,z等表示个体域:个体变项的取值范围全总个体域:宇宙间一切事物例如“若x是偶数,则x能被2整除.”x、偶数和2是个体词,偶数和2是个体常项,x是个体变项个体域可以是自然数集N,整数集Z,…,也可以是全总个体域7谓词谓词:表示个体词性质或相互之间关系的词谓词常项:表示具体性质或相互之间关系的谓词谓词变项:表示抽象性质或相互之间关系的谓词谓词用F,G,H,P等表示n元谓词P(x1,x2,…,xn):含n个命题变项的谓词,是定义在个体域上,值域为{0,1}的n元函数一元谓词:表示事物的性质多元谓词(n2):表示事物之间的关系0元谓词:不含个体变项的谓词,即命题常项或命题变项8实例例1(1)4是偶数4是个体常项,“是偶数”是谓词常项,符号化为:F(4)(2)小王和小李同岁小王,小李是个体常项,同岁是谓词常项.记a:小王,b:小李,G(x,y):x与y同岁,符号化为:G(a,b)(3)xyx,y是命题变项,是谓词常项,符号化为:L(x,y)(4)x具有某种性质Px是命题变项,P是谓词变项,符号化为:P(x)9实例例2将下述命题用0元谓词符号化,并讨论它们的真值:(1)是无理数,而是有理数(2)如果23，则34解(1)设F(x):x是无理数,G(x):x是有理数符号化为真值为0(2)设F(x,y):xy,G(x,y):xy,符号化为F(2,3)G(3,4)真值为123)3()2(GF10量词量词:表示数量的词全称量词:表示任意的,所有的,一切的等如x表示对个体域中所有的xxF(x)表示所有的x具有性质F存在量词:表示存在,有的,至少有一个等如x表示在个体域中存在xxF(x)表示存在x具有性质F11一阶逻辑命题符号化例3在一阶逻辑中将下面命题符号化:(1)人都爱美;(2)有人用左手写字个体域分别取(a)人类集合,(b)全总个体域.解:(a)(1)设F(x):x爱美,符号化为xF(x)(2)设G(x):x用左手写字,符号化为xG(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)xF(x)真值为1(2)xG(x)真值为0(b)(1)xF(x)真值为1(2)xG(x)真值为113实例例5将下面命题符号化:(1)兔子比乌龟跑得快(2)有的兔子比所有的乌龟跑得快(3)并不是所有的兔子都比乌龟跑得快(4)不存在跑得一样快的兔子和乌龟解用全总个体域,令F(x):x是兔子,G(y):y是乌龟,H(x,y):x比y跑得快,L(x,y):x和y跑得一样快(1)xy(F(x)G(y)H(x,y))(2)x(F(x)(y(G(y)H(x,y)))(3)xy(F(x)G(y)H(x,y))(4)xy(F(x)G(y)L(x,y))14注意(1)一元谓词和多元谓词的使用(2)全称量词和存在量词的区别(3)多个量词出现时,不能随意交换顺序如在个体域R中,记H(x,y):x+y=10xyH(x,y)真值为1yxH(x,y)真值为0(4)命题的符号化不惟一如例5(1)x(F(x)y(G(y)H(x,y)))(3)xy(F(x)G(y)H(x,y))(4)xy(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(续)定义3.2L的项的定义如下：(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.4L的合式公式定义如下：(1)原子公式是合式公式(2)若A是合式公式,则(A)也是合式公式(3)若A,B是合式公式,则(AB),(AB),(AB),(AB)也是合式公式(4)若A是合式公式,则xA,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)，指导变元为yx的两次出现均为约束出现y的第一次出现为自由出现,第二次出现为约束出现z为自由出现.19实例例7公式x(F(x)xG(x))x的辖域:(F(x)xG(x))，指导变元为xx的辖域: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真命题例xF(x,y)指定个体域:自然数集,F(x,y):x=yy=021解释与赋值定义3.7设一阶语言L的个体常项集{ai|i1},函数符号集{fi|i1},谓词符号集{Fi|i1},L的解释I由下面4部分组成:(1)非空个体域DI(2)对每一个个体常项ai,DI,称作ai在I中的解释(3)对每一个函数符号fi,设其为m元的,是DI上的m元函数,称作fi在I中的解释(4)对每一个谓词符号Fi,设其为n元的,是一个n元谓词,称作Fi在I中的解释iaifiF22解释与赋值(续)(5)对每一个自由出现的个体变项x指定个体域中的一个值(x),称作赋值.任何公式在给定的解释和赋值下都是命题.23实例例8给定解释I如下:(a)个体域D=N(b)(c)(d)谓词及赋值:(x)=0,(y)=1,(z)=2.说明下列公式在I及下的含义,并讨论其真值(1)xF(g(x,a),y)2axyyxgyxyxf),(,),(yxyxF:),(x(2x=1)假命题24实例(续)(3)xyzF(f(x,y),z)(5)F(f(x,a),g(y,a))(4)xF(f(x,y),g(x,z))x(x+1=2x)真命题xyz(x+y=z)真命题(6)x(F(x,y)yF(f(x,a),g(y,a)))x(x=1y(x+2=2y))假命题0+2=12真命题(2)xy(F(f(x,a),y)F(f(y,a),x))xy(x+2=yy+2=x)假命题25闭式的性质定理3.1闭式在任何解释下都变成命题.闭式只需给定解释,如例8(2),(3).只给定解释,非闭式可能成为命题,但通常不能成为命题.只有给定解释和赋值,非闭式才能一定成为命题.26一阶逻辑公式的分类永真式(逻辑有效式):无成假解释和赋值矛盾式(永假式):无成真解释和赋值可满足式:至少有一个成真解释和赋值在一阶逻辑中,公式的可满足性(永真性,永假性)是不可判定的,即不存在算法能在有限步内判断任给的公式是否是可满足式(永真式,矛盾式)27代换实例定义3.9设A0是含命题变项p1,p2,…,pn的命题公式,A1,A2,…,An是n个谓词公式,用Ai处处代替A0中的pi(1in),所得公式A称为A0的代换实例.例如F(x)G(x),xF(x)yG(y)等都是pq的代换实例定理3.2重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式.28实例例9判断下列公式的类型:(1)x(F(x)G(x))非永真式的可满足式(2)(xF(x,y))(xF(x,y))这是pp的代换实例,pp是重言式,取解释I1,D1=R,:x是整数,:x是有理数,真命题)(xF)(xG永真式(3)(xF(x)yG(y))yG(y)这是(pq)q的代换实例,(pq)q是矛盾式矛盾式取解释I2,D2=R,:x是整数,:x是自然数,假命题)(xF)(xG29实例(续)(4)xF(x,y)非永真式的可满足式解释I1,D1=N,:xy;赋值(y)=0,真命题),(yxF解释I2,D2=N,:xy;赋值(y)=1,假命题),(yxF303.2一阶逻辑等值演算•3.2.1一阶逻辑等值式与置换规则–基本等值式–置换规则、换名规则•3.2.2一阶逻辑前束范式31等值式定义3.10若AB是永真式,则称A与B是等值的,记作AB,并称AB为等值式基本等值式命题逻辑中基本等值式的代换实例如，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)32基本等值式(续)量词辖域收缩与扩张等值式设A(x)是含x自由出现的公式，B中不含x的出现关于全称量词的：x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)关于存在量词的:x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)33基本等值式(续)量词否定等值式设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)注意：对，对无分配律34置换规则、换名规则置换规则设(A)是含公式A的公式,(B)是用公式B取代(A)中的所有A得到的公式,则(A)(B)换名规则将公式A中某量词的指导变元及其在辖域内的所有约束出现改成该量词辖域内未曾出现的某个个体变项,其余部分不变,记