离散数学关系部分经典练习及答案

离散数学关系部分综合练习

一、单项选择题

1．设集合A = {1, a }，则A的幂集P(A) = ( )．

A．{{1}, {a}} B．{?,{1}, {a}}

C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }}

2．若集合A的元素个数为10，则其幂集的元素个数为（ ）． A．1024 B．10 C．100 D．1

7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={|x+y=10且x, y?A}，则R的性质为（ ）．

A．自反的 B．对称的

C．传递且对称的 D．反自反且传递的

8．设集合A = {1，2，3，4，5，6 }上的二元关系R ={?a , b??a , b?A , 且a +b = 8}，则R具有的性质为（ ）．

A．自反的 B．对称的

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

9．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（ ）个．

A．0 B．2 C．1 D．3 10．设集合A={1 , 2 , 3 , 4}上的二元关系

R = {?1 , 1?，?2 , 2?，?2 , 3?，?4 , 4?}， S = {?1 , 1?，?2 , 2?，?2 , 3?，?3 , 2?，?4 , 4?}，

则S是R的（ ）闭包．

A．自反 B．传递 C．对称 D．以上都不对 11．设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系

1 的哈斯图如图一所示，若A的子集B = {3 , 4 , 5}，

3 2 则元素3为B的（ ）．

A．下界 B．最大下界 4 5

图一 C．最小上界 D．以上答案都不对

12．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合

B的最大元、最小元、上界、下界依次为 ( )．

A．8、2、8、2 B．无、2、无、2 C．6、2、6、2 D．8、1、6、1

13．设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={, }，R2={, , }，R3={, }，则（ ）不是从A到B的函数．

A．R1和R2 B．R2 C．R3 D．R1和R3

1

二、填空题 1．设集合A有n个元素，那么A的幂集合P(A)的元素个数为 ． 2．设集合A＝{a，b}，那么集合A的幂集是 ． 应该填写：{?,{a,b},{a},{b }}

3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， R?{?x,y?x?A且y?B且x,y?A?B} 则R的有序对集合为 ． 4．设集合A={0, 1, 2}，B={0, 2, 4},R是A到B的二元关系，

R?{?x,y?x?A且y?B且x,y?A?B}

则R的关系矩阵MR＝

． 5．设集合A={a,b,c}，A上的二元关系

R={,}，S={,,}

则(R?S)－1= ．

6．设集合A=｛a,b,c｝，A上的二元关系R={, , , }，则二元关系R具有的性质是 ．

7．若A={1,2}，R={|x?A, y?A, x+y=10}，则R的自反闭包为 ．

8．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为 ．

三、判断说明题（判断下列各题，并说明理由．） 2．如果R1和R2是A上的自反关系，判断 结论：“R-11、R1∪R2、R1?R2是自反的” 是否 成立？并说明理由．

3． 若偏序集的哈斯图如图一所示， 则集合A的最大元为a，最小元不存在．

4．若偏序集的哈斯图如图二所示， 则集合A的最大元为a，最小元不存在． 图一

四、计算题

图二 x，y>|x?A， 4．设A={0，1，2，3，4}，R={|x?A，y?A且x+y<0}，S={<

y?A且x+y?3}，试求R，S，R?S，R-1，S-1，r(R)．

5．设A={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}，R是A上的整除关系，B={2, 4, 6}． （1）写出关系R的表示式； （2）画出关系R的哈斯图； （3）求出集合B的最大元、最小元．

a

2

d c

图三

b 6．设集合A＝{a, b, c, d}上的二元关系R的关系图 如图三所示．

（1）写出R的表达式； （2）写出R的关系矩阵；

（3）求出R2．

7．设集合A={1，2，3，4}，R={|x, y?A；|x?y|=1或x?y=0}，试 （1）写出R的有序对表示； （2）画出R的关系图； （3）说明R满足自反性，不满足传递性．

五、证明题

3．设R是集合A上的对称关系和传递关系，试证明：若对任意a?A，存在b?A，使得?R，则R是等价关系．

4．若非空集合A上的二元关系R和S是偏序关系，试证明：R?S也是A上的偏序关系．

参考解答

一、单项选择题

1．A 2．A 7．B 8．B

9．B 10．C 11．C 12．B 13．B

二、填空题 1．2n

2．{?,{a,b},{a},{b }}

3．{<2, 2>，<2, 3>，<3, 2>}，<3, 3>

?110?? 0004．?????110?? 5．{, }

6．反自反的

7．{<1, 1>, <2, 2>} 8．8

三、判断说明题（判断下列各题，并说明理由．） 2．解：成立．

因为R1和R2是A上的自反关系，即IA?R1，IA?R2。 由逆关系定义和IA?R1，得IA? R1-1；

由IA?R1，IA?R2，得IA? R1∪R2，IA? R1?R2。

3

所以，R11、R1∪R2、R1?R2是自反的。 3．解：正确．

对于集合A的任意元素x，均有?R （或xRa），所以a是集合A中的最大元．

按照最小元的定义，在集合A中不存在最 小元．

4．解：错误．

集合A的最大元不存在，a是极大元．

四、计算题

4．解：R=?,

S={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>} R?S=?，

R-1=?， S-1= S， 12 8 r(R)=IA．

5．解：（1）R=I?{<1,2>, <1,3>, ?, <1,12> , 10 4 6 <2,4>, <2,6>, <2,8>, <2,10>, <2,12>, <3,6>, <3,9> , 2 3 5 <3,12>, <4,8>, <4,12>, <5,10>, <6,12>}

（2）关系R的哈斯图如图四

1 （3）集合B没有最大元，最小元是：2

-

9 7 11

图四：关系R的哈斯图

6．解：R＝{, , , }

0?0??

0??1?R2 = {, , , }?{, , , } ={, , }

7．解：（1）R={<1,1>,<2,2>,<3,3>,<4,4>, ? 1 2 <1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>} 3 ? ? （2）关系图如图五

4 ? （3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R，

即A的每个元素构成的有序对均在R中，故R在

图五 A上是自反的。

因有<2,3>与<3,4>属于R，但<2,4>不属于R， 所以R在A上不是传递的。

五、证明题

3．设R是集合A上的对称关系和传递关系，试证明：若对任意a?A，存在b?A，使得?R，则R是等价关系．

证明：已知R是对称关系和传递关系，只需证明R是自反关系．

?1?0MR???0??000001100 4

?a?A，?b?A，使得?R，因为R是对称的，故?R； 又R是传递的，即当?R，?R ??R；

由元素a的任意性，知R是自反的．

所以，R是等价关系．

4．若非空集合A上的二元关系R和S是偏序关系，试证明：R?S也是A上的偏序关系．

证明：.① ?x?A,?x,x??R,?x,x??S??x,x??R?S，所以R?S有自反性； ②?x,y?A,因为R，S是反对称的，

?x,y?R?S??y,x?R?S?(?x,y??R??x,y??S)?(?y,x??R??y,x??S)?(?x,y??R??y,x??R)?(?x,y??S??y,x??S)?x?y?y?x?x?y

所以，R?S有反对称性．

③ ?x,y,z?A，因为R，S是传递的， ?x,y??R?S??y,z??R?S

??x,y??R??x,y??S??y,z??R??y,z??S ??x,y??R??y,z??R??x,y??S??y,z??S ??x,z??R??x,z??S??x,z??R?S 所以，R?S有传递性． 总之，R是偏序关系．

5