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

《离散数学》习题一参考答案第一节集合的基数1.证明两个可数集的并是可数集。证明：设A，B是两可数集，},,,,,{321naaaaA，},,,,,{321nbbbbBjbiaNBAfji212:，f是一一对应关系，所以|A∪B|=|N|=0。2．证明有限可数集的并是可数集证：设kAAAA321,,是有限个可数集，kiaaaaAiniiii,,3,2,1),,,,,(321ikjaNAAfijkii)1(:1，f是一一对应关系，所以|A|=|kiiA1|=|N|=0。3.证明可数个可数集的并是可数集。证：设kAAAA321,,是无限个可数集，,3,2,1),,,,,(321iaaaaAiniiiiijijiaNAAfijii)2)(1(21:1，所以f是一一对应关系，所以|A|=|1iiA|=|N|=0。4.证明整系数多项式所构成的集合是可数集。证明：设整系数n次多项式的全体记为}|{1110ZaaxaxaxaAinnnnn则整系数多项式所构成的集合1NnAA；由于kx的系数ka是整数，那么所有kx的系数的全体所构成的集合是可数集，由习题2“有限个可数集的并是可数集”可得nA是可数集，再又习题4“可数个可数集的并是可数集”得出整系数多项式所构成的集合1NnAA也是可数集。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．证明正有理数集合是可数集，从而能证明有理数集是可数集。证明：因为},|{NnmnmQ，是正分数集，设},,4,3,2,1},|{miNninAi，iA是可数集，并1iiAQ由可数集性质4“可数个可数集的并仍然是可数集”，所以正有理数集合是可数集。有理数集Q=QQ}0{，由可数集性质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．已知}|{7NnnA，}|{109NnnB，求（1）A，B的基数；（2）A∪B，A∩B的基数。解：（1）nnNNnnAf77)|[:，f是一一对应关系，所以|A|=N|=0nnNNnnBf109109)|[:，f是一一对应关系，所以|B|=N|=0（2）有可数集性质（2）可得A∪B是可数集，既|A∪B|=N|=0因为BAnn71091097)()(，所以A∩B≠φnnNNnnBAf71097109)()|)[(:，f是一一对应关系，所以|A∩B|=N|=09.设A为任意集合，证明P（A）与{0，1}A等势，其中{0，1}A为A到{0，1}的全体函数。解：若)(xfA是A到{0，1}上的一个集函数，则AxAxxfA01)(f：ρ（A）→A}1,0{B→)(xfB所以f是一一对应的，即ρ（A）与A}1,0{等势。10.集合A，B的笛卡尔乘积可表示为A×B＝｛〔a，b〕│a∈A，b∈B｝，若A1，A2，…，An是可数集，证明A1×A2×…×An也是可数集。解：．设A=},,,,,{321naaaa，B=},,,,,{321nbbbb，并C=A×B},|),{(BbAaba=1nnA，}|){(,BbbaAiinn，因为nA是可数集，n=1，2，3，…，所以C=A×B=1nnA也是可数集，（可数个可数集是可数集）。同理A×B×C也是可数集，由于nAAAA,,,3,21是有限个可数集，所以nAAAA321也是可数集。