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

作业答案：集合论部分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}，所以该题的结论应该为{,{{1,2}},{{2,1,1}},{{1,2},{2,1,1}}}（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为任意集合，证明()()()()ABBAABAB证明：()(){|}{|()()}{|()()()()}{|()()}{|()()}{|()()}{|()()}{|()(ABBAxxABxBAxxAxBxBxAxxAxBxBxBxAxAxBxAxxAxBxBxAxxABxAxBxxABxAxBxxABxABxxABxA)}BABAB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。证明：,,xAxxAAxxBBxB所以有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定义集合(){|}iRxyxRy显然()iRxX。如果{4,3,2,1,0,1,2,3,4},X且令1{,|,}RxyxyXxy2{,|,12}RxyxyXyxy23{,|,}RxyxyXxy求11223(0),(1),(0),(1),(3)RRRRR。解答：11223(0){1,2,3,4}(1){2,3,4}(0){1,0}(1){2,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.解答：{1,2,2,4,3,3,1,3,4,2}AB{2,4}ABdom{1,2,3}Adom{1,2,4}Bdom(){1,2,3,4}ABran{2,3,4}Aran{2,3,4}Bran(){4}ABfld(){1,2,3}AB16、设{,,,}Aabcd，12,RR为A上的关系，其中1{,,,,,}Raaabbd，2{,,,,,,,}Radbcbdcb。求12RR，21RR，21R，32R。解答：12{,,,,,}RRadacad21{,}RRcd21{,,,,,}Raaabad22{,,,,,}Rbbcccd32{,,,,,}Rbcbdcb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4,3}（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,()(),()()(),(),(),()xyCyzCxyyxCyzzyCxyCyxCyzCzyC下面证明()xzC(),axzaxaz若ay，则ayz，所以aC若ay，则axy，所以aC所以()xzC，同理可证，()zxC所以()()xzxzzxC所以,xzR。因此满足传递性。27、设{,,,},AabcdA上的等价关系{,,,,,,,}ARabbacddcI画出R的关系图，并求出A中各元素的等价类。解答：关系图为等价类[][]{,}abab；[][]{,}cdcd30、设{1,2,3,4},A，在AA上定义二元关系R，,,,,,,uvxyAAuvRxyuyxv。（1）证明R为AA上的等价关系。（2）确定由R引起的对AA的划分。解答：（1）证明：①自反性：,xyAA，由于xyxy，所以,,,xyxyR；②对称性：,,,xyuvR有xvuy，所以uyxv因此,,,uvxyR③传递性：,,,,,,,xyuvuvstR有xvuy，utsv，所以xsty因此,,,xystR。（2）等价类有[1,1]{1,1,2,2,3,3,4,4}[1,2]{1,2,2,3,3,4}[1,3]{1,3,2,4}[1,4]{1,4}[2,1]{2,1,3,2,4,3}[3,1]{3,1,4,2}[4,1]{4,1}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，{,,,,,,,,,,,,,}ARadacabaebecedeI（2）{,,,,}Aabcde{,}ARcdI解答：（1）哈斯图为极小元为,af,极大元为,ef，无最大元、最小元（2）哈斯图为极小元为,,,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。解答：/{{,},{}}ARabc{,},()abxabgxcxc19、设,fg是从N到N的函数，且10,1,2,3()045xxfxxxx()23xxisevengxxisodd（1）求fg（2）说明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