11 关系 习题答案
- 格式：doc
- 大小：110.50 KB
- 文档页数：4
练习 11.1
1. 设A = {1, 2, 3, 4, 5, 6}，B = {1, 2, 3}，A到B的关系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 = {
1(2)）
A. 自反的 B. 对称的 C. 传递的、对称的 D. 反自反的、传递的
3. 设A = {1, 2, 3, 4, 5, 6}上的关系为R = {
A. 对称的 B. 自反的的
C. 反自反的、反对称的、传递的 D. 反对称的
4. 设A,B为集合，A= n, B=m。（P179 3）
（1）问A到B的二元关系共多少个？
（2）问A上二元关系共多少个？
解： （1）A到B的二元关系共2nm个
（2）A上二元关系共22n个
5. 设A＝{0,1,2,3,4,5}，B={1,2,3}，用列举法描述下列关系，并作出它们的关系图及关系
矩阵：（P179 4(2)(3)）
（1）R2={
（2）R3={
解：
（1）R2={<1,1>,<4,2>}
2
R
M
=000010000000001000
（2）R3={<0,5>,<1,4>,<2,3>,<3,2>,<4,1>,<5,0>}
3
R
M
=000001000010000100001000010000100000
6. 设A＝{a,b,c,d}，A上二元关系R1，R2分别为
0
1
2
3
4
5
1
2
3
0 5
4
3 2
1
R1={
R2={
计算R1◦R2，R2◦R1，R21，R22。（P180 7）
解： R1◦R2 = {
R21= {
7. 设{1,2,3}{,,}{,,}ABabcC，，， R是A到B的关系，S是B到C的关系，且
。，},,,,,,,{},2,,2,,1{ccbaScabR
（1） 求复合关系SR。
（2） 用矩阵的逻辑乘求SR的关系矩阵。
（3） 画出R、S和SR的关系图。
解：
（1）},2,,2,,1{SR
（2）000110001
（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 ◦ R
3
R3 ◦ R1 R3 ◦ R2 （P181 15）
证明：（1）设任意x，yA， x R1 ◦ R3y u(xR1u uR3y)
u(xR2u uR3y)
x R2 ◦ R3y
所以R1 ◦ R3 R2 ◦ R
3
（2）设任意x，yA，若x R
3 ◦ R1y ，则存在uA使xR3u uR1y成立；因为R1 R2
且uR
1y，所以uR2y成立，则xR3u uR2y成立，所以x R3 ◦ R2
y。证明完毕。
*10. 称A上关系R是反传递的，如果
xyz(xRy yRz → ┐xRz)
证明：R是反传递的当且仅当R2 R = （P181 17）
证明：设R2 R = 。若xRy且yRz，则xR2z，由于R2 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上等价关系，证明ni1Ri也是A上等价关系。（P188 4）
证明： R1，R2，…，Rn均为A上等价关系，则R1，R2，…，Rn均满足自反、对称、传递
性，而交运算对自反、对称、传递性都封闭，所以ni1Ri也满足自反、对称、传递性，故ni1R
i
也是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）下列命题哪些为真？
a
b
c
d
e
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, 下确界不存在.
a
b
d
c
e
