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

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