精品文档
?0?0???0??0??00000001010101001??0?01???0???0??0??01????01000001010001000??00?001???0???00??0??001????0010100010101?1??0??MR2?0?1??MR4?MR3?R?MR3?MR
?0?0???0??0??01000??0?00101???0001?V?0??0100??00001????00101??0?00011???0100?V?0??0010??00001????00011?0101??0010??0100?0001??Mt(R)?MRUR2UR3?MRVMR2VMR3?0?0???0??0??01000011110111101?1??0??0?1??
因此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有限） 其关系图如下：
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））
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
?（b）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。 证法二：
（a）R是自反的： 对任何a，a?A
?(a,a)?R (R都是自反的)
所以，R是自反的；
?综合（a）（b）（c）可知R是等价关系。
????(a,a)?R
?（b）R是对称的：
?对任何a，b?A，(a,b)?R
?(b,a)?R
?(a,b)?R (R是对称的) ?(b,a)?R
??所以，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 (?的交换律)
??(a,c)?R (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）∈
?(c,a)?R (R是传递的)
.
精品文档
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。 综合（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上的等价关系。
.