第二章关系与映射

1、第二章关系与映射1 设集合 A=1,2,3,4, A上的二元关系 R= x, y | x, y A,且x _ y, 求R的关系图与关系矩阵解 R 二 x,y |x, y A,且x _ y珂 1,1 , 2,1 , 3,1 ,4,1 , 2,2 ,3,2,4,2,3,3,4,3,4,4R的关系图如图2-1所示。图2-110 0 0Mr1 0 01 1 01 1 1 一22.在由n个元素组成的集合上，可以有多少种不同的二元关系？若集合AB的元数分别为|A| = m,|B|二n，试问从A到B有多少种不同的二元关系？解因为一个由 n个元素组成的集合A上,任何一个二元关系都是A A的子集，而A A=A2

2、中共有n个元素，取o个到n个元素可以组成2n子集，所以有2n个不同的关系。 而当|A|=m,|B| = n时，a B这个全关系中共有 m n个元素，取0个到m n个元素 组成的子集共有2mn个，因此从A到B共有2mn种不同的二元关系。3.设集合A二1,2,3,令，A上的二元关系分别为：R 珂 1,1, 1,2, 2,4, 31,3,3S 二1,3, 2,2, 3,2, 4,4试用定义求R *S , S *R , R2, R4 , S ,，并画出其关系图。解 R*S 二1,3,1,2, 2,4, 3,3, 3,2S R= 1,1, 1,3, 2,4, 3,4 r2= 1,1,1,2,1,4,3,

3、1,32,3,3rJ 1,1 , 1,3, 2,1 , 3,3, 4,2 S4 = 2,2, 2,3, 3,1, 4,4 r.SA= 1,1 , 3,1 , 4,2, 4,3 其关系图如图2-2所示。图2-2说明 1.当用定义求复合关系时，先将左关系中每个序偶的第二元素作为中介元素， 到右关系中每个序偶里找与其相同的第一元素，将这个元素去掉，用剩余两个元素组成新序 偶成为复合关系中的元素2.用定义求出的复合关系与逆关系，可以用关系矩阵来验证其正确性。4. 设集合A=x, y,z，集合B=a,b,c,d,e，r是集合a上的关系，S是A,B上的 关系。R = x,x，x,z , y,x , y,y

4、，z,x，z,y，z,zS = x,a , x,d , y,a , y,c , y , e , z,b, z,d 试验证M（rs）丄=Ms丄M R丄-1011-100101mR =110Ms：-10101证111 一i-01010 一Mrs - M r M S1 0 1 10 0 101 1 0 10 10 1_ 1 1 1 0 1 0 1 0 一110 1010 111_ J 1111 一1 1 11 0 10 1 1T11M（rs）= = Mrs= o 1111011 HYPERLINK l bookmark2 o Current Document MRj10J110001010101Ms

5、010Mr1 二 Ms1 M R丄_110 00 11 0=0101101010J_1 1 11 0 10 1 1M（RS）丄二Ms 丄 MR 丄。5. 图2-3所示的图形是集合别写出对应的关系矩阵，并说明每种关系所具有的性质（自反性，对称性，反对称性，传递 性）。图2-31 0 00 1 0解M = . 001 _jRi具有自反性，对称性，反对称性与传递性。1 0 00 1 1Mr2=P 1 1jR2具有对称性与传递性。0 1 00 0 1Mr3= J 0 0JR3具有反对称性。0 0 00 0 0 皿艮八000R4具有对称性，反对称性与传递性。说明本题判断关系所具有的性质，主要通过已知关系

6、图与求出的关系矩阵进行，同时对于比较难于判定的传递性，都可以一结合定义进行判定。如果不破坏定义所要求的条件， 可以 认为满足定义要求，如对 R4的判定。5. 5.下列关系是否具有如下性质：自反性，对称性，反对称性，传递性？ R 二 x, y |x,y l,x y；R2 = x, x | x _ 0,且x为实数；A上的恒等关系R3 = x,x|x a；A=1,2,3，0上的空关系o解Ri具有反对称性与传递性；R2具有反对称性；R3具有自反性，对称性，反对称性与传递性；A上的空关系具有对称性，反对称性与传递性。说明 本题中的前两个小题均为无限集合，第小题也未给定集合 A的元数，这样不能得到完整的关

