离散数学集合论部分综合练习.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。
离散数学集合论部分综合练习
本课程综合练习共分3次, 分别是集合论部分、 图论部分、 数理逻辑部分的综合练习, 这3次综合练习基本上是按照考试的题型安排练习题目, 目的是经过综合练习, 使同学自己检验学习成果, 找出掌握的薄弱知识点, 重点复习, 争取尽快掌握。本次是集合论部分的综合练习。

一、 单项选择题
1．若集合A={a, b}, B={ a, b, { a, b }}, 则( ) ．
A．AÌB, 且AÎB B．AÎB, 但AËB
C．AÌB, 但AÏB D．AËB, 且AÏB
2．若集合A＝{2, a, { a }, 4}, 则下列表述正确的是( )．
A．{a, { a }}ÎA B．{ a }ÍA
C．{2}ÎA D．ÎA
3．若集合A＝{ a, {a}, {1, 2}}, 则下列表述正确的是( )．
A．{a, {a}}ÎA B．{2}ÍA
C．{a}ÍA D．ÆÎA
4．若集合A={a, b, { 1, 2 }}, B={ 1, 2}, 则( ) ．
A．B Ì A, 且BÎA B．BÎ A, 但BËA
C．B Ì A, 但BÏA D．BË A, 且BÏA
5．设集合A = {1, a }, 则P(A) = ( )．
A．{{1}, {a}} B．{,{1}, {a}}
C．{,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }}
6．若集合A的元素个数为10, 则其幂集的元素个数为( ) ．
A．1024 B．10 C．100 D．1
7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={<x, y>|x+y=10且x, yA}, 则R的性质为( ) ．
A．自反的 B．对称的
C．传递且对称的 D．反自反且传递的
8．设集合A = {1, 2, 3, 4, 5, 6 }上的二元关系R ={a , bêa , bA , 且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．以上都不对
2
4
1
3
5
图一
11．设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系
的哈斯图如图一所示, 若A的子集B = {3 , 4 , 5},
则元素3为B的( ) ．
A．下界 B．最大下界
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={<a, 2>, <b, 2>}, R2={<a, 1>, <a, 2>, <b, 1>}, R3={<a, 1>, <b, 2>}, 则( ) 不是从A到B的函数．
A．R1和R2 B．R2 C．R3 D．R1和R3

二、 填空题
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的有序对集合为　 　　　　　　．
4．设集合A={0, 1, 2}, B={0, 2, 4},R是A到B的二元关系,

则R的关系矩阵MR＝
　　　　　　　　　　　　　　　 　　．
5．设集合A={a,b,c}, A上的二元关系
R={<a, b>,<c. a>}, S={<a, a>,<a, b>,<c, c>}
则(R·S)－1=　　　　　　　　　　　．
6．设集合A=｛a,b,c｝, A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}, 则二元关系R具有的性质是　　　　　　　　　．
7．若A={1,2}, R={<x, y>|xÎA, yÎA, x+y=10}, 则R的自反闭包为 ．
8．设集合A={1, 2}, B={a, b}, 那么集合A到B的双射函数是
　　　　　　　　　　　　　 ．
9．设A={a, b, c}, B={1, 2}, 作f: A→B, 则不同的函数个数为 ．

三、 判断说明题( 判断下列各题, 并说明理由．)

图一
1．设A、 B、 C为任意的三个集合, 如果A∪B=A∪C, 判断结论B=C 是否成立? 并说明理由．
2．如果R1和R2是A上的自反关系, 判断
结论: ”R-11、 R1∪R2、 R1ÇR2是自反的” 是否
成立? 并说明理由．
3． 若偏序集<A, R>的哈斯图如图一所示,
则集合A的最大元为a, 最小元不存在．
4．若偏序集<A, R>的哈斯图如图二所示,
则集合A的最大元为a, 最小元不存在．
图二

5．设N、 R分别为自然数集与实数集, f: N
→R, f (x)=x+6, 则f是单射．

