离散数学第二版邓辉文编著第一章第五节习题答案 VIP免费

1.5集合的划分与覆盖习题1.51.设},,,{dcbaA，求出集合A的所有不同的划分.解可以按照划分的块的数目依次求出A的所有不同的划分共15个.仅一个划分块:}},,,{{1dcba.有两个划分块:}},,{},{{2dcba，}},,{},{{3dcab，}},,{},{{4dbac，}},,{},{{5cbad；}},{},,{{6dcba，}},{},,{{7dbca，}},{},,{{8cbda.有三个划分块:}},{},{},{{9dcba，}},{},{},{{10dbca，}},{},{},{{11cbda，}},{},{},{{12dacb，}},{},{},{{13cadb，}},{},{},{{14badc.有四个划分块:}}{},{},{},{{15dcba.2.对于整数集合Z，令}Z|3{1kkA，}Z|13{2kkA，}Z|23{3kkA,则},,{321AAA是Z的划分.试验证之.解因为(1)iA，3,2,1i.(2)jiAA，3,2,1,,jiji.(3)321AAAZ.所以，},,{321AAA是Z的划分.3.设}|{IiAi是集合A的一种划分，对于集合B，所有BAi的BAi组成的集合是BA的划分.试证明之.证对于任意ji，因为jiAA，于是BAABABAjiji)()(B.又因为AAIii，所以BABABAIiiIii)(.故BABAii|{},Ii是BA的划分.4.设集合A有两种划分}|{1IiAi和}|{2JjBj，问21是否必是A的划分，为什么？21呢?解21及21均不一定是A的划分.例如},,,{dcbaA，取A的划分为}},,{},{{1dcba，}},{},{},{{2cbda，这时}},,{},,{},{},{{21dcbcbda，}},,{{21dcb，它们都不是A的划分.5.证明:设1n，则(1).1)1,(nS(2).1),(nnS(3).12)2,(1nnS证(1)和(2)显然.(3)将n个元素的集合A划分成2个块1A和2A，先将A中的第一个放在第一个块1A中，对于其余的1n个元素分别考虑是否与第一个元素在同一个块1A中，只有两种情况发生:1Ax或1Ax，于是共有1122...22nn种放的方式，但要排除所有元素都在1A中而2A为空的情形.故.12)2,(1nnS6.设},,,,,,,,,,{jihgfedcbaA},,,,{1dcbaA},,,{2gfeA},,,,{3igedA},,,{4jhdA},,,{5jihA},,,,,,{6jhfcbaA分别判定下列集合是否是A的划分、覆盖:(1)},,{521AAA.(2)},,{531AAA.(3)}.,{63AA(4)}.,,{432AAA解显然对于任意61i，有iA.(1)因为21AA，51AA，52AA且AAAA521，所以},,{521AAA是A的划分.(2)由于Af而531AAAf，所以},,{531AAA不是A的覆盖.(3)因为63AA，且AAA63，所以},{63AA是A的划分.(4)由于Aa而432AAAa，所以},,{432AAA不是A的覆盖.7.写出集合},{baA的所有不同的覆盖.解由A得到的非空子集为},{},{},{baba，于是},{baA的所有不同的覆盖分别为(1)}},{{ba.(2)}}{},{{ba.(3)}},{},{{baa.(4)}},{},{{bab.(5)}},{},{},{{baba.