离散数学习题一,二参考答案

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《离散数学习题一,二参考答案》，欢迎阅读！

《离散数学》习题一参考答案

第一节 集合的基数

1.证明两个可数集的并是可数集。

证明：设A，B是两可数集，A{a1,a2,a3,,an,}，B{b1,b2,b3,,bn,}

ABN

f:ai2i1 ，f是一一对应关系，所以|A∪B|=|N|=0。 b2jj

2．证明有限可数集的并是可数集

证：设A1,A2,A3Ak是有限个可数集，Ai(ai1,ai2,ai3,ain,),i1,2,3,,k

kkAAiN

，f是一一对应关系，所以|A|=|Ai|=|N|=0。 f:i1

i1aijj(k1)i



3.证明可数个可数集的并是可数集。

证：设A1,A2,A3Ak是无限个可数集，Ai(ai1,ai2,ai3,ain,),i1,2,3,





AAiNi1f:， 1aij(ij1)(ij2)i

2

所以f是一一对应关系，所以|A|=|

A|=|N|=。

i



0

i1



4.证明整系数多项式所构成的集合是可数集。 证明：设整系数n次多项式的全体记为

An{a0xna1xn1an1xan|aiZ}

则整系数多项式所构成的集合AAn；

N1

由于xk的系数ak是整数，那么所有xk的系数的全体所构成的集合是可数集，由习题2“有限个可数集的并是可数集”可得An是可数集，再又习题4“可数个可数集的并是可数集”得出整系数多项式所构成的集合AAn也是可数集。

N1


5.证明不存在与自己的真子集等势的有限集合.

证明：设集合A 是有限集，则|A|=n，若B是A的真子集，则|B|≤|A|=n，A-B≠φ，即|A-B|=|A|-|AB|＞0；又A=（A-B）∪B，（A-B）B=φ，所以，，就是|A|＞|B|，即得结论。

6．证明正有理数集合是可数集，从而能证明有理数集是可数集。

m

证明：因为Q{|m,nN}，是正分数集，

n



n

设Ai{|nN},i1,2,3,4,,m}，Ai是可数集，并QAi

ii1

由可数集性质4“可数个可数集的并仍然是可数集”，所以正有理数集合是可数

集。

有理数集Q=Q{0}Q，由可数集性质1，2，马上可得有理数集是可数集。 7．A、B为无限集，试说明下面的集合是否是无限集。 （1）A∪B （2）A∩B；（3）A－B；（4）A×B 答：（1）A∪B是无限集，由可数集性质（2）可得。 （2）A∩B不一定是无限集，若A∩B=φ，则|A∩B|=0； （3）A－B不一定是无限集，若A=B，则A－B=φ，

（4）A×B是无限集。相当于无限个无限集的并是无限集。 8．已知A{n7|nN}，B{n109|nN}，求 （1）A，B的基数；（2）A∪B，A∩B的基数。

A[n7|nN)N解：（1）f:，f是一一对应关系，所以|A|=N|=0 7

nn

B[n109|nN)N

f:，f是一一对应关系，所以|B|=N|=0 109

nn

（2）有可数集性质（2）可得A∪B是可数集，既| A∪B|=N|=0 因为(n7)109(n109)7AB，所以A∩B≠φ

AB[(n109)7|nN)N

，f是一一对应关系，所以| A∩B|=N|=0 f:1097

(n)n9.设A为任意集合，证明P（A）与{0，1} A等势，其中{0，1} A为A到{0，1}的

全体函数。

1xA

解：若fA(x)是A到{0，1}上的一个集函数，则fA(x)

0xA

f：ρ（A）→{0,1}

B →fB(x) 所以f是一一对应的，即ρ（A）与{0,1}等势。

A

A

本文来源：https://www.wddqxz.cn/8252b155c5da50e2524d7f55.html