离散数学例题整理.doc

《离散数学例题整理.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.第一章定律证明:(1)AÈB=BÈA(交换律)证"xxÎAÈBÞxÎA或xÎB,自然有xÎB或xÎAÞxÎBÈA得证AÈBÍBÈA.同理可证BÈAÍAÈB.(2)AÈ(BÇC)=(AÈB)Ç(AÈC)(分配律)证"xxÎAÈ(BÇC)ÞxÎA或(xÎB且xÎC)Þ(xÎA或xÎB)且(xÎA或xÎC)ÞxÎ(AÈB)Ç(AÈC)得证AÈ(BÇC)Í(AÈB)Ç(AÈC).类似可证(AÈB)Ç(AÈC)ÍAÈ(BÇC).(3)AÈE=E(零律)证根据并的定义,有EÍAÈE.根据全集的定义,又有AÈEÍE.(4)AÇE=A(同一律)证根据交的定

2、义,有AÇEÍA.又,"xxÎA,根据全集E的定义,xÎE,从而xÎA且xÎE,ÞxÎAÇE得证AÍAÇE.例4证明AÈ(AÇB)=A（吸收律）证利用例3证明的4条等式证明AÈ(AÇB)=(AÇE)È(AÇB)(同一律)=AÇ(EÈB)(分配律)Word资料.=AÇ(BÈE)(交换律)=AÇE(零律)=A(同一律)例5证明(A-B)-C=(A-C)-(B-C)证(A-C)-(B-C)=(AÇ~C)Ç~(BÇ~C)(补交转换律)=(AÇ~C)Ç(~BÈ~~C)(德摩根律)=(AÇ~C)Ç(~BÈC)(双重否定律)=(AÇ~CÇ~B)È(AÇ~C

3、ÇC)(分配律)=(AÇ~CÇ~B)È(AÇÆ)(矛盾律)=AÇ~CÇ~B(零律,同一律)=(AÇ~B)Ç~C(交换律,结合律)=(A–B)–C(补交转换律)例6证明(AÈB)Å(AÈC)=(BÅC)-A证(AÈB)Å(AÈC)=((AÈB)-(AÈC))È((AÈC)-(AÈB))=((AÈB)Ç~AÇ~C)È((AÈC)Ç~AÇ~B)=(BÇ~AÇ~C)È(CÇ~AÇ~B)=((BÇ~C)È(CÇ~B))Ç~A=((B-C)È(C-B))Ç~A=(BÅC)-A例7设A,B为任意集合,证明:若AÍB,则P(A)ÍP(B)证"xxÎP(A)Û

4、xÍAÞxÍB(已知AÍB)ÛxÎP(B)例8证明AÅB=AÈB-AÇB.AÅB=(AÇ~B)È(~AÇB)=(AÈ~A)Ç(AÈB)Ç(~BÈ~A)Ç(~BÈB)=(AÈB)Ç(~BÈ~A)=(AÈB)Ç~(AÇB)Word资料.=AÈB-AÇB直接法若n是奇数,则n2也是奇数.假设n是奇数,则存在kÎN,n=2k+1.于是n2=(2k+1)2=2(2k2+2k)+1得证n2是奇数.间接法若n2是奇数,则n也是奇数.只证:若n是偶数,则n2也是偶数.假设n是偶数,则存在kÎN,n=2k.于是n2=(2k)2=2(2k2)得证n2是偶数.归谬

5、法若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,矛盾构造性对每正整数n,存n个连的正合数.证令x=(n+1)!+1考虑如下n个连续正整数：x+1,x+2,…,x+n，对于i（i=1,2,3,…,n），x+i=(n+1)!+(1+i),此式含有因子1+i，而1+i不等于1也不等于x+i，因此x+i是合数。所以x+1,x+2,…,x+n是n个连续的正合数。非构造性对每个正整数n,存在大于n的素数.Word资料.令x等于所

6、有小于等于n的素数的乘积加1,则x不能被所有小于等于n的素数整除.于是,x或者是素数,或者能被大于n的素数整除.因此,存在大于n的素数.数学归：对所有n³1,1+3+5+…+(2n-1)=n2归纳基础.当n=1时,1=12,结论成立.归纳步骤.假设对n(n³1)结论成立,则考虑n+1的情况有1+3+5+…+(2n-1)+(2n+1)=n2+(2n+1)=(n+1)2得证当n+1时结论也成立.第二数学归任>=2的整数均可表成素数的乘积证归纳基础.对于2,结论显然成立.归纳步骤.假设对所有的k(2£k£n)结论成立,要证结论对n+1也成立.若n+

7、1是素数,则结论成立;否则n+1=ab,2£a,b

8、qÙØ(p®q)解qÙØ(p®q)ÛqÙØ(ØpÚq)（蕴涵等值式）ÛqÙ(pÙØq)（德摩根律）ÛpÙ(qÙØq)（交换律，结合律）ÛpÙ0（矛盾律）Û0（零律）