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

第六章作业 评分要求：

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∩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的素数个数.

分析: 本题有一定难度, 难在如何定义集合. 考虑到素数只有1和其自身两个素因子, 而不超过120的合数的最小素因子一定是2,3,5或7(比120开方小的素数), 也就是说, 不超过120的合数一定是2,3,5或7的倍数. 因此, 可定义4条性质分别为2,3,5或7的倍数, 先求出不超过120的所有的合数, 再得出素数的个数.

解 定义集合: 设全集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分) 证明

(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) (补交转换律) 得证.

(2) 逻辑演算法: ?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分) 解

(1) 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即为所求充要条件.

说明: 这类题型一般先求出必要条件, 再验证其充分性.

三 设全集为n元集, 按照某种给定顺序排列为E={x1,x2,…,xn}. 在计算机中可以用长为n的0,1串表示E的子集. 令m元子集A={xi1,xi2,…,xim}, 则A所对应的0,1串为j1j2…jn, 其中 当k=i1,i2,…,im时jk=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串是什么?

(2) 设A与B对应的0,1串分别为i1i2…in和j1j2…jn, 且A∪B, A∩B, A－B, A⊕B对应的0,1串分别为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∨jk, bk=ik∧jk, ck=ik∧?jk, dk=(ik∧?jk)∨(?ik∧jk).

说明: 这里ck和dk的求解可以使用主范式求解. ck, dk的真值表如下

ik 0 0 1 jk 0 1 0 ck 0 0 1 0 dk 0 1 1 0 1 1 因此可用主析取范式表示ck和dk如下: ck?m2=ik∧?jk dk?m1∨m2=(?ik∧jk)∨(ik∧?jk).

本文来源：https://www.bwwdw.com/article/jti5.html