《离散数学》(集合论部分)自测试题

- --------- -

----- ---- ---- - 2015 - 2016学年第一学期 ---- ----- ---- - 《离散数学》（集合论部分）自测试题

--- ------ ---- -

--- ----- ----- -题号 一 二 三 四 五 总分 统分人 统分复核人 -- ---- -----线号线得分 -学-----------

--- ------ -----得分 阅卷人 复核人 - ---- ---- ----- - ---- ---- ------ -一、单项选择题(本大题共8小题，每小题2分，共16分)

--- ----- 装 装-在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的-- ---- ---- ---括号内。错选、多选或漏选均不得分。 - ------ --名-----1）等价关系一定不是--．．【 】 ---姓--------A. 对称的 B. 自反的 -12 --- ---- -----C. 可传递的

D. 反自反的

- ---- ---- -----2）设A{a,{1}}，则下列描述中正确- -．．的是【 】 --- ---- ---A. {1}A B. {1}A 第 第- ---- ---- -C. {a}A

D. A

--- ------ ---- -3）设A、B是两个任意集合，则AB【 】 --- --级-----------A. AB B. AB -班-------------C. AB

D. B

--------------4）设X{{},{a},{b}}，则其幂集P(X)的元素总个数为【 】 ------------ A. 4

B. 8

第 1 页 共 4 页 C. 16 D. 32

5）设R是实数集合，f:RR,f(x)2x1，则f【 】 A. 是关系，但不是函数 B. 仅是满射函数 C. 仅是单射函数

D. 是双射函数

6）设R是A上的二元关系，r、s、t分别指关系的自反闭包、对称闭包、传递闭包、则下列描述不正确．．．的是【 】 A. r(R)RIA

B. t(R)RR2

C. s(R)RR1

D.

（R-1）-1R 7）如果R1和R2是集合A上的自反关系，则R1∪R2, R1∩R2, R1―R2中自反关系有【 】个 A. 0 B. 1 C. 2

D. 3

8）设集合A=｛a,b,c｝，B=｛1,2,3,4｝，作f：A→B，则不同的函数个数为【 】个 A. 12 B. 81

C. 64

D. 以上均不正确

得分 阅卷人 复核人 二、填空题(本大题共12空，每空2分，共24分)

请在每小题的空格中填上正确答案。错填、漏填均不得分。 7）设集合A={1,2,3,4}，则A中的划分有_____________个.

8）设R=｛<1,2>,<1,3>,<2,4>,<4,3>｝，那么fldR=_____________. 9）设集合A =｛1，2，3，4｝，则AA _____________.

10）设关系F ={<3,3>,<6,2>},G ={<2,3>}，则FG= _____________.

11）设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B上的二元关系，其中

R={|x∈A，y∈B且x,y∈A∩B} 则R的有序对集合为_____________. 12

）

设

集

合

A=

｛

a, b, c, d

｝，

A

上

的

二

元

关

系

R={, , , }，若在R中再增加两个元素_____________，则新得到的关系就具有对称性．

13）设A={1, 2}上的二元关系为R={|x∈A∧y∈A∧x+y =10}，则R的自反闭包

为_____________.

14）设R、S是定义在集合P上的二元关系，其中P是所有人的集合.

R=｛|x,y∈P且x是y的父亲｝； S=｛|x,y∈P且x是y的母亲｝；

（1）R º R表示的关系是：_____________. （2）S-1

º R表示的关系是：_____________. （3）S º R-1

表示的关系是：_____________.

（4）关系｛|x,y∈P且y是x的的外祖母｝，其关系表达式为_____________. （5）关系｛|x,y∈P且x是y的的祖母｝，其关系表达式为_____________.

得分 阅卷人 复核人 三、计算题(本大题共3小题，共30分)

15）（8分）某班级有25名学生，已知期中考试与期末考试得优的人数相等并且仅在一次考试中得优的人数是4人，在两次考试中均没有得到优的人数是15人.试求期中考试、期末考试和两次考试中得优人数各是多少？（要求：应用包含排斥原理求解）

第 2 页 共 4 页

16）（13分）设集合A={2,3,6,8},在集合A上定义整除关系R≤，偏序集对应的哈斯

图如右图所示，请求解下列问题． 86（1）画出关系R的关系图.

（2）求关系R的传递闭包t(R)（要求：应用沃舍尔算法求解）. （3）求集合A的最大元、极小元、上界、下确界. 23

17）（9分）设A，B为非空集合，|A|=n,|B|=m，请计算：

（1）能够构造从集合A到B，具有单射性质的函数共有多少种？并讨论此时n与m的关系. （2）能够构造从集合A到B，具有满射性质的函数共有多少种？并讨论此时n与m的关系.

19）设R是集合A上的自反和传递关系，如下定义A上的关系T，使得对于任意的x,y∈A，

均有∈T∈R ∧∈R成立. 证明：T是集合A上的等价关系. （3）能够构造从集合A到B，具有双射性质的函数共有多少种？并讨论此时n与m的关系.

得分 阅卷人 复核人 四、证明题(本大题共2小题，每小题6分，共12分)

18）设A,B为任意集合，P(A)、P(B)分别表示集合A、B的幂集.

证明：P(A)∩P(B) = P(A∩B).

第 3 页 共 4 页

得分 阅卷人 复核人

21）一个计算机公司开发的项目需要完成7个任务，其中的某些任务只能在其他任务结束之后才能开始.考虑如下建立任务上的偏序，如果任务Y在任务X结束之后才能开始，则任务X<任务Y.这7个任务关

G五、综合应用题(本大题共2小题，每小题9分，共18分)

20）设全集为n元集，按照某种给定顺序排列为E={x1，x2，…, xn}. 在计算机中可以用长为n的0,1串表示E的子集.令m元子集A={ x i , ,… ， x i},则A对应的0,1串为j1j2…jn，

1xi2m其中 jk1,ki1,i2,…，im

0,否则例如，E={1,2,…，8}，则A={1,2,5,6}和B={3,7}对应的0,1,串分别为11001100和00100010. （1）设A对应的0，1串为10110010，则~A对应的0,1串是什么？ （2）设A与B对应的0,1串分别为i1i2…in和

j1j2…jn ,且A∪B，A∩B，A-B ，A⊕B

对应0,1串分别为a1a2…an，b1b2…bn，c1c2…cn，d1d2…dn ，求ak，bk，ck，dk ，k=1,2,…，n.

第 4 页 共 4 页于该偏序的哈斯图如右图所示，求一个全序使得可以按照此全序执行这些任务，以完成这个项目.（要求：有具体分析过程）

DFBACE