第2章一阶谓词逻辑

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,离 散 数 学,孙道德、王敏生、王秀友,吴向,军 张,冬,玲,2015.03.01,第,2,章,一阶谓词逻辑,2.1,基本概念,2.2,谓词合式公式与客体变元的约束,2.3,谓词公式的等价与蕴涵,2.4,谓词逻辑的推理理论,2.5,前束范式,2.6,小结,2.1,基本概念,将下列命题符号化。,(1),麦镇豪来上离散数学课。,(2),张文亮来,上离散数学课,。,(3),集合,D,中所有学生都来,上离散,数学课，,D=,s,1,s,2,s,n,。,解：,(1) P,：麦镇豪来上离散数学课。,(2) Q,：张文亮来上离散数学课。,(,3) R(,x,),：,x,来上离散,数学课。,R(,s,1,),R(,s,2,),R(,s,n,),：集合,D,中,的所有学生都,来上,离散数学课。,R(,麦镇豪,),R(,张文亮,),客体域,客体,(,个体,),2.1,基本概念,客体：在命题中表达对象的部分。,客体常元：表示具体的客体，用具体文字，或小写字母等来表示，如：麦镇豪，张文亮，,a,，,b,1,等；,客体变元：表示泛指的客体，用小写字母，如：,x,，,y,，,x,1,等；,客体域,(,论域,),：客体变元,的取值,范围，一般用,D,来表示。如：班上所有学生。,谓词,：,含有客体变元的,命题，也,称命题函数。一般用大写字母来表示，如：,P(,x,),，,Q(,x,y,),等。,2.1,基本概念,n,元谓词：含,n,个客体变,元的,谓词,T(,x,),：,x,是教师；,M(,x,),：,x,是人；,Mortal(,y,),：,y,会死的；,Taller(,x,1,x,2,),：,x,1,比,x,2,高；,Friend(,x,y,),：,x,和,y,是朋友；,Money(,x,m,),：,x,在银行有,m,元存款；,Between(,x,y,1,y,2,),：,y,1,x,y,2,；,一元谓词,二,元谓词,三元谓词,2.1,基本概念,谓词的定义域是谓词中各客体变元论域的乘集,(,笛卡尔集,),。,假设：,D,是人的集合，,R,是实数集。,T(,x,),：,x,是教师；,Mortal(,y,),：,y,会死的；,Taller(,x,1,x,2,),：,x,1,比,x,2,高；,Firend(,x,y,),：,x,和,y,是朋友；,Money(,x,m,),：,x,在银行有,m,元存款；,Between(,x,y,1,y,2,),：,y,1,x,y,2,；,谓词的定义域：,D,谓词的定义域：,D,D=D,2,谓词的,定义域：,D,R,谓词的定义域：,R,R,R,=R,3,2.1,基本概念,复合命题函数：由有限个,简单,谓词,，,逻辑,联结词,(,、,、,、,),以及,括号,组合而成。,如：,M(,张三,),M(,李四,),Taller(,张,三,李,四,),M(,张三,),M(,李四,),Firend(,张三,李四,),Money(,张三, 10000),Money,(,李四, 1000000),Rich(,李四,),Money,(,王五, -10000),注：王五欠银行,1,万元,M(,x,),：,x,是人；,Rich(,x,),：,x,富裕；,Taller(,x,1,x,2,),：,x,1,比,x,2,高；,Firend(,x,y,),：,x,和,y,是朋友,；,Money(,x,m,),：,x,在银行有,m,元,存款。,2.1,基本概念,将,下列命题用零元谓词,符号化：,(,1) C+,和,Java,都是计算机高级程序语言。,(2),如果张明比李民高，李民比赵亮高，那么，张明比赵亮高。,解：,(1),P(,x,),：,x,是计算机高级程序,语言,。,符号化：,P(,C+,),P(,Java,),(2),H,(,x,y,),：,x,比,y,高。,符号化：,H,(,张明,李民,),H,(,李民,赵,亮,),H,(,张明,赵亮,),复合命题函数,2.1,基本概念,设：,谓词,P(,x,),，,个体域集,D,，,a,i,D,，,i,=1,2,3,。,全称量词：表示论域中的所有客体，记作：,x,；,x,P(,x,), P(,a,1,) P(,a,2,) P(,a,3,) ,存在量词：表示论域中的存在某个客体，,记作,：,x,。,x,P(,x,), P(,a,1,),P(,a,2,) ,P(,a,3,) ,设,谓词,P(,x,),和,Q(,x,),的个体域,D=,a,b,c,，消,去命题,中的量词。,x,(,R,(,x,),x,(Q(,x,),解：,x,(,R,(,x,),x,(,Q,(,x,),(,R,(,a,),R,(,b,),R,(,c,),(,Q,(,a,),Q,(,b,),Q,(,c,),(,R,(,a,),R,(,b,),R,(,c,),(,Q,(,a,),Q,(,b,),Q,(,c,),2.1,基本概念,当出现多,个,量词时,，不能随意颠倒其顺序,。,如：,(1) P(,x,y,),：,x,+,y,= 0,x,y,P(,x,y,),为真，,y,x,P(,x,y,),是假。,(2) Q(,x,y,),：,x,*,y,= 0,x,y,P(,x,y,),为真，,y,x,P(,x,y,),也为真。,2.1,基本概念,在论域为所有大学生集，符号下列语句：,(1),所有大学生都会说英语。,(2),有的大学生会说英语。,(3),不是所有大学生都会,说英语。,解：,F(,x,),：,x,会说英语。,(1),x,F(,x,),(2),x,F(,x,),(3),x,F(,x,),x,F(,x,),x,F(,x,),2.1,基本概念,在论域为所有人，符号下列语句：,(1),所有大学生都会说英语。,(2),有的大学生会说英语。,(3),不是所有大学生都会,说英语。,解：,M,(,x,),：,x,是大学生，,F(,x,),：,x,会说英语,。,(1),x,(M(,x,),F(,x,),(2),x,(M(,x,),F(,x,),(3),x,(M(,x,),F(,x,),显然，,M(,x,),是特性谓词，表达个体变元,x,所具有的特性。,所有人,大学生,2.1,基本概念,将下列命题符号化：,(1),好人,自有好报,。,(,2),有会说话的机器人。,(3),没有免费的午餐,。,(4),在北京工作的人未必都是北京人。,(5),不是,一切人都一样高。,解,(1) F(,x,),：,x,是好人,，,G(,x,),：,x,会有好,报。,(2,) M(,x,),：,x,是,机器人，,S(,x,),：,x,会说话。,(3,),L(,x,),：,x,是,午餐，,F(,x,),：,x,是免费,的。,(4,) B,(,x,),：,x,是北京人，,W(,x,),：,x,在北京,工作。,(5) H(,x,),：,x,是人,，,E(,x,y,),：,x,与,y,一样高。,x,(F(,x,),G(,x,),x,(M(,x,),S(,x,),x,(L(,x,),F,(,x,),x,(W(,x,),B(,x,),x,y,(H(,x,),H(,y,),E(,x,y,),2.1,基本概念,习 题,1,. (1,), (,2,), (,5),2. (3,), (,5,), (,6,), (,7),4.,(1), (2),2.2,谓词,合式公式与客体变元的,约束,为进行,谓词,演算和推理，先介绍一些基本的常用符号。,常元符号：,a,b,c,a,1,a,2,b,6, ,变元符号：,x,y,z,u,v,x,12,y,6,z,5, ,函数符号,：,f,g,h,f,1,g,1,h,1, ,谓词,符号,：,P,Q,R,i,其中,i,1,论域符号：,D,谓词合式公式：,wff,2.2,谓词,合式公式与客体变元的,约束,一阶谓词逻辑的项,(,1),个体常元和个体变元是项；,(2),若,f,(,x,1,x,2, ,x,n,),是任意的,n,元函数，且,(,t,1,t,2,t,n,),是任意的,n,个项，则,f,(,t,1,t,2,t,n,),是项；,(3),所有的项都是有限次,使用,(1),(2),得到的。,例如：,(1),x,1,x,2,a,b,张三等是项；,(2),g,(,a,x,1,),f,(,x,1,x,2,b,g,(,a,x,1,),等是,项。,2.2,谓词,合式公式与客体变元的,约束,设,P(,x,1,x,2, ,x,n,),是任意的,n,元谓词，,t,1,t,2, ,t,n,是,任意项,，则称,P(,t,1,t,2, ,t,n,),是原子公式,。,下列各公式都是原子公式：,F(,x,y,),R(,x,y,z,),R(,z,f,(,z,),g,(,x,y,),F(,f,(,x,1,x,2,),g,(,x,3,x,4,),x,y,是项,x,y,z,是项,z,f,(,z,),g,(,x,y,),是项,f,(,x,1,x,2,),g,(,x,3,x,4,),是项,2.2,谓词,合式公式与客体变元的,约束,谓词合式公式,(,合式公式,),(1),原子是合式公式，如：,P(,x,),；,(2),合式公式经过,逻辑联结,运算,(,、,、,、,、,),后,，也是,合式公式,，,如：,A,B,；,(3),若,A,是合式公式,，且,x,是,A,中出现的变元，那么,x,A,和,x,A,也是公式；,(4),有限,次地应用,(1)(3),形成的符号串仍是合式公式,。,如：,x,y,Q(,x,y,),(,z,P(,z,),Q(,x,y,),2.2,谓词,合式公式与客体变元的,约束,谓词,公式,X,是谓词公式,A,的一部分，则称,X,为,A,的子公式,。,子,公式,x,P(,x,),或,x,P(,x,),中,，称,x,为指导变元，,P(,x,),为相应量词的辖域。,在,x,和,x,的辖域中，,x,的所有出现都称为公式,A,的约束出现，,A,中不是约束出现,的变,元均称为自由出现,。,例谓词公式,A,：,x,(P(,x,),Q(,x,),),y,R(,x,y,),S,(,x,y,),其子,公式,有：,x,(P(,x,),Q(,x,),y,R(,x,y,),S,(,x,y,),；,在子公式,x,(P(,x,),Q(,x,),，,x,的辖域,是,P(,x,),Q(,x,),，,x,是,约束出现,；,在子,公式,y,R(,x,y,),，,y,的,辖域,是,R(,x,y,),，,y,是约束出现，,x,是自由出现,。,2.2,谓词,合式公式与客体变元的,约束,在谓词公式中，,某变元至少有一次约束出现，则称该变元为约束变元。,若某变元至少有一次自由出现，则称该变元为自由变元。,例：,x,(,x+y=,1),中，,x+y=,1,是,x,的,辖域，,x,是,约束变,元，,y,是自由变元。,在,y,R(,x,y,),S,(,x,y,),中，,x,是自由变元，,变元,y,在,y,R(,x,y,),中是约束,变元，,y,在,S,(,x,y,),中是,自由变元,。,2.2,谓词,合式公式与客体变元的,约束,有,多个相连量词时，,后量词及其辖域是前量词的辖域。,如：公式,x,y,Q(,x,y,),，,x,的辖域是,y,Q(,x,y,),。,(1),公式,x,(P(,x,),y,R(,x,y,),中，,y,的辖域是,R(,x,y,),；,x,的辖域是,P(,x,),y,R(,x,y,),。,(2),公式,x,y,(P(,x,y,),Q(,y,z,),x,P(,x,y,),中,，,y,的,辖域,是,P(,x,y,),Q(,y,z,),；,x,的辖域是,y,(P(,x,y,),Q(,y,z,),；,x,的辖域是,(,x,y,),。,2.2,谓词,合式公式与客体变元的,约束,指出下列公式的指导变元、辖域、,约束变,元和自由变元。,(1),x,(P(,x,),y,R(,x,y,),(,2),解：,(1),x,是指导变元，对应辖域为,P(,x,),y,R(,x,y,),。,y,是,指导变元，对应辖域,为,R(,x,y,),。,在,y,R(,x,y,),中，,y,是约束变元，,x,是自由变元。,在,𝒙,(P(,x,),y,R(,x,y,),中，,x,和,y,是约束变元,。,2.2,谓词,合式公式与客体变元的,约束,指出下列公式的指导变元、辖域、,约束变,元和自由变元。,(1),x,(P(,x,),y,R(,x,y,),(,2),解：,(2),x,是辖域,y,(P(,x,y,),Q(,y,z,),的指导变,元；,y,是辖域,P(,x,y,),Q(,y,z,),的指导变,元,；,在,x,y,(,P(,x,y,),Q(,y,z,),中，,x,和,y,是约束出现，,z,是自由,出现,。,x,是辖域,P(,x,y,),的指导变,元，,在,x,P(,x,y,),中，,x,是约束出现，,y,是自由出现,。,2.2,谓词,合式公式与客体变元的,约束,换名规则：在,谓词公式中，将某量词辖域中出现的某个约束变元以及对应的指导变元换为本辖域中未曾出现过的个体变元符号，其余部分保持不变，公式的等价性,不变。,如：,x,y,(P(,x,y,),Q(,y,z,), ,x,P(,x,y,),使用,换名,规则，将,y,换,u,，得：,x,u,(P(,x,u,),Q(,u,z,), ,x,P(,x,y,),2.2,谓词,合式公式与客体变元的,约束,代入规则,：,在,谓词公式中，将某个自由变元的所有出现用其中未曾出现过的某个体变元符号代替，其余部分保持不变，公式的等价性不变,。,如：,x,y,(P(,x,y,),Q(,y,z,), ,x,P(,x,y,),使用,代入规则,，将,u,代以,y,，得：,x,y,(P(,x,y,),Q(,y,z,), ,x,P(,x,u,),2.2,谓词,合式公式与客体变元的,约束,换名,规则与代入规则,区别,实施对象不同：换名对约束变元，代入对自由变元。,实施范围不同：换名只对子,公式,(,一,个量词及其,辖域,),，,代入,对整个,公式,(,整个,公式中的一个,自由变元,),。,施行后的结果,不同：换名后公式含义不变，代入后公式含义可能变化。,对,谓词公式分别使用换名规则和代入规则,：,x,(P(,x,),x,Q(,x,z,),y,R(,x,y,),Q(,x,z,),将,x,换,u,，得,：,u,(P(,u,),u,Q(,u,z,),y,R(,u,y,),Q(,x,z,),代,u,以,x,，,得,：,x,(P(,x,),x,Q(,x,z,),y,R(,x,y,),Q(,u,z,),2.2,谓词,合式公式与客体变元的,约束,谓词逻辑,的,解释,谓词,公式,A,的论域为,D,，根据,D,和,A,中的常元符号，函数符号和谓词符号按下列规则做的一组指派称为,A,的一个,解释,(,赋值,),。,每一常元符号指定,D,的一个元素。,每,一,n,元函数,指定,D,n,到,D,的一个函数。,每一,n,元谓词指定,D,n,到,真,假,的一个函数。,谓词公式中的自由变元可看作常元,。,对于,公式,A,给定一个解释,I,，则,A,在,I,下,可计算,其真值。,2.2,谓词,合式公式与客体变元的,约束,谓词公式,A=,y,(P(,y,),Q(,y,a,),B=,x,(P(,f,(,x,),Q,(x,f,(,a,),解释给定为：,D,=,2, 3,a,=2,解：,A=(P(2),Q(2,2),(P(3),Q(3,2),=(0,1) (1,1),=0,B=(P(,f,(2),Q(2,f,(2),(P(,f,(3),Q(3,f,(2),=,(P(3),Q(2,3),(P(2),Q(3,3),=(1,1),(,0,1)=1,每,一常元符号指定,D,的一个元素。,每,一,n,元函数,指定,D,n,到,D,的一个函数。,每一,n,元谓词指定,D,n,到,真,假,的一个函数。,x,P(,x,),f,(,x,),2,0,3,3,1,2,x,y,Q(,x,y,),2,2,1,2,3,1,3,2,1,3,3,1,2.2,谓词,合式公式与客体变元的,约束,设谓词公式,A=,x,y,P(,x,y,),(1),定义解释,I,1,为：,D,1,=,1,2,对于,D,1,的每个元素,x,，都存在,y,，使得,P(,x,y,)=1,。,故,A,的真值为,1,。,(2,),定义解释,I,2,为：,D,2,=,1,2,3,当,x,=1,时,，存在,y,，使得：,P(1,y,)=,1,；,当,x,=2,时,，存在,y,，使得：,P(2,y,)=1,；,当,x,=3,时，不存在,y,，使得：,P(3,y,)=1,。,故,A,的真值为,0,。,x,y,P(,x,y,),1,1,0,1,2,1,2,1,1,2,2,0,x,y,P(,x,y,),1,1,1,1,2,0,1,3,1,2,1,0,2,2,0,2,3,1,3,1,0,3,2,0,3,3,0,2.2,谓词,合式公式与客体变元的,约束,由上述例子可知：,(1) ,x,P(,x,),的,真值为,1,对于,论域,D,中的,每个,x,，都有,P(,x,)=1,。,(2) ,x,P(,x,),的,真值,为,1,在,论域,D,中存在,一,个,x,，使得,P(,x,)=1,。,2.2,谓词,合式公式与客体变元的,约束,习 题,1,. (1),(4),3.,4.,6,. (,3,),2.3,谓词,公式的等价与,蕴涵,设谓词公式,A,的论域为,D,。,(1),永,真,式,(,重言式,),若对,A,的任一,解释，其真值都为,真，则,A,在,D,上是永真的,；,若,论域,D,是,任意的，则称,A,为永真,式,(,或重言式,),。,(2),永,假,式,(,矛盾,式，或不可满足,公式,),若对,A,的任一,解释，其真值都为,假，则,A,在,D,上是永假的,；,若,论域,D,是,任意的，则称,A,为永假,式,(,或,不可满足,公式,),例：,x,P(,x,),x,P(,x,),，,永,真,式,x,P(,x,),x,P(,x,),，,永,假式,2.3,谓词,公式的等价与,蕴涵,设,谓词公式,A,和,B,有相同的论域,D,。,(1),等价,若,在,A,和,B,的任一解释,下，所得,命题的真值都相同，则称,A,和,B,在,D,上等价。记作,：,A,B,。,(2),蕴涵,若,在,A,和,B,的任一解释下,，,A,的真值,为,1,时,，,B,的,真值,也为,1,，则称,A,蕴涵,B,。记作,：,A,B,。,即,：在,D,上,A,B,是重言式,。,如：,x,(,P(,x,), Q,(,x,),x,(,P(,x,),Q,(,x,),2.3,谓词,公式的等价与,蕴涵,论域,D,是班上所有学生的集合。,P(,x,),：,x,的成绩,90,P(,x,),：,x,的,成绩不大于等于,90,x,P(,x,),：,班,上所有学生的成绩都大于等于,90,x,P(,x,),：,班上有人学生的成绩大于等于,90,x,P(,x,),：不是,“,班,上所有学生的成绩都大于等于,90”,，也就是说，班上有,学生的,成绩不大于,等于,90,，即：,x,P(,x,),。,x,P(,x,),：不是,“,班,上有人学生的成绩大于等于,90”,，也就是说，,班,上所有学生,的,成绩都不,大于等于,90,，即,：,x,P(,x,),。,2.3,谓词,公式的等价与,蕴涵,定理,2.1,量词与否定联结词的关系为,：,(,x,P,(,x,) ,x,(P(,x,),(,x,P(,x,) ,x,(P(,x,),2.3,谓词,公式的等价与,蕴涵,定理,2.2,量词辖域扩张与收缩关系为：,(1),x,(P(,x,),Q,), ,x,P(,x,),Q,(2),x,(P(,x,),Q,), ,x,P(,x,),Q,(3),x,(P(,x,),Q,), ,x,P(,x,),Q,(4,),x,(P(,x,),Q,), ,x,P(,x,),Q,(5),(,Q,x,P(,x,), ,x,(Q,P(,x,),(6,),(Q,x,P(,x,), ,x,(Q,P(,x,),(7),(,x,P(,x,),Q,),x,(P(,x,),Q),(8),(,x,P(,x,),Q,),x,(P(,x,),Q,),扩张,收缩,2.3,谓词,公式的等价与,蕴涵,定理,2.3,量词与逻辑联结词,，,有,下列基本等价,式,：,(9),x,P(,x,),x,Q(,x,),x,(P(,x,),Q(,x,),(,10),x,P(,x,),x,Q(,x,),x,(P(,x,),Q(,x,),定理,2.4,量词与逻辑,联结词,有,下列基本等价式,：,(11),x,(P(,x,),Q(,x,),x,P(,x,), ,x,Q(,x,),2.3,谓词,公式的等价与,蕴涵,定理,2.5,量词,与逻辑联结词有下列基本蕴涵式,：,(12,) ,x,P(,x,),x,Q(,x,) ,x,(P(,x,),Q(,x,),(,13,) ,x,(P(,x,),Q(,x,),x,P(,x,),x,Q(,x,),(,14),x,(P(,x,),Q(,x,) ,x,P(,x,),x,Q(,x,),(,15,),x,P(,x,),x,Q(,x,) ,x,(P(,x,),Q(,x,),(16),x,(P(,x,), Q(,x,) ,x,P(,x,),x,Q(,x,),2.3,谓词,公式的等价与,蕴涵,定理,2.6,两个量词的等价与蕴涵关系：,等价式,(1),x,y,A(,x,y,),y,x,A(,x,y,),(2),x,y,A(,x,y,),y,x,A(,x,y,),蕴涵式,(3),x,A(,x,y,),x,y,A(,x,y,),(4),A(,x,y,),y,x,A(,x,y,),(5),x,y,A(,x,y,),y,x,A(,x,y,),(6),x,A(,x,y,),x,y,A(,x,y,),A(,x,y,),x,y,A(,x,y,),(8),A(,x,y,),y,x,A(,x,y,),(9),A(,x,y,),x,y,A(,x,y,),多个量词名相同可交换,量词,名不变,量词,名有变,2.3,谓词,公式的等价与,蕴涵,证明：,x,y,A(,x,y,),x,y,A(,x,y,),证：,x,y,A(,x,y,),x,y,A(,x,y,), ,x,y,A(,x,y,),x,y,A(,x,y,),x,y,A(,x,y,) ,x,y,A(,x,y,),x,(,y,A(,x,y,) ,y,A(,x,y,),x,(T),T,故,，,x,y,A(,x,y,) ,x,y,A(,x,y,),成立,。,等价式,定理,2.1,定理,2.3(10),排中律,2.3,谓词,公式的等价与,蕴涵,证明：,x,y,(P(,x,)Q(,y,),x,P(,x,) ,y,Q(,y,),证：,x,y,(P(,x,)Q(,y,),x,(P(,x,),y,Q(,y,),x,P(,x,),y,Q(,y,),故，,x,y,(P(,x,)Q(,y,),x,P(,x,) ,y,Q(,y,),成立。,定理,2.2(5),定理,2.2(7),2.3,谓词,公式的等价与,蕴涵,判断下列推证是否正确。,x,(P(,x,),Q(,x,),x,(,P(,x,) Q(,x,),x,(P(,x,), Q(,x,),x,(P(,x,) Q(,x,),(,x,P(,x,) ,x,Q(,x,),(,x,P(,x,) ,x,Q(,x,),x,P(,x,), ,x,Q(,x,),x,P(,x,),x,Q(,x,),，,条件等价式,，,德摩根律,，,定理,2.1,，不符合,定理,2.3,2.3,谓词,公式的等价与,蕴涵,习 题,2,.,(2),(3),(4,),2.4,谓词逻辑,的推理,理论,设,x,是谓词合式公式,A,的一个客体变元。若以,y,代替,x,后不产生变元的新约束变元，则称,A(,x,),关于,y,是自由的。,定理,2.7,(,全称量词,消去规则，,US),如果,x,A(,x,),为真,，则对于论域中的任一具体成员,a,1,，可得,A(,a,1,),为真。,即：,x,A(,x,),A(,y,),定理,2.8(,存在量词,消去规则，,ES),如果,x,A(,x,),为真，,则可得出在论域中,至少,存在一个,具体成员,c,，使得,A(,c,),为真。,即,：,x,A(,x,),A(,c,),2.4,谓词逻辑,的推理,理论,定理,2.9(,存在量词,引入规则,，,EG),对于,论域,里的某个元素,c,，都有,A(,c,),为真，则可,得出,x,A(,x,),为真。,即：,A(,c,),x,A(,x,),，某个,c,定理,2.10,(,全称量词,引入规则，,UG),对于,论域里所有元素,c,，都有,A(,c,),为真，则可得出,x,A(,x,),为真。,即,：,A(,c,),x,A(,x,),，任意,c,2.4,谓词逻辑,的推理,理论,推理：从前提为真，推得结论为真。,在谓词逻辑中进行推理，,可使用下列规则：,P,规则,：,使用,前提；,T,规则,：,使用,前面已演绎公式的逻辑,结果,(,用,等价式记为,TE,，用蕴涵式记为,TI,),；,CP,规则,：,用,已有的结果,B,和,BC,，演绎出结果,C,；,US,规则,：,去,x,；,ES,规则,：,去,x,；,UG,规则：加,x,；,EG,规则：加,x,。,2.4,谓词逻辑,的推理,理论,例：在本离散数学课堂的每一个人学过一门计算机课程，张洁杰是,本离散数学课堂,的学生。可推得张,洁,杰,学过一门计算机,课程。,解：设,D(,x,):,x,在,本离散数学,课堂，,C(,x,):,x,学过一门计算机,课程。,“,本,离散数学课堂的每一个人学过一门计算机,课程,”,可,表示为,x,(D(,x,),C(,x,),。,(1),x,(D(,x,),C(,x,),(2) D(,张洁杰,),C,(,张洁杰,),(,3) D(,张洁杰,),(,4) C(,张洁杰,),前提引入,US(1),前提引入,假言推理,(2)(3),前提,结论,2.4,谓词逻辑,的推理,理论,证明,蕴涵式,x,(P(,x,),Q(,x,),x,P(,x,),x,Q(,x,),证明一：使用,推理规则演绎如下：,(,x,P(,x,),x,Q(,x,),(,x,P(,x,) (,x,Q(,x,),(,x,P(,x,),x,(P(,x,),P(,a,),(,x,Q(,x,),x,(Q(,x,),Q(,a,),P(,a,),Q(,a,),(P(,a,),Q(,a,),x,(P(,x,),Q(,x,),P(,a,) Q(,a,),F,故,x,(P(,x,),Q(,x,),x,P(,x,), ,x,Q(,x,),成立。,P (,附加前提,),TE(1,),TI(2,),TE(3,),ES(4),TI(2,),TE(6),ES(7,),IT(5,)(8),TE(9,),P,US(,11,),TE(10,)(12),2.4,谓词逻辑,的推理,理论,证明,蕴涵式,x,(P(,x,),Q(,x,),x,P(,x,),x,Q(,x,),证明二：,x,P(,x,), ,x,Q(,x,), (,x,P(,x,),),x,Q(,x,),原问题可改为：,x,(P(,x,),Q(,x,),(,xP(x),) ,xQ(x),使用,CP,规则演绎如下：,(,x,P(,x,),),x,(,P(,x,),),(,P(,a,),),x,(P(,x,),Q(,x,),P(,a,),Q(,a,),Q(,a,),xQ(x),由,CP,规则可知，,。,成立。,P,(,附加前提,),TE(1,),ES(2),P,ES(4),TI(3,)(5),EG(6),2.4,谓词逻辑,的推理,理论,例,每一个出席会议的代表都是经理且是女性。有一些代表是有代表性的人。所以，有一些具有代表性的女性代表,。,解,：,命题,符号化,个体,域,D,取全总个体域。,F,(,x,),：,x,是参加会议的代表,；,G,(,x,),：,x,是经理；,H,(,x,),：,x,是,女性,；,R,(,x,),：,x,是有代表性的人。,前提,：,x,(F(,x,),G(,x,),H(,x,),，,x,(F(,x,),R(,x,),结论,：,x,(F(,x,),R(,x,),H(,x,),2.4,谓词逻辑,的推理,理论,例 每,一个出席会议的代表都是经理且是女性。有一些代表是有代表性的人。所以，有一些具有代表性的女性代表,。,解,：,证明,x,(F(,x,),R(,x,),F(,a,),R(,a,),x,(F(,x,),G(,x,),H(,x,),F(,a,),G(,a,),H(,a,),F(,a,),G(,a,),H(,a,),H(,a,),F(,a,),R(,a,),H(,a,),x,(F(,x,),R(,x,),H(,x,),前提,：,x,(F(,x,)G(,x,),H(,x,),，,x,(F(,x,),R(,x,),结论：,x,(F(,x,),R(,x,),H(,x,),P,ES(1,),P,US(3,),TE(2,),TE(4,)(5),TE(6,),TE(2,)(7),EG(8),2.4,谓词逻辑,的推理,理论,习 题,2,. (1,), (,4),4. (1),2.5,前束范式,若谓词公式,A,可表示为：,，其中,Q,i,x,i,表示,x,i,或,x,i,，,i,=1,2,3, ,，,G,是不含量词的谓词公式，则称公式,A,为,前束范式。,也就是说：将,谓词公式中的所有量词放在公式的前部,。,(1),如果,G,是合取范式，则称,A,为前束合取范式,。,(2),如果,G,是析取范式，则称,A,为前束析取范式。,例：,x,y,(P(,x,),Q(,y,),前束范式,x,P(,x,),y,Q(,y,),非前束范式,x,y,(P(,x,y,),Q(,x,),前束,合,取,范式,x,(P(,x,),Q(,x,),前束,析取,范式,2.5,前束范式,定理,2.11(,前束范式存在定理,),任何,一个谓词公式都有一个与它等价的前束范式。,例：,(,z,(P(,x,z,),P(,y,z,),u,Q(,x,y,u,),(,P(,x,z,), P(,y,z,),u,Q(,x,y,u,),u,(,P(,x,z,), P(,y,z,),Q(,x,y,u,),u,(,P(,x,z,), P(,y,z,),Q(,x,y,u,),u,(P(,x,z,), P(,y,z,) Q(,x,y,u,),定理,2.2,(7),定理,2.2,(6),，前束,前束析取范式,2.5,前束范式,求,前束范式的步骤,消去公式中包含,的,“,”,，,“,”,；,反复运用德摩根定律，,将,“,”,内移,到原子谓词公式的前端；,如果需要，将约束变元进行换名；,使用谓词的等价公式将所有量词提到公式的最前端。,例：,P(,x,),Q(,z, y,),(,R(,x,y,),P(,x,) ,Q(,z, y,),(,R(,x,y,),P(,x,) ,Q(,z, y,),(,R(,x,u,),P(,x,) Q(,z, y,),(,R(,x,u,),u,(,P(,x,) Q(,z, y,),(R(,x,u,),u,(P(,x,) ,Q(,z, y,),),R(,x,u,),去掉,定理,2.2(6),，前束,前束析取范式,2.5,前束范式,例 求前束范式,P(,x,),Q(,z, y,),(,R(,x,y,),P(,x,) ,Q(,z, y,),(,R(,x,),P(,x,) ,Q(,z, y,),(,R(,x,u,),P(,x,) Q(,z, y,),(,R(,x,u,),u,(,P(,x,) Q(,z, y,),(R(,x,u,),u,(P(,x,) ,Q(,z, y,),),R(,x,u,),u,(,P(,x,) R(,x,u,) (Q(,z, y,),R(,x,u,),由本例知：谓词公式的前束范式,不,惟一。,注意：题词的顺序不能随便变动。,去掉,，换元,定理,2.2(1),，定理,2.1,定理,2.2(8),(6),前束范式,前束析取范式,前束合取范式,2.5,前束范式,习 题,1,. (1,), (,2),2.6,小结,(1),谓词逻辑命题符号化,个体词，谓词，量词,(2),谓词,公式,项，原子公式，,合式公式,(,谓词公式,),指导,变元，辖域，约束出现，自由出现,谓词公式的,解释,谓词逻辑,的分类：永真式，永假,式和满足,式,(3),谓词逻辑,的,等价、蕴含关系,(4,),谓词逻辑推理：,USES,，,UGEG,规则,(5),谓词,公式的,标准化：前束范式,