四、 计算题
1．设集合A＝{a, b, c}, B={b, d, e}, 求
( 1) BÇA; ( 2) AÈB; ( 3) A－B; ( 4) BÅA．
2．设A={{a, b}, 1, 2}, B={ a, b, {1}, 1}, 试计算
( 1) ( A-B) ( 2) ( A∪B) ( 3) ( A∪B) -( A∩B) ．
3．设集合A={{1},{2},1,2}, B={1,2,{1,2}}, 试计算
( 1) ( A-B) ; ( 2) ( A∩B) ; ( 3) A×B．
4．设A={0, 1, 2, 3, 4}, R={<x, y>|xÎA, yÎA且x+y<0}, S={<x, y>|xÎA, 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的哈斯图;
a
d
b
c
图三
( 3) 求出集合B的最大元、 最小元．
6．设集合A＝{a, b, c, d}上的二元关系R的关系图
如图三所示．
( 1) 写出R的表示式;
( 2) 写出R的关系矩阵;
( 3) 求出R2．
7．设集合A={1, 2, 3, 4}, R={<x, y>|x, yÎA; |x-y|=1或x-y=0}, 试
( 1) 写出R的有序对表示; ( 2) 画出R的关系图;
( 3) 说明R满足自反性, 不满足传递性．

五、 证明题
1．试证明集合等式: AÈ (BÇC)=(AÈB) Ç (AÈC)．
2．试证明集合等式AÇ (BÈC)=(AÇB) È (AÇC)．
3．设R是集合A上的对称关系和传递关系, 试证明: 若对任意aÎA, 存在bÎA, 使得<a, b>ÎR, 则R是等价关系．
4．若非空集合A上的二元关系R和S是偏序关系, 试证明: 也是A上的偏序关系．

参考解答
一、 单项选择题
1．A 2．B 3．C 4．B 5．C 6．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>
4．
5．{<a. c>, <b, c>}
6．反自反的
7．{<1, 1>, <2, 2>}
8．{<1, a >, <2, b >}, {<1, b >, <2, a >}
9．8

三、 判断说明题( 判断下列各题, 并说明理由．)
1．解: 错．
设A={1, 2}, B={1}, C={2}, 则A∪B=A∪C, 但B¹C．
2．解: 成立．
因为R1和R2是A上的自反关系, 即IAÍR1, IAÍR2。
由逆关系定义和IAÍR1, 得IAÍ R1-1;
由IAÍR1, IAÍR2, 得IAÍ R1∪R2, IAÍ R1ÇR2。
因此, R1-1、 R1∪R2、 R1ÇR2是自反的。
3．解: 正确．
对于集合A的任意元素x, 均有<x, a>ÎR
( 或xRa) , 因此a是集合A中的最大元．
按照最小元的定义, 在集合A中不存在最
小元．
4．解: 错误．
集合A的最大元不存在, a是极大元．
5．解: 正确．
设x1, x2为自然数且x1¹x2, 则有f(x1)= x1+6¹ x2+6= f(x2), 故f为单射．

四、 计算题
1．解: ( 1) BÇA={a, b, c}Ç{b, d, e}={ b }
( 2) AÈB={a, b, c}È{b, d, e}={a, b, c, d, e }
( 3) A－B={a, b, c}－{b, d, e}={a, c}
( 4) BÅA= AÈB－BÇA={a, b, c, d, e }－{ b }={a, c, d, e }
2．解: ( 1) ( A-B) ={{a, b}, 2}
( 2) ( A∪B) ={{a, b}, 1, 2, a, b, {1}}
( 3) ( A∪B) -( A∩B) ={{a, b}, 2, a, b, {1}}
3．解: ( 1) A-B ={{1},{2}}
( 2) A∩B ={1,2}
( 3) A×B={<{1},1>, <{1},2>, <{1},{1,2}>, <{2},1>, <{2},2>,
<{2},{1,2}>, <1,1>, <1,2>, <1, {1,2}>, <2,1>, <2,2>,
<2, {1,2}>}
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=Æ,
1
2
3
4
6
9
5
7
8
10
11
12
图四: 关系R的哈斯图
R-1=Æ,
S-1= S,
r(R)=IA．
5．解: ( 1) R=IÈ{<1,2>, <1,3>, …, <1,12> ,
<2,4>, <2,6>, <2,8>, <2,10>, <2,12>, <3,6>, <3,9> ,
<3,12>, <4,8>, <4,12>, <5,10>, <6,12>}
( 2) 关系R的哈斯图如图四
( 3) 集合B没有最大元, 最小元是: 2
6．解: R＝{<a, a>, <a, c>, <b, c>, <d,d>}

R2 = {<a, a>, <a, c>, <b, c>, <d, d>}·{<a, a>, <a, c>, <b, c>, <d, d>}
°
°
°
°
1
2
3
4
图五
={<a, a>, <a, c>, <d,d>}
7．解: ( 1) R={<1,1>,<2,2>,<3,3>,<4,4>,
<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}
( 2) 关系图如图五
( 3) 因为<1,1>,<2,2>,<3,3>,<4,4>均属于R,
即A的每个元素构成的有序对均在R中, 故R在
A上是自反的。
因有<2,3>与<3,4>属于R, 但<2,4>不属于R,
因此R在A上不是传递的。

五、 证明题
1．证明: 设, 若x∈AÈ (BÇC), 则x∈A或x∈BÇC,
即 x∈A或x∈B 且 x∈A或x∈C．
即x∈AÈB 且 x∈AÈC ,
即 x∈T=(AÈB) Ç (AÈC),
因此AÈ (BÇC)Í (AÈB) Ç (AÈC)．
反之, 若x∈(AÈB) Ç (AÈC), 则x∈AÈB 且 x∈AÈC,
即x∈A或x∈B 且 x∈A或x∈C,
即x∈A或x∈BÇC,
即x∈AÈ (BÇC),
因此(AÈB) Ç (AÈC)Í AÈ (BÇC)．
因此．AÈ (BÇC)=(AÈB) Ç (AÈC)．
2．证明: 设S=A∩(B∪C), T=(A∩B)∪(A∩C), 若x∈S, 则x∈A且x∈B∪C, 即 x∈A且x∈B 或 x∈A且x∈C,
也即x∈A∩B 或 x∈A∩C , 即 x∈T, 因此SÍT．
反之, 若x∈T, 则x∈A∩B 或 x∈A∩C,
即x∈A且x∈B 或 x∈A且x∈C
也即x∈A且x∈B∪C, 即x∈S, 因此TÍS．
因此T=S．
3．设R是集合A上的对称关系和传递关系, 试证明: 若对任意aÎA, 存在bÎA, 使得<a, b>ÎR, 则R是等价关系．
证明: 已知R是对称关系和传递关系, 只需证明R是自反关系．
"aÎA, $bÎA, 使得<a, b>ÎR, 因为R是对称的, 故<b, a>ÎR;
又R是传递的, 即当<a, b>ÎR, <b, a>ÎR Þ<a, a>ÎR;
由元素a的任意性, 知R是自反的．
因此, R是等价关系．
4．若非空集合A上的二元关系R和S是偏序关系, 试证明: 也是A上的偏序关系．
证明: .① , 因此有自反性;
②因为R, S是反对称的,
因此, RÇS有反对称性．
③ , 因为R, S是传递的,

因此, 有传递性．
总之, R是偏序关系．