7、系图与关系矩阵。但是，可以在草纸上作出部分元素的关系图与关系矩阵进行判断，同时要充分利用定义要求，便具有该种性质。第小题，与上题中题类型一致，只是 元数大一些，结果应与上题相同。7.设R和R2是集合A上的任意关系，试证明或用反例推翻下列论断：若R1和R2都是自反的，则 R1 R2也是自反的；若R1和R2都是对称的，则 R1 R2也是对称的；若R1和R2都是反对称的，则 R1 R2也是反对称的；若R1和R2都是传递的，则 R1 R2也是传递的。证 论断正确。对任意a A，若R和R2都是A上的自反关系 ，(a,a 护 R,(a,a) R?所以a,aR2，即R1 R2也是自反的。论断不正确。例如，设

8、 A 二x,y,z，当 R = a,b , b,a , c,c, R2 = b,c, c,b，Ri与 R?都是对称的，但是R1只2 = a,c , c,b已不是对称的，故原论断不正确。论断不正确。Ri 門 a,a , b,a , b,c , c,a例如，设集合A二a,b,c，当R2二a,b,b,b b,c,c,cR与R2都是反对称的，但是，Ri只2=(a,b)(b,b)(b,c)(c,b已不是反对称的，(因为(b,c)(c,b)w RR2)，故故原论断不正确。论断不正确。例如，设集合 A =a,b,c，当 Ri 門 a,b , b,c , a,c, R b,c , c,a b,a，Ri R a

9、,a , a,c , b,a 不是传递的，因为 b,a R 只2, a,c R R，而 b, c R1 R2，故原论断不正确。证毕。8设R的关系图如图2-4所示，试画出r(R)，S(R)和t(R)的关系图。r(R)dbcas(R)dcabct(R)图2-5说明 对于r(R)的关系图，因为r(R)二R - IA，只要在r的关系图上对没有自回路的 结点都添加上自回路，使可以画成R的自反闭包r(R)的关系图。 对于s(R)的关系图，因为s(R)二R- R*，只要将R的关系图中所有单向弧都画成双 向弧，便可以画成 R的对称闭包s(R)的关系图。nt(R) = R在 对于t(R)的关系图，当R是有限集合

10、上的关系时， 画图时，如果R关 系图中从结点 x到结点y有一连串带箭头的头尾相接的弧相连着，则在R的关系图上添加一条直接从x到y的弧，便可以画出t(R)的关系图，如图2-5中t(R)关系图上的a与c， a与d，a与e，b与d之间都应画一条有向弧。但是这里要特别注意Gd两个结点，原有两条c到d与d到c的有向弧，这属于总结规律中的特殊情形，作为结点c看成是两个结点的重合，所以结点 c处要画一条自回路，表示从结点c到结点c。同理，结点d也要画一条自回路。9.设集合 A =1,2,3,4， a上的关系 R =(1,2，2,3 )(3,1，4,4求 t(R)和 sr(R)，并写 出它们的关系矩阵解因为

11、R=1,2,2,3,3,1,4,42所以R 二1,3,2,1 ,3,2,4 ,4R3 =1 ,1 , 2,2,3,3,4,4R4 = 1 ,2,2,3,3,1,4,4t(R) =RR2R3R4= (1 ,1 ,1,2 ,(1,3 ,2 ,1 2,2 ,2,3 ,(3,1 )(3,2 ,3,3 ,4,4 r (R) = R IA=1 ,1 , 1 ,2,2 ,2,2 ,3,3,1, 3,3,4 ,4(r(R)二1,1, 1 ,3,2,1, 2,2,3,2,3,3,4,4sr(R) =r(R) (r(R)二 1,1 , 1,2 , 1 ,3,2 ,1 2 ,2,2,3,3,1 , 3,2,3,3,

12、4 ,4此题t( R)二sr(R),故其关系矩阵为111011101110M t(R) = M sr(R) = -0001_说明 此题t(R)二sr(R),这纯属偶然情况，一般地，t(R) =sr(R)。设R是集合A上的二元关系，若 R是传递的，则r(R)也是传递的，而s(R)不一定是 传递的。证 由 2.4定理1知，R是传递的，当且仅当t(R) =R,故要证r(R)是传递的，只需证 明 t(r(R) =r(R)。因为 t(r(R) =t(RI a) =t(RR0) =R0)(I r)i(2 R0) = u Rj下面用归纳法证明j出当i -1时，左端=R R0 =右端k,(2 R0)k =2

13、Rj假设当i =k时，命题成立，即) uk., (RuR0)2 = (RuR0)k (R.R0)=uRj (R.R0) 当 i =k T 时，i=o由 2.2，习题7的结论，可得kR _ _ Rj R0k 1Rjj =0kk厂占(R R0)k；：1Rj丄k 1Rj o:i .-R = t(R) 一 Ia = R- lA=r(R)R j故 t(r(R)十jMR即t(r(R)二r(R)，故r(R)是传递的。s(R)不一定是传递的。例如 设集合A二a,b,c上的二元关系 R，当R二 a,b , b,c , a,c，r是传递的，而 s(R) =R 一 R= a,b , a,c , b,a , b,c

14、, c,a , c,b时，s(R)已经不是传递的。 证毕。设R是集合A上的二元关系，判断下列命题是否正确？ rt(R) =tr(R)； ts(R) =st(R)。解命题正确。由于 tr(R) =t(R I a)， rt(R) =t(R)I a，并利用 Ra = 1 a R，以及对于一切n自然数n, iA=Ia，用数学归纳法的可以证明(r-Ia)a-R)，所以tr(R) =t(r(R) =t(R_. Ia)=(R lA) 一(R- l A)? 一 (- Ia)3 -=IA - R - R? - R3 -=Ia - t(R)=r(t(R) = rt(R)。 命题不正确。可以证明 st(R)匚ts(

15、R)。首先证明，当 Ri 二 R?时，则 s(Ri) = s(R2)且t(Ri) =t(R2)。这是因为，s(Ri)是对称的且s(Ri)二R1，但是R1=R?，故s(RJ二R?。由s(R2)的定义，s(R?)是包含R?的最小对称关系，故s(R)二s(R?)。同理可证， t(RO 二 t(R2)。由对称闭包定义，有 S(R)二R，利用上面证过的结论：ts(R)二 t(R),sts(R)二 st(R)再由教材P58例5(2)可知，s(R)是对称的，ts(R)也是对称的，又根据 2.4定理1中(2)， ts( R)是对称的，当且仅当 sts(R) =ts(R)，因此 ts(R)二 st(R)，即 s

16、t(R)三 ts(R)。st(R)二 ts(R)不一定成立。例如，集合A Ha,b,c上关系，R 珂 a,b ,b,c，则 R2 珂 a,c, R3 二,R 珂 b,a ,c,b，t(R) = R 一 R2 一 R3= a,b , b,c , a,c(t(R)= b,a ,c,b, c,as(t(R) (R) 一 t(R)，= a,b ,a,c, b,a b,c ,c,a, c,b而 s(R)二R 一 RJ = a,b , b,a , b,c,c,bs(R)2 a,a , a,c , b,b , c,a , c,c(s(R)3 二a,b ,b,c ,b,a, c,b。t(s(R) =s(R)

17、一 s(R)2 一 s(R)3珂 a,a , a ,b , a ,c , b,a , b ,b , b ,c , c,a , c ,b , c ,c故 s(t(R)不包含 t(s(R)设R|和R2是集合A上的二兀关系，试判断下列命题是否正确？ r(R 一 R2)寸侃)rR)； s(RR2) =s(Ri) s(R2)； t( R - R2 ) - t(Rlt(R2 )。解命题正确。因为 r(Ri .JR2)=RiR2j a = Ri.J I a1R2- I a = r (Ri)r(R2)。命题正确。首先证明任取a,b - (Ri _ R2)，当且仅当b，a R &，当且仅当b，a R或b,a &

18、, 当且仅当a，b,或a，bR2J ,当且仅当a，bR R2 1 ,故证得 TOC o 1-5 h z .i丄 _. i(Ri _ R2 ) = Ri R2而 S( R - R2 ) (Ri - R2) - (R - R2 ) i . i=Ri _ R2 _ Ri - R2 i i=(R- _ Ri ) - (R2 -)二 s(R) 一 sR)命题不正确，可以证明t(Ri - R2) = t(Ri) t(R2)。因为Ri - R2 - Ri ,利用前一例题中证明中证过的结论：当Ri二R2时，则t(Ri )二 t(R2)，有 t (Ri - R2)二 t (Ri )同理，Ri - R R2，有

19、t(R - R2) JR)故 t(Ri 一 R2) =t(Ri) _ t(R2)t(Ri) 一 t(R2)=t(Ri 一 R2)不一定成立。例如，设集合A二a,b,c , a上的二元关系Ri和R2分别为R = a,b , b,cR2 = a,c , c,b则Ri2 = a,cRi3 二R；珂 a,bR；二t(RJ 二尺 一 Ri2 - Ri；= a,b , a,c , b,ct(R2)讥-R； - R；二 a,b , a,c ,c,b t(Ri) t(R2)- a,b , a,c , b,c , c,b而 Ri _ R2= a,b ,a,c ,b,c, c,b(Ri R2) = a,c , a

20、,b , b,b , c,c(Ri 一 R2)3= a,b , a,c ,b,c,c,b2 3t (RiR2) = (RiR2)-(Ri-R2)-(Ri-R2)显然，= a,b , a,c , b,b , b,c , c,b , c,c t(R1) _. t(R2)不包含 t(R1R2)13.设集合A二a,b,c,d,e , a上的关系关于等价关系 R的等价类为:Mi =a，b,c, M2 =d,e，试求:等价关系R :写出关系矩阵M r ；画出关系图。解 因为等价关系R具有自反性，所以Ia = a,a , b,b , c , c, d,d ,e,e。Ia R又因为 a,b,c在同一个等价类中

21、, 所以( a,b), (b,a), (a,c), (c,a)(b,c), (c,b) 5 R再因为d,e在同一个等价类中，所以 (d,e),(e,d) 乂 R因此 R =1A - (a,b),(b,a),(a,c),(c,a),(b,c),(c,b),(d,e),(e,d)。图2-611101110M r = li110000114.设Ri和R2是非空集合A上的等价关系，下列各式哪些是 A上的等价关系？哪些不是A上的等价关系？举例说明： A A - Ri ； Ri - R2 ；2 R ； r(R1 - R2)； Rl R2解 A A-Ri不是A上的等价关系。例如，设集合 A二a,b , A上

22、的关系R a,a ,b,bA A = a, a ,a,b ,b,a, b,bA A-R 二a,b , b,a不具A A-Ri不是A上的等价关系。R1 -R2不是A上的等价关系。例如，设集合A二a，b，C,R = a,a , a,b , b ,a , b,b , b,c , c ,b , c,cR2 - a,a , b,b , c ,cR -R2 = a,b , b ,a , b,c , c,b不具有自反性和传递性，因此Ri -r2不是A上的等 价关系。r2是集合A上的等价关系。2 因为R是集合A上的等价关系，任取A ,有a，a A ,而且有a,a Ri只1二Ri , 所以R2在集合A上是自反的

23、。任取a,bA,若a,b R2,则存在A,使得 a,c R且c,b R,因为Ri是2 2 对称的，有c，a 尺且b,c 尺，于是b，a Ri ,所以Ri是对称的。任取a,b,cA,若a,b R2且b,c R；,贝y存在d,eA ,分别使得dRi,且 d,b ReR ,且 e,cRi由于Ri是传递的，元素 a与b之间以d为中介元素，b与c之间以e为中介元素，有a,bRi , b,c R ,再根据关系的复合，有 a,c R Ri =Ri2所以Ri2是可传递的，2故R是集合A上的等价关系r(R1 -R2)不是集合A上的等价关系。由题所举例子，R1 -R2 二 a,b , b,a , b,c ,c,b

24、有 r(R1 iR2)=(Rli R2) - I A巩 a, a , a,b , b,a , b,b , b,c , c,b , c , cr(Ri -R2)不具有传递性，所以r(Ri -R2)不是集合A上的等价关系。Ri R2是集合A上的等价关系。对于任意aA，有a,a R且a,aR2，故a,aRi R2，因此Ri R2是自反的任取a，bA，若(a，b)Ri,Ri是对称的，必有(b,a)，Ri，而R2是自反的，对于a,b A，有(a,a)R2,(b,b)R2，由(a,b)Ri与(b,b)R2,得(a,b)RiR2,由(b,a)R|与(a, a)，R2，得(b,a)，RiR2,因此RiR2 是

25、对称的。任取a,b,cA，若(a,b) Ri, (b,c) Ri , Ri是传递的，必有(a,c) Ri。由于R2是自反的，由(a,b) R 与(b,b)FR，得(a, b) R R?(b,c)R1 与(c,c)R?，得(b,c)Ri R2 (a,c)乏 Ri 与(c,c)e R2,得(a,c) e R R故Ri R2是集合A上的等价关系。15.设集合A=1,2,3,4，A上的四个半序关系分别为：R =( 1,1), (1,2), (1,3), (1,4), (2,2),(2,3), (3,3), (4,4)R2 二(1,1), (1,2), (2,2), (3,1), (3,2), (3,3

26、), (4,1), (4,2), (4,3), (4,4)R3 二(1,1),(2,2),(2,4),(3,1),(3,3),(4,4)哪个具有良序关系?2-7所示。R =(1,1), (1,2), (1,3), (1,4), (2,2),(2,3),(2,4), (3,3), (3,4),(4,4) 试分别画出它们的哈斯图，并判断起其中哪个具有序关系？ 解 集合上的半序关系的哈斯图如图RiR2Ri图2-7其中关系图R2与所有元素都排在链上，即任意两个元素之间都有关系存在，所以R2和&都是序关系。由于 R2和R4中每一非空子集都有最小元，所以也都是良序关系。说明此题中的阿拉伯数字已经失去了它们

27、在实数集中的大小关系，应该把它们看成四个不同符号。16.设集合A珂2,3,4,6,8,12,24，R为A上的整除关系。画出半序集（A,R）的哈斯图；写出集合 A中的最大元，最小元，极大元，极小元；写出A的子集B二2,3,6,12的上界，下界，最小上界，最大下界。解 半序集（A,R）的哈斯图如图2-8所示。81263图2-8集合A中的最大兀是24,无最小兀，极大兀也是24,极小兀是2和3。集合B的上界是12与24,无下界，最小上界是12,无最大下界说明最大元与极大元的区别在于，最大元是一个集合中的最大”者，若有则是唯一的；而极大元则是集合中的元素没有比它“大”的，可能不唯一。对于最小元与极小元具

28、有同样情况。这里把“大”字用弓I号引起来，因为实际上不一定在研究数与数之间的大小关系，而是 在研究某种半序关系。17. 设R是集合A上的半序关系，且B A，试证明RRr（B B）是b上的半序关 系。证 对于B任意，因为B A，故A，而R是A上的半序关系，贝U R在A上具有 自反性，于是（a,a）R，且（a,a）B B，这样可得（a,a） R 一 （B B）二 R即R 在B上是自反的。任取a,b B，且a = b，若（a,b） R ，可得（a,b） R且（a,b）B B，因为r具有 反对称性，必有（b, ab R，故（b, aV R,即R在B上具有反对称性。对于任意a，b,cB ,因为B A ,

29、故a,b,cA ,若（a,b） R且（b,c） R而 R=R-（B B），故（a,b） R 一 （B B）,（b,c） R 一 （B B），由（a,b） R 一 （B B）, 可得（a,b） R且（a,b）B B，即当（a,b）R同时R且b R。同理，当（b,c） R - （B B），也有（b,c） R 同时 b R 且 c R。因为R在A上具有传递性，由（a,b） R且（b,c） R，得（a,c），R。又a,b,c，B，故 （a,c）B B，因此（a,c）R- （B B）二R：r，满足传递性，所以R是B上的半序关 系。18 设集合 A 二0,1,2,3,4,5, B 二% ,映射二定义为二(

30、2n) =0,；(2 n 1) =1,( n =0,1,2),C =2,3解 因为二:A B , A 二O，1,2,3,4,5, B 二0,1，当 aA时(2n)=0当门=0,1,2时，a = 0,2,4cr (a)=呼(2n+1)=1当门=0,1,2时，a=1,3,5而 C 二2,3A，设映射.:C B二(2n) =0二(2n 1) = 1 故皿(犷1 即 .(2) = 0, .(3) = 1t (a) = *此时n只取1, a = 2此时n也只取1, a =3a = 2a = 3为 二 在 C 上 的 限 制 二(0) = 0,二(2) = 0,；(4) = 0,二二仁=仁二1为.在A上的

31、扩充。设A和B是两个有限集合，它们的元数都是n，则二:A B是单射的充分必要条件是二为满射证 必要性，当-是单射时，二(A)的元数是n，而匚(A) b,b的元数也是 n，故 二(A) =B，因此c : A B是满射。充分性，若二:A B为满射时，有 匚(A) = B，则；(A)的元数为n，A的元数也是 n，n个原象对应n个象，即不同元素对应不同的象，因此二是a到B的单射。设 R 为实数集，二：R R、Rf(X,y) =x y,又.:R R R, (x,y x y,试证 明二和都是满射，而不是单射。证 对于任意a R，可以使x y成立的x, y有无数对，且(x, y) R R，也就是说值域R中每个元素都有无数原象在R R中，所以二是满射，而不是单射。对于任意aR，能使a=xy成立的x, y也不止一对实数存在。例如a=6，而 x=2, y=3，或x=3,y=2, ，即象集中每一元素都有原象， 而且原象不唯一，所以是 满射，而不是单射。证毕