离散数学及应用习题及答案3-1.docx

应用离散数学 集合与关系第3章：集合与关系§3.1 集合及其运算习题3.11. 判断下列命题成真还是成假（这里表示空集） （1） （2） （3） （4） （5） （6） （7） （8） （9） （10） （11） （12）解 成真的有：（1）（3）（4）（5）（8）（9）（10）（11） 成假的有：（2）（6）（7）（12）2. 设，，，全集，求下列集合（1） （2）（3） （4）p(A)（5）p(A)- p(BC)解 （1）={4}（2）={1，3，5，6}（3）={2，3，4，5，6}（4）p(A)={ Æ，{1}，{4}，{1，4}}（5）p(A)- p(BC)={{1}，{1，4}}3. 某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有两人会打这三种球已知6个会打网球的人中有4人会打排球求不会打球的人数解 设A表示会打篮球的人的集合，B表示会打排球的人的集合，C表示会打网球的人的集合据题意有： |A|=14, |B|=12,| AÇB|=6，|AÇC|=5，|AÇBÇC|=2，|C|=6，|BÇC|=4，据公式|AÈBÈC|=|A|+|B|+|C|-| AÇB |-| AÇC |-| BÇC |+|AÇBÇC|=14+12+6-6-5-4+2=19所以不会打球的人数为25-19=6。

所以有6个人不会打球4. 设是全集的任意子集，证明（1）分配律： （2）吸收律： ，（3）德·摩根律： ，（4）德·摩根律： （5）德·摩根律： 解 用集合运算的定义方法证明：（1）A ∩ (B ∪ C) = { x | xÎAÙxÎ B∪C }= { x | xÎAÙ (xÎBÚ xÎC) }= { x | (xÎAÙ xÎB)Ú( xÎAÙ xÎC) }= (A ∩ B) ∪ (A ∩ C)（2）AÈ( AÇB) = { x | xÎA Ú xÎ AÇB}= { x | xÎA Ú（xÎA Ù xÎB）}={ x | xÎA}=A AÇ ( AÈB) = { x | xÎA ÙxÎ AÈB}= { x | xÎA Ù（xÎAÚ xÎB）}={ x | xÎA}=A（3）（AÈB）C= { x |xÎE Ù¬（ xÎA Ú xÎB） }={ x |¬xÎA Ù¬xÎB }=ACÇBC（4）（AÇB）C= { x |xÎE Ù¬（ xÎA Ù xÎB） }={ x |¬xÎA Ú¬xÎB }=ACÈBC（5）A − (B ∩C) = (A − B)∪(A − C) 设x ∈ A − (B ∩C)⇔(x ∈ A) ∧ (x Ï B∩C)⇔(x ∈ A) ∧ ¬[(x ∈ B) Ù (x ∈ C)]⇔(x ∈ A) ∧ (¬(x ∈ B) Ú¬(x ∈ C))⇔((x ∈ A) ∧ (x Ï B)) Ú( (x ∈ A)∧ (x Ï C))⇔[(x ∈ A) ∧ (x Ï B)] Ú [(x ∈ A) ∧ (x Ï C)] ⇔(x ∈ A − B) Ú (x ∈ A − C)⇔x ∈ (A − B) ∪ (A − C) 5. 设是任意集合，证明（1）（2）（3）（4）（5）（6）解 （1）左式= (A ∩ Bc) ∪ (B ∩ Ac) = [(A ∩ Bc) ∪ B] ∩ [(A ∩ Bc) ∪ Ac] =(A∪B)∩(Bc ∪B)∩(A∪Ac)∩(Bc ∪Ac) =(A∪B)∩E∩E∩(Ac ∪Bc) = (A ∪ B) ∩ (A ∩ B)c = (A ∪ B) − (A ∩ B) （2）因为所以。

