精品文档
6）
1??23??1?1 R6???1??4?1111?111?? 111??111?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?
?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的
?若R是反对称的，则对任何（x，y）∈R，即有（x， y）∈R及（x，y）
??反对称性，可得x=y。于是就有（x，y）=（x，x）∈IA，所以R∩R?IA。
充分性
若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，若 (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 (IA是幺关系，因此是自反关系) ?(x,x)∈IA?R
?(x,x)∈? (因IA?R=?) 则与空集不含任何元素，(x,x)??矛盾。 故对任何x∈A，(x,x)?R ； 所以，R是反自反关系； 3)?)对任何x，y∈A
(x,y)∈R
?(y,x)∈R (R是对称关系) ?(x,y)∈R 所以，R=R； ?):对任何x,y∈A
(x,y)∈R
?(x,y)∈R (R=R) ?(y,x)∈R
????.
精品文档
所以，R是对称的； 4)?)对任何x，y∈A
(x,y)∈R?R
??(x,y)∈R?(x,y)∈R ?(x,y)∈R?(y,x)∈R
?x=y (R是反对称关系) ? (x,y)∈IA (IA是自反关系) 所以，R?R?IA ； ?):对任何x,y∈A
(x,y)∈R
?(x,y)∈R (R=R) ?(y,x)∈R 所以，R是对称的；
13．设A、B为有穷集合，R，S?A×B，MR=（xij）m×n，MS=（yij）m×n
1）为了R?S，必须且只须?i?j（xij≤ yij）
2）设MR∪S=（Zij）m×n，那么Zij=xijVyij，I=1，2……，m，j=1，2，……n. 3）设MR∩S=（tij）m×n，那么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）m×n中第I行第j列元素xij=1，根据R?S，可得（ai，bj）∈S，从而得S的关系矩阵MS=（yij）m×n中第I行第j列元素yij=1，由于是1≤1故此xij≤yij；若（ai，bj）?R，则R的关系矩阵MR=（xij）m×n中第i行第j列元素xij=0，因此由S的关系矩阵MS=（yij）m×n中第j列元素yij≥0，可得xij≤yij。总之，有（?i）(?j)（xij≤yij）。 2）充分性
若（?i）(?j)（xij≤yij），则对任何（ai，bj）∈R，就有R的关系
矩阵MR=（xij）m×n中第i行第j列元素xij=1，由于xij≤yij，所以yij≥1，故此yij≥1这说明S的关系矩阵MS=（yij）m×n中第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，于是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оR1R1
3[解] MR1?1?0???0??0100??0?0001?? ，MR??2?0000???000??0001010100?1?? 0??0?1）
MR?R?MR121?11?00?MR2??00??0000??0001??0?0011??001???????00??0100??0????00??0000??0010001?00?? 00??00?1?2?
3?3?3?4?4?4?R1 R2
1?2?1?2?无论从复合关系图还是从复合关系矩阵 都可得R1оR2={（1，3），（1，4）}
.