离散数学04

2020/2/6离散数学1离散数学2020/2/6离散数学2第一部分数理逻辑第四章一阶逻辑基本概念2020/2/6离散数学3复习——命题演算命题演算形式系统:语法:语义:可靠性:凡是推出来的都是正确的.完全性:凡是正确的都可以推出来.形式推理形式规则形式公理命题公式永真式公式的值赋值2020/2/6离散数学4问题的提出命题演算不能表达所有正确的推理.例:所有实数的平方都是非负的.π是一个实数.π的平方是非负的.如用命题演算推理形式来表示:由p,q推出r.——非有效推理形式2020/2/6离散数学5§1一阶逻辑命题符号化需要进一步分析推理结构.上述推理中,各命题之间的关系在于简单命题的成分之间.需要进一步分解简单命题.简单命题的符号化.2020/2/6离散数学6简单命题的结构个体词,谓词主语谓语宾语讨论对象对象的性质或关系讨论对象个体词(组)谓词个体词(组)2020/2/6离散数学7例1分析下列各命题中的个体和谓词(1)π是无理数.(2)张三与李四同在计算机系.(3)x与y的和等于z(x,y,z是确定的数).(4)π的平方是非负的.(5)所有实数的平方都是非负的.(6)有一个比21000大的素数.2020/2/6离散数学8例1(1)(1)π是无理数.解:个体:π(代表圆周率)谓词:…是无理数,表示”π”的性质.2020/2/6离散数学9例1(2)(2)张三与李四同在计算机系.解:个体:张三,李四谓词:…与…同在计算机系,表示”张三”与”李四”之间的关系.个体:张三谓词:…与李四同在计算机系,表示”张三”的性质.个体:李四谓词:张三与…同在计算机系,表示”李四”的性质.2020/2/6离散数学10例1(3)(3)x与y的和等于z(x,y,z是确定的数).解:个体:x,y,z谓词:…与…的和等于…个体:x,z谓词:…与y的和等于…个体:y谓词:x与…的和等于z谓词可以表示单个个体的性质,也可以表示两个个体词之间的关系或性质,分别称为一元谓词和二元谓词.表示n个个体间的关系或性质的谓词称为n元谓词.2020/2/6离散数学11例1(4)(4)π的平方是非负的.解:个体:π谓词:…的平方是非负的个体:π的平方谓词:…是非负的“π的平方”是一个”复合”个体,需要再分解.个体:π函词:…的平方一元函词谓词:…是非负的2020/2/6离散数学12例1(5)(5)所有实数的平方都是非负的.解:个体:每一个实数函词:…的平方谓词:…是非负的“所有”是什么?量词:所有2020/2/6离散数学13例1(6)(6)有一个比21000大的素数.解:个体:一个素数谓词:…比21000大“有一个”是什么?量词:有一个2020/2/6离散数学14表示简单命题的新符号个体:x,y,z,a,b,c,…谓词:Fn,Gn,Hn,…n表示元数函词:fn,gn,hn,…n表示元数量词:--所有:∀全称量词--有一个:∃存在量词2020/2/6离散数学15例1(1)的符号化(1)π是无理数.解:个体:π(代表圆周率)谓词:…是无理数,以F表示则此命题可表示为F(π).2020/2/6离散数学16例1(2)的符号化(2)张三与李四同在计算机系.解:个体:张三,李四:分别以a,b表示谓词:…与…同在计算机系:以G表示则此命题可表示为:G(a,b)个体:张三:以a表示谓词:…与李四同在计算机系:以G’表示此命题可表示为:G’(a)个体:李四:以b表示谓词:张三与…同在计算机系:以G’’表示此命题可表示为:G’’(b)2020/2/6离散数学17例1(3)的符号化(3)x与y的和等于z(x,y,z是确定的数).解:个体:x,y,z谓词:…与…的和等于…:以R表示符号化:R(x,y,z)个体:x,z谓词:…与y的和等于…:以R’表示符号化:R’(x,z)个体:x,y,z函词:…与…的和:以f2表示谓词:…等于…:以R’’表示符号化:R’’(f2(x,y),z)2020/2/6离散数学18例1(4)的符号化(4)π的平方是非负的.解:个体:π的平方:以a表示谓词:…是非负的:以R表示符号化:R(a)个体:π函词:…的平方:以f表示谓词:…是非负的:以R表示符号化:R(f(π))2020/2/6离散数学19例1(5)的符号化(5)所有实数的平方都是非负的.解:个体:每一个实数:以x表示函词:…的平方:以f表示谓词:…是非负的:以R表示量词:所有:以∀表示符号化:∀xR(f(x))x可以代表不同的个体,称为个体变元相对地π等称为个体常元2020/2/6离散数学20例1(5)的符号化(续)(5)所有实数的平方都是非负的.解:个体:每一个实数:以z表示谓词:…是一个实数,以R’表示函词:…的平方:以f表示谓词:…是非负的:以R表示量词:所有:以∀表示符号化:(∀z)(R’(z)→R(f(z))最清晰个体变元x和z的取值范围不同.个体变元的取值范围称为它的论域.2020/2/6离散数学21例1(6)的符号化(6)有一个比21000大的素数.解:个体:一个素数:以y表示谓词:…比21000大:以P1表示量词:有一个:以∃表示符号化:(∃y)P1(y)还可以表示为:(∃x)(P2(x)∧P1(x)),其中:x表示某个数,P2表示”…是一个素数”,P1同上.2020/2/6离散数学22表示命题的符号个体变元:x,y,z,…个体常元:a,b,c,…谓词:Fn,Gn,Hn,…函数:fn,gn,hn,…量词:全称量词∀,存在量词∃联结词:¬,∨,∧,→,↔2020/2/6离散数学23例2将下列命题符号化.(1)凡是有理数皆可写成分数.(2)教室里有同学在说话.(3)对于任意x,y,都存在唯一的z,使x+y=z.(4)在我们班中,并非所有同学都能取得优秀成绩.(5)有一个整数大于其它每个整数.(6)任意ε0,存在δ0,如果|x-a|δ,则|F(x)–b|ε.(7)恰有三个互不相同的素数小于7.2020/2/6离散数学24例2(1)的符号化(1)凡是有理数皆可写成分数.解:(∀x)(Q1(x)→F1(x))x:数Q1:…是有理数F1:…可写成分数注:不能写成(∀x)(Q1(x)∧F1(x))也不能写成(∀x∈Q)F1(x)2020/2/6离散数学25例2(2)的符号化(2)教室里有同学在说话.解:(∃x)(C1(x)∧T1(x))x:同学C1:…在教室里T1:…在说话注:不能写成(∃x)(C1(x)→T1(x))也不能写成(∃x∈C)T1(x).2020/2/6离散数学26例2(3)的符号化(3)对于任意x,y,都存在唯一的z,使x+y=z.解:(∀x)(∀y)(∃z)((x+y=z)∧(∀u)(u=x+y→u=z)).注:量词的嵌套“存在唯一”的表示2020/2/6离散数学27例2(4)的符号化(4)在我们班中,并非所有同学都能取得优秀成绩.解:¬(∀x)(C(x)→E(x))x:同学C:…在班级里E:…能取得优秀成绩注:C(x)→E(x)⇔¬C(x)∨E(x)⇔¬(C(x)∧¬E(x)),从而命题可表示为:¬(∀x)¬(C(x)∧¬E(x)).另一方面,此命题也可表为(∃x)(C(x)∧¬E(x)),即:“¬(∀x)¬”与”∃x”有相同的意义.2020/2/6离散数学28例2(5)的符号化(5)有一个整数大于其它每个整数。解：(∃x)(Z(x)∧(∀y)((Z(y)∧¬(y=x))→xy))x,y:数Z:…是整数注:此符号串中,“=“和””是什么类型的符号?2020/2/6离散数学29例2(6)的符号化(6)任意ε0,存在δ0,如果|x-a|δ,则|F(x)–b|ε.解:∀ε(ε0→(∃δ)(δ0∧(|x-a|δ→|f(x)-b|ε)))注:此符号串中有哪些谓词符号?2020/2/6离散数学30例2(7)的符号化(7)恰有三个互不相同的素数小于7.解:(∃x1)(∃x2)(∃x3)((x17∧x27∧x37)∧(P(x1)∧P(x2)∧P(x3))∧(¬(x1=x2)∧¬(x1=x3)∧¬(x2=x3))∧(∀y)((y7∧P(y))→(y=x1∨y=x2∨y=x3)))注:两个量词可以表示任意确定个数的个体.2020/2/6离散数学31应注意的问题谓词(函数)的元数是固定的.谓词(函数)中的变元是有顺序性的.例如:F(x,y)与F(y,x)不具有相同的含义.量词也有顺序性.例如:(∀x)(∃y)(xy)与(∃y)(∀x)(xy)并不表示同一含义.谓词公式真假值判别的困难性.2020/2/6离散数学32本章开头推理的正确表示因为(∀x)(G12(x)→G11(f(x)))G12(π)所以G11(f(π))其中:x代表”数”.f代表”…的平方”.G11代表”…是非负实数”.G12代表”…是实数”.2020/2/6离散数学33§2一阶逻辑公式及其解释一阶语言是谓词演算系统形式语言.符号库谓词公式逻辑符号非逻辑符号公式项2020/2/6离散数学34非逻辑符号可能包括下列符号:个体常元符号:c,c1,c2,…,cn,…谓词符号:Fn,Gn,Pn,Qn,Rn等——n(n,n0)表示此谓词符号的元数函数符号:fm,gm,hm等——m(m,m0)表示此函数符号的元数由一些非逻辑符号作为元素组成的集合常记为ℒ.2020/2/6离散数学35逻辑符号包括下列符号:个体变元符号:x0,x1,x2,…联结词符号:¬,∧,∨,→,↔量词符号:∀,∃辅助符号:),,,(2020/2/6离散数学36逻辑符号与非逻辑符号非逻辑符号更象是所描述的特定对象中的符号.而逻辑符号是逻辑系统中的符号.故此得名.在描述特定对象时,并不需要所有非逻辑符号.但可能用到所有逻辑符号.一阶语言与符号库指定的非逻辑符号集ℒ有关,称为ℒ生成的一阶语言.2020/2/6离散数学37项ℒ生成的一阶语言的”项”归纳定义如下:1.个体变元符号和ℒ中的个体常元符号都是项;2.若fm是ℒ中一个m元函数符号,t1,t2,…,tm是ℒ中项,则fm(t1,t2,…,tm)是ℒ中项;3.每个项都是有限次应用(1)和(2)得到的.“项”相当于”复合个体”.2020/2/6离散数学38公式ℒ生成的一阶语言的”公式”归纳定义如下:(1)如果Fn是ℒ中的一个n元谓词符号,t1,t2,…,tn是ℒ中项,则Fn(t1,t2,…,tn)是ℒ中公式,——称为原子公式(2)若A是公式,则(¬A)是公式;(3)若A,B是公式,则(A∨B),(A∧B),(A→B),(A↔B)是ℒ中公式;(4)若A是公式,x是个体变元符号,则(∀x)A,(∃x)A也是公式;(5)每个公式都是有限次使用(1)-(4)得到的.2020/2/6离散数学39一些注记注1:与命题演算的形式语言相比,一阶语言中没有符号,代之的是原子公式.注2:所有一阶语言中都含有相同的逻辑符号,但所含的非逻辑符号不一定相同.注3:在定义中没有要求个体变元x一定要在A中出现:(∀x1)F2(x1,x2)和(∀x3)F2(x1,x2)都是公式.注4:总假设:ℒ中至少有一个谓词符号.否则ℒ生成的一阶语言中没有公式.2020/2/6离散数学40括号省略规则(1)省略公式最外层的括号;(2)联结词符号”¬”的优先级高于其它的四个联结词,可以去掉(¬A)中的外层括号;(3)A1→A2→…→An-1→An表示(A1→(A2→…→(An-1→An)…));对∨,∧,↔也类似规定.(4)∀x,∃x的优先级高于所有联结词.将(∀x)A,(∃x)A分别记为∀xA,∃xA.(5)(∀x1)…(∀xn)A简记为∀x1…xnA;(∃x1)…(∃xn)A简记为∃x1…xnA.2020/2/6离散数学41项和公式项的作用是描述”复合”个体公式的作用是描述命题.“项”相当于”词组”,它们不表达完整的判断;“公式”代表完整的句子,表达判断.f(x1,x2,…,xn)表示f作用到个体x1,…,xn得到的个体Fn(x1,x2,…