离散数学（第三版）陈建明，刘国荣课后习题答案(6)

(x,y)∈R

?(y,x)∈R ?(x,y)∈R?

所以，R=R?；

?):对任何x,y∈A

(x,y)∈R

?(x,y)∈R? ?(y,x)∈R 所以，R是对称的； 4)?)对任何x，y∈(x,y)∈R?R?A

?(x,y)∈R?(x,y)∈R? ?(x,y)∈R?(y,x)∈R

?x=y ? (x,y)∈IA 所以，R?R??IA ； ?):对任何x,y∈A

18

(IA是幺关系，因此是自反关系) (因IA?R=?) (R是对称关系)

(R=R?)

(R是反对称关系) (IA是自反关系) ???(x,y)∈R (R=R)

?(y,x)∈R 所以，R是对称的；

13．设A、B为有穷集合，R，S?A3B，MR=（xij）m3n，MS=（yij）m3n

1）为了R?S，必须且只须?i?j（xij≤ yij）

2）设MR∪S=（Zij）m3n，那么Zij=xijVyij，I=1，2??，m，j=1，2，??n. 3）设MR∩S=（tij）m3n，那么tij=xij^yij i=1，2，??m；j=1，2，??，n. [证] 由于A、B是有穷集合，不妨设

A={a1，a2??，am}，B={b1，b2，??，bn} 1）必要性

若R?S，则对任何i∈{1，2，??，m}，对任何j∈{1，2，??n}，若（ai，bj）∈R，则R的关系矩阵MR=（xij）m3n中第I行第j列元素xij=1，根据R?S，可得（ai，bj）∈S，从而得S的关系矩阵MS=（yij）m3n中第I行第j列元素yij=1，由于是1≤1故此xij≤yij；若（ai，bj）?R，则R的关系矩阵MR=（xij）m3n中第i行第j列元素xij=0，因此由S的关系矩阵MS=（yij）m3n中第j列元素yij≥0，可得xij≤yij。总之，有（?i）(?j)（xij≤yij）。 2）充分性

若（?i）(?j)（xij≤yij），则对任何（ai，bj）∈R，就有R的关系

矩阵MR=（xij）m3n中第i行第j列元素xij=1，由于xij≤yij，所以yij≥1，故此yij≥1这说明S的关系矩阵MS=（yij）m3n中第i行第j列元素yij为1，因此必有

（ai，bj）∈S，所以R?S。

2）对任何i∈{1，2，??，m}，对任何j∈{1，2，??，n}若Zij=1，则（ai，bj）∈R∪S，故此（ai，bj）∈R或者（ai，bj）∈S，于是xij=1或者yij=1。从而 bj）?S，于是xij=0且yij=0。从而xij∨yij=0。因而Zij=xij∨yij=0； 综合上述两种情况，就有zji=xij∨yij，i=1，2，??，m，j=1,2,??n，。 3）对任何i∈{1，2，??m}，对任何j∈{1，2，??，n}。若tij=1，则（ai，bj）∈R∩S，故此（ai，bj）∈S且（ai，bj）∈S，于是xij=1，且yij=1从而xij∧yij=1。因而tij=xij∧yij=1；若tij=0，则（ai，bj）?R∩S，故此（ai，bj）?S，于

(x,y)∈R

19

是xij=0或者yij=0，从而xij∧yij=0。因而tij=xij∧yij=0。

综合上述两种情况，就有tij=xij∧yij，i=1，2，??，m，j=1，2，??，n。 14．设A={1，2，3，4}，R1，R2为A上的关系，R1={（1，1），（1，2），（2，4）}，

R2={（1，4），（2，3），（2，4），（3，2）}，求R1оR2，R2оR1，R1оR2оR1R13

[解] MR1?1?0???0??0100??0?0001?? ，MR??2?0000???000??0001010100?1?? 0??0?1）

MR1?R2?MR1?1?0?MR2??0??0100000000??0?01????0??0??0??0001001001??00?001????0??00??0??0010001?0?? 0??0?1?2?3?4?

1?2?3?4?R1 R2

1?2?3?4??0?0?MR1??0??0

无论从复合关系图还是从复合关系矩阵 都可得R1оR2={（1，3），（1，4）}

2）MR2?R1?MR2001001001??1?01????0??0??0??0100000001??0?01????0??0??0??0000000000?0?? 1??0?

1?2?3?4?

1?2?3?4?R2 R1

1?

2?3?4? 无论从复合关系图还是从复合关系矩阵 都可得R2оR1={（3，4）}

20