R6是自反的，对称的，传递的，循环的。从而是等价关系。 7）
1??23??0?0 R7???0??4?0000?000?? 000??000?R7是反自反的对称的，传递的，循环的，反传递的，反对称的。
12．设A是A上的关系，证明 1）R是自反的当且反当IA?R
2）R是反自反的当且仅当IA∩R=?
?3）R是对称的当且反当R=R
4） R是反对称的当且仅当R∩R?IA 5）R是传递的当且仅当R?R?R [证] 1）必要性
若R是自反的，则对任何x∈A，都有（x，x）∈R，但是IA={（x，x）|x∈A}，所以IA?R。
充分性
若IA?A则由IA={（x，x）|x∈A}，可知对任何x∈A，都有（x，x）∈R，所以R是自反的。 2）必要性
若R是反自反的，则对任何x∈A，都是（x，x）?R，从而（x，x）∈R′，由IA={（x，x）|x∈A} 可知IA?R′。于是IA∩R?R′∩R=?，另外??IA∩R，所以IA∩R=?。
充分性
若IA∩R=?，则R是反自反的。否则，不是反自反的，那么应存在某一x0
∈A，使得（x0，x0）∈R。但是（x0，x0）∈IA，从而（x0，x0）?。这不可能，矛盾。 3）必要性，
若R是对称的，则对任何（x，y）∈R，就有（y，x）∈R。于是根据逆
????关系的定义，可得（x，y）∈R，于是R?R；对任何（x，y）∈R，由逆关
?系的定义，可得（y，x）∈R。再次利用R的对称性有（y，x）∈R，于是R?
16
?R；综合两方面，有R=R。
充分性
若R= R，则对任何（x， y）∈R，由R=R可得（x，y）∈R。从而由逆关系的定义，可知（y，x）∈R这说明R是对称的。 4）必要性
???∈R，从逆关系的定义，就有（x， y）∈R及（y，x）∈R，因此，利用R的反对称性，可得x=y。于是就有（x，y）=（x，x）∈IA，所以R∩R?IA。 充分性
??若R是反对称的，则对任何（x，y）∈R，即有（x， y）∈R及（x，y）
???若R∩R ?IA，则对任何（x，y）∈R及（y，x）∈R，从逆R关系的定
???义，可得（x，y）∈R及（x，y）∈R，也即（x，y）∈R∩R，利用R∩R =IA
可得（x，y）∈IA，于是x=y。所以R是反对称的。 5）必要性
若R是传递的，则对任何（x，y）RоR，由复合关系的定义可知，存在着y∈A，使（x，y）∈R且（y，y）∈R，从而利用R的传递性，可知（x，y）∈R。所以
RоR?R。
充分性
RоR。从而利用RоR?R可得（x，y）∈R。所以R是传递的。 证法二： 1)?):对任何x，
x∈A
?(x,x)∈IA (IA是幺关系，因此是自反关系) ?(x,x)∈R (R是自反关系) 所以 IA?R ； ?):对任何x∈A，
x∈A
?(x,x)∈IA (IA是幺关系，因此是自反关系) ?(x,x)∈R (因IA?R) 所以，R是自反关系； 2)?)首先 ??IA?R ；
其次，对任何x，y∈A，若
17
(x,y)∈IA?R ?(x,y)∈IA?(x,y)∈R
?x=y?(x,y)∈R (IA是幺关系，因此是自反关系) ?(x,x)∈R
则与R是反自反关系，(x,x)?R矛盾。故IA?R?? ； 因此，由包含关系?的反对称性，可得 IA?R=? ； ?):对任何x∈A，若
(x,x)∈R
?(x,x)∈IA?(x,x)∈R ?(x,x)∈IA?R
?(x,x)∈? 则与空集不含任何元素，(x,x)??矛盾。 故对任何x∈A，(x,x)?R ； 所以，R是反自反关系； 3)?)对任何x，y∈A
(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
