离散数学高等教育出版社屈婉玲省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,主要内容,一阶逻辑等值式与基本等值式,置换规则、换名规则、代替规则,前束范式,自然推理系统,N,L,及其推理规则,第五章 一阶逻辑等值演算与推理,1/36,1,5.1,一阶逻辑等值式与置换规则,定义5.1,设,A,B,是两个谓词公式,假如,A,B,是永真式,则称,A,与,B,等值,记作,A,B,并称,A,B,是,等值式,基本等值式,第一组 命题逻辑中16组基本等值式代换实例,比如，,xF,(,x,),xF,(,x,),xF,(,x,),yG,(,y,),xF,(,x,),yG,(,y,)等,第二组,(1)消去量词等值式,设,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,),2/36,2,基本等值式,(2)量词否定等值式,xA,(,x,),x,A,(,x,),xA,(,x,),x,A,(,x,),(3)量词辖域收缩与扩张等值式.,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,),3/36,3,基本等值式,关于存在量词：,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,),(4)量词分配等值式,x,(,A,(,x,),B,(,x,),xA,(,x,),xB,(,x,),x,(,A,(,x,),B,(,x,),xA,(,x,),xB,(,x,),注意：,对,，,对,无分配律,4/36,4,置换规则、换名规则、代替规则,1.,置换规则,设,(,A,)是含,A,公式,那么,若,A,B,则,(,A,),(,B,).,2.,换名规则,设,A,为一公式，将,A,中某量词辖域中个体变项全部约束,出现及对应指导变元换成该量词辖域中未曾出现过个,体变项符号，其余部分不变，设所得公式为,A,，则,A,A,.,3.,代替规则,设,A,为一公式，将,A,中某个个体变项全部自由出现用,A,中,未曾出现过个体变项符号代替，其余部分不变，设所得,公式为,A,，则,A,A,.,5/36,5,实例,例1,将下面命题用两种形式符号化,并证实二者等值:,(1)没有不犯错误人,解 令,F,(,x,)：,x,是人，,G,(,x,)：,x,犯错误.,x,(,F,(,x,),G,(,x,)或,x,(,F,(,x,),G,(,x,),x,(,F,(,x,),G,(,x,),x,(,F,(,x,),G,(,x,)量词否定等值式,x,(,F,(,x,),G,(,x,)置换,x,(,F,(,x,),G,(,x,)置换,6/36,6,实例,(2)不是全部人都爱看电影,解 令,F,(,x,)：,x,是人，,G,(,x,)：爱看电影.,x,(,F,(,x,),G,(,x,),或,x,(,F,(,x,),G,(,x,),x,(,F,(,x,),G,(,x,),x,(,F,(,x,),G,(,x,)量词否定等值式,x,(,F,(,x,),G,(,x,)置换,x,(,F,(,x,),G,(,x,)置换,7/36,7,实例,例2,将公式化成等值不含现有约束出现、又有自由出现,个体变项:,x,(,F,(,x,y,z,),yG,(,x,y,z,),解 ,x,(,F,(,x,y,z,),y,G,(,x,y,z,),x,(,F,(,x,y,z,),t,G,(,x,t,z,),换名规则,x,t,(,F,(,x,y,z,),G,(,x,t,z,),辖域扩张等值式,或者,x,(,F,(,x,y,z,),y,G,(,x,y,z,),x,(,F,(,x,u,z,),y,G,(,x,y,z,),代替规则,x,y,(,F,(,x,u,z,),G,(,x,y,z,),辖域扩张等值式,8/36,8,实例,例3,设个体域,D,=,a,b,c,消去下述公式中量词:,(1),x,y,(,F,(,x,),G,(,y,),解 ,x,y,(,F,(,x,),G,(,y,),(,y,(,F,(,a,),G,(,y,),(,y,(,F,(,b,),G,(,y,),(,y,(,F,(,c,),G,(,y,),(,(,F,(,a,),G,(,a,),(,F,(,a,),G,(,b,),(,F,(,a,),G,(,c,),(,(,F,(,b,),G,(,a,),(,F,(,b,),G,(,b,),(,F,(,b,),G,(,c,),(,(,F,(,c,),G,(,a,),(,F,(,c,),G,(,b,),(,F,(,c,),G,(,c,),9/36,9,实例,解法二,x,y,(,F,(,x,),G,(,y,),x,(,F,(,x,),y,G,(,y,)辖域缩小等值式,x,(,F,(,x,),G,(,a,),G,(,b,),G,(,c,),),(,F,(,a,),G,(,a,),G,(,b,),G,(,c,),),(,F,(,b,),G,(,a,),G,(,b,),G,(,c,),),(,F,(,c,),G,(,a,),G,(,b,),G,(,c,),),10/36,10,实例,(2),x,yF,(,x,y,),x,yF,(,x,y,),x,(,F,(,x,a,),F,(,x,b,),F,(,x,c,),),(,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,),),11/36,11,5.2,一阶逻辑前束范式,定义5.2,设,A,为一个一阶逻辑公式，若,A,含有以下形式,Q,1,x,1,Q,2,x,2,Q,k,x,k,B,则称,A,为,前束范式,，其中,Q,i,(1,i,k,)为,或,，,B,为不含量词,公式.,比如，,x,(,F,(,x,),G,(,x,),x,y,(,F,(,x,),(,G,(,y,),H,(,x,y,)是前束范式,而,x,(,F,(,x,),G,(,x,),x,(,F,(,x,),y,(,G,(,y,),H,(,x,y,)不是前束范式，,12/36,12,前束范式存在定理,定理5.1（前束范式存在定理）,一阶逻辑中任何公式都存在与之等值前束范式,例4,求以下公式前束范式,(1),x,(,M,(,x,),F,(,x,),解,x,(,M,(,x,),F,(,x,),x,(,M,(,x,),F,(,x,)（量词否定等值式）,x,(,M,(,x,),F,(,x,),后两步结果都是前束范式，说明公式前束范式不惟一.,13/36,13,求前束范式实例,(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,)辖域收缩扩张规则,14/36,14,求前束范式实例,(3),xF,(,x,),y,(,G,(,x,y,),H,(,y,),或,xF,(,x,),y,(,G,(,z,y,),H,(,y,)代替规则,x,y,(,F,(,x,),(,G,(,z,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,)辖域收缩扩张规则,15/36,15,5.3,一阶逻辑推论理论,推理形式结构,1.,A,1,A,2,A,k,B,若次式是永真式,则称推理正确,记作,A,1,A,2,A,k,B,2.前提:,A,1,A,2,A,k,结论:,B,推理定理:永真式蕴涵式,16/36,16,推理定理,第一组 命题逻辑推理定理代换实例,如,xF,(,x,),yG,(,y,),xF,(,x,),第二组 基本等值式生成推理定理,如,xF,(,x,),xF,(,x,),xF,(,x,),xF,(,x,),xF,(,x,),x,F,(,x,),x,F,(,x,),xF,(,x,),第三组 其它惯用推理定律,(1),xA,(,x,),xB,(,x,),x,(,A,(,x,),B,(,x,),(2),x,(,A,(,x,),B,(,x,),xA,(,x,),xB,(,x,),(3),x,(,A,(,x,),B,(,x,),xA,(,x,),xB,(,x,),(4),x,(,A,(,x,),B,(,x,),xA,(,x,),xB,(,x,),17/36,17,量词消去引入规则,1.全称量词消去规则(,-),或,其中,x,y,是个体变项符号,c,是个体常项符号,且在,A,中,x,不在,y,和,y,辖域内自由出现.,2.全称量词引入规则(+),其中,x,是个体变项符号,且不在前提任何公式中自由出现,xA,(,x,),A,(,y,),xA,(,x,),A,(,c,),A,(,x,),xA,(,x,),18/36,18,量词消去引入规则,3.存在量词消去规则(,-),其中,x,是个体变项符号,且不在前提任何公式和,B,中自由,出现,A,(,x,),B,xA,(,x,),B,19/36,19,量词消去引入规则,4.存在量词引入消去规则(,+),或,或,其中,x,y,是个体变项符号,c,是个体常项符号,且在,A,中,y,和,c,不在,x,和,x,辖域内自由出现.,B,A,(,y,),B,xA,(,x,),B,A,(,c,),B,xA,(,x,),A,(,y,),xA,(,x,),A,(,c,),xA,(,x,),20/36,20,自然推理系统,N,L,定义5.3,自然推理系统,N,L,定义以下:,1.字母表.同一阶语言,L,字母表,2.合式公式.同,L,合式公式,3.推理规则:,(1)前提引入规则,(2)结论引入规则,(3)置换规则,(4)假言推理规则,(5)附加规则,(6)化简规则,(7)拒取式规则,21/36,21,自然推理系统,N,L,(8)假言三段论规则,(9)析取三段论规则,(10)结构性二难推理规则,(11)合取引入规则,(12),-,规则,(13),+,规则,(14),-,规则,(15),+规则,推理证实,22/36,22,结构推理证实实例,例5,在自然推理系统,N,L,中结构下面推理证实,取个体域R:,任何自然数都是整数.存在自然数.所以,存在整数.,解 设,F,(,x,):,x,是自然数,G,(,x,):,x,是整数.,前提:,x,(,F,(,x,),G,(,x,),xF,(,x,),结论:,xG,(,x,),证实:,x,(,F,(,x,),G,(,x,)前提引入,F,(,x,),G,(,x,),-,F,(,x,),xG,(,x,),+,xF,(,x,),xG,(,x,),-,xF,(,x,)前提引入,xG,(,x,),假言推理,23/36,23,结构推理证实实例,例6,在自然推理系统,N,L,中结构下面推理证实,取个体域R:,不存在能表示成份数无理数.有理数都能表示成份数.,所以,有理数都不是无理数.,解 设,F,(,x,):,x,是无理数,G,(,x,):,x,是有理数,H,(,x,):,x,能表示成份数.,前提:,x,(,F,(,x,),H,(,x,),x,(,G,(,x,),H,(,x,),结论:,x,(,G,(,x,),F,(,x,),证实:,x,(,F,(,x,),H,(,x,)前提引入,x,(,F,(,x,),H,(,x,),置换,x,(,F,(,x,),H,(,x,),置换,F,(,x,),H,(,x,),-,24/36,24,结构推理证实实例,x,(,G,(,x,),H,(,x,),前提引入,G,(,x,),H,(,x,),-,H,(,x,),F,(,x,),置换,G,(,x,),F,(,x,),假言三段论,x,(,G,(,x,),F,(,x,),+,25/36,25,主要提醒,要尤其注意使用,-、+、-、+规则条件.,反例1,.对,A,=,x,yF,(,x,y,)使用-规则,推得,B,=,yF,(,y,y,).,取解释,I,:个体域为R,在,I,下,A,被解释为,x,y,(,x,y,),真;而,B,被解释为,y,(,y,y,),假,原因:在,A,中,x,自由出现,在,y,辖域,F,(,x,y,)内,反例2,.前提:,P,(,x,),Q,(,x,),P,(,x,),结论:,xQ,(,x,),取解释,I,:个体域为Z,在,I,下前提为,真,结论为假,从而推理不正确,26/36,26,反例2(续),“证实”:,P,(,x,),Q,(,x,)前提引入,P,(,x,)前提引入,Q,(,x,)假言推理,xQ,(,x,),+,错误原因:在使用,+规则,而,x,在前提公式中自由出现.,27/36,27,第五章 习题课,主要内容,一阶逻辑等值式,基本等值式，置换规则、换名规则、代替规则,前束范式,推理形式结构,自然推理系统,N,L,推理定律、推理规则,28/36,28,基本要求,深刻了解并切记一阶逻辑中主要等值式,并能准确而熟练地应用它们,熟练正确地使用置换规则、换名规则、代替规则,熟练地求出给定公式前束范式,深刻了解自然推理系统,N,L,定义，切记,N,L,中各条推理规则，尤其是注意使用,、,+、,+、,4条推理规则条件,能正确地给出有效推理证实,29/36,29,练习,1,1.给定解释I以下:,(1)个体域,D,=2,3,(2),(3),(4),求下述在,I,下解释及其真值:,x,y,(,F,(,f,(,x,),G,(,y,f,(,a,),解,xF,(,f,(,x,),yG,(,y,f,(,a,),F,(,f,(2),F,(,f,(3)(,G,(2,f,(2),G,(3,f,(2),10(10)0,30/36,30,练习,2,2.求下述公式前束范式,:,xF,(,x,),y,(,G,(,x,y,),H,(,x,y,),解 使用换名规则,xF,(,x,),y,(,G,(,x,y,),H,(,x,y,),zF,(,z,),y,(,G,(,x,y,),H,(,x,y,),z,(,F,(,z,),y,(,G,(,x,y,),H,(,x,y,),z,y,(,F,(,z,),(,G,(,x,y,),H,(,x,y,),使用代替规则,xF,(,x,),y,(,G,(,x,y,),H,(,x,y,),xF,(,x,),y,(,G,(,z,y,),H,(,z,y,),x,(,F,(,x,),y,(,G,(,z,y,),H,(,z,y,),x,y,(,F,(,x,),(,G,(,z,y,),H,(,z,y,),31/36,31,练习,3,3.,结构下面推理证实:,(1)前提：,x,(,F,(,x,),G,(,x,),xF,(,x,),结论：,xG,(,x,),证实：,x,(,F,(,x,),G,(,x,)前提引入,F,(,y,),G,(,y,),xF,(,x,),前提引入,F,(,y,),G,(,y,),假言推理,yG,(,y,),+,xG,(,x,),置换,32/36,32,练习3(续),(2)前提：,x,(,F,(,x,),G,(,x,),xG,(,x,),结论：,xF,(,x,),证实：用归谬法,xF,(,x,)结论否定引入,x,F,(,x,)置换,xG,(,x,)前提引入,x,G,(,x,)置换,x,(,F,(,x,),G,(,x,),前提引入,F,(,c,),G,(,c,),F,(,c,),G,(,c,),G,(,c,)析取三段论,G,(,c,),G,(,c,)合取引入,33/36,33,练习3(续),(3)前提：,x,(,F,(,x,),G,(,x,),x,(,G,(,x,),H,(,x,),结论：,xF,(,x,),xH,(,x,),证实:用附加前提法,xF,(,x,)附加前提引入,F,(,x,),x,(,F,(,x,),G,(,x,),前提引入,F,(,x,),G,(,x,),x,(,G,(,x,),H,(,x,),前提引入,G,(,x,),H,(,x,),F,(,x,),H,(,x,),假言三段论,H,(,x,),假言推理,xH,(,x,),+,34/36,34,练习,4,4.在自然推理系统,N,L,中，结构推理证实,人都喜欢吃蔬菜但不是全部人都喜欢吃鱼所以,存在喜欢吃蔬菜而不喜欢吃鱼人,解 令,F,(,x,):,x,为人，,G,(,x,):,x,喜欢吃蔬菜，,H,(,x,):,x,喜欢吃鱼,前提：,x,(,F,(,x,),G,(,x,),x,(,F,(,x,),H,(,x,),结论：,x,(,F,(,x,),G,(,x,),H,(,x,),证实：用归谬法,(1),x,(,F,(,x,),G,(,x,),H,(,x,)结论否定引入,(2),x,(,F,(,x,),G,(,x,),H,(,x,)(1)置换,(3),(,F,(,y,),G,(,y,),H,(,y,)(2),(4),G,(,y,),F,(,y,),H,(,y,)(3),置换,(5),x,(,F,(,x,),G,(,x,),前提引入,35/36,35,练习,4(续),(6),F,(,y,),G,(,y,)(5),(7),F,(,y,),F,(,y,),H,(,y,)(4)(6),假言三段论,(8),F,(,y,),H,(,y,)(7),置换,(9),y,(,F,(,y,),H,(,y,)(8),+,(10),x,(,F,(,x,),H,(,x,)(9),置换,(11),x,(,F,(,x,),H,(,x,),前提引入,(12)0 (10)(11)合取,36/36,36,