[优质文档]等价关系与偏序关系温习题谜底

[优质文档]等价关系与偏序关系温习题谜底 第5章 等价关系与偏序关系 一、选择题(每题3分) 1、设Z为整数集，下面哪个序偶不够成偏序集( A ) A、 B、,Z,,,(,:小于等于关系),Z,,,(,:小于关系) C、 D、,,ZDD,():整除关系,,ZMM,():整倍数关系 2、序偶必为( B ) ,,,(),A, A、非偏序集 B、偏序集 C、线序集 D、良序集 ,:小于等于关系3、设Z为整数集，下面哪个序偶能够成良序集( D ) ，，，A、 B、,,RR,(),:正实数集,,,QQ,():正有理数集 ，，C、 D、,,,NN,():自然数集,,,ZZ,():正整数集 4、设，则上包含关系“”的哈斯图为( C )A,A,,{,{1},{1,3},{1,2,3}} 5、集合上的偏序关系图为 A,{ 1, 2, 3,4 } 则它的哈斯图为( A ) A6、某人有三个儿子，组成集合ASSS,{ , , }，则在上的兄弟关系一定不是( D )123 A、偏序关系 B、线序关系 C、良序关系 D、等价关系 AAPPP,{ , , , }？7、有一个人群集合，则在上的同事关系一定是( D )12n A、偏序关系 B、线序关系 C、良序关系 D、等价关系 AA8、设为非空集合，则下列上的二元关系中为等价关系的是( D ) A、空关系 B、全域关系 C、恒等关系 D、上述关系都是 A9、设，则上不同等价关系的个数为( C ) A,{ 1, 2, 3 } 3564A、 B、 C、 D、 A10、设，则上不同等价关系的个数为( C ) A,{ 1, 2, 3, 4 }13151614A、 B、 C、 D、 注:除了等价关系可以对空集定义，而划分不能外，等价关系与划分是相同概念的不同描述( SS，S11、设S,{ 1, 2 }，“”为中元素的普通乘法，定义上的等价关系, RabcdabSScdSSadbc,,,,,,,,,,，,,,，,,,{,,, | ,,,,}， S，SR则由产生的上一个划分的分块数为( D ) 3124A、 B、 C、 D、 提示:记， aaaa,,,,,,,,,,,,1,1,1,2,2,1,2,21234 则由的关系图易知( RSSaaaa，,{{},{},{},{}}1234 SS，S12、设，“”为中元素的普通乘法，定义上的等价关系S,{ 1, 2, 3 }， ，R,{,,a,b,,,c,d, | ,a,b,,S，S,,c,d,,S，S,a，d,b，c} S，S则由产生的上一个划分的分块数为( C ) R 3579A、 B、 C、 D、 adbc，,，abcd,,,提示:因，则 S，S5因，则等价关系产生的上一个划分的分块数为(Rab,,,,2,1,0,1,2 二、填充题(每题4分) 1、设，其上偏序关系的哈斯图为 RAabcd,{ , , , } 则 (R,{,,,,,,,,,},,,,,,,,,,abacadbdcdI:A 2、设，偏序集的哈斯图为 Aabcdefg,{ , , ,,,, },,AR, fcdb eg a ， R,则 ({,,,,,,,,,,,,,},,,,,,,,,,,,,,abacadaeafdfefI:A ,, a,b ,,,,ab 3、偏序集的Hass图为 ,,,,({,}),ab , 244、对于，则偏序集的哈斯图为,,A,整除关系A,{ 1,2,3,4,6,8,12,24 } 128 46 23 1( A15、设，“”为上整除关系，则偏序集的极小元为，A,{ 1,2,3,4,6,8,12,24 },,,A,, 24241最小元为，极大元为、最大元为( A6、设，“”为上整除关系，则偏序集的极小元为，A,{ 2,3,4,6,8,12 },,,A,2,3, 最小元为无，极大元为，最大元为无，既非极小元也非极大元的是(8,124,6 S,{{a,b},{b,c}}S,{{a},{a,b},{a,c}}7、设A,{a,b,c}考虑下列子集，，12S,{{a},{b,c}}S,{{a},{b},{c}}S,{{a},{a,c}}S,{{a,b,c}}，，，3564 AASSSSS,,,,SSS，，则的覆盖有 ，的划分有( 12345345 SA8、设A,{ 1, 2, 3,4 }S,{{1},{2,3},{4}}，为的一个分划，则由导出的等价关系为 R,{1,1,2,2,2,3,3,2,3,3,4,4},,,,,,,,,,,, ( 提示:( R,({1}{1})({2,3}{2,3})({4}{4})，，，:: kkAR/,9、非空正整数子集上的模等价关系的秩为，(AR{[0],[1],,[1]}？k,kkk 三、问答题(每题6分) 1、试比较偏序集合、线序集合与良序集合( 答:若集合上的二元关系是自反的，反对称的和传递的，称序偶为偏序集;AR,,AR, 偏序集中的各元素并非都能比较，若都能比较，偏序集成为线序集; 在线序集中，若的任一非空子集都有一最小元素，则线序集成为良序集(A 2、设，是的等价关系，由诱导的的划分块数为3，则不同的有多少种,RARAR||5A, 答:一个集合上的等价关系数目与该集合的划分数目是一致的，因而，该题只需求出将5 个元素的集合分成3份的划分种数即可( 3 如果3份中元素个数分别为3，1，1，则共有种， C5 2 如果3份中元素个数分别为2，2，1，则共有种， C5 32因此，A上秩为3的等价关系共有+( CC,2055 3、设A是实数集合，试判断是A上的偏序关系RxyxAyAxy,,,,,,,,,{,3} 吗,等价关系吗,为什么, 答:都不是;因 ,x A，x,x=0?2，所以,x,x, R，R不是自反的( 四、画图填表题(每题10分) R,1、设上的关系 ，画出偏序集的哈斯图，{,},,cdI:Aabcde,{ , , ,,},,AR,A A的子集的极大元、极小元、最大列表给出BabcdeBcdBcde,,,{ ,, ,,},{ ,},{,,}123 元、最小元、上界、下界、上确界和下确界( 解:哈斯图如图4.44所示: 其子集Bi,1,2,3,上的各种特殊元素如下表所示， i 极大元 极小元 最大元 最小元 上界 下界 上确界 下确界 无 无 无 无 无 无 B a,b,d,e a,b,c,e 1 B d c d c d c d c 2 无 无 无 无 无 无 B d,e c,e 3 {,()()},,,,,,,xyxAyAxy,,,,2、设的幂集上的关系 ，Aabc,{ , , },()A Bab,,{ ,{},{}},{{},{}}Bac,画出偏序集哈斯图，列表给出子，,,,,(),A,()A12Bacabc,{{,},{,,}}的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界(3 解:哈斯图如图4.45所示: 极大元 极小元 最大元 最小元 上界 下界 上确界 下确界 其子集无 B ,a,,,b, ,a,b,c,, ,a,b, ,a,b, , , , , 1 无 无 B ,a,,,c, ,a,,,c, ,a,b,c,, ,a,c, ,a,c, , , 2Bi,1,2,3,iB ,a,b,c, ,a,c, ,a,b,c, ,a,c, ,a,b,c, ,a,c, ,a,b,c, ,a,c, 3 上的各 种特殊元素如下表所示， 3、试填出上的等价关系，RA,{1,2,3,4,5} 其产生划分,并画出关系AR/{{1,2},{3},{4,5}}, 图( 解:R,，，，{1,2}{1,2}{3}{3}{4,5}{4,5}:: 其关系图为: 六、证明题(每题10分) RARRA1、设是上的二元关系，如果是传递的和反自反的，称是上的拟序关系， RAA证明:如果是上的拟序关系，则是上的偏序关系(rRRI(),:A ，有是自反的; 证明:(1)因rRRII(),,:rR()AA xy,(2)设而，则若,,,xyrR,(),,,,xyR,,,,,yxR,, RR由的传递性，知与的反自反性矛盾，则 ,,,xxR,,,,,yxR,,又有，于是有是反对称的;,,,yxI,,,,,,yxRIrR,():rR()AA RRR,,R(3)由的传递性，知， 因 rRrRRIRIRIRRII()()()()(())(()),:,::,::,,,AAAAA ，则可传递;,,,(()())(()())()()RRIRRIIIRRRIrR,:,:,:,,::rR()AAAAA A综上所述，可证是上的偏序关系( rR() RARAR2、设是上的二元关系，如果是传递的和反自反的，称是上的拟序关系， RAA证明:如果是上的偏序关系，则RI,是上的拟序关系( A 证明:(1)RI,，则反自反;()()()RIIRIIRIIR,,,,,,,::::::AAAAAAA xyyz,,,,,,,,,,,xyRIyzRI,,,(2)设，则，而，,,,,,,xyRyzR,,,AA RR因是传递的，有;若，则，由的反对称性，xz,,,,xzR,,,,,,,zyRyzR,,, yz,yz,,,,,xzRI,RI,知，与矛盾，于是，则，有是传递的;xz,AA ARI,综上所述，可证是上的拟序关系( A RA3、设是上的对称和传递关系， RA证明:若，则是上的等价关系( ,,，,,,,,aAbAabR,,, R证明:,,，,,,,,aAbAabR,,,，因是对称的，有,,,baR,， RRARA又因是传递的，所以,,,aaR,，则在上自反，故是上的等价关系( ,1SSRR4、设是上的偏序关系，证明:是上的偏序关系( ,,xSSR证明:(1),,,xxR,，因在上的自反性，则， ,1,1SR有，于是，在上是自反的; ,,,xxR, ,1SRxy,,,,yxR,,,,,xyR,,(2)设而，则因在上的反对称性，有,,,xyR,, ,1,1S则于是，在上是反对称的; R,,,yxR,, ,,11,,11(3)设，则，,,,,,,xyRyzR,,,,,,,,,zyRyxR,,, ,1SS'因在上的传递性，有则于是，在上是传递的;RR',,,zxR,,,,,xzR,, ,1S综上所述，可证是上的偏序关系((题4在证明中用了定义法) R ,1SS5、设是上的等价关系，证明:是上的等价关系( RR ,1,,11SS证明:(1)因在上的自反性，有，则，有在上自反;RRIR,IIR,,SSS ,1,1,,,111SS(2)因在上的对称性，有，则，有在上对称;RRR,R()RRR,, 2,1,,1221SSRR,(3)因R在上的传递性，有，则，有在上可传递;R()RRRR,,, 2S'则，有在上是对称的;R'RRRRSSRSSR'(')('(''))('')',，,，,,:,: ,1S综上所述，可证是上的等价关系((题5在证明中用了集合法) R RS:6、设是上的偏序关系，证明:是上的偏序关系( AARS, RS:,,xA证明:(1)，因在A上的自反性，则，有在A上自反;RS,,,,xxRS,: (2)设而xy,，则因在A上的反对称性，,,,xyRS,,:,,,,,,xyRxyS,,,,RS, RS:有则于是，在A上是反对称的;,,,,,,yxRyxS,,,,,,,yxRS,,: (3)设， ,,,,,,xyRSyzRS,,,:: A则，因在上的传递性，,,,,,,,,,,,,xyRyzRxySyzS,,,;,,,RS, RS:A有,则，于是，在上是传递的;,,,,,,xzRxzS,,,,,,xzRS,: RS:A综上所述，可证是上的偏序关系((题6在证明中用了定义法) RS:AA7、设是上的等价关系，证明:是上的等价关系( RS, RS:AA证明:(1)因在上自反，有，则，有在上自反;IRIS,,,IRS,:RS,AAA ,,11A(2)因在上对称，有， RS,RRSS,,, ,,,111RS:A则，有在上对称; ()RSRSRS:::,, 22A(3)因在上传递，有， RS,RRSS,,, 222RS:A则，有在上可传递;()(())(())RSRSRRSSRSRS::,::,::,,, RS:A综上所述，可证是上的等价关系((题7在证明中用了集合法) SS',SS'R8、设是上的二元关系，定义上的二元关系,RRSS'(''),，: SS'RR'证明:如果是上的偏序关系，那么是上的偏序关系( ,,,xSS'SR证明:(1)，因在上的自反性，则，而，,,,xxR,,,,，xxSS,'' S'R'有，于是，在上是自反的; ,,,，,xxRSSR,('')': SRxy,(2)设而，则因在上的反对称性，有,,,xyR,',,,,xyR,,,,,yxR,, S'R'则于是，在上是反对称的; ,,,，,yxRSSR,('')',: SR(3)设，因在上的传递性，有,,,,,,xyRyzR,',,',,,xzR,, S'R'而，则，于是，在上是传递的;,,,，xzSS,'',,,，,xzRSSR,('':)' S'R'综上所述，可证是上的偏序关系((题8在证明中用了定义法) SS',SS'R9、设是上的二元关系，定义上的二元关系,RRSS'(''),，: SS'RR'证明:如果是上的等价关系，那么是上的等价关系( SS',SRIR,IIR,,ISS,，''证明:(1)因在上的自反性，则，而,有，而，SSS'S' S'R'IRSSR,，,:('')'有，于是，在上是自反的; S' ,1,1SRRR,(2)因在上的对称性，有，而，('')''SSSS，,， ,,,,1111S'R'则，有在上是对称的;(')((''))('')'RRSSRSSR,，,，,:: 2SRR,R(3)因在上的传递性，有， 22有，而， RRRR',,,RSSSSSS'('')('')'',，,，,， 2S'则，有在上是传递的;R'RRRRSSRSSR'(')('(''))('')',，,，,,:,: S'综上所述，可证是上的等价关系((题9在证明中用了集合法) R' 10、若是上的等价关系，则RASababAcAacRcbR,,,,,，,,,,,,,,{,|,(,,)}也是上的一个等价关系( A ,a,AS证明:(1)，由自反，则，，有自反;R,,,,,,,aaRaaR,,？,a,a,,S ，,cA(2)，则，使 ,,,,abS,,,,,,,acRcbR,,,, S由在上对称，有有，知对称;RA,,,,,,bcRcaR,,,,,,,baS, ，,dA(3)若，则，使,,,,,,abSbcS,,,,,,,,,adRdbR,,,, ，,eA同时，使 ,,,,,,beRecR,,,, S由在上传递，知有，有传递;RA,,,,,,abRbcR,,,,,,,acS, S综上所述，可证是上的等价关系((题10在证明中用了定义法) A 六、证明计算题(每题10分) abcd，,，1、设，在A，A上定义 ，A,{1,2,3}RabcdR:,,,,,,,,,,, “”为普通加法，证明:R是A，A上的等价关系，并求出([1,3],/,,，AAR，R 证明:(1)即R自反;,,,,，，,，？,,,,,,,abAAababababR,,,,,,,？ (2),,,,,,,,，,，，,，abcdRabcdcdab,,,,,,则？ R则，即对称; ,,,,,,,cdabR,,, (3)，则abcdef，,，,，,,,,,,,,,,,,,,,abcdRcdefR,,,,,,,, R即传递; ？,,,,,,,abefR,,,, RA，A 综上得出，是上的等价关系， ,,,,,,，，,,,,,,,,{,,,4}{1,3,2,2,3,1}ababAAab且,[1,3],,R ( AAR，,,,,,,,,,,,/{[1,1],[1,2],[1,3],[2,3],[3,3]}RRRRR a，d,b，cA，A2、设，在上定义 ，A,{1,2,3,4}RabcdR:,,,,,,,,,,, RA，A“”为普通加法，证明:是上的等价关系，并求出([2,4],/,,，AAR，R R证明:(1)即自反;,,,,，，,，？,,,,,,,abAAabbaababR,,,,,,,？ (2),,,,,,,,，,，，,，abcdRadbccbda,,,,,,则？ R则，即对称; ,,,,,,,cdabR,,, (3) ,,,,,,,,,,,,,,,abcdRcdefR,,,,,,,, 则adbccfdeadcfbcde，,，，,，，，，,，，，,？ R有 ，即传递; afbe，,，？,,,,,,,abefR,,,, RA，A 综上得出，是上的等价关系， ,,,,,,，,,,,,,,{,,,2}{1,3,2,4}ababAAab[2,4],,且,R AAR，,,,,,,,,,,,,,,,/{[1,1],[1,2],[2,1],[1,3],[3,1],[1,4],[4,1]}(RRRRRRR adbc ,A，A3、设，在上定义 ，A,{1,2,3,4}RabcdR:,,,,,,,,,,, RA，A[2,4],/,,，AAR“” 为普通乘法，证明: 是上的等价关系，并求出( R R证明:(1),,,,，,？,,,,,,,abAAabbaababR,,,,,,,？ 即自反; ,,,,,,,,,,abcdRadbccbda,,,,,,则 ？ (2) R 则,,,,,,,cdabR,,,，即对称; ,,,,,,,,,,,,,,,abcdRcdefR,,,,,,,, (3) 则adbccfdeadcfbcde ,,,,？ ， 有 ，即传递; Rafbe ,？,,,,,,,abefR,,,, 综上得出，是上的等价关系， RA，A且,,,,,,,，,,,,,,{,,,2}{1,2,2,4}ababAAab[2,4],,R (AAR，,,,,,,,,,,,,,,,/{[1,1],[1,2],[2,1][1,3],[3,1],[1,4],[4,1]}RRRRRRR 4、设，在的幂集上规定， AA,{ 1, 2, 3, 4 },()ARststAst,,,,,,{,|,()(||||}, 证明:是上的等价关系，并写出商集( R,()AR,()A 证明:? ，由于，所以，即自反的;R,,sA,()|s|,|s|,s,s,,R ? ，若，则，，是对称的;R,,stA,(),,s,t,,R|s|,|t|,|t|,|s|？,t,s,,R ?，若，即， ,s,t,,R且,t,u,,R,,stuA,,(),|s|,|t|,|u| 则 所以是传递的; R,,,suR, 综上得出，是上的等价关系， R,()A (,(){[],[{1}],[{1,2}],[{1,2,3}],[{1,2,3,4}]}AR,,RRRRR