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

3），（3，4），（4，3）（4，4）}（因为|A|=4有限） 其关系图如下：

26

1 2

1

2

3 4

3

4

R的关系图 R1的关系图

3）能。因为R1并非全关系（否则，当R1是全关系时，就找不到了），所以只要取

R2=A3A是A上的全关系就可满足R2?R，R2≠R，并且全关系R2显然是一个传递关系。

22．设A={1，2，3，4??，9}，定义A3A上的关系如下：

（a，b）R（c，d）∷ a+d=b+c 1） 证明R是A3A上的等价关系； 2） 求[（2，5）]R；

3） R?A3A对吗？请阐明理由。 1）[证明] （a）R是自反的

对于任何（a，b）∈A3A，由于a+b = b+a，所以（a，b）R（a，b）。

（b）R是对称的

对于任何（a，b），（c，d）∈A3A，若（a，b）R（c，d），则有a+d = b+c从而c+b+a，所以可得（c，d）R（a，b）。 （c）R是传递的

对于任何（a，b），（c，d），（e，f）∈A3A，若（a，b）R（c，d），且（c，d）R（e，f），于是有a+d = b+c及c+f = d+e，二式相加有a+f+c+d = b+e+c+d，两边同时减c+d，可得a+f = b+e，从而可得（a，b）R（e，f）。 综合（a）、（b）、（c）、说明R是A3A上的等价关系。

2）[解] 因为{（2，5）}R = {（a，b）|（a，b）∈A3A（a，b）R（2，5）} = {（a，b）|（a，b）∈A3A∧a+5 = b+2} = {（a，b）|（a，b）∈A3A∧b = a+3}

={（1，4），（2，5，（3，6），（4，7），（5，8），（6，9））

27

3）[答] R?A3A不对。因为R是A3A上的关系，所以R?（A3A）3（A3A）=(A?A)2。

23．设A是一个非空集合，R?A3A。如果R在A上是对称的，传递的，下面的推

导说明R在A上是自反的：

对任意的a，b∈A，由于R是对称的，有： aRb?bRa

于是aRb?aRb∧bRa，又利用R是传递的，得： aRb∧bRa?aRa 从而说明R是自反的。 上述推导正确吗？请阐明理由。

[答] 上述推导不正解。推殖民地的谬论误在于假设A的每个元素都由R关联着A的某一别的元素。如果这不是真的，那么对称性的条件的假设就始终是假的，因此结论当然是假的。因而在一个空集上的空关系都是平凡的对称和可传递，但不是自反的。另外关系{（a，a），（b，b），（a，b），（b，a）}是自反的和传递的，但在集合{a，b，c}上不是自反的。

24．设R是集合A上的等价关系，证明R也是集合A上的等价关系。 [证明] 证法一：

?? （a）R是自反的

对任意的a∈A，由于R是自反的，所以（a，a）∈R，再由逆关系的定义有（a，a）∈R

??对任何（a，b）∈R由逆关系的定义，有（b，a）∈R,由R的对称性，可

?得（a，b）∈R，再由逆关系的定义，就有（b，a）∈R。

?（c）R是传递的

??对任何（a，b）∈R及（b，c）∈R，由逆关系的定义，有（b，a）∈R

及（c，b）∈R，根据R的传递性，可得（c，a）∈R，再次由逆关系的定义，就有（a，c）∈R。 证法二：

?（b）R是对称的

?综合（a）（b）（c）可知R是等价关系。

??R（a）是自反的：

对任何a，a?A

?(a,a)?R (R都是自反的)

??(a,a)?R

28

?所以，R是自反的；

?R（b）是对称的：

对任何a，b?A，(a,b)?R?

?(b,a)?R

?(a,b)?R (R是对称的)

所以，R是对称的；

???(b,a)?R

?（c）R是传递的：

对任何a，b，c?A，

??(a,b)?R?(b,c)?R

?((b,a)?R?(c,b)?R

?((c,b)?R?(b,a)?R (?的交换律) ?(c,a)?R (R是传递的)

?R?(a,c)? (R是对称的)

?所以，R是对称的；

?综合（a）、（b）、（c），可知R是A上的等价关系。

25．设R1和R2都是集合A上的等价关系

1）证明R1∩R2也是A上的等价关系；

2）用例于证明R1∪R2不一定是A上的等价关系（要尽可能小地选取集合A）。 [证] 1）证法一：

（a）R1∩R2是自反的

对任何a∈A，由于R1，R2都是A上的自反关系，所以（a，a）∈R1（a，a）∈R2，因此（a，a）∈R1∩R2

（b）R1∩R2是对称的

对任何的（a，b）∈R1∩R2，就有（a，b）∈R1且（a，b）∈R2，由R1，R2都是A上的对称关系，所以（a，b）∈R1且（b，a）∈R2，所以（b，a）∈R1∩R2。

（c）R1∩R2是传递的

对任何的（a，b）∈R1∩R2及（b，c）∈R1∩R2，就有（a，b）∈R1，（a，b）∈R2及（b，c）∈R1，（b，c）∈R2，于是（a，b）∈R1且（b，c）∈R1及（a，b）∈R2且（b，c）∈R2由于R1，R2都是A上的传递关系，所以（a，c）∈R1及（a，c）∈R2，因此（a，c）∈R1∩R2。

29

综合（a），（b），（c），可知R1∩R2是等价关系。 证法二：

（a）R1∩R2是自反的： 对任何a，a?A

?(a,a)?R1?(a,a)?R2 (R1，R2都是自反的) ?(a,a)?R1?R2

所以，R1?R2是自反的； （b）R1∩R2是对称的： 对任何a，b?A，(a,b)?R1?R2

?(a,b)?R1?(a,b)?R2

?(b,a)?R1?(b,a)?R2 (R1，R2都是对称的) ?(b,a)?R1?R2

所以，R1?R2是对称的； （c）R1∩R2是传递的： 对任何a，b，c?A，

(a,b)?R1?R2?(b,c)?R1?R2

?((a,b)?R1?(a,b)?R2)? ((b,c)?R1?(b,c)?R2)

?((a,b)?R1?(b,c)?R1)? ((a,b)?R2?(b,c)?R2) (?的结合律、交换律) ?(a,c)?R1?(a,c)?R2 (R1，R2都是传递的) ?(a,c)?R1?R2 所以，R1?R2是对称的；

综合（a）、（b）、（c），可知R1?R2是A上的等价关系。

2）两个自反的（对称的）关系的并将是自反的（对称的），但是，两个传递关系的并却未必是传递的。我们就从破坏传递性出发来构造反例： 令R1={（a，a），（b，b），（c，c），（a，b），（b，a）} R2={（a，a），（b，b），（c，c），（b，c），（c，b）} 当A={a，b，c}时，R1，R2显然都是等价关系。但是

R1∪R2={（a，a），（b，b），（c，c），（a，b），（b，a）（b，c），（c，b）}都不是A上的等价关系，因为R1∪R2不传递：（a，b）∈R1∪R2且（bc，但（a，c）?R1∪R2；同样（c，b）∈R1∪R2且（b，a）∈R1∪R2，但（c，a）?R1∪R2。

a a

c

a b b 30 c b c