离散数学 第三章 一阶逻辑.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第三章 一阶逻辑,1,一阶逻辑基本概念,一阶逻辑命题符号化,一阶逻辑公式、解释,2,谓词逻辑（一阶逻辑）的引入,著名的三段论论证：,所有的人都将死去。,苏格拉底是人。,所以：苏格拉底将死去。,从人们的实践经验可知，这是一个有效的推论。,但在命题逻辑中却无法判断它的正确性。,因为在命题逻辑中只能将推理中的三个简单命题符号化为,p,q,r,，那么由,p,q,这两个命题无论如何不可能得出,r,为有效结论。,3,3.1,一阶逻辑基本概念,个体词,谓词,量词,一阶逻辑中命题符号化,一阶逻辑公式与分类,4,基本概念,个体词、谓词、量词,个体词（个体）,:,所研究对象中可以独立存在的具,体或抽象的客体,个体常项,：具体的事务，用,a,b,c,表示,个体变项,：抽象的事物，用,x,y,z,表示,个体域（论域）,:,个体变项的取值范围,有限个体域,，如,a,b,c,1,2,无限个体域,，如,N,Z,R,全总个体域,:,宇宙间一切事物组成,如果事先没有给出个体域，都应以全总个体域为个体域。,5,基本概念,(,续,),谓词,:,刻划个体词性质或相互之间关系的词,谓词常项,：表示具体性质和关系的谓词，用,F,G,H,表示；,谓词变项,：表示抽象或泛指的谓词，也用,F,G,H,表示；,一元谓词,:,表示事物的性质,多元谓词,(,n,元谓词,n,2),:,表示事物之间的关系,如,L,(,x,y,),：,x,与,y,有关系,L,，,L,(,x,y,),：,x,y,，,0,元谓词,:,不含个体变项的谓词,即命题常项或命,题变项,6,实例,(1)4,是偶数,4,是个体常项,“,是偶数”是谓词常项,符号化为,:,F,(4),(2),小王和小李同岁,小王,小李是个体常项,同岁是谓词常项,.,记,a,:,小王,b,:,小李,G,(,x,y,):,x,与,y,同岁,符号化为,:,G,(,a,b,),(3),x y,x,y,是命题变项,3,，则,3,y,，,G,(,x,y,),：,x,y,符号化为,F,(2,3),G,(3,4),9,将下列命题符号化,并讨论其真值,:,(1),对任意的,x,均有,x,2,-3,x,+2=(,x,-1)(,x,-2),(2),存在,x,使得,x,+5=3,分别取,(,a),个体域,D,1,=N,(b),个体域,D,2,=R,解 记,F,(,x,):,x,2,-3,x,+2=(,x,-1)(,x,-2),G,(,x,):,x,+5=3,(a)(1),x F,(,x,),真值为,1,(2),x G,(,x,),真值为,0,(,b)(1),x F,(,x,),真值为,1,(2),x G,(,x,),真值为,1,10,基本概念,(,续,),量词,:,表示数量的词,全称量词,:,表示任意的,所有的,一切的等,如,x,表示对个体域中所有的,x,存在量词,:,表示存在,有的,至少有一个等,如,x,表示在个体域中存在,x,11,一阶逻辑中命题符号化,(,续,),例,2,在一阶逻辑中将下面命题符号化,(1),人都爱美,;(2),有人用左手写字,分别取,(,a,),D,为人类集合,(,b,),D,为全总个体域,.,解：,(a)(1),设,G(x),：,x,爱美,符号化为,x G,(,x,),(2),设,G,(,x,),：,x,用左手写字,符号化为,x G,(,x,),(,b,),设,F,(,x,),：,x,为人，,G,(,x,),：同,(,a,),中,(1),x,(,F,(,x,),G,(,x,),(2),x,(,F,(,x,),G,(,x,),这是两个基本公式,注意这两个基本公式的使用,.,在这里是,F,(,x,),特性谓词,12,几点注意：,1.,谓词的记法,设论域,A,中元素,a,b,c A,满足关系,P,Q,R,，记作,P(a),Q(a,b),R(a,b,c,).,不满足关系记作,P(a,),Q(a,b,),R(a,b,c,).,一阶逻辑命题符号化,例 将下列命题符号化,:,李明是位大学生,.,解,:,S(x):x,是位大学生；,c:,李明,则该命题符号化为,S(c,),13,例,:,若,x,的论域为某大学的全体学生，则,S(x,),为真；,若,x,的论域为某中学的全体学生，则,S(x,),为假；,若,x,的论域为某剧场中的观众，则,S(x,),真值不确定；,2.,个体变元在哪些论域取特定的值，,对命题的真值有影响。,14,例 将下列命题符号化,:,(1),小李比小赵高,.,(2),武汉位于北京和广州之间,3.,个体变项的顺序影响命题真值，不能随意调换,.,解,(1),L(x,y):x,比,y,高；,a:,小李；,b:,小赵,则该命题符号化为,L(a,b,),(2),P(x,y,z):x,位于,y,和,z,之间；,a:,武汉,;b:,北京,;,c:,广州,则该命题符号化为,P(a,b,c,),15,例：将命题符号化,:,凡有理数均可表成分数,(1),个体域是有理数集合,.,(2),个体域是实数集合,4.,在不同的个体域中,命题符号化的形式可能不一样,解,(1)xA(x),其中,A(x,),：,x,可表成分数,(2)x(,R(x)A(x,),其中,R(x,),：,x,是有理数，,A(x,),：,x,可表成分数,16,5.,在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的。,例将命题符号化,:(1),每个自然数都是实数,.,(2),有的自然数是实数,.,解,(1),x(N(x,),R(x,),其中特性谓词,N(x,),：,x,是自然数,;,R(x,),：,x,是实数,(2),x(N(x,),R(x,),其中特性谓词,N(x,),：,x,是自然数,;,R(x,),：,x,是实数,17,例：对任意的,x,，存在着,y,使得,x+y,=5,个体域为实数集，其中,H(x,y,),：,x+y,=5,，,xyH(x,y,),真命题,如果颠倒量词的顺序，,yxH(x,y,),假命题,意为“存在着,y,，对任意的,x,，都有,x+y,=5”,，意义不符、假命题。,6.,多个量词同时出现时,不能随意颠倒它们的顺序，颠倒后会改变原命题的含义,.,18,一阶逻辑中命题符号化,(,续,),例,3,在一阶逻辑中将下面命题符号化,(1),兔子比乌龟跑得快,(2),有的兔子比所有的乌龟跑得快,（,3,）并不是所有的兔子都比乌龟跑得快,（,4,）不存在跑得同样快的两只兔子,19,一阶逻辑中命题符号化,(,续,),解 用全总个体域,令,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,),20,3.1.4,一阶逻辑公式及分类,字母表,合式公式,(,简称公式,),个体变项的自由出现和约束出现,解释,永真式（逻辑有效式）,矛盾式（永假式）,可满足式,21,字母表,定义 字母表,包含下述符号：,(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),括号与逗号：,(,),，,22,字母表中的函数,是广义的函数，它是一个从个体到个体的映射。,例,1.,f(x,y,),表示,x-y,f(7,4),表示个体自然数,3,例,2.,函数,f(x,),：,x,的母亲,c:,张明,谓词,P(x,),：,x,是教师，则,P(,f(c,),：张明的母亲是教师。,23,项,定义 项,的定义如下：,(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),得到的,.,其实,个体常项、变项是项，由它们构成的,n,元函数,和复合函数还是项,24,原子公式,定义,设,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,),等均为原子公式,25,合式公式,定义 合式公式,（,谓词公式,，简称,公式,）定义如下：,(1),原子公式是合式公式,.,(2),若,A,是合式公式，则,(,A,),也是合式公式,(3),若,A,B,是合式公式，则,(,A,B,),(,A,B,),(,A,B,),(,A,B,),也是合式公式,(4),若,A,是合式公式，则,xA,xA,也是合式公式,(5),只有有限次地应用,(1)(4),形成的符号串,才是合式公式,.,请举出几个合式公式的例子,.,26,个体变项的自由出现与约束出现,定义,在公式,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,均为自由出现,.,闭式,(,封闭的公式,),:,不含自由出现的个体变项的公式,.,27,例,3,1.,x(x+1=0),量词的辖域是全公式。,x,是约束变元,2.,x(x,+y+10),量词的辖域是全公式。,x,是约束变元,y,是自由变元,3.,x(x+y+1=0 y(x+y+10),的辖域是,(x+y+12,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,),有成假解释吗？,29,解释,定义,解释,I,由下面,4,部分组成：,(a),非空个体域,D,I,(b),D,I,中一些特定元素的集合,(c),D,I,上特定函数集合,(d),D,I,上特定谓词的集合,说明：,在解释的定义中引进了元语言符号,如 等,被解释的公式,A,中的个体变项均取值于,D,I,若,A,中含个体常项,a,i,，,就解释成,30,解释,(,续,),为第,i,个,n,元谓词,.,例如，表示第,2,个,3,元谓词，它可能以 形式出现在解释中，公式,A,中若出现,F,2,(,x,y,z,),就解释成,为第,i,个,n,元函数,.,例如，表示第一个二元函数,它出现在解释中，可能是,=2,xy,等，一旦公式中出现,f,1,(,x,y,),就解释成,出现,g,1,(,x,y,),就解释成,31,解释,(,续,),例,4,给定解释,I,如下,:,(,a,),个体域,D,=,N,(,b,),(,c,),(,d,),谓词,说明下列公式在,I,下的涵义,并讨论真值,(1),xF,(,g,(,x,a,),x,),x,(2,x=x,),假命题,(2),x,y,(,F,(,f,(,x,a,),y,),F,(,f,(,y,a,),x,),x,y,(,x+,2=,y,y,+2=,x,),假命题,32,例,1,(续),(3),x,y,zF,(,f,(,x,y,),z,),两点说明,:,5,个小题都是闭式,在,I,下全是命题,(3),与,(5),说明，量词顺序不能随意改变,(5),x,y,zF,(,f,(,y,z,),x,),x,y,z,(,y+z,=,x,),假命题,(4),xF,(,f,(,x,x,),g,(,x,x,),x,(2,x,=,x,2,),真命题,x,y,z,(,x+y,=,z,),真命题,33,解释,(,续,),被解释的公式不一定全部包含解释中的,4,部分,.,闭式在任何解释下都是命题，,注意不是闭式的公式在某些解释下也可能是命题,.,34,公式的分类,永真式（逻辑有效式）,：无成假赋值,矛盾式（永假式）,：无成真赋值,可满足式,：至少有一个成真赋值,几点说明：,永真式为可满足式，但反之不真,判断公式是否为可满足式不是易事,(,不同于命题逻辑,),某些特殊公式可以判断类型,35,代换实例,(,续,),例,5,证明下面公式既不是永真式，也不是矛盾式,(1),x,(,F,(,x,),G,(,x,),(2),x,(,F,(,x,),G,(,x,),(3),x,y,(,F,(,x,),G,(,y,),H,(,x,y,),不难对每一个公式给出一个成假解释和一个成真,解释,从而证明它们既不是永真式，也不是矛盾,式,.,36,代换实例,定义,设,A,0,是含命题变项,p,1,p,2,p,n,的命题公式，,A,1,A,2,A,n,是,n,个谓词公式，用,A,i,处处代替,A,0,中的,p,i,(1,i,n,),，,所得公式,A,称为,A,0,的,代换实例,.,例如,:,F,(,x,),G,(,x,),xF,(,x,),yG,(,y,),等都是,p,q,的换实例，,x,(,F,(,x,),G,(,x,),等不是,p,q,的代换实例,.,定理,重言式的代换实例都是永真式，矛盾式的代,换实例都是矛盾式,.,37,代换实例,(,续,),例,6,判断下面公式类型,(1),xF,(,x,),(,x,y,G,(,x,y,),xF,(,x,),(2),(,x,y,G,(,x,y,),xF,(,x,),xF,(,x,),38,3.2,一阶逻辑等值演算,等值式,基本等值式,量词否定等值式,量词辖域收缩与扩张等值式,量词分配等值式,39,等值式与基本等值式,在一阶逻辑中，有些命题可以有不同的符号化形式。,例如,：没有不呼吸的人。,取全总个体域时有下面两种不同的符号化形式：,(1),x,(,F,(,x,),G,(,x,),(2),x,(,F,(,x,),G,(,x,),F,(,x,),：,x,是人，,G,(,x,),：,x,要呼吸,40,等值式与基本等值式,基本等值式,:,命题逻辑中,16,组基本等值式的代换实例,如，,xF,(,x,),yG,(,y,),xF,(,x,),yG,(,y,),(,xF,(,x,),yG,(,y,),xF,(,x,),yG,(,y,),等,消去量词等值式,设,D,=,a,1,a,2,a,n,xA,(,x,),A,(,a,1,),A,(,a,2,),A,(,a,n,),xA,(,x,),A,(,a,1,),A,(,a,2,),A,(,a,n,),定义,若,A,B,为逻辑有效式，则称,A,与,B,是,等值,的，,记作,A,B,，,并称,A,B,为,等值式,.,41,实例,例,设个体域,D,=,a,b,c,消去下面公式中的量词:,(1),x,(,F,(,x,),G,(,x,),(,F,(,a,),G,(,a,),(,F,(,b,),G,(,b,),(,F,(,c,),G,(,c,),(2),x,(,F,(,x,),y,G,(,y,),xF,(,x,),y,G,(,y,),量词辖域收缩,(,F,(,a,),F,(,b,),F,(,c,),)(,G,(,a,),G,(,b,),G,(,c,),x,(,F,(,x,a,),F,(,x,b,),F,(,x,c,),),(3),x,yF,(,x,y,),(,F,(,a,a,),F,(,a,b,),F,(,a,c,),),(,F,(,b,a,),F,(,b,b,),F,(,b,c,),),(,F,(,c,a,),F,(,c,b,),F,(,c,c,),),42,实例,解 (,F,(,f,(2),G,(2,f,(2),(,F,(,f,(3),G,(3,f,(3),例,给定解释,I,:(a),D,=2,3,(b),(c):,x,是奇数,:,x,=2,y,=2,:,x=y.,在,I,下求下列各式的真值:,(1),x,(,F,(,f,(,x,),G,(,x,f,(,x,),(2),x,yL,(,x,y,),(1,1,),(0,1,),1,解 ,yL,(2,y,),yL,(3,y,),(,L,(2,2),L,(2,3),(,L,(3,2),L,(3,3),(1,0,),(0,1,),0,43,基本的等值式,(,续,),量词否定等值式,设,A,(,x,),是含,x,自由出现的公式,xA,(,x,),x,A,(,x,),xA,(,x,),x,A,(,x,),44,基本等值式,(,续,),量词辖域收缩与扩张等值式,设,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,),45,基本的等值式,(,续,),量词分配等值式,x,(,A,(,x,),B,(,x,),xA,(,x,),xB,(,x,),x,(,A,(,x,),B,(,x,),xA,(,x,),xB,(,x,),注意：,对,无分配律，,对,无分配律,46,基本的等值式,(,续,),例 将下面命题用两种形式符号化,(1),没有不犯错误的人,(2),不是所有的人都爱看电影,解,(1),令,F,(,x,),：,x,是人，,G,(,x,),：,x,犯错误,.,x,(,F,(,x,),G,(,x,),x,(,F,(,x,),G,(,x,),请给出演算过程，并说明理由,.,(2),令,F,(,x,),：,x,是人，,G,(,x,),：,爱看电影,.,x,(,F,(,x,),G,(,x,),x,(,F,(,x,),G,(,x,),给出演算过程，并说明理由,.,47,等值演算的三条原则,置换规则,：若,A,B,则,(,B,),(,A,),换名规则,:,将量词辖域中出现的,某个约束变项,的所有出现及对应的指导变项，,改成该量词辖域中未曾出现过的个体变项符号,，公式中其余部分不变，则所得公式与原来的公式等值,.,代替规则,:,对某,自由出现的个体变项,用与,原公式中所有个体变项符号不同的符号,去代替，则所得公式与原来的公式等值,.,48,换名规则与代替规则,例,(,1),xF,(,x,),y,(,G,(,x,y,),H,(,y,),zF,(,z,),y,(,G,(,x,y,),H,(,y,),（换名规则）,(2),x,(,F,(,x,y,),y,(,G,(,x,y,),H,(,x,z,),x,(,F,(,x,u,),y,(,G,(,x,y,),H,(,x,z,)(,代替规则,),49,例 给定解释,I,如下：,(a),个体域,D=,2,3,(b)D,中特定元素,a=2,(c)D,中特定函数,f,(,x,),为：,f,(,2,)=3,，,f,(3)=2,(d)D,中特定谓词,G,(,x,y,),为：,G,(2,2)=,G,(2,3)=,G,(3,2)=1,G,(3,3),=,0,.L,(2,2)=,L,(3,3)=1,L,(2,3)=,L,(3,2)=0.,F,(,x,),为：,F,(2)=0,，,F,(3)=1,。在,I,下求下列各式的值,(1),x,(,F,(,x,),G,(,x,a),(2),x,(,F,(,f,(,x,),G,(,x,f,(,x,),(3),x,yL,(,x,y,),(4),y,xL,(,x,y,),50,前束范式,例如，,x,y,(,F,(,x,),(,G,(,y,),H,(,x,y,),x,(,F,(,x,),G,(,x,),是前束范式,而,x,(,F,(,x,),y,(,G,(,y,),H,(,x,y,),x,(,F,(,x,),G,(,x,),不是前束范式，,定义,设,A,为一个一阶逻辑公式,若,A,具有如下形式,Q,1,x,1,Q,2,x,2,Q,k,x,k,B,则称,A,为,前束范式,其中,Q,i,(1,i,k,),为,或,，,B,为不含量词的公式,.,51,公式的前束范式,定理（前束范式存在定理）,一阶逻辑中的任何公,式都存在与之等值的前束范式,注意,:,公式的前束范式不惟一,求公式的前束范式的方法,:,利用重要等值式、,置换规则、换名规则、代替规则进行等值演算,.,52,公式的前束范式,(,续,),例 求下列公式的前束范式,(1),x,(,M,(,x,),F,(,x,),解 ,x,(,M,(,x,),F,(,x,),x,(,M,(,x,),F,(,x,),（,量词否定等值式）,x,(,M,(,x,),F,(,x,),两步结果都是前束范式，说明前束范式不惟一,.,53,例(续),(2),xF,(,x,),xG,(,x,),解 ,xF,(,x,),xG,(,x,),xF,(,x,),x,G,(,x,),（,量词否定等值式）,x,(,F,(,x,),G,(,x,),（,量词分配等值式）,另有一种形式,xF,(,x,),xG,(,x,),xF,(,x,),x,G,(,x,),（量词否定等值式）,xF,(,x,),y,G,(,y,)(,换名规则,),x,y,(,F,(,x,),G,(,y,)(,量词辖域扩张,),两种形式是等值的,54,例(续),(3),xF,(,x,),xG,(,x,),解 ,xF,(,x,),xG,(,x,),xF,(,x,),x,G,(,x,),（量词否定等值式）,x,(,F,(,x,),G,(,x,),（,为什么？）,(4),xF,(,x,),y,(,G,(,x,y,),H,(,y,),解 ,xF,(,x,),y,(,G,(,x,y,),H,(,y,),zF,(,z,),y,(,G,(,x,y,),H,(,y,),（,换名规则）,z,y,(,F,(,z,),(,G,(,x,y,),H,(,y,),（,为什么？）,55,例(续),或,xF,(,x,),y,(,G,(,z,y,),H,(,y,),（,代替规则）,x,y,(,F,(,x,),(,G,(,z,y,),H,(,y,),(5),x,(,F,(,x,y,),y,(,G,(,x,y,),H,(,x,z,),解 用换名规则,也可用代替规则,这里用代替规则,x,(,F,(,x,y,),y,(,G,(,x,y,),H,(,x,z,),x,(,F,(,x,u,),y,(,G,(,x,y,),H,(,x,z,),x,y,(,F,(,x,u,),G,(,x,y,),H,(,x,z,),注意：,x,与,y,不能颠倒,56,一阶逻辑推理理论,推理的形式结构,判断推理是否正确的方法,重要的推理定律,推理规则,构造证明,附加前提证明法,57,推理,推理的形式结构,有两种：,第一种,A,1,A,2,A,k,B,(*),第二种,前提：,A,1,，,A,2,，,，,A,k,结论：,B,其中,A,1,A,2,A,k,B,为一阶逻辑公式,.,若,(*),为永真式,则称,推理正确,否则称,推理,不正确,.,58,重要的推理定律,第一组 命题逻辑推理定律代换实例,如,xF,(,x,),yG,(,y,),xF,(,x,),为化简律代换实例,.,第二组 由基本等值式生成,如 由,xA,(,x,),x,A,(,x,),生成,xA,(,x,),x,A,(,x,),x,A,(,x,),xA,(,x,),第三组,xA,(,x,),xB,(,x,),x,(,A,(,x,),B,(,x,),x,(,A,(,x,),B,(,x,),xA,(,x,),xB,(,x,),59,推理规则,(1),前提引入规则,(2),结论引入规则,(3),置换规则,(4),假言推理规则,(5),附加规则,(6),化简规则,(7),拒取式规则,(8),假言三段论规则,(9),析取三段论规则,(10),构造性二难推理规则,(11),合取引入规则,60,推理规则,(,续,),(12),全称量词消去规则（简记为,UI,规则或,UI,）,两式成立的条件是：,在第一式中，取代,x,的,y,应为任意的不在,A,(,x,),中,约束出现的个体变项,.,在第二式中，,c,为任意个体常项,.,用,y,或,c,去取代,A,(,x,),中的自由出现的,x,时，一定要,在,x,自由出现的一切地方进行取代,.,61,推理规则,(,续,),(13),全称量词引入规则（简记为,UG,规则或,UG,）,该式成立的条件是：,无论,A,(,y,),中自由出现的个体变项,y,取何值，,A,(,y,),应该均为真,.,取代自由出现的,y,的,x,，,也不能,在,A,(,y,),中约束出,现,.,62,推理规则,(,续,),(14),存在量词引入规则（简记为,EG,规则或,EG,）,该式成立的条件是：,c,是使,A,为真的特定个体常项,.,取代,c,的,x,不能在,A,(,c,),中出现过,.,63,推理规则,(,续,),(15),存在量词消去规则,（,简记为,EI,规则或,EI,）,该式成立的条件是：,c,是使,A,为真的特定的个体常项,.,c,不在,A,(,x,),中出现,.,若,A,(,x,),中除自由出现的,x,外，还有其他自由出现,的个体变项，此规则不能使用,.,64,构造推理证明,例,1,证明苏格拉底三段论,:“,人都是要死的,苏格拉,底是人，所以苏格拉底是要死的,.”,令,F,(,x,):,x,是人,G,(,x,):,x,是要死的,a,:,苏格拉底,前提：,x,(,F,(,x,),G,(,x,),，,F,(,a,),结论：,G,(,a,),证明：,F,(,a,),前提引入,x,(,F,(,x,),G,(,x,),前提引入,F,(,a,),G,(,a,),UI,G,(,a,),假言推理,注意：使用,UI,时，用,a,取代,x,.,65,构造推理证明,(,续,),例,2,乌鸦都不是白色的,.,北京鸭是白色的,.,因此，,北京鸭不是乌鸦,.,令,F,(,x,):,x,是乌鸦,G,(,x,):,x,是北京鸭,H,(,x,):,x,是白色的,前提：,x,(,F,(,x,),H,(,x,),，,x,(,G,(,x,),H,(,x,),结论：,x,(,G,(,x,),F,(,x,),66,例,2,(续),证明：,x,(,F,(,x,),H,(,x,),前提引入,F,(,y,),H,(,y,),UI,x,(,G,(,x,),H,(,x,),前提引入,G,(,y,),H,(,y,),UI,H,(,y,),G,(,y,),置换,F,(,y,),G,(,y,),假言三段论,G,(,y,),F,(,y,),置换,x,(,G,(,x,),F,(,x,),UG,67,构造推理证明,(,续,),例,3,构造下述推理证明,前提：,x,(,F,(,x,),G,(,x,),，,xF,(,x,),结论：,xG,(,x,),证明：,xF,(,x,),前提引入,x,(,F,(,x,),G,(,x,),前提引入,F,(,c,),EI,F,(,c,),G,(,c,),UI,G,(,c,),假言推理,xG,(,x,),EG,注意：必须先消存在量词,68,构造推理证明,(,续,),例,4,构造下述推理证明,前提：,xF,(,x,),xG,(,x,),结论：,x,(,F,(,x,),G,(,x,),证明：,xF,(,x,),xG,(,x,),前提引入,x,y,(,F,(,x,),G,(,y,),置换,x,(,F,(,x,),G,(,z,),UI,F,(,z,),G,(,z,),UI,x,(,F,(,x,),G,(,x,),UG,说明,:,不能对,xF,(,x,),xG,(,x,),消量词,因为它不是前束范式,.,对此题不能用附加前提证明法,.,69,构造推理证明,(,续,),例,5,构造下述推理证明,前提：,x,(,F,(,x,),G,(,x,),结论：,xF,(,x,),xG,(,x,),证明：,xF,(,x,),附加前提引入,F,(,y,),UI,x,(,F,(,x,),G,(,x,),前提引入,F,(,y,),G,(,y,),UI,G,(,y,),假言推理,xG,(,x,),UG,本题可以使用附加前提证明法,70,