離散數(shù)學(xué)-第六章集合代數(shù)課后練習(xí)習(xí)題及答案

第六章作業(yè)評(píng)分要求：1.合計(jì)57分2.給出每小題得分(注意:寫(xiě)出扣分理由).3.總得分在采分點(diǎn)1處正確設(shè)置.一有限集合計(jì)數(shù)問(wèn)題(合計(jì)20分:每小題10分,正確定義集合得4分,方法與過(guò)程4分,結(jié)果2分)要求:掌握集合的定義方法以及處理有限集合計(jì)數(shù)問(wèn)題的基本方法1對(duì)60個(gè)人的調(diào)查表明,有25人閱讀《每周新聞》雜志,26人閱讀《時(shí)代》雜志,26人閱讀《財(cái)富》雜志,9人閱讀《每周新聞》和《財(cái)富》雜志,11人閱讀《每周新聞》和《時(shí)代》雜志,8人閱讀《時(shí)代》和《財(cái)富》雜志,還有8人什么雜志也不讀.(1)求閱讀全部3種雜志的人數(shù);(2)分別求只閱讀《每周新聞》、《時(shí)代》和《財(cái)富》雜志的人數(shù).解定義集合:設(shè)E={x|x是調(diào)查對(duì)象},A={x|x閱讀《每周新聞》},B={x|x閱讀《時(shí)代》},C={x|x閱讀《財(cái)富》}由條件得|E|=60,|A|=25,|B|=26,|C|=26,|A∩C|=9,|A∩B|=11,|B∩C|=8,|E-A∪B∪C|=8(1)閱讀全部3種雜志的人數(shù)=|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)只閱讀《每周新聞》的人數(shù)=|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同理可得只閱讀《時(shí)代》的人數(shù)為10,只閱讀《財(cái)富》的人數(shù)為12.2使用容斥原理求不超過(guò)120的素?cái)?shù)個(gè)數(shù).分析:本題有一定難度,難在如何定義集合.考慮到素?cái)?shù)只有1和其自身兩個(gè)素因子,而不超過(guò)120的合數(shù)的最小素因子一定是2,3,5或7(比120開(kāi)方小的素?cái)?shù)),也就是說(shuō),不超過(guò)120的合數(shù)一定是2,3,5或7的倍數(shù).因此,可定義4條性質(zhì)分別為2,3,5或7的倍數(shù),先求出不超過(guò)120的所有的合數(shù),再得出素?cái)?shù)的個(gè)數(shù).解定義集合:設(shè)全集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}.則不超過(guò)120的合數(shù)的個(gè)數(shù)=|A∪B∪C∪D|－4(因?yàn)?,3,5,7不是合數(shù))=(|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(理由見(jiàn)說(shuō)明部分)=89因此不超過(guò)120的素?cái)?shù)個(gè)數(shù)=120－1－89=30(因?yàn)?不是素?cái)?shù))說(shuō)明:|A|=int(120/2);|AB|=int(120/lcd(2,3));|ABC|=int(120/lcd(2,3,5));|ABCD|=int(120/lcd(2,3,5,7)).二集合關(guān)系證明1設(shè)A,B,C是任意集合,證明(1)(A－B)－C=A－(B∪C)(2)A∩C?B∩C∧A－C?B－C?A?B(合計(jì)12分:每小題6分;格式3分,過(guò)程每錯(cuò)一步扣1分)證明(1)邏輯演算法:?x,x∈(A－B)－C?x∈(A－B)∧?x∈C (－定義)?(x∈A∧?x∈B)∧?x∈C (－定義)?x∈A∧(?x∈B∧?x∈C) (∧的結(jié)合律)?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 (補(bǔ)交轉(zhuǎn)換律)=A∩(~B∩~C) (∩的結(jié)合律)=A∩~(B∪C) (德摩根律)=A－(B∪C) (補(bǔ)交轉(zhuǎn)換律)得證.(2)邏輯演算法:?x,x∈A?x∈A∩(C∪~C) (排中律,同一律)?x∈(A∩C)∪(A∩~C) (∪對(duì)∩的分配率)?x∈A∩C∨x∈A－C (∪的定義,補(bǔ)交轉(zhuǎn)換律)?x∈B∩C∨x∈B－C (已知條件A∩C?B∩C與A－C?B－C)?x∈(B∩C)∪(B－C) (∪的定義)?x∈(B∩C)∪(B∩~C) (補(bǔ)交轉(zhuǎn)換律)?x∈B∩(C∪~C) (∩對(duì)∪的分配率)?x∈B (排中律,同一律)所以A?B.集合演算法A=A∩(C∪~C) (同一律,排中律)=(A∩C)∪(A∩~C) (∩對(duì)∪的分配率)=(A∩C)∪(A－C) (補(bǔ)交轉(zhuǎn)換律)?(B∩C)∪(B－C) (已知條件A∩C?B∩C與A－C?B－C)=(B∩C)∪(B∩~C) (補(bǔ)交轉(zhuǎn)換律)=B∩(C∪~C) (∩對(duì)∪的分配率)=B (排中律,同一律)得證.方法三因?yàn)锳∩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)=?(合計(jì)10分:每小題5分;正確給出充分必要條件2分,理由3分)解(1)A－B=B－A方法一兩邊同時(shí)∪A得:A=(B－A)∪A=B∪A?B?A;同理可得A?B,綜合可得A=B.另一方面,當(dāng)A=B時(shí)顯然有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即為所求充要條件.說(shuō)明:這類(lèi)題型一般先求出必要條件,再驗(yàn)證其充分性.三設(shè)全集為n元集,按照某種給定順序排列為E={x1,x2,…,xn}.在計(jì)算機(jī)中可以用長(zhǎng)為n的0,1串表示E的子集.令m元子集A={xi1,xi2,…,xim},則A所對(duì)應(yīng)的0,1串為j1j2…jn,其中當(dāng)k=i1,i2,…,im時(shí)jk=1,其它情況下jk=0.例如,E={1,2,…,8},則A={1,2,5,6}和B={3,7}對(duì)應(yīng)的0,1串分別為11001100和00100010.設(shè)A對(duì)應(yīng)的0,1串為10110010,則~A對(duì)應(yīng)的0,1串是什么?(2)設(shè)A與B對(duì)應(yīng)的0,1串分別為i1i2…in和j1j2…jn,且A∪B,A∩B,A－B,A⊕B對(duì)應(yīng)的0,1串分別為a1a2…an,b1b2…bn,c1c2…cn,d1d2…dn,求ak,bk,ck,dk,k=1,2,…(合計(jì)15分:(1)3分;(2)12分,每個(gè)結(jié)果正確2分,求解過(guò)程4分)解下述運(yùn)算是二進(jìn)制數(shù)的位運(yùn)算(1)01001101(2)ak=ik∨jk,bk=ik∧j