离散数学第2章一阶逻辑

*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第2章 一阶逻辑,一阶逻辑基本概念、命题符号化,一阶逻辑公式、解释及分类,一阶逻辑等值式、前束范式,一阶逻辑推理理论,1,例,“苏格拉底三段论”,人都是要死的.(p),苏格拉底是人.(q),所以苏格拉底是要死的.(r),在命题逻辑中，推理的形式结构：,（,p,q,）,r,(,不是重言式,),原因：,命题逻辑中，,p,、,q,、,r,之间的内在联系没有反映出来.,方法：,反映,p,、,q,、,r,内在联系，对简单命题进一步分析.,2,2.1 一阶逻辑基本概念,个体词,谓词,量词,一阶逻辑中命题符号化,3,基本概念个体词、谓词、量词,个体词（个体）,:所研究对象中可以独立存在的具体或抽象的客体，它可以是一个具体的事物，也可以是一个抽象的概念.表示主语的词（名词或代词）：苏格拉底，2，黑板，自然数，思想，定理.,个体常项,：具体的或特定的个体词，,用,a,b,c,表示,个体变项,：抽象的或泛指的个体词，,用,x,y,z,表示,个体域,:个体变项的取值范围,有限个体域,，如,a,b,c,1,2,无限个体域,，如,N,Z,R,全总个体域,:宇宙间一切事物组成,4,基本概念(续),谓词,:表示个体词的性质或相互之间关系的词,谓词常项,：表示具体性质或关系的谓词,F,:是人，,F,(,a,)：,a,是人,G：,是自然数，,F,(2)：2是自然数,谓词变项,：表示抽象的或泛指的谓词,F,:具有性质,F,，,F,(,x,)：,x,具有性质,F,元数,：谓词中所包含的个体词数,一元谓词,:表示事物的性质,多元谓词(,n,元谓词,n,2),:表示个体词之间的关系,如,L,(,x,y,)：,x,与,y,有关系,L,，,L,(,x,y,)：,x,比,y,高2厘米,注意：多元谓词中，个体变项的顺序不能随意改动,5,个体变项和谓词的联合体，,F(x),L(x,y)，,也称为,谓词,n元谓词,L(x,1,x,2,x,n,),可看作一个函数,，,定义域为个体变项的个体域，值域为0,1,n元谓词,L(x,1,x,2,x,n,),的真值不确定，不是命题,如：,L(x,y),如果,L(x,y)表示“x小于y”，,谓词部分已经是常项，但,还不是命题.,考虑,L(2,3)和L(3,2),L(x,1,x,2,x,n,),是命题：,只有当L是常项，x,1,x,2,x,n,是个体常项,0元谓词,:不含个体变项的谓词,如,L(a,b),如,L,的意义明确，则,0元谓词,都是命题,6,一阶逻辑中命题符号化,例1 用0元谓词将命题符号化,要求：先将它们在命题逻辑中符号化，再在一阶,逻辑中符号化,(1)墨西哥位于南美洲,在命题逻辑中,设,p,:,墨西哥位于南美洲,符号化为,p,这是真命题,在一阶逻辑中,设,a,：墨西哥，,F,(,x,)：,x,位于南美洲,符号化为,F,(,a,),7,例1(续),(2)是无理数仅当 是有理数,在命题逻辑中,设,p,：是无理数，,q,：是有理数.,符号化为,p,q,这是假命题,在一阶逻辑中,设,F,(,x,):,x,是无理数,G,(,x,):,x,是有理,数符号化为,(3)如果23，则33，,q,：3,y,，,G,(,x,y,)：,x,y,x,(,F,(,x,),y,(,G,(,y,),L,(,x,y,)或,x,y,(,F,(,x,),G,(,y,),L,(,x,y,)两者等值,(2)令,F,(,x,):,x,是无理数,G,(,y,):,y,是有理数,L,(,x,y,)：,x,y,x,(,F,(,x,),y,(,G,(,y,),L,(,x,y,),或 ,x,y,(,F,(,x,),G,(,y,),L,(,x,y,)两者等值,13,一阶逻辑中命题符号化(续),几点注意：,1元谓词与多元谓词的区分,无特别要求，用全总个体域,量词顺序一般不要随便颠倒,例：对任意x，存在着y，使得x+y=5.个体域为实数集.,符号化为：,x,y H,（,x,y,),其中,H,（,x,y,):,x,+,y,=5,考虑,y,x H,（,x,y,),否定式的使用,14,例：在一界逻辑中命题符号化,没有不呼吸的人,不是所有的人都喜欢吃糖,不是所有的火车都比所有的汽车快,x,(,F,(,x,),G,(,x,),其中,F,(,x,)：,x,是人，,G,(,x,)：,x,呼吸,或者：,x,(,F,(,x,),G,(,x,),x,(,F,(,x,),G,(,x,),其中,F,(,x,)：,x,是人，,G,(,x,)：,x,喜欢吃糖,或者：,x,(,F,(,x,),G,(,x,),x,(,F,(,x,),y,(,G,(,y,),H(,x,y,),),或者：,x,(,F,(,x,),y,(,G,(,y,),H(,x,y,),),),15,例：在一界逻辑中命题符号化,一切人都不一样高,每个自然数都有后继数,有的自然数无先驱数,x,y,(,F,(,x,),F,(,y,),G(,x,y,),H,(,x,y,),),其中,F,(,x,)：,x,是人，,G(,x,y,):,x,和,y,不是同一个人，,H,(,x,y,)：,x,和,y,一样高,或者：,x,y,(,F,(,x,),F,(,y,),G(,x,y,),H,(,x,y,),),x,(,F,(,x,),y,(,G,(,y,),H,(,x,y,),),其中,F,(,x,)：,x,是自然数，,H,(,x,y,),：,y,是,x,的后继数,或者：,x,(,F,(,x,),L,(,x,)，,L,(,x,)：,x,有后继数,x,(,F,(,x,),y,(,G,(,y,),H,(,x,y,),),或者：,x,(,F,(,x,),L,(,x,),)，,L,(,x,)：,x,有先驱数,16,2.2 一阶逻辑公式及解释,字母表,合式公式,(,简称公式,),个体变项的自由出现和约束出现,解释,永真式（逻辑有效式）,矛盾式（永假式）,可满足式,17,字母表,定义 字母表,包含下述符号：,(1)个体常项：,a,b,c,a,i,b,i,c,i,i,1,(2)个体变项：,x,y,z,x,i,y,i,z,i,i,1,(3)函数符号：,f,g,h,f,i,g,i,h,i,i,1,(4)谓词符号：,F,G,H,F,i,G,i,H,i,i,1,(5)量词符号：,(6)联结词符号：,(7)括号与逗号：(,),，,18,项,定义 项,的定义如下：,(1)个体常项和个体变项是项.,(2)若,(,x,1,x,2,x,n,)是任意的,n,元函数，,t,1,t,2,t,n,是任意的,n,个项，则,(,t,1,t,2,t,n,)是项.,(3)所有的项都是有限次使用(1),(2)得到的.,例：,a，b，x，y，f,(,x,y,)=,x,+,y，g,(,x,y,)=,x-y,都是项,f,(,a,g,(,x,y,)=,a,+(,x-y,)是项,其实,个体常项、变项是项，由它们构成的,n,元函数,和复合函数还是项,19,原子公式,定义,设,R,(,x,1,x,2,x,n,)是任意的,n,元谓词，,t,1,t,2,t,n,是任意的,n,个项，则称,R,(,t,1,t,2,t,n,)是,原子公式,.,其实，原子公式是由项组成的,n,元谓词.,例如，,F,(,x,y,),F,(,f,(,x,1,x,2,),g,(,x,3,x,4,)等均为原子公式,20,合式公式,定义 合式公式,（简称,公式,）定义如下：,(1)原子公式是合式公式.,(2)若,A,是合式公式，则(,A,)也是合式公式,(3)若,A,B,是合式公式，则(,A,B,),(,A,B,),(,A,B,),(,A,B,)也是合式公式,(4)若,A,是合式公式，则,xA,xA,也是合式公式,(5)只有有限次地应用(1)(4)形成的符号串,才是合式公式(,谓词公式),.,21,个体变项的自由出现与约束出现,定义,在公式,xA,和,xA,中，称,x,为,指导变元,，,A,为相,应量词的,辖域,.在,x,和,x,的,辖域,中，,x,的所有出现都,称为,约束出现,，,A,中不是约束出现的其他变项均称,为是,自由出现的,.,例如,在公式,x,(,F,(,x,y,),G,(,x,z,)中,A,=(,F,(,x,y,),G,(,x,z,)为,x,的辖域，,x,为指导变项,A,中,x,的两次出现均为约束出现，,y,与,z,均为自由出现.,闭式,:不含自由出现的个体变项的公式.,22,例1：,x,(,F,(,x,),y,H,(,x,y,),y,H,(,x,y,),中，,y,为,指导变项，的辖域为,H,(,x,y,)，,其中,y,为,约束出现的，,x,为,自由出现的.,在整个合式公式中，,x,为指导变项，,的辖域为,(,F,(,x,),y,H,(,x,y,)，,其中,x,与,y,都是约束出现的，,x,约束出现2次，,y,约束出现1次,.,例2：,x,y,(,R,(,x,y,),L,(,y,z,),x,H,(,x,y,),x,y,(,R,(,x,y,),L,(,y,z,),中，,x,y,都是指导变项,，,辖域为,(,R,(,x,y,),L,(,y,z,)，,x,与,y,都是约束出现的，,z,为,自由出现的.,x,H,(,x,y,),中，,x,为指导变项，的辖域为,H,(,x,y,)，,其中,x,为约束出现的，,y,为自由出现的,在此公式中，,x,为约束出现的，,y,为约束出现的，又为自由出现的,.,z,为,自由出现的.,23,换名规则,将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成另一个辖域中未出现过的个体变项符号，公式中的其余部分不变。,例：,xF,(,x,),G,(,x,y,),换名规则：,zF,(,z,),G,(,x,y,),代替规则,将某个自由出现的个体变项及对应的指导变项，改成公式中未出现过的个体变项符号，处处代替。,代替规则：,xF,(,x,),G,(,z,y,),用处：不存在既是约束出现，又是自由出现的个体变项,24,公式的解释与分类,给定公式,A,=,x,(,F,(,x,),G,(,x,),成真解释,:个体域,N,F,(,x,),:,x,2,G,(,x,):,x,1,代入得,A,=,x,(,x,2,x,1)真命题,成假解释,:个体域,N,F,(,x,),:,x,1,G,(,x,):,x,2,代入得,A,=,x,(,x,1,x,2)假命题,问:,xF,(,x,),x,F,(,x,)有成真解释吗？,xF,(,x,),x,F,(,x,)有成假解释吗？,25,解释,定义,解释,I,由下面4部分组成：,(a)非空个体域,D,I,(b),D,I,中一些特定元素,(c),D,I,上特定函数集合,(d),D,I,上特定谓词的集合,说明：,1 将公式的个体常项用,I,的特定常项代替，函数和谓词用,I,的特定函数和 谓词代替,2 被解释的公式不一定全部包含解释中的4部分.,3 闭式在任何解释下都是命题，,4 不是闭式的公式在某些解释下也可能是命题.,26,例 给定解释,I,：,(a),D,I,2,3,(b),D,I,中特定元素,a,=2,(c),D,I,上特定函数,f,(,x,):,f,(2)=3,f,(3)=2,(d),D,I,上特定谓词F(,x,):,F,(2)=0,F,(3)=1，,G(,x,y,)为G(,i,j,)=1,其中,i,j=2,3,1）,x,（,F,(,x,),G(,x,a,),（,F,(2),G(2,2),（,F,(3),G(3,2),(0,1)(1 1),0,假命题,2),x,(,F,(,f,(,x,),G(,x,f,(,x,),(,F,(,f,(2),G(2,f,(2),(,F,(,f,(3),G(3,f,(3),(,F,(3),G(2,3),(,F,(2),G(3,2),(1,1,),(0,1),1,真命题,27,例 给定解释：,(a)个体域为自然数集合,D,N,(b),D,N,中特定元素,a,=0,(c),D,N,上特定函数,f