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

第六章作业评分要求：1. 合计57分2. 给出每小题得分(注意：写出扣分理由).3. 总得分在采分点1处正确设置•一有限集合计数问题(合计20分：每小题10分，正确定义集合得 4分，方法与过程4分，结果2分)要求：掌握集合的定义方法以及处理有限集合计数问题的基本方法1对60个人的调查表明，有25人阅读《每周新闻》杂志，26人阅读《时代》杂志，26人阅 读《财富》杂志，9人阅读《每周新闻》和《财富》杂志 ，11人阅读《每周新闻》和《时代》 杂志，8人阅读《时代》和《财富》杂志 ，还有8人什么杂志也不读.(1) 求阅读全部3种杂志的人数；(2) 分别求只阅读《每周新闻》、《时代》和《财富》杂志的人数 .解定义集合：设E={x|x是调查对象}，A={x|x阅读《每周新闻》}，B={x|x阅读《时代》}，C={x|x阅读《财富》}由条件得 |E|=60, |A|=25, |B|=26, |C|=26, |A n C|=9, |A n B|=11, |B n C|=8, |E-A U B U C|=8(1) 阅读全部3种杂志的人数=|A n b n C|=|A U B U C| — (|A|+|B|+|C|)+(|A n B|+|A n C|+|B n C|)=(60-8) — (25+26+26)+(11+9+8)=3(2) 只阅读《每周新闻》的人数 =|A — B U C|=|A — A n (B U C)|=|A — (A n B) U (A n C)|=|A| — (|A n B|+|A n C|— |A n B n C|)=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 € Z A K x A x < 120}A={2k|k € Z A k > 1 A 2k< 120},B={3k|k € Z A k > 1 A 3k< 120},C={5k|k € Z A k > 1 A 5k< 120},D={7k|k € Z A k > 1 A 7k< 120}.则不超过120的合数的个数=|A U B U C U D| — 4 (因为2,3,5,7不是合数)=(|A|+|B|+|C|+|D|)— (|A n b|+|a n C|+|A n d|+|b n C|+|B n D|+|cn d|)+(|a n b n C|+|A n b n d|+|a n cn d|+|b n cn d|) — |A n b n c n d| — 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 B C D|=int(120/lcd(2,3,5,7)).二 集合关系证明1 设 A,B,C 是任意集合 , 证明（1） （A — B） — C=A — （B U C）（2） A A C? B A C A A — C? B — C ? 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 € A A (?x € B A ?x € C) (A 的结合律)? x € A A ?(x € B V x€ C)(德摩根律)? x € A A ?x€ BU C (U定义)? x€ A—BUC (—定义)所以 (A—B)—C=A—(BU C).集合演算法(A—B)—C=(AA ~B)A ~C =AA (~BA ~C) =AA ~(BU C) =A— (BU C) 得证.（补交转换律 ）（A的结合律）（德摩根律 ）（补交转换律 ）（2） 逻辑演算法 : ? x,x€ A? x€ AA (CU ~C) (排中律 , 同一律 )x€ (AA C)U (AA ~C) x€ AA CV x€ A— C（U对A的分配率）（U的定义，补交转换律）? x€? x€? x€? x€? x€B A C V x€ B — C (BAC)U(B—C) (BA C)U (BA ~C)B A (C U ~C) B (排中律 ，（已知条件A A C? B A C与A — C? B（U的定义） （补交转换律（A对U的分配率C)同一律 ）（同一律 , 排中律 ）所以 A? B. 集合演算法 A=A A (CU ~C)=(AA C)U (AA ~C) =(AA C)U (A— C) ? (B A C)U (B— C)（A对U的分配率）（补交转换律 ）（已知条件 A A C? B A C 与 A — C? B — C）=(BA C)U (BA ~C) (补交转换律 )=B A （CU ~C） （A对U的分配率）=B （排中律 ， 同一律 ）得证.方法三 因为 AA C? BA C， A— C? B— C， 所以(A n C) U (A — C)? (B n C) U (B — C)|,整理即得 A? B,得证• 2 求下列等式成立的充分必要条件(1) A—B=B—A(2) (A —B)n (A— C)=?(合计 10 分: 每小题 5分; 正确给出充分必要条件 2分, 理由 3 分) 解(1) A—B=B—A方法一两边同时U A得：A=(B — A) U A=B U A ? B? A;同理可得A? B,综合可得 A=B.另一方面，当A=B时显然有A — B=B — A.因此所求充要条件为 A=B.方法二? x,x€ A — B A x€ B — A? x € (A — B) n (B — A)? x € ?所以 A— B=B — A? A—B=? A B—A=?A? B A B? A ? A=B因此 A=B 即为所求 • (2) (A —B)n (A— C)=? ? (An ~B)n (An ~C)=?A n (~B n ~C)=? A n ~(B U C)=?A—(BU C)=?A? BU C所以A? BUC即为所求充要条件•说明 ： 这类题型一般先求出必要条件 , 再验证其充分性三 设全集为n元集，按照某种给定顺序排列为 E={xi,x2,…,xn}.在计算机中可以用长为 n的0,1串表示E的子集•令m元子集A={x i1,Xi2,…,Xim},则A所对应的0,1串为jlj2…jn,其中 当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串分别为i1i2…in和j1j2…jn,且A U B, A n B, A — B, A ® B对应的0,1 串分另U为 a1a2…an, b1b2…bn, C1C2…cn, d1d2…dn,求 ak,bk,ck,dk, k=1,2,…,n.(合计15分： (1)3 分; (2)12 分, 每个结果正确 2分, 求解过程 4分)解 下述运算是二进制数的位运算(1) 01001101(2) ak=ik V j k, bk=ik A jk, Ck=ikA ?jk, dk=(i kA ?jk) V (?ik A jk).说明：这里Ck和dk的求解可以使用主范式求解 .Ck, dk 的真值表如下ikjkCkdk0000010110111100因此可用主析取范式表示 Ck和dk如下:Ck? m2=ikA ?jkdk? mi V m2=(?ik A jk) V (i kA ?jk).。