离散数学及应用第3版习题及答案

第3章：集合与关系

§3.1集合及其运算

习题3.1

1.判断下列命题成真还是成假（这里。表示空集）

(1)0=/(2)。e。

(3){。}(4)

(5){a}o{a}(6){a}G{a}

(7){a}o{{«}}(8){a}G{{a}}

(9){a,b}c[a,b,c,{a,b,c}}(10){a,b}e{a,b,c,[a,b}}

(11){a,h}c{a,h,{{a,b}}}(12){a,b}e{a,b,{{a,b}}}

解成真的有：(1)(3)(4)(5)(8)(9)(10)(11)

成假的有：(2)(6)(7)(12)

2.设4={1,4},B={1,2,5},C={2,4},全集E={1,2,3,4,5,6},求下列

集合

(1)AC\BC(2)(AA5)UCC'

(3)(AdB)r(4)p(A)

(5)p(A)-p(Bc)

解

(1)An"*}

(2)(AA5)UCC={1,3,5,6}

(3)(AP|B)c={2,3,4,5,6)

⑷p(A)={0,{1},{4},{1,4})

(5)p(A)-p(Bc)={{l},{1,4}}

3.某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会

打篮球和网球，还有两人会打这三种球。已知6个会打网球的人中有4人会打排球。求不会打

球的人数。

解设A表示会打篮球的人的集合，B表示会打排球的人的集合，C表示会打网球的人的

集合。

据题意有:|A|=14,|B|=12,|AnB|=6,|AcC|=5,|AcBcC|=2,|C|=6,

|BcC|=4,

据公式|AuBuC|=|A|+|B|+|C|-|AcB|-|AnC|-|BcC|+1AnBnC|=14+12+6-6-5-4+2=19

所以不会打球的人数为25-19=6。

所以有6个人不会打球。

4.设A,B,C是全集E的任意子集，证明

(1)分配律：An(BUC)=(AnB)U(AAC)

(2)吸收律：AU(AnB)=A,An(AUB)=A

(3)德•摩根律：(AUB)，=A'、n6',

(4)德•摩根律：(AnB)c=AU厅

(5)德•摩根律：A-(5DC)=(A—B)U(A—C)

解用集合运算的定义方法证明：

(1)An(BUC)={x|xeZlAxeBUC}={x|xeA人(xwBvxe。}

={x|(XE4AxeB)v(XS4AxeC)}=(AnB)U(AnC)

(2)Au(AryB)={x|xeAvXGAryB}={x\xeAv(xeAAxeB)}

={x|x&A}-A

(AuB)={x|xeAAXSAuB}={x\x&AA(xeAvxeB)}

={x|xE}=A

(3)(AuB)c={x|XGEA-I(xwAvxeB)}={x\->xe/\A-nxeB}-AcnBc

(4)(AcB)c={x|xeEA-I(xe/4AXSB)}={x\-ixe>4v-ixeB}=AcuBc

(5)A-(BnC)=(A-B)U(A-C)

设xeA-(BnC)

Q(xeA)A(xgBnC)

o(xeA)AT(xGB)A(XGC)]

0(xeA)A(TxeB)v-(xec))

0((xeA)A(xiB))v((xeA)A(x任c))

=[(xeA)A(xB)]v[(xeA)A(xgC)]

o(xGA-B)v(x6A-C)

oxG(A-B)U(A-C)

5.设A,B,C是任意集合，证明

(1)(4-8)U(B-A)=(AUB)-(AnB)

(2)(A-B)-C=4-(BUC)

(3)(A-B)-C=(A-C)-(B-C)

(4)(A-B)-C=(A-C)-B

(5)(A㊉B)㊉C=A㊉(B㊉C)

(6)AA(3㊉C)=(ADB)㊉(ADC)

解(1)左式=(AcB。)U(BClA。)

=[(AnBc)UB]n[(AnBc)UAc]

=(AUB)n(BcUB)n(AUAc)n(BcUAC)

=(AUB)nEnEn(AcUBc)

=(AUB)n(AnB)c

=(AUB)-(AnB)

(2)因为

oxeAA-ixeBA——i(xeBvxeC)

<=>xeA/\—i(xGBIJC)<=>XGA-(JBUC)

所以(A—B)—C=A-(BUC)。

(3)右式=(A-C)-(B-C)=(AnCc)n(BnCc)c

=(AnCc)n(BcUC)=(AnCcnBc)U(AnCcnC)

=(AnCcnBc)U0=AnC。nBc

=(A-B)-C=左式

(4)(A-B)-C=(A-B)nCc=(AnBc)nCc

=(Ar>Cc)nB，=(A-C)-B

(5)A©B=(Au8)-(Ac8)=(AuB)C(AC<JBC)

