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

3）MR2?R1?MR2?0?0?MR1??0??0000010001??1?00????0??0??0??0100000001??0?01????0??0??0??0000000000?0?? 0??0?1?2?3?4?

1?2?3?4?

1?2?3?4? 无论从复合关系图还是从复合关系矩阵 都可得R1оR2оR1=?

MR3?MR1?MR1?MR11?11?00???00??0000??11?0001????00??00??00??0001??11?0001????00??00??00??0000?01??00??00?

4）

?11?00???00??00

01??11?0000????00??00??00??0000??11?0001?0???00??00??0??0000000?0??0??0?1?2?3?4?

????

????

?1?2?3?4

无论从复合关系图还是从复合关系矩阵

3都可得R1оR1оR1={（1，1），（1，2）， （1，4）}

R1 R1 R1

15）设R1，R2，R3是A上的二元关系，如果R1?R2，证明

1）R1?R3?R2?R3 2）R3?R1?R3?R2

[证明] 1）对任何（x，y）∈R1R3，由复合关系之定义，必存在z∈A，使得（x，z）

∈R1且（z，y）∈R3，利用R1?R2可知（x，z）∈R2且（z，y）∈R3，再次利用复合关系之定义，有（x，y）∈R2?R3。所以R1?R3?R2?R3。 2）对任何（x，y）∈R3?R1，由复合关系之定义，必有z∈A，使得（x，z）

21

∈R3且（z，y）∈R1，再由复合关系之定义，有（x，y）∈R3?R2。所以R3?R1?R3?R2。

16．设A是有限个元素的集合，在A上确定两个不同的关系R1和R2，

2使得R1=R1，R22=R2

2因为，令R1=?，则R1?R1=?，故此R1=R1=?。

22令R2=A×A，则R2=R2?R2?A×A=R2，故需证明R2?R2οR2=R2。为此，

对任何x，y∈A，（x，y）∈A×A=R2，一定存在着z∈A（至少有z=x或z=y存在），使（x，z）∈A×A=R2且（z，y）∈A×A=R2，故此（x，y）R2?R2=R22，

2所以R2?R2?R2=R22。于是R2=R2=A×A。

2）由于A是有限个元素的集合，是不心设A={a1，a2，??an}

令R1={（ai，aj）|ai∈A∧aj∈A∧|≤i≤n∧|≤j≤n-|} R2={（an，an）∪R1}

2则R1R2，即R1与R1是不同的关系。我们来证明R1=R1，R22=R2， 2（a）先征R1=R1

若（ai，aj）∈R1，则由R1的定义必定1≤i≤n，1≤i≤n-1，并且一定存在着1≤k≤n-1（至少有k=j存在），使（ai，ak）∈R1且（ak，aj）∈R1，从而（ai，

22aj）∈R1?R1=R1。故此R1?R1。

2若（ai，aj）∈R1= R1?R1，则存在着k，1≤k≤n-1，使（ai，ak）∈R1且（ak，

aj）∈R1，于是由R1的定义，必有1≤i≤n，1≤j≤n-1，从而根据R1的定义，

2有（ai，aj）∈R1。故此R1= R1 2综合两个方面，可得R1= R1。

（b）次证R22=R2

若（ai，aj）∈R2，则由R2的定义，要么1≤i≤n，1≤j≤n-1，要么I=n，j=n 若1≤i≤n，1≤j≤n-1，则一定存在着1≤k≤n-1（至少有k=j存在），使（ai，ak）∈R2且（ak，aj）∈R2，从而（ai，aj）∈R2οR2=R2；若i=n，j=n，则（ai，aj）=（an，an）∈R2，那么（an，an）∈R2，所以（ai，aj）=（an，an）∈R2οR2=R2因此R2=R2。

若（ai，aj）∈R2= R2οR2，则存在着k，使（ai，ak）∈R2且（ak， ai）∈R2，于是由R2的定义，有k=n或者1≤k≤n-1。

若k=n，则由（ai，ak）∈R2必有I=n，所以无论1≤j≤n-1还是j=n，由R2

的定义，有（ai，aj）=（an，aj）∈R2；

若1≤k≤n-1，则由（ai，ak）∈R2必有1≤j≤n-1故此（ai，aj）∈R2总之

2222 22

?17．设R是集合A上的反对称关系，|A|=h，指了在R∩R的关系矩阵中有多少个非

零值？

的关系矩阵中非零值最多不超过n个。

18．设R1和R2是集合A上的关系，判断下列命题的真假性，并阐明理由。

1） 如果R1和R2都是自反的，那么R1?R2是自反的。 2） 如果R1和R2都是反自反的，那未R1?R2是反自反的。 3） 如果R1和R2都是对称的，那末R1?R2是对称的。 4） 如果R1和R2都是反对称的，那末R1?R2是反对称的。 5） 如果R1和R2都是传递的，那末R1?R2是传递的。

[解] 1）真。由于R1和R2和R2都是自反的，因而对任何，都有（x，x）∈R1，（x，x）

∈R2。因此，对任何x∈A，都有（x，x）∈ R1?R2。所以R1?R2是自反的。 2）假。令A={a，b}，R1={（a，b）}，R2={b，a}。那么R1?R2={（a，a）}，它就不是A上的反自反关系。

3）假。令A={a，b，c}，R1={（a，b），（b，a）}，R2={（b，c），（c，b）}。那末R1?R2={（a，c）}，就不是A的对称关系。 4）假。令A={a，b，c，d}，R1={（a，c），（b，c）}

R2={（c，b），（d，a）}易证R1，R2都是反对称关系。但是R1?R2={（a，b），（b，a）}就不是A上的反对称关系。

5）假。令A={a，b，c}，R1={（a，c），（b，a），（b，c）}，R2={（c，b），（a，c），（a，b）}，易证R1和R2都是传递关系，但R1?R2={（a，b），（b，b），（b，c）}就不是A上的传递关系。

19．设A={1，2，3，4，5}，R?A×A，R={（1，2），（2，3），（2，5），（3，4），（4，3），（5，5）}用作图方法矩阵运算的方法求r（R），s（R），t（R）。 [解] 1）作图法：

R5 的关系图 （R）的关系图

5

2证得R22= R2，综合两方面，我们证明了R2= R2。

[解] 由第12题的4） R是反对称关系当且反当R∩R?IA，及|A|=n可知，在R∩R

??4 1

4 1

3 2

23

3 2 5 5 4

4

1

2 1

3 2 3

S（R）的关系图 t（R）的关系图

因此：

r（R）={（1，1），（1，2），（2，2），（2，3），（2，5），（3，3），（3，4），（4，3），

（4，4），（5，5）}

s（R）={（1，2），（2，1），（2，3），（2，5），（3，2），（3，4），（4，3），（5，2），

（5，5）}

t（R）={（1，2），（1，3），（1，4），（1，5），（2，3），（2，4），（2，5），（3，3），

（3，4），（4，3），（4，4），（5，5）} 2）矩阵运算法：

?0??0??0??0???0

0??1??0? ?0??1??MR?100000101000100

?1?0?MIAVMR=?0??0??00100000100000100??0?00???0?V?0??0??01????01000001010001000??1?01???0???0??0??01????01100000110001100?0??0? ?0?1??Mr（R）=MIAUR?

24