工学离散数学课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,工学左孝凌离散数学课件,工学左孝凌离散数学课件工学左孝凌离散数学课件第二章 谓词逻辑（Predicate Logic）2.1谓词的概念与表示(Predicate and its expression),2.2命题函数与量词(Propositional functions&Quantifiers),2.3谓词公式与翻译(Predicate formulae),2.4变元的约束(Bound of variable),2.5谓词演算的等价式与蕴含式(Equivalences&,implications of predicate calculus),2.6前束范式(Prenex normal form),2.7谓词演算的推理理论(Inference theory of,predicate calculus),第二章 谓词逻辑,（,Predicate Logic,）,2.1,谓词的概念与表示,(,Predicate and its expression),2.2,命题函数与量词,(Propositional functions&Quantifiers),2.3,谓词公式与翻译,(Predicate formulae,),2.4,变元的约束,(Bound of variable,),2.5,谓词演算的等价式与蕴含式,(Equivalences&,implications of p,redicate calculus,),2.6,前束范式,(Prenex normal form,),2.7,谓词演算的推理理论,(Inference theory of,p,redicate calculus,),第二章 谓词逻辑,（,Predicate Logic,）,2.1,谓词的概念与表示,(,Predicate and Its Expression),命题逻辑的局限性,：,在命题逻辑中，命题是命题演算的基本单位，不再对原子,命题进行分解，因而无法研究命题的内部结构、成分及命,题之间的内在联系，甚至无法处理一些简单而又常见的推,理过程。例如，下列推理：,所有的人都是要死的。,苏格拉底是人。,苏格拉底是要死的。,众所周知,这是真命题。但在命题逻辑中,如果用,P,Q,R,表,示以上三个命题，则上述推理过程为：（,P,Q,）,R,。借,助命题演算的推理理论不能,证明其为重言式,。,第二章 谓词逻辑,（,Predicate Logic,）,2.1,谓词的概念与表示,(,Predicate and Its Expression),原因：命题逻辑不能将命题之间的内在联系和数量关,系反映出来。,解决办法：将命题进行分解。,2.1,谓词的概念与表示,(,Predicate and its expression),在谓词逻辑中，可将,原子命题,划分为,客体,和,谓词,两部分。,客体,：可以独立存在的具体事物的或抽象的概念。,例,如，电子计算机、李明、玫瑰花、黑板、实数、中国、,思想、唯物主义等，客体也可称之为主语。,第二章 谓词逻辑,（,Predicate Logic,）,2.1,谓词的概念与表示,(,Predicate and Its Expression),谓词：,用来刻划客体的性质或客体之间的相互关系的词。,例如在下面命题中：,（,1,）张明是个劳动模范。,（,2,）李华是个劳动模范。刻划客体的性质,（,3,）,王红,是个大学生。,（,4,）,小李比小赵高,2cm,。,（,5,）点,a,在,b,与,c,之间。刻划客体之间的相互关系,（,6,）,阿杜与阿寺同岁。,“是个劳动模范”、“,是个大学生,”,、,“,比,高,2cm,”,、,“,在,与,之间,”,都是,谓词。,第二章 谓词逻辑,（,Predicate Logic,）,2.1,谓词的概念与表示,(,Predicate and Its Expression),刻划,一个客体性质,的词称之为,一元谓词,刻划,n,个客体之间关系,的词称之为,n,元谓词,.,一般我们用大写英文字母表示,谓词，,用小写英文字母表示客体名称，例如，,将上述谓词分别记作大写字母,F,、,G,、,H,、,R,，,S,则上述命题可表示为：,(1)F(a)a,：,张明,(2)F(b)b,：,李华,(3)G(c)c,：,王红,(4)H(s,t)s,：,小李,t,：小赵,(5)R(a,b,c)(6)S(a,b)a:,阿杜。,b:,阿寺。,其中,(1),、,(2),、,(3),为一元谓词，,(4),、,(6),为二元谓词，,(5),为三元谓词。,第二章 谓词逻辑,（,Predicate Logic,）,2.1,谓词的概念与表示,(,Predicate and Its Expression),注,:,(1),单独一个谓词并不是命题，在谓词字母后填上客体所得到的式子称之为谓词填式。,(2),在谓词填式中，若客体确定，则,A(a,1,，,a,2,.a,n,),就变成了命题,(3),在多元谓词表达式中，客体字母出现的先后次序与事先约定有关,一般不可以随意交换位置,(,如,上例中,H(s,t),与,H(t,s),代表两个不同的命题,),。,第二章 谓词逻辑,（,Predicate Logic,）,2.1,谓词的概念与表示,(,Predicate and Its Expression),小结,:,本节将原子命题进行分解,分为客体和谓词,两部分,.,进而介绍了客体和谓词、一元谓词和,n,元,谓词的概念。重点掌握一元谓词和,n,元谓词的概,念。,作业,:1.,预习第二章,2.2,2.3,9,离散数学,(,Discrete Mathematics,),10,第二章 谓词逻辑,（,Predicate Logic,）,2.1,谓词的概念与表示,(,Predicate and its expression),2.2,命题函数与量词,(Propositional functions&Quantifiers),2.3,谓词公式与翻译,(Predicate formulae,),2.4,变元的约束,(Bound of variable,),2.5,谓词演算的等价式与蕴含式,(Equivalences&,implications of p,redicate calculus,),2.6,前束范式,(Prenex normal form,),2.7,谓词演算的推理理论,(Inference theory of,p,redicate calculus,),11,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),2.2.1,命题函数,(Propositional functions),2.2.2,量词,(,Quantifiers,),12,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),2.2.1,命题函数,(Propositional functions),设谓词,H,表示,“是劳动模范”,a,表示客体名称,张明,b,表示客,体名称,李华,c,表示客体名称这只老虎，,那么,H(a),、,H(b),、,H(c),表示三个不同的命题,但它们有一个共同的形式,即,H(x).,一般地，,H(x),表示客体,x,具有性质,H,。这里,x,表示,抽象的或泛指的客体，称为,客体变元,，常用小写英文字母,x,y,z,表示。相应地，表示具体或特定的客体的词称为,客体常项,，常用小写英文字母,a,b,c,表示。,同理，客体变元,x,，,y,具有关系,L,，记作,L(x,y);,客体变元,x,y,z,具有关系,A,，记作,A(x,y,z).,13,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),H(x),、,L(x,y),、,A(x,y,z),本身并不是一个命题,.,只有用,特定的客体取代客体变元,x,y,z,后，它们才成为命题。我,们称,H(x),、,L(x,y),、,A(x,y,z),为,命题函数。一般地我们,有,定义,2.2.1:,由一个谓词,H,和,n,个客体变元组成的表达式,H(x,1,x,2,x,n,),称为,n,元,简单命题函数,.,由定义可知,n,元谓词就是有,n,个客体变元的,命题函数,.,当,n=0,时,称为,0,元谓词,.,因此,一般情况下,命题函数不是命题,;,特殊情况,0,元谓词就变成一个命题,.,14,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),复合命题函数,:,由一个或几个简单命题函数以及逻辑联结词组合而成的表达式,.,例,1:,若,x,的学习好,则,x,的工作好,设,S(x):x,学习好；,W(x):x,工作好,则有,S(x),W(x),例,2:,将下列命题用,0,元谓词符号化,.,(1)2,是素数且是偶数,.,(2),如果,2,大于,3,则,2,大于,4.,(3),如果,张明比李民高,李民比赵亮高,则张明比赵亮高,.,15,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),解,:(1),设,F(x):x,是素数,.G(x):x,是偶数,.,则,命题符号化为：,F(2),G(2),(2),设,L(x,y),：,x,大于,y.,则,命题符号化为：,L(2,3),L(2,4),(3),设,H(x,y):x,比,y,高,.a:,张明,b:,李民,c,：赵亮,则,命题符号化为：,H(a,b),H(b,c),H(a,c),注意,:,命题函数中,客体变元在哪些范围内取特定的值,对,命题的真值极有影响,.,16,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),例如,:,H(x,y),H(y,z),H(x,z),若,H(x,y,),解释为,:x,大于,y,当,x,y,z,都在实数中取值时,则这个式子表示“若,x,大于,y,且,y,大于,z,，则,x,大于,z”,。这是一个永真式。,如果,H(x,y,),解释为,:“x,是,y,的儿子”,当,x,y,z,都指人时，则这个式子表示“若,x,为,y,的儿子 且,y,是,z,的儿子，则,x,是,z,的儿子”。这是一个永假式。,如果,H(x,y,),解释为,:“x,距,y10,米”,当,x,y,z,为平面上的点，则这个式子表示“若,x,距,y10,米且,y,距,z10,米，则,x,距,z10,米”。这个命题的真值将由,x,y,z,的具体位置而定，它可能是,1,，也可能是,0,。,17,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),在命题函数中，客体变元的取值范围称为,个体域,，又称之为论域。个体域可以是有限事物的集合，也可以是无限事物的集合。,全总个体域：,宇宙间一切事物组成的个体域称为,全总个体域。,18,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),2.2.2,量词,(,Quantifiers,),量词,：分为全称量词,(),和存在量词,(),1.,全称量词,(The Universal Quantifiers),对日常语言中的,“,一切”、“所有”、“凡”、“每一,个”、“任意”等词，,用符号,“,”,表示,，,表示,对个体域里的所有个体，,(,),表示个体域,里的所有个体具有性质,F.,符号,“,”,称为,全称量词,.,19,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),例,3,：,在谓词逻辑中将下列命题符号化,.,（,1,）凡是人都呼吸。,（,2,）每个学生都要参加考试。,(3),任何整数或是正的或是负的。,解,:(1),当个体域为,人类集合,时：,令,F(x):x,呼吸。则（,1,）符号化为,xF(x),当个体域为,全总个体域,时：,令,M(x):x,是人。则（,1,）符号化为,x(M(x),F(x).,20,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),(2),当个体域为,全体学生的集合,时：,令,P(x):x,要参加考试。则（,2,）符号化为,xP(x).,当个体域为,全总个体域,时：,令,S(x):x,是学生。则（,2,）符号化为,x(S(x),P(x).,(3),当个体域为,全体整数的集合,时：,令,P(x):x,是正的。,N(x):x,是负的。则（,3,）符号化为,x(P(x),N(x),.,当个体域为,全总个体域,时：,令,I(x):x,是,整数,。则（,3,）符号化为,x(I(x),(P(x),N(x),).,21,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),2.,存在量词,(The Existential Quantifiers),对日常语言中的,“,有一个,”,、,“,有的,”,、,“,存在着,”,、,“,至少,有一个,”,、,“,存在一些,”,等,词，,用符号,“,”,表示,，,表,示存在个体域里的个体，,(,),表示存在个体域里,的个体具有性质,F.,符号,“,”,称为,存在量词,.,例,4,：,在谓词逻辑中将下列命题符号化,.,（,1,）一些数是有理数。,（,2,）有些人活百岁以上。,22,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),解,:(1),令,Q(x):x,是有理数。则（,1,）符号化为,Q(x),。,（,2,）当个体域为,人类集合,时：,令,G(x):x,活百岁以上。则（,2,）符号化为,x,G,(x),。,当个体域为,全总个体域,时：,令,M(x):x,是人。则（,2,）符号化为,x(M(x),G(x),23,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),有时需要同时使用多个量词。,例,5.,命题“对任意的,x,存在,y,使得,x+y=5”,取个体域为实,数,集合,则该命题,符号化为,:,x y H(x,y).,其中,H(x,y):,x+y=5.,这是个真命题,.,3.,使用,量词时应注意的问题,（,1,）在不同的个体域，同一命题的符号化形式可能相同也可能不同。,（,2,）在不同的个体域，同一命题的真值可能相同也可能不同。,(,如,R(x),表示,x,为大学生。如果个体域为大学里的某个班级的学生，则,x,R(x),为真；若个体域为中学里的某个班级的学生，则,x,R,（,x,）为假,.).,24,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),（,3,）约定以后如不指定个体域，默认为全总个体域。对每个客体变元的变化范围,用特性谓词加以限制,.,特性谓词,:,限定客体变元变化范围的谓词,(,如例,3,中的,M,（,x,）,).,一般而言，对全称量词，特性谓词常作蕴含的前,件，如（,x,）,(M(x),F(x),；对存在量词，特性,谓词常作合取项，如（,x,）,(M(x),G(x).,25,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),(4),一般来说，当多个量词同时出现时，它们的顺序不能随意调换。如：,在实数域上用,H(x,y),表示,x+y=5,则命题“对于任意的,x,都存在,y,使得,x+y=5”,可符号化为：,xyH(x,y),其真值为,1.,若调换量词顺序后为：,yxH(x,y),其真值为,0,。,(5),当,个体域为有限集合时,如,D=a,1,a,2,a,n,对任意,谓词,A(x),有,(x)A(x),A(a,1,),A(a,2,),A(a,n,),（,x,）,A(x),A(a,1,),A(a,2,),A(a,n,),26,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),例,6,：在谓词逻辑中将下列命题符号化,.,（,1,）所有的人都长头发。,（,2,）有的人吸烟。,（,3,）没有人登上过木星。,（,4,）清华大学的学生未必都是高素质的。,解：令,M(x):x,是人。（特性谓词）,（,1,）令,F(x):x,长头发。则符号化为：,（,x,）,(M(x),F(x),27,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),（,2,）令,S(x):x,吸烟。则符号化为：,（,x,）,(M(x),S,(x),（,3,）令,D(x):x,登上过木星。则符号化为：,（,x,）,(M(x)D(x),（,4,）令,Q(x):x,是清华大学的学生。,H(x):x,是高素质的。则符号化为：,（,x,）,(Q(x),H,(x),28,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),小结,:,本节介绍了,n,元谓词、命题函数、全称量词和存在量词等概念。,重点掌握全称量词和存在量词及量化命题的符号化。,作业：,P59,（,2,）单数,29,离散数学,(,Discrete Mathematics,),30,第二章 谓词逻辑,（,Predicate Logic,）,2.1,谓词的概念与表示,(,Predicate and its expression),2.2,命题函数与量词,(Propositional functions&Quantifiers),2.3,谓词公式与翻译,(Predicate formulae,),2.4,变元的约束,(Bound of variable,),2.5,谓词演算的等价式与蕴含式,(Equivalences&,implications of p,redicate calculus,),2.6,前束范式,(Prenex normal form,),2.7,谓词演算的推理理论,(Inference theory of,p,redicate calculus,),31,第二章 谓词逻辑,（,Predicate Logic,）,2.3,谓词公式与翻译,(Predicate formulae,),2.3,谓词公式与翻译,(Predicate formulae,),n,元,谓词,A(x,1,，,x,2,.x,n,),称为谓词演算的,原子公式。,定义,2.3.1,谓词演算的,合式公式,可由下述各条组成,:,（,1,）原子公式是合式公式。,（,2,）若,A,是合式公式，则,(,A),也是合式公式。,（,3,）若,A,，,B,是合式公式，则,(A,B),，,(A,B),，,(A,B),，,(A,B),也是合式公式。,（,4,）若,A,是合式公式，,x,是,A,中出现的任何变元,则,(,x),A,(,x),A,，也是合式公式。,(5),只有有限次应用,(1)(4),得到的公式是,合式公式,.,32,第二章 谓词逻辑,（,Predicate Logic,）,2.3,谓词公式与翻译,(Predicate formulae,),例,1,：在谓词逻辑中将下列命题符号化,.,（,1,）凡正数都大于零。,（,2,）存在小于,2,的素数。,（,3,）没有不能表示成分数的有理数。,（,4,）并不是所有参加考试的人都能取得好成绩。,解：,（,1,）令,F(x):x,是正数。,M(x):x,大于零。则符号化为：,（,x,）,(F(x),M,(x),33,第二章 谓词逻辑,（,Predicate Logic,）,2.3,谓词公式与翻译,(Predicate formulae,),（,2,）令,E(x):x,小于,2,。,S(x):x,是素数。则符号化为：,（,x)(E(x),S,(x),真值为,0,。,（,3,）令,D(x):x,是有理数。,F(x):x,能表示成分数。则符号化为：,(x)(D(x),F,(x),或,(x)(D(x)F(x),真值为。,（,4,）令,M(x),：,x,是人,.Q(x):x,参加考试。,H(x):x,取得好成绩。则符号化为：,(x)(M(x)Q(x),H,(x),或,(x)(M(x)Q(x)H(x),34,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),例,2,：,在谓词逻辑中将下列命题符号化,.,（,1,）所有运动员都钦佩某些教练,.,（,2,）有些运动员不钦佩教练,.,设：,L(x):x,是运动员,J(y):y,是教练,A(x,y):x,钦佩,y,(1)(x),(,L(x),（,y),(,J,(y),A,(x,y),),),(2),（,x),(,L(x),(y),(,J,(y),A,(x,y),),),35,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),例,3,：,在谓词逻辑中将下列命题符号化,.,（,1,）那位戴眼镜的用功的大学生在看这本大而厚的巨著,.,（,2,）,P63(7),解,:(1),设：,S(x):x,是大学生,.A(x):x,戴眼镜,.,B(x):x,用功,.D(x):x,是巨著,.F(x,y):x,看,y.,E(y):y,是大的,.G(y):y,是厚的,.a:,那位,b:,这本,(1),符号化为,:,A(a),B(a),S(a),D(b),E(b),G(b),F(a,b),36,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),（,2,）设：,P(x,y):x,在,y,连续,.Q(x,y):x,大于,y.,(2),符号化为,:,P(f,a),(,),(,Q(,0,),(,(,),Q(,0,),(x),(,Q(,),Q(,),),),),P(f,a),(,),(,)(x),(,Q(,0,),(,Q(,0,),(,Q(,),Q(,),),),).,37,第二章 谓词逻辑,（,Predicate Logic,）,2.2,命题函数与量词,(Propositional functions&Quantifiers),小结：,本节介绍了,谓词合式,公式的概念，,重点掌握,谓词公式的翻译,.,作业,:P63(5),38,离散数学,(,Discrete Mathematics,),39,第二章 谓词逻辑,（,Predicate Logic,）,2.4,变元的约束,(Bound of variable,),2.1,谓词的概念与表示,(,Predicate and its expression),2.2,命题函数与量词,(Propositional functions&Quantifiers),2.3,谓词公式与翻译,(Predicate formulae,),2.4,变元的约束,(Bound of variable,),2.5,谓词演算的等价式与蕴含式,(Equivalences&,implications of p,redicate calculus,),2.6,前束范式,(Prenex normal form,),2.7,谓词演算的推理理论,(Inference theory of,p,redicate calculus,),40,第二章 谓词逻辑,（,Predicate Logic,）,2.4,变元的约束,(Bound of variable,),2.4,变元的约束,(Bound of variable,),2.4.1,变元的约束,2.4.2,约束变元的,换名与,自由变元的,代入,41,第二章 谓词逻辑,（,Predicate Logic,）,2.4,变元的约束,(Bound of variable,),2.4.1,变元的约束,(Bound of variable,),定义,2.4.1,:,在,谓词,公式,中,形如,(,x)P(x),和,(,x)P(x),的部,分,称为,谓词,公式的,x,约束部分,.,(,x)P(x),或,(,x),P(x),中,的,x,叫做,量词的,指导变元,或,作用变元,，,P(x),称为,相应量,词的,作用域,或,辖域,。,在,x,和,x,的辖域中，,x,的所有出现都称为,约束出现,，相,应的,x,称为,约束变元,;P(x),中除约束变元以外出现的变,元称为是,自由变元,。,例,1,：,1,、,x,(,H(x,y)y,(,W(y),L,(x,y,z),),),2,、,x,(,H(x)W(y),),y,(,F(x),L,(x,y,z),),42,第二章 谓词逻辑,（,Predicate Logic,）,2.4,变元的约束,(Bound of variable,),说明,:,(1),n,元谓词公式,A(x,1,，,x,2,.x,n,),中有,n,个自由变元,若对其中的,k(k,n),个进行约束,则构成了,n-k,元谓词,;,如果一个公式中没有自由变元出现,则该公式就变成了一个命题,(2),一个公式的约束变元所使用的名称符号是无关紧要的,如,(x)M(x),与,(y)M(y),意义相同,.,43,第二章 谓词逻辑,（,Predicate Logic,）,2.4,变元的约束,(Bound of variable,),2.4.2,约束变元的,换名与,自由变元的,代入规则,在例,1,中,一个变元在同一个公式中既是自由出现又是约束出现,这样在理解上容易发生混淆,.,为了避免这种混乱,可对,约束变元进行换名,.,换名规则,:,(,对约束变元而言）,对约束变元进行换名,使得一个变元在一个公式中只呈一,种形式出现,(1),约束变元可以换名,其更改的变元名称范围是量词中的指导变元以及该量词作用域中所出现的该变元,公式的其余部分不变,(2),换名时一定要更改为作用域中没有出现的变元名称,44,第二章 谓词逻辑,（,Predicate Logic,）,2.4,变元的约束,(Bound of variable,),例,1:,x,(,P(x),R(x,y),),L,(x,y),换名为,t,(,P(t),R(t,y),),L,(x,y),x,(,H(x,y),y,(,W(y),L,(x,y,z),),),换名为,x,(,H(x,y),s,(,W(s),L,(x,s,z),),),45,第二章 谓词逻辑,（,Predicate Logic,）,2.4,变元的约束,(Bound of variable,),代入规则,（对自由变元而言）,对公式中自由变元的更改称为代入,(1),对于谓词公式中的自由变元可以作代入,代入时需要对公式中出现该自由变元的,每一处,进行,;,(2),用以代入的变元与原公式中所有变元的名称不能相同,.,例如对例,1,中的公式,x,(,P(x),R(x,y),),L,(x,y),自由变元,y,用,z,来代入,得,x,(,P(x),R(x,z,),),L,(x,z,),46,第二章 谓词逻辑,（,Predicate Logic,）,2.4,变元的约束,(Bound of variable,),小结：,本节介绍了,约束变元、,自由变元,的概念，,重点掌握,约束变元的,换名与,自由变元的,代入,.,作业,:P66(4)a,，（,5,）,b,47,离散数学,(,Discrete Mathematics,),48,第二章 谓词逻辑,（,Predicate Logic,）,2.1,谓词的概念与表示,(,Predicate and its expression),2.2,命题函数与量词,(Propositional functions&Quantifiers),2.3,谓词公式与翻译,(Predicate formulae,),2.4,变元的约束,(Bound of variable,),2.5,谓词演算的等价式与蕴含式,(Equivalences&,implications of p,redicate calculus,),2.6,前束范式,(Prenex normal form,),2.7,谓词演算的推理理论,(Inference theory of,p,redicate calculus,),49,第二章 谓词逻辑,（,Predicate Logic,）,2.5,谓词演算的等价式与蕴含式,2.5,谓词演算的等价式与蕴含式,(Equivalences&,implications of p,redicate calculus,),2.5.1,谓词的等价和永真的概念,2.5.2,谓词演算的等价式与蕴含式,50,第二章 谓词逻辑,（,Predicate Logic,）,2.5,谓词演算的等价式与蕴含式,2.5.1,谓词的等价和永真的概念,定义,2.5.1,:,给定任意的谓词公式,A,其个体域为,E,对于,A,的所有赋值,公式,A,都为真,则称,A,在,E,上是,永真的,(,或有效的,);,若对于,A,的所有赋值,公式,A,都为假,则称,A,在,E,上是,永假的,(,或不可满足的,);,若至少存在着一种赋值使得公式,A,为真,则称,A,在,E,上是,可满足的,.,定义,2.5.2,:,给定任何两个谓词公式,A,、,B,，设它们有共同的个体域,E,，若对,A,和,B,的任一组变元进行赋值，所得命题的真值相同，则称,谓词公式,A,和,B,在,E,上等价,，并记为,A,B,51,第二章 谓词逻辑,（,Predicate Logic,）,2.5,谓词演算的等价式与蕴含式,1,、命题公式的推广,在命题公式中成立的式子，用谓词公式去代换其中相应的命题变元，得到的公式依然成立,如：,x,(,P(x),Q(x),x,(,P(x),Q(x),P(x),Q(x),（,P(x),Q(x),）,等,2,、量词与,之间的关系,（,x,）,P(x),（,x,）,P(x),（,x,）,P(x,）,（,x,）,P(x),52,第二章 谓词逻辑,（,Predicate Logic,）,2.5,谓词演算的等价式与蕴含式,3,、量词辖域的扩张与收缩,量词辖域中如果有合取或析取项，且其中有一个是命题，则可将该命题移至量词辖域之外。如：,（,x,）,（,A(x),B,）,（,x,）,A(x),B,（,x,）,（,A(x)B,）,（,x,）,A(x),B,（,x,）,（,A(x),B,）,（,x,）,A(x),B,（,x,）,（,A(x)B,）,（,x,）,A(x),B,53,第二章 谓词逻辑,（,Predicate Logic,）,2.5,谓词演算的等价式与蕴含式,量词辖域的扩张,（,xA(x)B,）,（,x),(A(x),B,）,(,（,x)A(x),B,),(,x),(A(x)B,）,(,B (x)A(x),）,（,x),(B,A(x),）,(,B (x)A(x),),(x),(B,A(x),另有多个公式见课本,70,页,4,、量词分配等值式,设,A(x),、,B(x),是任意的含自由出现个体变元,x,的公式，则,(1),x(A(x)B(x),x A(x)x B(x),(2)x(A(x)B(x),x A(x),x B(x),(3)x(A(x)B(x)x A(x)x B(x),(4),x(A(x)B(x)x A(x)x B(x),54,第二章 谓词逻辑,（,Predicate Logic,）,2.5,谓词演算的等价式与蕴含式,小结：,本节介绍了,约束变元、,自由变元,的概念，,重点掌握,约束变元的,换名与,自由变元的,代入,.,作业,:P66(4)a,，（,5,）,b,55,离散数学,(,Discrete Mathematics,),56,第二章 谓词逻辑,（,Predicate Logic,）,2.1,谓词的概念与表示,(,Predicate and its expression),2.2,命题函数与量词,(Propositional functions&Quantifiers),2.3,谓词公式与翻译,(Predicate formulae,),2.4,变元的约束,(Bound of variable,),2.5,谓词演算的等价式与蕴含式,(Equivalences&,implications of p,redicate calculus,),2.6,前束范式,(Prenex normal form,),2.7,谓词演算的推理理论,(Inference theory of,p,redicate calculus,),57,第二章 谓词逻辑,（,Predicate Logic,）,2.6,前束范式,(Prenex normal form,),2.6,前束范式,(Prenex normal form,),2.6.1,前束范式,(Prenex normal form,),2.6.2,前束析取范式和前束合取范式,(Prenex,disjunctive normal form&Prenex,conjunctive normal form,),58,第二章 谓词逻辑,（,Predicate Logic,）,2.6,前束范式,(Prenex normal form,),2.6.1,前束范式,(Prenex normal form,),定义,2.6.1:,任何一个谓词公式,A,，如果具有如下形式：,(x,1,)(x,2,)(,x,n,)B,其中,可能是量词或量词，,x,i,（,i=1,，,n,）,是客体变,元，,B,是不含量词的,谓词公式，则称,A,是前束范式。,说明,:,前束范式,的量词,均在全式的开头,它们的作用域延伸到整个公式的末尾,。,例,1:,xy,（,F(x)G(y,),）,H(x,y,),）,xy(F(x,y)G(y,z,)x,H(x,y,z,),59,第二章 谓词逻辑,（,Predicate Logic,）,2.6,前束范式,(Prenex normal form,),定理,2.6.1:,任何一个谓词公式,均和一个前束范式等价。,前束范式的求法：,第一步：否定深入。即利用量词转化公式，把否定联结,词深入到命题变元和,谓词填式的,前面。,第二步：改名。即利用换名规则、代入规则更换一些变元的名称，以便消