等价关系与偏序关系温习
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
谜底[宝典]
第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