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

《离散数学--1.3证明方法概述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.3证明方法概述逻辑推理的形式结构证明方法直接证明法间接证明法归谬法(反证法)数学归纳法穷举法构造证明法空证明法平凡证明法举反例——命题为假的证明1逻辑推理的形式结构逻辑推理的形式结构A1A2…AkB(*)当(*)为重言式时,记作A1A2…AkB(**)并称推理有效或推理正确,又称B是A1,A2,…,Ak的有效(或逻辑)结论;否则称推理不正确.ABAB(1)001(2)011(3)100(4)111(1),(2),(4)推理正确(3)推理不正确(1)中B是A的逻辑结论,但不是正确结论;(2)和(4)中B既是逻辑结论,又是正确结论.2逻辑推理的证明推理的常见形式:(1)若A

2、,则BAB(2)A当且仅当BAB(3)证明BB都可归结为形式(1)3直接证明法做法证明“若A为真,则B为真”理由“若A为真,则B为真”“AB为真”例1若n是奇数,则n2也是奇数.证存在kN,n=2k+1.于是,n2=(2k+1)2=2(2k2+2k)+1得证n2是奇数.4间接证明法做法证明“¬B¬A”为真理由“AB为真”“¬B¬A为真”例2若n2是奇数,则n也是奇数.证用间接证明法.只要证:若n是偶数,则n2也是偶数.假设n是偶数,则存在kN,n=2k.于是,n2=(2k)2=2(2k2)得证n2是偶数.5归谬法(反证法)做法假设A真并且¬B真,推出矛盾,即证明:A¬B

3、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,m2=2n2,m2是偶数,从而m是偶数.设m=2k,得(2k)2=2n2,n2=2k2,这又得到n也是偶数,与m/n为既约分数矛盾.间接证明法是归谬法的特殊形式:¬B¬A,A¬A07穷举法(分情况证明法)推理AB,其中A=A1A2

4、…Ak.做法证明A1B,A2B,…,AkB均为真理由A1A2…AkB¬(A1A2…Ak)B(¬A1¬A2…¬Ak)B(¬A1B)(¬A2B)…(¬AkB)(A1B)(A2B)…(Ak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cccbcacbbbbbbacccacbcacaaacabbbbbcbabaaa9构造证明法推理AB,其中B是存在具有某种性质的客体做法在A为真的条件下,构造出

5、具有这种性质的客体例6对于每个正整数n,存在n个连续的正合数.证令x=(n+1)!则x+2,x+3,…,x+n+1是n个连续的正合数:i

6、x+i,i=2,3,…,n+110空证明法与平凡证明法空证明法(前件假证明法)做法证明“A恒为假”理由“A恒为假”“AB为真”例如,“是任何集合的子集”(定理1.1)的证明平凡证明法(后件真证明法)做法证明“B恒为真”理由“B恒为真”“AB为真”例如,若ab,则a0b0.常在归纳证明的归纳基础中出现11命题为假的证明——举反例例7判断下述命题是真是假:若AB=AC,则B=C.解反例:取A={a,b},B={a,b,c},C={a,b,d}

7、,有AB=AC={a,b}但BC,故命题为假.12数学归纳法的应用对象命题形式:x(xNxn0),P(x)命题的提出——归纳与猜想例如,观察11+21+2+31+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)/213数学归纳法的步骤(1)归纳基础证P(n0)为真(2)归纳步骤x(xn0),假设P(x)为真,证P(x+1)为真.称“P(x)为真”为归纳假设例8证明:对所有n1,1+2+…+n=n(n+1)/2证归纳基础.当n=1时,1=1(1+1)/2,结论成立.归

8、纳步骤.假设对n1结论成立,则有1+2+…+n+(n+1)=n(n+1)/2+(n+1)(归纳假设)=(n+1)(n+2)/2得证当n+1时结论也成立.14数学归纳法的步骤(续)注意:归纳基础与归纳步骤两者缺一不可反例1命题n1,21+22++2n=2n+1证假设n1,结论成立,则21+22++2n+2n+1=2n+1+2n+1=2n+2对n+1结论成立,故命题成立.15数学归纳法的步骤(续)反例2