精品文档

2）MR2?R1?MR2?0?0?MR1??0??0001001001??1?01????0??0??0??0100000001??0?01????0??0??0??0000000000?0?? 1??0?

1?1?1?2?2?2?3? 3? 3? 无论从复合关系图还是从复合关系矩阵

4?4?4?都可得R2оR1={（3，4）} R2 R1

??101??0000?3）?0011?M0??10001?000?R2?R1?M?M000R2R?1??0000?????000?????000?? ?0000???0?000???000??0000??1?1?1?2?2?2?3? 3? 3? 无论从复合关系图还是从复合关系矩阵

4?4?4?都可得R1оR2оR1=?

?11000???1101??11M01?01??000R3?MR1?MR1?M??001R1??0000??00????00????0?0000?00???0000????00?0004）

?110100???11??1100???0000??0001??0000???0000????000????00???0000??00???000????00?0000??

.

0?1?0??0??

精品文档

1?2? 3?4??? ????1无论从复合关系图还是从复合关系矩阵

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

??2 ??3??4R1 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）∈R3且（z，y）∈R1，再由复合关系之定义，有（x，y）∈R3?R2。所以R3?R1?R3?R2。

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

使得R1=R1，R2=R2

22

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=R2，所以R2?R2?R2=R2。于是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}

则R1R2，即R1与R1是不同的关系。我们来证明R1=R1，R2=R2， （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，aj）∈R1?R1=R1。故此R1?R1。

若（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的定义，有（ai，aj）∈R1。故此R1= R1 综合两个方面，可得R1= R1。

22222222222.

精品文档

2（b）次证R2=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总之证得R2= R2，综合两方面，我们证明了R2= R2。 零值？

的关系矩阵中非零值最多不超过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，

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

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

??.

精品文档

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）作图法：

5 5

4 1

4 3

2

3 2 1 R的关系图 （R）的关系图

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?

1000??0101?0010?

?0100??0001???MR?

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

?0?0???MS（R）=MRUR=MRVMR=?0??0??01000??0?10100???0010?V?0??0100??00001????00000??0?10000???1010???0??0100??00001????01000?0101??1010?

?0100?1001??

?0?0?MR2=MRοR=MR?MR=?0??0??01000??0?0100???00010???0??0100??00001????01000??00?0101???000010???00??0100??000001????00101?011??010?

?100?001??

?0?0?MR3=MR2?R=MR2?MR=?0??0??0.

0101??0?1011???00100???0??0010??00001????01000??00?0101???000010???00??0100??000001????00011?101??010?

?100?001??