《离散数学例题整理》由会员分享，可在线阅读，更多相关《离散数学例题整理（13页珍藏版）》请在金锄头文库上搜索。
1、第一章定律证明:(1) AB=BA (交换律)证 x xAB xA 或 xB, 自然有 xB 或 xA xBA得证 ABBA.同理可证 BAAB.(2) A(BC)=(AB)(AC) (分配律)证 x xA(BC) xA或(xB且 xC ) (xA或xB)且(xA或xC) x(AB)(AC) 得证 A(BC)(AB)(AC).类似可证 (AB)(AC)A(BC).(3) AE=E (零律)证 根据并的定义, 有EAE.根据全集的定义, 又有A EE.(4) AE=A (同一律)证 根据交的定义, 有AEA.又, x xA,根据全集E的定义, xE, 从而 xA且xE, xAE得证 AAE. 例
2、4 证明 A(AB)=A （吸收律）证 利用例3证明的4条等式证明 A(AB) = (AE)(AB) (同一律) = A(EB) (分配律) = A(BE) (交换律) = AE (零律) = 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 (交换律,结合律) = (A B) C
3、(补交转换律)例6 证明 (AB)(AC)= (BC) - A证 (AB)(AC) =(AB) - (AC)(AC) - (AB) =(AB)AC)(AC)AB) = (BAC)(CAB) =(BC)(CB)A =(B-C)(C-B)A = (BC) - A例7 设A,B为任意集合, 证明: 若AB, 则P(A)P(B)证 x xP(A) xA xB (已知AB) xP(B)例8 证明 AB=AB-AB.AB=(AB)(AB) =(AA)(AB)(BA)(BB) =(AB)(BA) =(AB)(AB) =AB-AB 直接法 若n是奇数, 则n2也是奇数.假设n是奇数, 则存在kN, n=2k+
4、1. 于是 n2 = (2k+1)2 = 2(2k2+2k)+1得证n2是奇数.间接法 若n2是奇数, 则n也是奇数.只证:若n是偶数, 则n2也是偶数.假设n是偶数, 则存在kN, n=2k. 于是 n2 = (2k)2= 2(2k2)得证n2是偶数.归谬法 若A-B=A, 则AB=证 用归谬法, 假设AB, 则存在x,使得 xAB xA且xB xA-B且xB (A-B=A) (xA且xB)且xB xB且xB, 矛盾构造性 对每正整数n, 存n个连的正合数.证 令x=(n+1)! +1考虑如下n个连续正整数：x+1, x+2, x+n ，对于i（i=1,2,3,n），x+i=(n+1)! +
5、(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的素数.数学归：对所有n1, 1+3+5+ +(2n-1)=n2 归纳基础. 当n=1时, 1=12, 结论成立.归纳步骤. 假设对n(n1)结论成立, 则考虑n+1的情况有1+3+5+ +(2n-1)+(2n+1)=n2 +(2n+1) = (n+1)2得证当n+1时结
6、论也成立.第二数学归 任=2的整数均可表成素数的乘积证 归纳基础. 对于2, 结论显然成立.归纳步骤. 假设对所有的k(2kn)结论成立, 要证结论对n+1也成立. 若n+1是素数, 则结论成立; 否则n+1=ab,2a,bn. 由归纳假设, a,b均可表成素数的乘积, 从而n+1也可表成素数的乘积. 得证结论对n+1成立.命题为假的证明举反例例11 证明下述命题不成立: 若AB=AC, 则B=C. 证明 反例: 取A=a,b, B=a,b,c, C=a,b,d, 有 AB=AC = a,b但 BC, 故命题不成立.第二章例3 证明 p(qr) (pq)r证 p(qr) p(qr) （蕴涵等值
7、式） (pq)r （结合律） (pq)r （德摩根律） (pq) r （蕴涵等值式） (1) q(pq) 解 q(pq) q(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律）该式为矛盾式.(2) (pq)(qp) 解 (pq)(qp) (pq)(qp) （蕴涵等值式） (pq)(pq) （交换律） 1该式为重言式.(pq)r 的析取范式与合取范式解 (pq)r (pq)r (pq)r 析取范式 (pr)(qr) 合取范式 (pq)r 的主析取范式主合取范式解 (1) (pq)r (pq)r pq (pq)1 同一律 (pq)(rr
8、) 排中律 (pqr)(pqr) 分配律 m4m5 r (pp)(qq)r 同一律, 排中律 (pqr)(pqr)(pqr)(pqr) m0 m2 m4 m6 分配律得 (pq)r m0 m2 m4 m5 m6可记作 S(0,2,4,5,6)(2) (pq)r (pr)(qr) pr p0r 同一律 p(qq)r 矛盾律 (pqr)(pqr) 分配律 M1M3 qr (pp)qr 同一律, 矛盾律 (pqr)(pqr) 分配律 M3M7得 (pq)r M1M3M7可记作 P(1,3,7)快速求 A (pq)(pqr)r的主析取范式(1) pq (pqr)(pqr) m2 m3 pqr m1 r
9、 (pqr)(pqr)(pqr)(pqr) m1 m3 m5 m7得 A m1 m2 m3 m5 m7 S(1,2,3,5,7)(2) 求 B p(pqr)的主合取范式解 p (pqr)(pqr)(pqr)(pqr) M4M5M6M7pqr M1得B M1M4M5M6M7 P(1,4,5,6,7)例3 用主析取范式判断公式的类型:(1) A (pq)q (3) C (pq)r A ( pq)q ( pq)q 0 矛盾式(2) B p(pq) B p(pq) 1 m0m1m2m3 重言式 (3) C (pq)r C (pq)r (pq)r (pqr)(pqr)(pqr) (pqr)(pqr)(p
10、qr) m0m1m3 m5m7 非重言式的可满足式用主析取范式判断下面2组公式是否等值:(1) p与(pq)(pq)解 p p(qq) (pq)(pq) m2m3 (pq)(pq) (pq)(pq) (pq)(pq) m2m3故 p (pq)(pq)(2) (pq)r 与 p(qr)解 (pq)r (pqr)(pqr) (pqr) (pqr)(pqr)(pqr) m1m3m5 m6m7 p(qr) (pq)(p r) (pqr)(pqr)(pqr)(pqr) m5 m6m7故 (pq)r 不等于 p(qr)例5 某单位要从A,B,C三人中选派若干人出国考察, 需满足下述条件:(1) 若A去, 则C必须去;(2) 若B去, 则C不能去;(3) A和B必须去一人且只能去一人.问有几种可能的选派方案?解 记p:派A去, q:派B去, r:派C去
