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

?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?A3A，证明

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，