离散数学--1.3证明方法概述.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,1.3,证明方法概述,逻辑推理的形式结构,证明方法,直接证明法 间接证明法,归谬法(反证法)数学归纳法,穷举法 构造证明法,空证明法 平凡证明法,举反例,命题为假的证明,1,逻辑推理的形式结构,逻辑推理的形式结构,A,1,A,2,A,k,B,(*),当(*)为重言式时,记作,A,1,A,2,A,k,B,(*),并称,推理有效,或,推理正确,又称,B,是,A,1,A,2,A,k,的,有效,(或,逻辑,),结论,;否则称,推理不正确,.,A,B,A,B,(1),0,0,1,(2),0,1,1,(3),1,0,0,(4),1,1,1,(1),(2),(4)推理正确,(3),推理不正确,(1)中,B,是,A,的逻辑结论,但不是正确结论;(2)和(4)中,B,既是逻辑结论,又是正确结论.,2,逻辑推理的证明,推理的常见形式:,(1)若,A,则,B,A,B,(2),A,当且仅当,B,A,B,(3)证明,B,B,都可归结为形式(1),3,直接证明法,做法,证明“若,A,为真,则,B,为真”,理由,“若,A,为真,则,B,为真”,“,A,B,为真,”,例1,若,n,是奇数,则,n,2,也是奇数.,证 存在,k,N,n,=2,k,+1.,于是,n,2,=(,2,k,+1,),2,=2(,2,k,2,+,2,k,)+1,得证,n,2,是奇数.,4,间接证明法,做法,证明,“,B,A”,为真,理由,“,A,B,为真,”,“,B,A,为真”,例2,若,n,2,是奇数,则,n,也是奇数.,证 用间接证明法.只要证:若,n,是偶数,则,n,2,也是偶数.,假设,n,是偶数,则存在,k,N,n,=2,k,.,于是,n,2,=(,2,k,),2,=2(,2,k,2,),得证,n,2,是偶数.,5,归谬法(反证法),做法,假设,A,真并且,B,真,推出矛盾,即证明:,A,B,0,理由,A,B,0,为真,A,B,为假,A,为假或,B,为真,A,B,为真,例3,若,A-B,=,A,则,A,B,=,证 用归谬法,假设,A,B,则存在,x,使得,x,A,B,x,A,x,B,x,A-B,x,B,(,A-B,=,A,),x,A,x,B,x,B,x,B,x,B,矛盾,6,归谬法(续),例,4,证明 是无理数,证 假设 是有理数,存在正整数,n,m,使得 =,m,/,n,不妨设,m,/,n,为既约分数.于是,m,=,n,m,2,=2,n,2,m,2,是偶数,从而,m,是偶数.设,m,=2,k,得(2,k,),2,=2,n,2,n,2,=2,k,2,这又得到,n,也,是偶数,与,m,/,n,为既约分数矛盾.,间接证明法是归谬法的特殊形式:,B,A,A,A,0,7,穷举法(分情况证明法),推理,A,B,其中,A,=,A,1,A,2,A,k,.,做法,证明,A,1,B,A,2,B,A,k,B,均为真,理由,A,1,A,2,A,k,B,(,A,1,A,2,A,k,),B,(,A,1,A,2,A,k,),B,(,A,1,B,),(,A,2,B,),(,A,k,B,),(,A,1,B,),(,A,2,B,),(,A,k,B,),8,实例,例5,证明:,max(,a,max(,b,c,)=max(max(,a,b,),c,),证,情况,u=,max(,b,c,),max(,a,u,),v=,max(,a,b,),max(,v,c,),a,b,c,c,c,b,c,a,c,b,b,b,b,b,b,a,c,c,c,a,c,b,c,a,c,a,a,a,c,a,b,b,b,b,b,c,b,a,b,a,a,a,9,构造证明法,推理,A,B,其中,B,是存在具有某种性质的客体,做法,在,A,为真的条件下,构造出具有这种性质的客体,例6,对于每个正整数,n,存在,n,个连续的正合数.,证 令,x,=(,n,+1)!,则,x,+,2,x,+,3,x,+,n,+1,是,n,个连续的正合数,:,i,|,x,+,i,i,=2,3,n,+1,10,空证明法与平凡证明法,空证明法(前件假证明法),做法,证明“,A,恒为假”,理由,“,A,恒为假”,“,A,B,为真”,例如,“,是任何集合的子集”(定理1.1)的证明,平凡证明法(后件真证明法),做法,证明“,B,恒为真”,理由,“,B,恒为真”,“,A,B,为真”,例如,若,a,b,则,a,0,b,0,.,常在归纳证明的归纳基础中出现,11,命题为假的证明,举反例,例7,判断下述命题是真是假:,若,A,B,=,A,C,则,B,=,C,.,解 反例:取,A,=,a,b,B,=,a,b,c,C,=,a,b,d,有,A,B,=,A,C,=,a,b,但,B,C,故命题为假.,12,数学归纳法的应用对象,命题形式:,x,(,x,N,x,n,0,),P,(,x,),命题的提出,归纳与猜想,例如,观察,1,1+2,1+2+3,1+2+3+4,=1,(1+1)/2,=3=2,(2+1)/2,=6=3,(3+1)/2,=10=4,(4+1)/2,猜想,对所有,n,1,1+2+,+,n,=,n,(,n,+1)/2,13,数学归纳法的步骤,(1),归纳基础,证,P,(,n,0,),为真,(2),归纳步骤,x,(,x,n,0,),假设,P,(,x,),为真,证,P,(,x,+1),为真.,称“,P,(,x,),为真”为,归纳假设,例8,证明:,对所有,n,1,1+2+,+,n,=,n,(,n,+1)/2,证 归纳基础.当,n,=1时,1=,1,(1+1)/2,结论成立.,归纳步骤.假设对,n,1,结论成立,则有,1+2+,+,n,+(,n+,1),=,n,(,n,+1)/2,+(,n+,1)(,归纳假设),=(,n+,1),(,n+,2)/2,得证当,n+,1,时结论也成立.,14,数学归纳法的步骤(续),注意:归纳基础与归纳步骤两者缺一不可,反例1,命题,n,1,2,1,+2,2,+2,n,=2,n,+1,证 假设,n,1,结论成立,则,2,1,+2,2,+2,n,+2,n,+1,=,2,n,+1,+,2,n,+1,=,2,n,+2,对,n,+1,结论成立,故命题成立.,15,数学归纳法的步骤(续),反例2,观察2,n,-1,-1,是否被,n,整除,n,2,n,-1,-1,整除,n,2,n,-1,-1,整除,3,3,Y,10,511,N,4,7,N,11,1023,Y,5,15,Y,12,2047,N,6,31,N,13,4095,Y,7,63,Y,14,8191,N,8,127,N,15,16383,N,9,255,N,16,32767,N,16,反例2(续),由上表可能会提出下述命题,命题 设,n,3,n,是素数的充分必要条件是,2,n,-1,-1,被,n,整除.,但此命题不真.561=3,1117,是合数,而2,560,-1能被561整除.,n,2,n,-1,-1,整除,n,2,n,-1,-1,整除,17,65535,Y,21,1048575,N,18,131071,N,22,2097151,N,19,262143,Y,23,4194303,Y,20,524287,N,24,8388607,N,17,第二数学归纳法,归纳基础,证明,P,(,n,0,),为真,归纳步骤,x,(,x,n,0,),假设,P,(,n,0,),P,(,n,0,+1),P,(,x,),为真,证,P,(,x,+1),为真.,归纳假设,y,(,n,0,y,x,),P,(,y,),为真,例9,任何大于等于2的整数均可表成素数的乘积,证 归纳基础.对于,2,结论显然成立.,归纳步骤.假设对所有的,k,(2,k,n,),结论成立,要证结论,对,n,+1,也成立.若,n,+1,是素数,则结论成立;否则,n,+1=,ab,2,a,b,n,.由归纳假设,a,b,均可表成素数的乘积,从而,n,+1,也可表成素数的乘积.得证结论对,n,+1,成立.,18,注释,归纳基础,证,P,(,n,0,),P,(,n,0,+1),P,(,n,1,),为真,n,0,n,1,.,例10,可用4分和5分邮票组成,n,分邮资,n,12.,证 归纳基础.12=3,4,13=24+5,14=25+4,15=35,得证对,n,=12,13,14,15,时结论成立.,归纳步骤.设,n,15,假设对12,13,n,结论成立,由12,n,-3,n,和归纳假设,n,-3分邮资可用4分和5分邮票组,成,再加一张4分邮票即可得到,n,+1,分邮资,得证结论对,n,+1,也成立.,19,