11 关系 习题答案

1.  设A = {1, 2, 3, 4, 5, 6}，B = {1, 2, 3}，A到B的关系R = { | a = b2}，则Dom(R)和Ram(R)分别为（  C  ）（P178 1(1)）

A. {<1, 2>}, {1, 4} B. {<1, 4>}, {2, 1}

C. {1, 4}, {1, 2}                              D. {1, 2}, {1, 4}

2.  集合A = {1, 2, …, 10}上的关系R = { | x + y = 10}，则R的性质为（  B  ）（P178 1(2)）

A. 自反的       B. 对称的        C. 传递的、对称的         D. 反自反的、传递的

3.  设A = {1, 2, 3, 4, 5, 6}上的关系为R = { | i > z}，则R的性质是（  C  ）（P178 1(4)）

A. 对称的                                  B. 自反的的        

C. 反自反的、反对称的、传递的              D. 反对称的

4.  设A,B为集合，A= n, B=m。（P179 3）

  （1）问A到B的二元关系共多少个？

  （2）问A上二元关系共多少个？

解： （1）A到B的二元关系共2nm个

（2）A上二元关系共个

5.  设A＝{0,1,2,3,4,5}，B={1,2,3}，用列举法描述下列关系，并作出它们的关系图及关系矩阵：（P179 4(2)(3)）

  （1）R2={xA∧yB∧x=y2}

  （2）R3={xA∧yA∧x+y=5}

解：

（1）R2={<1,1>,<4,2>}

=

（2）R3={<0,5>,<1,4>,<2,3>,<3,2>,<4,1>,<5,0>}

=

6.  设A＝{a,b,c,d}，A上二元关系R1，R2分别为

                R1={,,}

                R2={,,,}

计算R1◦R2，R2◦R1，R，R。（P180 7）

解： R1◦R2 = {,}             R2◦R1 = {}

R= {,,}          R= {,,}

7.  设R是A到B的关系，S是B到C的关系，且

  （1） 求复合关系。

  （2） 用矩阵的逻辑乘求的关系矩阵。

  （3） 画出R、S和的关系图。

解：

（1）

（2） 

（3） 

*8. 证明：当关系R传递且自反时，R2＝R。（P181 14）

证明： 当R传递时，由定理已知R2  R；

设xRy。因为R自反，所以有yRy，于是有xR2y，因此R  R2。综上R2＝R。

*9. 证明：若集合A上关系R1，R2，满足R1  R2，那么对任一A上关系R3有

                 R1 ◦ R3  R2 ◦ R3

R3 ◦ R1  R3 ◦ R2  （P181 15）

证明：（1）设任意x，yA， x R1 ◦ R3y  u(xR1u  uR3y)

                                  u(xR2u  uR3y)

                                  x R2 ◦ R3y

所以R1 ◦ R3  R2 ◦ R3

（2）设任意x，yA，若x R3 ◦ R1y ，则存在uA使xR3u uR1y成立；因为R1  R2且uR1y，所以uR2y成立，则xR3u uR2y成立，所以x R3 ◦ R2y。证明完毕。

*10. 称A上关系R是反传递的，如果

              xyz(xRy  yRz → ┐xRz)

证明：R是反传递的当且仅当R2  R =   （P181 17）

证明：设R2  R = 。若xRy且yRz，则xR2z，由于R2  R = ，所以R，所以R是反传递的。

设R是反传递的，反设R2  R  ，则必存在xR2z且xRz。由xR2z，则存在yA使得xRy并且yRz，它们与xRz一起同R反传递相矛盾，所以R2  R = 。

R是反传递的当且仅当R2  R = 得证。

练习 11.2

1.  集合A上的等价关系R，决定了A的一个划分，该划分就是（  D  ）（P188 1(5)）

A. 并集A∪R         B. 交集A∩R          C. 差集A – R         D. 商集A/R

2.  集合A上的一个划分，确定A的元素间的关系为（  B  ）（P188 1(6)）

A. 全序关系          B. 等价关系            C. 序关系            D. 半序关系

*3. 设R1，R2，…，Rn均为A上等价关系，证明Ri也是A上等价关系。（P188 4）

证明： R1，R2，…，Rn均为A上等价关系，则R1，R2，…，Rn均满足自反、对称、传递性，而交运算对自反、对称、传递性都封闭，所以Ri也满足自反、对称、传递性，故Ri也是A上等价关系。

补充：求集合{a,b}上有几个等价关系，并写出这些等价关系。

解：集合{a,b}上有两个划分{{a}，{b}}和{{a，b}}，分别对应两个等价关系

{,} 和{, , , }

练习 11.3

1.  集合A上的关系R是序关系的必要条件是（  A  ）

A. 自反的，反对称的和传递的               B. 自反的和对称的

C. 传递的和自反的                         D. 传递的和反对称的

2.  设有两个集合{1, 2, 3, 4, 6, 8, 12, 24}和{3, 9, 27, 54}，定义偏序关系为整除关系，分别画出它们的哈斯图，并求两个集合的最大、最小、极大、极小元。

解：哈斯图如下图所示。

第一个集合，最大元24， 最小元1，极大元24，极小元1。

第二个集合，最大元54， 最小元3，极大元54，极小元3。

3.  右图为一有序集的哈斯图。

   （l）下列命题哪些为真？

        aRb，dRa， cRd， cRb， bRe， aRa， eRa；

   （2）恢复R的关系图。

   （3）指出A的最大、最小元（如果有的话），极大、极小元。

（4）求出子集B1 = {c,d,e}，B2 = {b,c,d }，B3 = {b,c,d,e}的上界、下界，上确界、下确界（如果有的话）。

解： 

（1）为真的命题有：dRa, aRa，eRa，

（2）见下图。

（3）A的最大元素为a，A的最小元素不存在；极大元为a，极小元为d，e。

（4）子集B1 = {c,d,e}的上界为a和c，下界不存在，上确界为c, 下确界不存在；

子集B2 = {b,c,d }的上界为a，下界为d，上确界为a，下确界为d；

子集B3 = {b,c,d,e}的上界为a，下界不存在，上确界为a, 下确界不存在.