离散数学及其应用集合论部分课后习题答案

Forpersonaluseonlyinstudyandresearch;notforcommercialuse螅作业答案：集合论部分蚅P90:习题六腿5、确定下列命题是否为真。蚀（2）袅（4）{}螂（6）{,}{,,,{,}}ababcab袁解答：（2）假（4）真（6）真葿8、求下列集合的幂集。羄（5）{{1,2},{2,1,1},{2,1,1,2}}膃（6）{{,2},{2}}薃解答：芈（5）集合的元素彼此互不相同，所以{2,1,1,2}{1,2}，所以该题的结论应该为肄（6）{,{{,2}},{{2}},{{,2},{2}}}薄9、设{1,2,3,4,5,6}E，{1,4}A，{1,2,5}B,{2,4}C,求下列集合。肁（1）AB羇（2）()AB肄解答：羅（1）{1,4}{3,4,6}{4}AB螃（2）(){1}{2,3,4,5,6}AB肀31、设A,B,C为任意集合，证明膄证明：膂34、设A,B为集合，证明：如果()()ABBAAB，则AB。膁证明：（反证法）蝿设aAB，则,aAaB，芄所以,aABaBA；薃所以()()aABBA羂但是aAB。薇与()()ABBAAB矛盾。蚈37、设A,B,C为任意集合，证明：()CACBCAB。羃证明：莀对任意xC，由于,CACB，所以xA且xB所以xAB薀因此，()CAB。蚈P121:习题七莄5、设A,B为任意集合，证明肂若AABB，则AB。荿证明：螈所以有AB螅9、设{1,2,4,6}A，列出下列关系R薀（2）{,|,||1}RxyxyAxy膈（3）{,|,}RxyxyAy为素数袇解答：袂（2）{1,2,2,1}R节（3）{1,2,2,2,4,2,6,2}R袇11、iR是X上的二元关系，对于xX定义集合羇显然()iRxX。如果{4,3,2,1,0,1,2,3,4},X且令芃求11223(0),(1),(0),(1),(3)RRRRR。螀解答：羀13、设{1,2,2,4,3,3}A，{1,3,2,4,4,2}B。求AB，AB，domA,domB,dom()AB,ranA,ranB,ran()AB,fld()AB.肇解答：蚄16、设{,,,}Aabcd，12,RR为A上的关系，其中蒂1{,,,,,}Raaabbd，2{,,,,,,,}Radbcbdcb。求12RR，21RR，21R，32R。虿解答：膇20、给定{1,2,3,4}A，A上的关系{1,3,1,4,2,3,2,4,3,4}R肅（1）画出R的关系图。衿（2）说明R的性质。蒈解答：芇（1）膂（2）R具有反自反性，反对称性，传递性薁21、设{1,2,3}A，图7.11给出12种A上的关系，对于每种关系写出相应的关系矩阵，并说明它所具有的性质。芆解答：芇（a）110111101,具有自反性。薂（b）110001100,具有反对称性和传递性。聿（c）111111111,具有自反性，对称性和传递性。艿23、设R的关系图如图7.12所示，试给出()rR，()sR和()tR的关系图。莇25、设{1,2,3,4}A，R是A上的等价关系，且R是A上所构成的等价类为{1},{2,3,4}。羃（1）求R。螁（2）求1RR肈（3）求R传递闭包。蒇解答：蒄（1）{1,1,2,2,3,3,4,4,2,3,3,2,2,4,4,2,3,4,R艿（2）由于等价关系满足对称性，所以1RR袇所以1RRR薆（3）由于等价关系满足传递性，所以传递闭包为其自身，即()tRR袅26、对于给定的A和R，判断R是否为A上的等价关系。羁（1）A为实数集，,,2xyAxRyxy。袀（2）{1,2,3}A，,,3xyAxRyxy。蚆（3）AZ，,,xyAxRyxy为奇数。羂（5）(),APXCX，,,xyAxRyxyC蚃解答：虿（1）不是，不满足自反性、对称性、传递性。螆（2）不是，由于{1,2,3}A集合较小，莃①自反性：,3,xAxxxxR膁②对称性，,,33,xyRxyyxyxR莈但是传递性不满足，1,3,3,2R，但是1,2R。袆（3）不是，满足对称性、传递性，但是不满足自反性螄取2x，但是224不为奇数，所以2,2R。袃（5）满足膇①自反性：,xAxXxxCxxR袆②对称性：,,xyRyxxyCyxR膅③传递性：,,,xyyzR芀下面证明()xzC膀若ay，则ayz，所以aC羆若ay，则axy，所以aC芁所以()xzC，同理可证，()zxC羂所以()()xzxzzxC羈所以,xzR。因此满足传递性。肆27、设{,,,},AabcdA上的等价关系蚂画出R的关系图，并求出A中各元素的等价类。蒀解答：关系图为螇等价类[][]{,}abab；[][]{,}cdcd膆30、设{1,2,3,4},A，在AA上定义二元关系R，肃,,,,,,uvxyAAuvRxyuyxv。（1）（2）膂证明R为AA上的等价关系。（3）（4）螀确定由R引起的对AA的划分。芅解答：蒄（1）证明：蚀①自反性：,xyAA，由于xyxy，所以,,,xyxyR；蕿②对称性：,,,xyuvR莅有xvuy，所以uyxv袅因此,,,uvxyR莂③传递性：,,,,,,,xyuvuvstR芈有xvuy，utsv，所以xsty蒅因此,,,xystR。肂（2）等价类有螀37、对于下列集合与整除关系画出哈斯图。肇（1）{1,2,3,4,6,8,12,24}蒅（2）{1,2,3,4,5,6,7,8,9,10,11,12}蒃解答：薂（1）膀（2）薅38、针对图7.14中的每个哈斯图，写出集合以及偏序关系的表达式。袄解答：罿（a）集合为{1,2,3,4,5}A，袈偏序关系为{1,3,1,5,2,4,2,5,3,5,4,5}IA蚅（b）集合为{,,,,,}Babcdef，芄偏序关系为{,,,,,}IBabcdef蚁（c）集合为{1,2,3,4,5}C，蚇偏序关系{1,2,1,3,1,4,1,5,2,4,2,5,3,4,3,5,4,5}IC螅40、分别画出下列偏序集,AR的哈斯图，并找出A的极大元、极小元、最大元和最小元。蚅（1）{,,,,,}Aabcdef，腿（2）{,,,,}Aabcde蚀解答：（1）（2）袅哈斯图为螂极小元为,af,极大元为,ef，无最大元、最小元（3）（4）袁哈斯图为葿极小元为,,,abce，极大元为,,,abde，无最大元、最小元羄41、{1,2,3....,12}A，R为整除关系，{|24}Bxx，在偏序集,AR中求B的上界、下界、最小上界和最大下界。膃解：下界即为公约数，2，3，4的公约数只有1，所以下界为1，最大下界也为1；薃下界即为公倍数，2，3，4的公倍数只有12，所以上界为1，最大上界也为12；芈P141:习题八肄4、判断下列函数中哪些是满射？哪些是单射？哪些是双射？薄（2）2:,()2fNNfxx肁（4）:{0,1}fN,0isodd()1xfxxiseven羇（6）2:,()215fRRfxxx肄解答：（2）单射；（3）满射；（4）既不为单射也不为满射。羅5、设{,,,},{1,2,3}XabcdY，{,1,,2,,3}fabc，判断下列命题的真假。螃（1）f是从X到Y的二元关系，但不是X到Y的函数。肀（3）f是从X到Y的满射，但不是单射。膄解答：（1）真；（3）假膂15、设{,,}Aabc，R为A上的等价关系，且{,,,}ARabbaI，求自然映射:/gAAR。膁解答：蝿19、设,fg是从N到N的函数，且（1）（2）芄求fg（3）（4）薃说明fg是否为单射、满射、双射？羂解答：薇（1）30,2,5,7,9......11,32(())046,8,10,12.....2xxxfggfxxxx蚈（2）为满射，但是不为单射。羃20、设:fNNN，(),1fxxx莀（1）说明f是否为单射和满射，说明理由。薀（2）f的反函数是否存在，如果存在，求出f的反函数；蚈（3）求ranf。莄解答：肂（1）xy时，,1,1xxyy，所以为单射；荿而对1,3NN，不存在xN，使得(),1fxxx，所以不为满射。螈（2）不存在反函数，因为不是双射函数；螅（3）{,1|}ranfxxxN薀22、对于以下集合A和B，构造从A到B的双射函数。膈（1）{1,2,3},{,,}ABabc袇（2）(0,1),(0,2)AB袂（3）{|0},AxxZxBN节（4）,ARBR袇解答：羇（1）1()23axfxbxcx芃（2）()2(0,1)fxxx螀（3）()1fxx（4）()(0,1)xfxaaa仅供个人用于学习、研究；不得用于商业用途。Forpersonaluseonlyinstudyandresearch;notforcommercialuse.NurfürdenpersönlichenfürStudien,Forschung,zukommerziellenZweckenverwendetwerden.Pourl'étudeetlarechercheuniquementàdesfinspersonnelles;pasàdesfinscommerciales.толькодлялюдей,которыеиспользуютсядляобучения,исследованийинедолжныиспользоватьсявкоммерческихцелях.以下无正文