2024年3月10日发(作者：联发科x30处理器好吗)

练习 11.1

1. 设A = {1, 2, 3, 4, 5, 6}，B = {1, 2, 3}，A到B的关系R = { | a = b

2

}，则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的二元关系共2

nm

个

（2）A上二元关系共

2

个

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

矩阵：（P179 4(2)(3)）

（1）R

2

={xA∧yB∧x=y

2

}

（2）R

3

={xA∧yA∧x+y=5}

解：

（1）R

2

={<1,1>,<4,2>}

n

2

M

R

2



0



1





0

=





0



0





0

00



00





00





00



10





00



0

1

2

3

4

1

2

3

5

（2）R

3

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



0



0





0

M

R

3

=





0



0





1

00001



00010





00100





01000



10000





00000



0 5

1

4

2 3

6. 设A＝{a,b,c,d}，A上二元关系R

1

，R

2

分别为

R

1

={,,}

R

2

={,,,}

2

计算R

1

◦R

2

，R

2

◦R

1

，R

1

，R

2

（P180 7）

2

。

解： R

1

◦R

2

= {,} R

2

◦R

1

= {}

2

R

1

= {,,} R

2

2

= {,,}

7. 设

A{1,2,3}，

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

B{a,b,c}，C{



,



,



}，

R{1,b,2,a,2,c}，S{a,



,b,



,c,



,c,



}。

（1） 求复合关系

RS

。

（2） 用矩阵的逻辑乘求

RS

的关系矩阵。

（3） 画出R、S和

RS

的关系图。

解：

（1）

RS{1,



,2,



,2,



}



100





（2）

011







000





（3）

*8. 证明：当关系R传递且自反时，R

2

＝R。（P181 14）

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

2

 R；

设xRy。因为R自反，所以有yRy，于是有xR

2

y，因此R

 R

2

。综上R

2

＝R。

*9. 证明：若集合A上关系R

1

，R

2

，满足R

1

 R

2

，那么对任一A上关系R

3

有

R

1

◦ R

3

 R

2

◦ R

3

R

3

◦ R

1

 R

3

◦ R

2

（P181 15）

证明：（1）设任意x，yA， x R

1

◦ R

3

y  u(xR

1

u  uR

3

y)

 u(xR

2

u  uR

3

y)

 x R

2

◦ R

3

y

所以R

1

◦ R

3

 R

2

◦ R

3

（2）设任意x，yA，若x R

3

◦ R

1

y ，则存在uA使xR

3

u uR

1

y成立；因为R

1

 R

2

且uR

1

y，所以uR

2

y成立，则xR

3

u uR

2

y成立，所以x R

3

◦ R

2

y。证明完毕。

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

xyz(xRy  yRz → ┐xRz)

2

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

证明：设R

2

 R = 。若xRy且yRz，则xR

2

z，由于R

2

 R = ，所以R，所以R

是反传递的。

设R是反传递的，反设R

2

 R  ，则必存在xR

2

z且xRz。由xR

2

z，则存在yA使

得xRy并且yRz，它们与xRz一起同R反传递相矛盾，所以R

2

 R = 。

R是反传递的当且仅当R

2

 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. 半序关系

（P188 4）



R也是A上等价关系。

i

n

*3. 设R

1

，R

2

，…，R

n

均为A上等价关系，证明

i1

证明： R

1

，R

2

，…，R

n

均为A上等价关系，则R

1

，R

2

，…，R

n

均满足自反、对称、传递

性，而交运算对自反、对称、传递性都封闭，所以

也是A上等价关系。

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

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

{,} 和{, , , }



R也满足自反、对称、传递性，故



R

i

nn

i

i1i1

练习 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. 右图为一有序集的哈斯图。

a

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

c

b

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

（2）恢复R的关系图。

e

d

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

（4）求出子集B

1

= {c,d,e}，B

2

= {b,c,d }，B

3

= {b,c,d,e}的上界、下界，上确界、下确界

（如果有的话）。

解：

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

（2）见下图。

a

c

b

d

e

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

（4）子集B

1

= {c,d,e}的上界为a和c，下界不存在，上确界为c, 下确界不存在；

子集B

2

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

子集B

3

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