(完整word版)离散数学-第六章集合代数课后练习习题及答案

1、第六章作业评分要求：1. 合计 57 分2. 给出每小题得分(注意：写出扣分理由).3. 总得分在采分点 1 处正确设置一有限集合计数问题(合计 20 分：每小题 10 分，正确定义集合得 4 分，方法与过程 4 分，结果 2 分)要求：掌握集合的定义方法以及处理有限集合计数问题的基本方法1 对 60 个人的调查表明，有 25 人阅读每周新闻杂志，26 人阅读时代杂志，26 人阅 读财富杂志，9 人阅读每周新闻和财富杂志，11 人阅读每周新闻和时代 杂志，8 人阅读时代和财富杂志，还有 8 人什么杂志也不读.(1) 求阅读全部 3 种杂志的人数；(2) 分别求只阅读每周新闻、时代和财富杂志的人

2、数 .解定义集合：设 E=x|x 是调查对象，A=x|x 阅读每周新闻，B=x|x 阅读时代，C=x|x 阅读财富由条件得 |E|=60, |A|=25, |B|=26, |C|=26, |AnC|=9, |AnB|=11, |BnC|=8, |E-AUBUC|=8(1) 阅读全部 3 种杂志的人数=|AnBnC|=|AUBUC|(|A|+|B|+|C|)+(|AnB|+|AnC|+|BnC|)=(60-8) (25+26+26)+(11+9+8)=3(2) 只阅读每周新闻的人数 =|A BUC|=|A An(BUC)|=|A (AnB)U(AnC)|=|A|(|AnB|+|AnC|AnBnC

3、|)=25(11+9-3)=8同理可得只阅读时代的人数为 10,只阅读财富的人数为 12.2 使用容斥原理求不超过 120 的素数个数.分析：本题有一定难度，难在如何定义集合.考虑到素数只有 1 和其自身两个素因子，而不 超过 120的合数的最小素因子一定是 2,3,5 或 7(比 120 开方小的素数),也就是说，不超过 120 的合数一定是 2,3,5或 7 的倍数.因此，可定义 4 条性质分别为 2,3,5 或 7 的倍数,先求出不 超过 120 的所有的合数，再得出素数的个数解 定义集合：设全集 E=x|x ZAK xAx 1A2k1A3k1A5k1A7k120.则不超过 120 的合

4、数的个数=|AUBUCUD| 4(因为 2,3,5,7 不是合数)=(|A|+|B|+|C|+|D|)(|AnB|+|AnC|+|AnD|+|BnC|+|BnD|+|cnD|)+(|AnBnC|+|AnBnD|+|AncnD|+|BncnD|)|AnBnCnD|4=(60+40+24+17) (20+12+8+8+5+3)+(4+2+1+1) 0 4 (理由见说明部分)=89因此不超过 120 的素数个数=120 1 89=30 (因为 1 不是素数)说明:|A|=int(120/2); |A B|=int(120/lcd(2,3);|A B C|=int(120/lcd(2,3,5); |A

5、 B C D|=int(120/lcd(2,3,5,7).二 集合关系证明1 设 A,B,C 是任意集合 , 证明（1）（AB）C=A（BUC）（2）AAC? BACAAC? BC ? A? B（合计 12 分: 每小题 6 分; 格式 3 分, 过程每错一步扣 1 分） 证明(1) 逻辑演算法 : ? x,x (A B) C? x (A B)A?x C (定义)? (x AA?x B)A?x C (定义 )? x AA(?x BA?x C) (A的结合律)? x AA?(x BVx C)(德摩根律)? x AA?x BUC (U定义)? x ABUC(定义)所以 (AB)C=A(BUC).所

6、以 A? B. 集合演算法 A=AA(CUC)（A对U的分配率）（补交转换律 ）（已知条件 AAC? BAC 与 A C? B C）=(BAC)U(BAC)(补交转换律 )=BA（CUC）（A对U的分配率）=B（排中律，同一律 ）得证.方法三 因为 AAC? BAC，A C? B C，所以集合演算法(AB)C=(AAB)AC=AA(BAC)=AA(BUC)=A(BUC) 得证.（补交转换律 ）（A的结合律）（德摩根律 ）（2） 逻辑演算法 : ? x,x A? x AA(CUC)(排中律 , 同一律 )x(AAC)U(AAC) xAACVxAC（U对A的分配率）（U的定义，补交转换律）? x?

7、 x? x? x? xBACVxBC(BAC)U(BC)(BAC)U(BAC)BA(CUC) B (排中律，（已知条件 AAC? BAC 与 A C? B（U的定义） （补交转换律（A对U的分配率C)同一律 ）（同一律 , 排中律 ）=(AAC)U(AAC)=(AAC)U(AC) ?(BAC)U(BC)(AnC)U(A C)? (BnC)U(B C)|,整理即得 A? B,得证 2 求下列等式成立的充分必要条件(1) AB=BA(2) (AB)n(AC)=?(合计 10 分: 每小题 5 分; 正确给出充分必要条件 2 分, 理由 3 分) 解(1) AB=BA方法一两边同时UA 得：A=(B

8、 A)UA=BUA ? B? A;同理可得 A? B,综合可得 A=B.另一方面，当 A=B 时显然有 A B=B A.因此所求充要条件为A=B.方法二? x,xABAxBA? x(AB)n(BA)? x ?所以 A B=B A? AB=?ABA=?A? BAB? A ? A=B因此 A=B 即为所求 (2) (AB)n(AC)=? ? (AnB)n(AnC)=?An(BnC)=? An(BUC)=?A(BUC)=?A? BUC所以 A? BUC 即为所求充要条件说明：这类题型一般先求出必要条件 , 再验证其充分性三 设全集为 n 元集，按照某种给定顺序排列为E=XI,X2,xn.在计算机中可

9、以用长为n 的0,1 串表示 E 的子集令 m 元子集 A=xi1,Xi2,Xim,则 A 所对应的 0,1 串为 jlj2jn,其中 当 k=i1,i2,im时jk=1,其它情况下 jk=0.例如，E=1,2，,8,贝 y A=1,2,5,6和 B=3,7对应的 0,1 串分别为 11001100 和 00100010.(1) 设 A 对应的 0,1 串为 10110010,则-A 对应的 0,1 串是什么？设 A 与 B 对应的 0,1 串分别为 i1i2in和 j1j2jn,且 AUB, AnB, A B, A B 对应的 0,1 串分另U为 a1a2an, b1b2bn, C1C2cn, d1d2dn,求 ak,bk,ck,dk, k=1,2,n.(合计 15 分：(1)3 分; (2)12 分, 每个结果正确 2 分, 求解过程 4 分)解 下述运算是二进制数的位运算(1) 01001101(2) ak=ikVjk, bk=ikAjk, Ck=ik