离散数学-第六章集合代数课后练习习题及答案

离散数学-第六章集合代数课后练习习题及答案第六章作业评分要求：573.1—有限集合计数问题20104421对60个人的调查表明,有25人阅读《每周新闻》杂志,26人阅读《时代》杂志,2691188(1)求3(2)分别求只阅读《每周新闻》、《时代》和《财富》杂志的人数.解定义集合:设E={x|xA={x|x阅读《每周新闻》},B={x|x阅读《时代》},C={x|x阅读《财富》}由条件得|E|=60,|A|=25,|B|=26,|C|=26,|A∩C|=9,|A∩B|=11,|B∩C|=8,|E-A∪B∪C|=8(1)阅读全部3种杂志的人数=|A∩B∩C|=|A∪B∪C|－(|A|+|B|+|C|)+(|A∩B|+|A∩C|+|B∩C|)=(60-8)－(25+26+26)+(11+9+8)=3(2)只阅读《每周新闻》的人数=|A－B∪C|=|A－A∩(B∪C)|=|A－(A∩B)∪(A∩C)|=|A|－(|A∩B|+|A∩C|－|A∩B∩C|)=25－(11+9-3)=8同理可得只阅读《时代》的人数为10,只阅读《财富》的人数为12.2使用容斥原理求不超过120的素数个数.11202,3,57(1201202,3,5742,3,57120解定义集合:设全集E={x|x∈Z∧1≤x∧x≤120}A={2k|k∈Z∧k≥1∧2k≤120},B={3k|k∈Z∧k≥1∧3k≤120},C={5k|k∈Z∧k≥1∧5k≤120},D={7k|k∈Z∧k≥1∧7k≤120}.则不超过120的合数的个数=|A∪B∪C∪D|－4 因为2,3,5,7不是合)=(|A|+|B|+|C|+|D|)－(|A∩B|+|A∩C|+|A∩D|+|B∩C|+|B∩D|+|C∩D|)+(|A∩B∩C|+|A∩B∩D|+|A∩C∩D|+|B∩C∩D|)－|A∩B∩C∩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∪C)(2)A∩C?B∩C∧A－C?B－C?A?B(合计12分:每小题6分;格式3分,过程每错一步扣1分)证明逻辑演算法:?x,x∈(A－B)－C?x∈(A－B)∧?x∈C(－定义)?(x∈A∧?x∈B)∧?x∈C(－定义)?x∈A∧(?x∈B∧?x∈C)(∧的结合律)?x∈A∧?(x∈B∨x∈C)(德摩根律)?x∈A∧?x∈B∪C(∪定义)?x∈A－B∪C(－定义)所以(A－B)－C=A－(B∪C).集合演算法(A－B)－C=(A∩~B)∩~C(补交转换律)=A∩(~B∩~C)(∩的结合律)=A∩~(B∪C)(德摩根律)=A－(B∪C)(补交转换律)得证.逻辑演算法:?x,x∈A?x∈A∩(C∪~C)(排中律,同一律)?x∈(A∩C)∪(A∩~C)(∪对∩的分配率)?x∈A∩C∨x∈A－C(∪的定义,补交转换律)?x∈B∩C∨x∈B－C(已知条件A∩C?B∩C与A－C?B－C)?x∈(B∩C)∪(B－C)(∪的定义)?x∈(B∩C)∪(B∩~C)(补交转换律)?x∈B∩(C∪~C)(∩对∪的分配率)?x∈B(排中律,同一律)所以A?B.集合演算法A=A∩(C∪~C)(同一律,排中律)=(A∩C)∪(A∩~C)(∩对∪的分配率)=(A∩C)∪(A－C)(补交转换律)?(B∩C)∪(B－C)(已知条件A∩C?B∩C与A－C?B－C)=(B∩C)∪(B∩~C)(补交转换律)=B∩(C∪~C)(∩对∪的分配率)=B(排中律,同一律)得证.方法三因为A∩C?B∩C,A－C?B－C,所以(A∩C)∪(A－C)?(B∩C)∪(B－C)|,整理即得A?B,得证.2求下列等式成立的充分必要条件(1)A－B=B－A(2)(A－B)∩(A－C)=?(合计10分:每小题5分;正确给出充分必要条件2分,理由3分)解A－B=B－A方法一两边同时∪A得:A=(B－A)∪A=B∪A?B?A;同理可得A?B,综合可得A=B.另一方面,当A=B时显然有A－B=B－A.因此所求充要条件为A=B.方法二?x,x∈A－B∧x∈B－A?x∈(A－B)∩(B－A)?x∈?所以A－B=B－A?A－B=?∧B－A=??A?B∧B?A?A=B因此A=B即为所求.(2)(A－B)∩(A－C)=??(A∩~B)∩(A∩~C)=??A∩(~B∩~C)=??A∩~(B∪C)=??A－(B∪C)=??A?B∪C所以A?B∪C即为所求充要条件.说明:这类题型一般先求出必要条件,再验证其充分性.三设全集为nE={x1,x2,…,xn}.n0,1EmA={xi1,xi2,…,xim},A0,1k=i1,i2,…,imjk=1,其它情况下jk=0.例如,E={1,2,…,8},则A={1,2,5,6}和B={3,7}对应的0,1串分别为11001100和00100010.(1)设A对应的0,1串为10110010,则~A对应的0,1串是什么?AB0,1i1i2…inj1j2…jn,且A∪B,A∩B,A B0,1a1a2…an,b1b2…bn,c1c2…cn,d1d2…dn,求k=1,2,…,n.15(1)3(2)1224下述运算是二进制数的位运算(1)01001101(2)ak=ik∨jk,bk=ik∧jk,ck=ik∧?jk,dk=(ik∧?jk)∨(?ik∧