离散数学形成性考核作业三.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。
离散数学集合论部分
综合练习辅导
本次活动是本学期的第一次活动( .10.14) , 主要是针对集合论单元的重点学习内容进行辅导, 方式是经过讲解一些典型的综合练习题目, 帮助大家进一步理解和掌握集合论的基本概念和方法, 也使大家尽早地了解本课程期末考试的题型。
离散数学是电大计算机科学与技术专业( 本科) 教学计划改革调整后设置的一门统设必修学位课程．本课程4学分, 课内72学时, 开设一学期．
本课程的学习目标: 经过本课程的学习, 使学生具有现代数学的观点和方法, 并初步掌握处理离散结构所必须的描述工具和方法．同时, 也要培养学生抽象思维和慎密概括的能力, 使学生具有良好的开拓专业理论的素质和使用所学知识, 分析和解决实际问题的能力, 为学生以后学习计算机基础理论与专业课程打下良好的基础．
本课程的主要内容包括: 集合论、 图论、 数理逻辑三个单元．
集合论单元主要介绍朴素集合论的相关内容, 主要在合适定义的论述域中讨论集合的概念、 关系及其性质, 以及函数概念等．

一、 单项选择题
1．若集合A＝{2, a, { a }, 4}, 则下列表述正确的是( )．
A．{a, { a }}ÎA B．{ a }ÍA
C．{2}ÎA D．ÎA
正确答案: B
2．若集合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
正确答案: B
3．设集合A = {1, a }, 则P(A) = ( )．
A．{{1}, {a}} B．{,{1}, {a}}
C．{,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }}
正确答案: C
注意: 若A是n元集, 则幂集P(A )有2 n个元素．
4．设集合A = {1, 2, 3, 4, 5, 6 }上的二元关系R ={a , bêa , bA , 且a +b = 8}, 则R具有的性质为( ) ．
A．自反的 B．对称的
　　C．对称和传递的　 D．反自反和传递的
正确答案: B
因为写出二元关系R的集合表示式为
R = {2 , 6, 6 , 2, 3 , 5, 5 , 3, 4 , 4}
显然, R是对称的, 不是自反的、 反自反的、 传递的．
要求大家能熟练地写出二元关系R的集合表示式．
5．设集合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．以上都不对
正确答案: C
想一想: R的自反闭包是什么?
如果集合A={1, 2, 3}, A上的二元关系R={<x, y>|xÎA, yÎA, x+y=8}, 那么R的自反闭包是什么? 请写出．
2
4
1
3
5
6．设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系
的哈斯图如右图所示, 若A的子集B = {3 , 4 , 5},
则元素3为B的( ) ．
A．下界 B．最大下界
C．最小上界 D．以上答案都不对
正确答案: C
£
二、 填空题
1．设集合A有n个元素, 那么A的幂集合P(A)的元素个数为 ．
应该填写: 2n
如果n=5, n=8, 那么A的幂集合P(A)的元素个数分别是多少?
2．设集合A = {1, 2, 3, 4, 5 }, B = {1, 2, 3}, R从A到B的二元关系,
R ={a , bêaA, bB且2a + b4}
则R的集合表示式为 ．
应该填写: R = {1 , 1, 1 , 2, 1 , 3, 2 , 1, 2 , 2, 3 , 1}
3．设集合A={0, 1, 2}, B={0, 2, 4},R是A到B的二元关系,

则R的关系矩阵MR＝
　　　　　　　　　　　　　　　 　　．
应该填写:
因为R ={<0,0>, <0,2>, <2,0>, <2,2>}, 由此能够写出R的关系矩阵．
4．设集合A={a,b,c}, A上的二元关系
R={<a, b>,<c. a>}, S={<a, a>,<a, b>,<c, c>}
则(R·S)－1=　　　　　　　　　　　．
应该填写: {<a, c>, <b, c>}
因为 R·S={<c, a>, <c, b>}, 因此(R·S)－1={<a, c>, <b, c>}．
5．设集合A=｛a,b,c,d｝, A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}, 则二元关系R具有的性质是　　　　　　　　　．
应该填写: 反自反的
6．设集合A={1, 2}, B={a, b}, 那么集合A到B的双射函数是
　　　　　　　　　　　　　 ．
应该填写: {<1, a >, <2, b >}, {<1, b >, <2, a >}
想一想: 集合A到B的不同函数的个数有几个?

三、 判断说明题( 判断下列各题, 并说明理由．)
1．设A、 B、 C为任意的三个集合, 如果A∪B=A∪C, 判断结论B=C 是否成立? 并说明理由．
解: 结论不成立．
设A={1, 2}, B={1}, C={2}, 则A∪B=A∪C, 但B¹C．

2．如果R1和R2是A上的自反关系, 判断结论: ”R-11、 R1∪R2、 R1ÇR2是自反的” 是否成立? 并说明理由．
解: 结论成立．
因为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是自反的．

a
c
b
e
d
f
3．判断”若偏序集<A, R>的哈斯图如右图所示, 则集合A的极大元为a, f; 最大元不存在．”是否正确, 并说明理由．
解: 正确
按照极大元定义: ”若对任意aB, 且ba, 都有
a = b, 则称b为B的极大元”, 可知a, f是A的极大元,
且最大元不存在．
想一想: ”若偏序集<A, R>的哈斯图如右图所示, 则集合
A的最大元为a; 最小元不存在．” 是否正确?
再给出一个判断说明题, 大家要重视的。
想一想: ”设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．
解: ( 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．设集合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的最大元、 最小元．
1
2
3
4
6
9
5
7
8
10
11
12
关系R的哈斯图
解: ( 1) R=IAÈ{<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)

( 3) 集合B没有最大元, 最小元是: 2

a
d
b
c
3．设集合A＝{a, b, c, d}上的二元关系R的
关系图如右图所示．
( 1) 写出R的表示式;
( 2) 写出R的关系矩阵;
( 3) 求出R2．
解: ( 1) R＝{<a, a>, <a, c>, <b, c>, <d,d>}
( 2)
( 3) R2 = {<a, a>, <a, c>, <b, c>, <d, d>}·{<a, a>, <a, c>, <b, c>, <d, d>}
={<a, a>, <a, c>, <d,d>}

五、 证明题
1．试证明集合等式: AÈ (BÇC)=(AÈB) Ç (AÈC)．
证: 若x∈AÈ (BÇC), 则x∈A或x∈BÇC,
即 x∈A或x∈B 且 x∈A或x∈C．
即x∈AÈB 且 x∈AÈC ,
即 x∈(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)．

想一想: 等式AÇ (BÈC)=(AÇB) È (AÇC)如何证明?

2．设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是等价关系．

3．若非空集合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ÇS是偏序关系.