华东交大 离散数学试卷三试题与答案

四、 1、 证明：

（1） 自反性：??x,y??X,由于x?y?x?y

???x,y?,?x,y???R?R自反

（2） 对称性：??x1,y1??X,??x2,y2??X

当??x1,y1?,?x2,y2???R时 即x1?y2?x2?y1也即x2?y1?x1?y2

故??x2,y2?,?x1,y1???R?R有对称性

（3） 传递性：??x1,y1??X,??x2,y2??X??x3,y3??X

当??x1,y1?,?x2,y2???R且??x2,y2?,?x3,y3???R时

?x?y2?x2?y1即?1?x2?y3?x3?y2(1)?(2)(1)(2)

x1?y2?x2?y3?x2?y1?x3?y2

即x1?y3?x3?y1

故??x1,y1?,?x3,y3???R?R有传递性

由（1）（2）（3）知：R是X上的先等价关系。 2、X/R={[?1,2?]R} 五、

?0??1MR??0??0?1、100??010?001??000??； 关系图

MR22、

?1??0?MR?MR??0??0??0??1?MR??0??0?10000100010010000??1?0??0??

MR3?MR21??0?0??0??

MR4?MR3?1??0?MR??0??0?010010000??1??MR20??0?? MR5?MR3,MR6?MR4,? ?1??1??0??0?110011001??1?1??0??

Mt(R)?MR?MR2?MR3?MR4? t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c ,

d > }。