离散数学例题整理

.Word资料第一章定律证明:(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(同一律)证根据交的定义,有AEA.又,xxA,根据全集E的定义,.Word资料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)(分配律)=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C)(分配律)=(A~C~B)(A)(矛盾律)=A~C~B(零律,同一律)=(A~B)~C(交换律,结合律).Word资料=(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)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是偶数.归谬法若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.Word资料考虑如下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的素数.令x等于所有小于等于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)结论成立,要证结论.Word资料对n+1也成立.若n+1是素数,则结论成立;否则n+1=ab,2a,bn.由归纳假设,a,b均可表成素数的乘积,从而n+1也可表成素数的乘积.得证结论对n+1成立.命题为假的证明——举反例例11证明下述命题不成立:若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,故命题不成立.第二章例3证明p(qr)(pq)r证p(qr)p(qr)（蕴涵等值式）(pq)r（结合律）(pq)r（德摩根律）(pq)r（蕴涵等值式）(1)q(pq).Word资料解q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）该式为矛盾式.(2)(pq)(qp)解(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1该式为重言式.(pq)r的析取范式与合取范式解(pq)r(pq)r(pq)r析取范式(pr)(qr)合取范式.Word资料(pq)r的主析取范式主合取范式解(1)(pq)r(pq)rpq(pq)1同一律(pq)(rr)排中律(pqr)(pqr)分配律m4m5r(pp)(qq)r同一律,排中律(pqr)(pqr)(pqr)(pqr)m0m2m4m6分配律得(pq)rm0m2m4m5m6可记作(0,2,4,5,6)(2)(pq)r(pr)(qr)prp0r同一律p(qq)r矛盾律(pqr)(pqr)分配律M1M3qr(pp)qr同一律,矛盾律(pqr)(pqr)分配律M3M7得(pq)rM1M3M7可记作(1,3,7).Word资料快速求A(pq)(pqr)r的主析取范式(1)pq(pqr)(pqr)m2m3pqrm1r(pqr)(pqr)(pqr)(pqr)m1m3m5m7得Am1m2m3m5m7(1,2,3,5,7)(2)求Bp(pqr)的主合取范式解p(pqr)(pqr)(pqr)(pqr)M4M5M6M7pqrM1得BM1M4M5M6M7(1,4,5,6,7)例3用主析取范式判断公式的类型:(1)A(pq)q(3)C(pq)rA(pq)q(pq)q0矛盾式(2)Bp(pq)Bp(pq)1m0m1m2m3重言式(3)C(pq)rC(pq)r(pq)r(pqr)(pqr)(pqr)(pqr)(pqr)(pqr).Word资料m0m1m3m5m7非重言式的可满足式用主析取范式判断下面2组公式是否等值:(1)p与(pq)(pq)解pp(qq)(pq)(pq)m2m3(pq)(pq)(pq)(pq)(pq)(pq)m2m3故p(pq)(pq)(2)(pq)r与p(qr)解(pq)r(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m1m3m5m6m7p(qr)(pq)(pr)(pqr)(pqr)(pqr)(pqr)m5m6m7故(pq)r不等于p(qr)例5某单位要从A,B,C三人中选派若干人出国考察,需满足下述条件:(1)若A去,则C必须去;(2)若B去,则C不能去;(3)A和B必须去一人且只能去一人..Word资料问有几种可能的选派方案?解记p:派A去,q:派B去,r:派C去(1)pr,(2)qr,(3)(pq)(pq)求下式的成真赋值A=(pr)(qr)((pq)(pq))求A的主析取范式A=(pr)(qr)((pq)(pq))(pr)(qr)((pq)(pq))((pq)(pr)(rq)(rr))((pq)(pq))((pq)(pq))((pr)(pq))((rq)(pq))((pq)(pq))((pr)(pq))((rq)(pq))(pqr)(pqr)成真赋值:101,010结论:方案1派A与C去方案2派B去A=(pqr)(pqr)(pqr)的主合取范式解Am1m3m7M0M2M4M5M6第二章.Word资料判断若今天是1号,则明天是5号.今天是1号.所以,明天是5号.解设p:今天是1号,q:明天是5号推理的形式结构为(pq)pq证明用等值演算法(pq)pq((pq)p)q((pq)p)qpqq1得证推理正确判断若下午气温超过30度,则小燕必去游泳，若她去游泳她就不去看电影了.所以若小燕没去看电影,下午气温必定超过了30度.m1解设p:下午气温超过30度,q:小燕去游泳，r:小燕去看电影.推理的形式结构为((pq)qr)rp)证明主析取范式法((pq)qr)rp)prm1m3m4m5m6m7主析取范式中缺少m0，m2，不是重言式，不正确。前提:pq,qr,ps,s结论:rpq.Word资料直接证明法证明①ps前提引入②s前提引入③p①②拒取式④pq前提引入⑤q③④析取三段论⑥qr前提引入⑦r⑤⑥假言推理⑧rpq⑦④合取推理正确rpq是有效结论构造推理的证明:若明天是星期一或星期三,我就有课.若有课,今天必需备课.我今天下午没备课.所以,明天不是星期一和星期三.解设p:明天是星期一,q:明天是星期三，r:我有课，s:我备课前提:(pq)r,rs,s结论:pq前提:(pq)r,rs,s结论:pq证明①rs前提引入.Word资料②s前提引入③r①②拒取式④(pq)r前提引入⑤(pq)③④拒取式⑥pq⑤置换结论有效,即明天不是星期一和星期三例4前提:pq,qr,rs结论:ps证明①p附加前提引入②pq前提引入③q①②析取三段论④qr前提引入⑤r③④析取三段论⑥rs前提引入⑦s⑤⑥假言推理推理正确ps是有效结论例5前提:(pq)r,rs,s,p结论:q证明用归缪法①q结论否定引入②rs前提引入③s前提引入.Word资料④r②③拒取式⑤(pq)r前提引入⑥(pq)④⑤析取三段论⑦pq⑥置换⑧p①⑦析取三段论⑨p前提引入⑩pp⑧⑨合取推理正确q是有效结论例6前提:pqr,rs,s结论:pq归结证明法解pqrpqrpqrpr)qrrsrspqpq把推理的前提改写成前提prqrrs