《离散数学例题整理》由会员分享，可在线阅读，更多相关《离散数学例题整理（15页珍藏版）》请在金锄头文库上搜索。
1、第一章定律证明：(1) A，jB=B=A (交换律)证-x x A 一B=xwA或xwB,自然有xB或xwA= x 三 B _ A得证 A _ B B_.A.同理可证B_.A A_.B. A=(BC)=(A，jB)c(A-C)(分配律)证 - x x A (B - C)=xwA 或(x B 且 xwC )二(xw A 或 xw B)且(xw A 或 xC)=x (A_.B) - (A 一 C)得证 A . (B - C) (A . B) (A . C).类似可证(A 一 B) - (A - C) A 一(B C).(3) A. E=E (零律)证 根据并白勺定义,有EAlE根据全集的定义，又有
2、Au E2E.(4) A E=A(同一律)证根据交白勺定义,有AcE2A.又，1x x A,根据全集E的定义，xE,从而 xeA 且 xE,= x A - E得证 A A - E.例4证明Au(AcB尸A (吸收律)证 利用例3证明的4条等式证明A 一 (A - B)=(AcE)u(AcB)(同一律)=A - (E - B)(分配律)=A(BuE)(交换律)=2 E(零律)=A(同一彳) 例 5 证明(A-B)-C=(A-C)-(B-C)证 (A-C)-(B-C)=(A cC) c (B cC)(补交转换律)=(A cC) c (b C)(德摩根律)=(A cC) c (b =C)(双重否定律
3、)=(A -C - B) - (A - C - C)(分配律)=(A c C，c B) u(A c0)(矛盾律)=A cC，r B (零律，同一律) =(A c B) c C(交换律,结合律)二(A - B) -C(补交转换律) 例 6 证明(A，jB)$(A，jC)=(B6C)- 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
4、为任意集合，证明：若 A三B,则 P(A)AP(B)证-x x P(A) ： = x二A口运B (已知A=B)=x P(B)例 8 证明 A9B=A jB-AcB.A 二 B=(A - B) (A - B)=(A . A) (A - B) (B 1 A) - (B 一 B)=(A . B) (B . A)=(A . B) (A - B)=A . B-A B直接法 若n是奇数，则n2也是奇数. 假设n是奇数,则存在kN, n=2k+1. 于是 n2 = (2k+1)2 = 2(2k2+2k)+1 得证n2是奇数.间接法 若n2是奇数，则n也是奇数.只证:若n是偶数，则n2也是偶数.假设n是偶数,
5、则存在k N, n=2k.于是 n2 = (2k)2= 2(2k2)得证n2是偶数.归谬法若A-B=A,则A-B=0证用归谬法，假设ACB。，则存在x,使得x-AB u xA 且 xB=xWA-B 且 xB (A-B=A)二(x且 xB)且 xB=x2B且xeB,矛盾构造性对每正整数n,存n个连的正合数.证令 x=(n+1)! +1考虑如下n个连续正整数：x+1, x+2，,x+n , 对于 i (i=1,2,3, ) , x+i=(n+1)! +(1+i),此式含有因子1+i,而1+i不等于1也不等于x+i, 因此x+i是合数。所以x+1, x+2,x+n是n个连续的正合数。非构造性对每个正
6、整数n,存在大于n的素数.令x等于所有小于等于n的素数的乘积加1, 则x不能被所有小于等于n的素数整除.于是，x或者是素数，或者能被大于n的素数整除. 因此，存在大于n的素数.数学归：对所有n之1, 1+3+5+(2-1)=n2归纳基础.当n=1时，1=12,结论成立.归纳步骤.假设对n(n)结论成立，则考虑n+1的情况有1+3+5+ +(2i-1)+(2n+1)=n2+(2n+1) = (n+1)2得证当n+1时结论也成立.第二数学归任=2的整数均可表成素数的乘积证归纳基础.对于2,结论显然成立.归纳步骤.假设对所有的k(2Mk。)结论成立，要证结论对n+1也成立.若n+1是素数，则结论成立
7、；否则n+1=ab, 2金,b （q r）u -npv（qvr）（蕴涵等值式）u （pvq） vr（结合律）u（pr-qr（德摩根律）u （pAq） t r（蕴涵等值式）（1） q -（p , q）解 q -(p q)u qA_,(_,pvq)(蕴涵等值式)u qA(pAq)(德摩根律)u pNq,q)(交换律，结合律)u Pa0(矛盾律)u 0(零律)该式为矛盾式.(p q) (-q -p)解(p q)f (-q - p)u (-pq)H (qvp)(蕴涵等值式)u (pyq)(pvq)(交换律)二 1该式为重言式.-(pq)/的析取范式与合取范式解一(p q) -之 一(-p q) -ru
8、 (pAq)vr析取范式u (pvr)A(qvr)合取范式(p-* q)vr的主析取范式主合取范式解(1) (p q) 一土 (p q) 一pAqu (pA-|q)Al同一律u (pA-nq)A(rvr)排中律u (pA-qA-r) v(pA-|qAr) 分酉己律仁 m4 m5-r u (pvp)Apqvq)Ar同一律，排中律:二(一p q r) (p q r) (p _q _r) (p q -r)=m0M m2Mm45 m6 分配律得 _(p- q) r ：= mo m2 m4 m5 m6可记作 =三(0,2,4,5,6)(2) (p q) r ：=(p r) (_q _r)pLru pWL
9、r同一律u pv(q A-q) vr矛盾律u (p vq v-r) A(p v-1 q vr) 分配律=Mi M3qJTu (pAp)vqv-,r同一律，矛盾律u (pvq vr)ACpvqvr)分配律仁 M3 M7得一(p； q) r = Mi M3 M7可记作u二(1,3,7)快速求 A= (-p q) (-p -q r) r的主析取范式(1) -p q =(p q -r) (p q r) = m2 m3一p -q r：- mir=(-p F r) Lp q r) (p _q r) (p q r) 二 mi m3 m5 m7得A二 mi m2 m3 m5 m7 仁三(1,2,3,5,7)求
10、Bu邛八四L1。的主合取范式解一p：二(-p q r) (-p q r)(p q r) (p q -r)二 M4 M5 M6 M7p q 一二 Mi得 B= Mi M4 M5 M6 M7 =二(1,4,5,6,7)例3用主析取范式判断公式的类型： A； -(p q) q (3) C= (p q) rAu -,(_| pvq)/q u ( pAiq).、。u 0 矛盾式 B= p (p q)Bu -1 pv(pvq) = i = movmi vm2vm3 重言式 C二(p q) rC :二 一(p q)二(p q) r:=(p q r) (一p q r) (-p q r)(p q r) (p -
11、q r) (p q r)u movmi 仃3 m5Mm7非重言式的可满足式 用主析取范式判断下面2组公式是否等值: p 与(p*q)T (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)(p/vqr 与 pA(qvr)解(p q) r ：=(p q -r) (p q r) (-p -q r)(p q r) (p q r) (p q r):二 mi m3 m5 m6 m7p (q r) = (p q) (p r)=(p q r) (p q r
12、) (p _q r) (p q r)=m5 m6 m7故 (p、q)r 不等于 pA(qvr)例5某单位要从A,B,C三人中选派若干人出国考察，需满 足下述条件：若A去，则C必须去；若B去，则C不能去；(3) A和B必须去一人且只能去一人.问有几种可能的选派方案？解 记p:派A去，q:派B去，r:派C去 p r, (2) q r, (3) (p -q) (一p q)求下式的成真赋值A=(p r) (q- 1 r) (p q) (p q)求A的主析取范式A=(p r) (q- 1 r) (p q) (p q)=(-p r) (q -)(p -q) (-p q)=(p q) (一p -)(r _q
13、) (r _r) (p -q) (p q)=(p q) (p q) (一p -)(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去 人气-八-八口川-4寸山户(八口的主合取范式解A ：二 mi m3 m7二 Mo M2 M4 M5 M6第二章判断若今天是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