(A㊉B)㊉C=((A㊉B)uC)c((A©B)^(5)

=((4ufi)c(AcuBc)))uC)c(((A'uB)c(AC(JBC))C(JC^)

=(AuBuC)n(4cuBcuC)c((A，cBc)u(AcB))uC(7)

=(A<JBUC)n(4cuBcuC)c(AcuBud)c(AuBcuC5)

A㊉(B㊉Q=(B㊉C)㊉A用代替规则得

=(BuCu4)S)c(BcuCuAc)c(8^(5(JAC)

=左边

(6)因为xe(AflB)㊉(AflC)=xe(AflB)U(AnC)A-lxeADBAC

=((xeA/\xeB)v(xeAAxeC))A—,(XGAAXEBAO

<=>(XGAAXGBUC)A(—ixGAV—ixeBPlC)

=(xeAAxe8UCA—ixeA)v(xeA/\xeBUC/\—ixeBDC)

<=>Ov(xeAA(xe1BUCA—1XGBnC))

oxe4AxeB㊉C=xeAn(3㊉C)

所以4n(8㊉。)=(ADB)㊉(ACIC)。

6.设A,3是任意集合，证明

(1)p(4)np(B)=p(Afl5)

(2)p(4)Up(5)qp(AUB)

(3)针对(2)举一反例，说明p(A)Up(B)=p(AUB)对某些集合A,B是不成立的。

解(1)设xep(A)nP(8)=xeP(A)AxeP(B)=xuA/\xcfi

oxr)A=x/\xr<B=x=>xn(AnB)=xnx=x=xqAnB=xep(AnB)

所以P(A)nP(B)cP(AnB)

另一方面，设xep(An8)=xqAcB=XRA/\xcB<=>xeP(/\)AxeP(B)

=xep(A)nP(B)

所以P(AnB)aP(A)nP(S)

因此，结论成立。

(2)设xep⑷UP(B)=xeP(A)VxeP(B)<=>xcAVxcB

=s>xc4UB<=>xc4U8=xep(AU8)

所以P⑷UP(B)cP(4UB)

因此，结论成立。

(3)举例：A={1,2},B={2,5}

p⑷UP(8)={0,{1},{2},{5},{1,2},{215})

但是P(AUB)={0,{1},{2},{5},{1,2},{2,5},{1,5},{1,2,5))

7.设A,B,C,。是任意集合，判断下列式子是否正确。如果正确请给出证明，否则请

举一个反例。

(1)AUC=8UC=4=8

(2)Anc=3nc=>A=B

(3)A㊉

(4)AnC=BnC，A—C=8-C=A=8

(5)A^B,CcD=>AUCcBUD

(6)AuB,CuD=AUCuBU。

解

(1)错，如果A={1,2},B={2,3},C={1,2,3,4)

(2)错，如果A={1,2},B={2,3},C=0

(3)A㊉3=A㊉C=3=C

正确，用反证法证明，若BRC,可不妨设xeB/xxeC。

(a)若XGA,则根据集合对称差运算的定义，XCA㊉3,xeA㊉C,与

A㊉B=A㊉C矛盾。

(b)若xeA,则根据集合对称差运算的定义，xeA㊉8,㊉C,也与

A㊉3=A㊉C矛盾。

所以A㊉B=A㊉Cn3=。。

(4)AACcBAC,A-C^B-C^A^B

正确，用反证法证明，若4=6不成立，则存在xeA/xxcB。

(a)若xeC,则xeADC,从而xeBDC,与xeB矛盾。

(b)若xeC,则xwA—C,从而xeB—C,也与xeB矛盾。

所以AACcBClC，A-C^B-C=>A^B.

(5)正确。七8=Au8=B

CcDnC<JD=D

(AJC)U(8UD)=(AJ8)USD)=8UD

从而Z^uCcBuD

(6)不正确。举例：A={1,2},B={1,2,3},C={1,3},D={1,2,3}

但是AuC=Bu。

8.假定全集七={1,2,3,4,5,6,7,8,9,10}

（1）用位串表示下列集合：

{3,4,5}{1,3,6,10}

{2,3,4,7,8.9}

(2)写出下列位串各自代表的集合

11110011110101111000

1000000001

解

(1){3,4,5}=0011100000{1,3,6,10}=1010010001

{2,3,4,7,8,9}=oiiioomo

(2)1111001111={1,2,3,4,7,8,9,10}

0101111000={2,4,5,6,7}

1000000001={1,10}

9.说明怎样用位串的按位运算求下列集合，其中A={a,b,C,d,e},

B-{b,c,d,g,p,t,v},C={c,e,i,o,u,x,y,z},D-{d,e,h,

i,n,o,t,u,x,y}。

(1)A\JB(2)API8

(3)(4UB)n(BUC)(4)AU3UCU。

解在全集E={a