离散数学习题解第一部分（集合论部分）(7)

?0?0?Mt(R)?MRUR2UR3?MRVMR2VMR3??0??0?0??0?0???0??0?0?1111?0111??0110??0110?0001??1000??0?00101???0001?V?0??0100??0?0001???00101??0?00011???0100?V?0??0010??0?0001???00011?0101??0010??0100?0001??

因此r（R），s（R），t（R）与1）作图法一致。 20．设R?A×A，证明

1）（R+）++R+2）=R*

[证明] 1）一方面，由于（R+）+是R+的传递闭包，所以R+?（R+）+；另一方面，

由于R+是R的传递闭包，故此R+是传递的。由于R+?R+及传递闭包（R+）+是包含R+的最小传递关系，就有（R+）+?R+（定理4之3）；所以（R+）+=R+。 2）一方面，由于（R*）*是R*的自反传递闭包，所以R*?（R*）*；另一方面，由于R*是R的自反传递闭包，故此R*是自反的传递的。由于R*?R*及自反传递闭包（R*）*是包含R*的最小自批传递关系，就有（R*）*?R*（定理5的3））。所以（R*）*=R*。

21．设A={1，2，3，4}，RAA，R={（1，2），（2，4），（3，4），（4，3），（3，3）} 1）证明R不是传递的；

2）求R1，使 R1?R并且R1是传递的；

3）是否存在R2，使R2?R，R2≠R1并且R2是传递的。

[解] 1）由于（1，2）∈R且（2，4）R但（1，4）? R，这说明R不是传递的。

2)由于R+是包含R的最小传递关系，所以，取R1=R+即为所求。现在来R+ R2={（1，4），（2，3），（3，3），（3，4），}（4，3），（4，4）} R3={（1，3），（2，3），（2，4），（3，3），（3，4），（4，3），（4，4）} R4={（1，3），（1，4），（2，3），（2，4），（3，3），（3，4），（4，3），（4，4）} 故此R1=R+=R∪R2∪R3∪R4={（1，2），（1，3），（1，4），（2，3），（2，4），（3，

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

26

1 2

1

2

3 4

3

4

R的关系图 R1的关系图

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

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

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

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

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

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

（b）R是对称的

对于任何（a，b），（c，d）∈A×A，若（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）∈A×A，若（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是A×A上的等价关系。

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

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

27

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

23．设A是一个非空集合，R?A×A。如果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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学习题解第一部分（集合论部分）(7)在线全文阅读。