3）右式=(A − C) − (B − C) = (A ∩ Cc) ∩ (B ∩ Cc)c =(A∩Cc)∩(Bc ∪C) =(A∩Cc ∩Bc)∪(A∩Cc ∩C) = (A ∩ Cc ∩ Bc) ∪ Æ= A ∩ Cc ∩ Bc = (A − B) − C =左式（4）(A − B) − C= (A − B) ∩ Cc = (A ∩ Bc) ∩ Cc =(A ∩Cc) ∩Bc = (A − C) – B（5）AÅB= (AÈB)-(AÇB)= (AÈB) Ç (ACÈBC)(AÅB)ÅC=((AÅB) ÈC) Ç ((AÅB) CÈCC)=((AÈB) Ç (ACÈBC)) ) ÈC) Ç (((AÈB) Ç (ACÈBC))CÈCC)=(AÈB ÈC) Ç(ACÈBC ÈC) Ç((AC Ç BC) È (AÇB)) ÈCC)=(AÈB ÈC) Ç(ACÈBC ÈC) Ç (ACÈB ÈCC) Ç (AÈBC ÈCC) AÅ(BÅC) =(BÅC) Å A 用代替规则得=(BÈC ÈA) Ç(BCÈCC ÈA) Ç (BCÈCÈAC) Ç (BÈCC ÈAC)=左边（6）因为所以。

6. 设是任意集合，证明 （1） （2） （3）针对（2）举一反例，说明对某些集合是不成立的解 （1）设xÎp(A) ∩ P(B) ⇔ xÎP(A)∧xÎP(B) ⇔ x Í A∧ xÍ B⇔ x∩A= x∧x∩B= x ⇒ x∩(A∩B)= x∩x= x⇔ x Í A∩ B ⇔ xÎp(A ∩ B)所以P(A) ∩ P(B) ÍP(A ∩ B)另一方面，设xÎp(A ∩ B) ⇔ x Í A∩ B ⇒ x Í A∧ xÍ B⇔ xÎP(A)∧xÎP(B)⇔xÎp(A) ∩ P(B) 所以P(A ∩ B) Í P(A) ∩ P(B)因此，结论成立 （2）设xÎp(A) ∪ P(B) ⇔ xÎP(A) ∨xÎP(B) ⇔ x Í A∨ xÍ B⇒ x Í A∪B ⇔ x Í A∪ B ⇔ xÎp(A∪ B)所以P(A) ∪P(B) ÍP(A ∪ B) 因此，结论成立 （3）举例：A={1，2}，B={2，5} p(A)∪P(B)={Æ，{1}，{2}，{5}，{1，2}，{2，5}}但是P(A ∪ B)= {Æ，{1}，{2}，{5}，{1，2}，{2，5}，{1，5}，{1，2，5}}7. 设是任意集合，判断下列式子是否正确。

如果正确请给出证明，否则请举一个反例 （1） （2） （3） （4） （5） （6） 解 （1）错，如果A={1，2}，B={2，3}，C={1，2，3，4}（2）错，如果A={1，2}，B={2，3}，C=Æ （3） 正确，用反证法证明，若，可不妨设a）若，则根据集合对称差运算的定义，，，与矛盾b）若，则根据集合对称差运算的定义，，，也与矛盾 （4）正确，用反证法证明，若不成立，则存在a）若，则，从而，与矛盾b）若，则，从而，也与矛盾5）正确AÍB Þ AÈB=B CÍD Þ CÈD=D (AÈC)È（BÈD）=（AÈB）È（CÈD)=BÈD 从而AÈCÍBÈD （6）不正确举例：A={1，2}，B={1，2，3}，C={1，3}，D={1，2，3}但是AÈC=BÈD8. 假定全集（1）用位串表示下列集合： （2）写出下列位串各自代表的集合 1 111 001 111 0 101 111 000 1 000 000 001 解 （1）=0011100000 =1010010001 =0111001110 （2）1 111 001 111={1，2，3，4，7，8，9，10} 0 101 111 000 ={2，4，5，6，7} 1 000 000 001={1，10}9. 说明怎样用位串的按位运算求下列集合，其中，，， 。

（1） （2） （3） （4）解 在全集中考虑问题，则集合A的位串是：11 111 000 000 000 000 000 000 000，集合B的位串是：01 110 010 000 000 010 001 010 000，集合C的位串是：00 101 000 100 000 100 000 100 111，集合D的位串是：00 011 001 100 001 100 001 100 110，集合的位串是 11 111 010 000 000 010 001 010 000，集合的位串是 01 110 000 000 000 000 000 000 000，集合的位串是 01 111 010 100 000 110 001 110 111，集合的位串是 01 111 010 000 000 010 001 010 000，集合的位串是 00 111 001 100 001 100 001 100 111，集合的位串是 11 111 011 100 001 110 001 110 111， 这些位串表示的集合为： 杭电－周丽、方景龙 第三章7。