东北师范大学2013年《离散数学》练习题和答案

《离散数学》练习题一

一、单项选择题

1．设集合E??0 , 1 , 2 , 3?，则下面集合与E相等的是 。

A．?x?R x?3?0 B．????x?R x2??9?

C．x?R x2?5x?6?0 D．?x?N 0?x?3?

2．设A??1 , 2 , 3 , 4 , 5 , 6?，R是集合A上的整除关系，下列叙述中错误的是 。

A．4，5，6全是A的极大元 B．A没有最大元 C．6是A的上界 D．1是A的最大下界3. 设X??1 , 2 , 3 , 4 ?，Y??a , b , c , d?，则下列关系中为从X到Y的映射是 。

A．?1 , a , 2 , b , 3 , c? B．?1 , a , 2 , b , 3 , c , 4 , b? C．?1 , a , 2 , a , 3 , b? D．?1 , a , 1 , b , 2 , b , 4 , b,3 , c?

4. 设G是4阶群，则其子群的阶不能是下面的 。 A. 1 B. 2 C. 3 D. 4 5．设S??1 , 2 , 3 , 4 , 5?，则下列集合中等于S的是 。 A．?1 , 2 , 3 , 4 ? B．?xx是有理数,x2?25?

C．?xx是正整数,x?5? D．?xx是有理数,x?5?

6．下面有关集合之间的包含和属于关系的说法，正确的是 。

Ⅰ． ??? Ⅱ． ??????,??,????? Ⅲ． ?a,b???a,b,?a,b?? Ⅳ． ?a,b???a,b,?a,b,c?? A．Ⅰ和Ⅱ B．Ⅰ和Ⅲ C．Ⅰ和Ⅳ D．Ⅱ、Ⅲ和Ⅳ 7. 设A为n个元素的集合，则A上有 个二元关系。 A．2n B．2n?n C．2n D．n

8. 数的加法在下列集合中 上是封闭的。

A．?0 , 1? B．??1 ， 1? C．?a?b a , b?Z? D．?x x是奇数? 9. 下列图形中为欧拉图的是 。

10．设L,?是格，a,b,c?L，且c?a,b?a，则a??b?c? ?a?b???a?c?。

1

A. = B. ? C. ? D. 没关系 11．设A?B??，则有 。

A．B?? B．B?? C．A?B D．B?A 12. P??Q? 。

A． ?P??P??Q? B． ??P??Q????Q?P? C． ??P?Q????Q?P? D． ??P??Q???Q?P?

13. 对于一个只有4个不同元素的集合A来说，A上的不同的二元关系的总数为 。

A．4 B．16 C．216 D．24 14. 下列代数系统G , *中， 不构成群。

A．G??1 , 10?，*是模11乘法 B．G??1 , 3 , 4 , 5 , 9?，*是模11乘法 C．G为有理数集，*是普通加法 D．G为有理数集，*是普通乘法 15. 设G为有n个顶点的简单图，则有 。

A． ??G??n B． ??G??n C． ??G??n D． ??G??n 16．设S??1 , 2 , 3 , 4 , 5?，则下列集合中等于S的是（ ）。

A．?1 , 2 , 3 , 4 ? B．?xx是有理数,x2?25?

C．?xx是正整数,x?5? D．?xx是有理数,x?5?

17．设A???1,2,3??,4,5??,6,7,8??，下列选项正确的是（ ）

。 A．1?A B．?1,2,3??A C．??4,5???A D．??A 18．设A为n个元素的集合，则A上有（ ）个二元关系。 A．2n B．2n?n C．2n D．n

19．数的加法在下列集合中（ ）上是封闭的。

A．?0 , 1? B．??1 ， 1? C．?a?b a , b?Z? D．?x x是奇数?20．下列图形中为欧拉图的是（ ）。

2

21．设S??1 , 2 , 3 , 4 , 5?，则下列集合中等于S的是（ ）。

A．?1 , 2 , 3 , 4 ? B．xx是有理数,x2?25 C．xx是正整数,x?5 D．xx是有理数,x?5 22．设A??。 ?1,2,3??,4,5??,6,7,8??，下列选项正确的是（ ）

A．1?A B．?1,2,3??A C．??4,5???A D．??A 23．设A为n个元素的集合，则A上有（ ）个二元关系。 A．2 B．2nn?n?????? C．2n D．n

24．数的加法在下列集合中（ ）上是封闭的。

A．?0 , 1? B．??1 ， 1? C．a?b a , b?Z D．x x是奇数

????25．下列图形中为欧拉图的是（ ）。

26．下列命题中， 是错误的。

A. x??x????x?? B. ?x???x????x??

C. 若A?x??x?，则x?A且x?A D. 若A?B??，则A?B 27．幂集P(P(P(?)))是 。

, ?? , ????? B．?? , ?? , ???? , ???? A．????

3

C．?? , ?? , ???? , ????? , ???? D．?? , ?? , ????? 28. 下列命题公式中 为重言式。

Ⅰ． ?p??p?q???r

Ⅱ． ?p??q?r?????p?q???p?r?? Ⅲ． ?p?q???p?r???p?r? Ⅳ． ??p?q??q?r

A.Ⅲ B.Ⅰ和Ⅲ C.Ⅰ和Ⅱ D.Ⅰ、Ⅱ、Ⅲ和Ⅳ 29．任意一个具有多个等幂元的半群 (若元素a满足a*a?a，则称a为等幂元)，该半群 。

A．不能构成群 B．不一定能构成群 C．必能构成群 D．能构成交换群

30．设I是整数集合，下列集合中 关于数的加法和乘法构成整环。 A．?2n n?I? B．?2n?1 n?I? C．?n n?0 , n?I? D．I 31．设集合A??1 , 2 , 3?，B??2 , 3 , 4 , 5?，C??2 , 4 , 8 , 16?，D??1 , 2 , 3 , 4?，又规定偏序关系“|”是集合上的“整除”关系，则下列偏序集中 能构成格。 A．A ,

二、填空题

1．设A为非空集合，且A?n，则A上不同的二元关系的个数为 ，A上不同的映射的个数为 。

2．设P、Q为两个命题，当且仅当 时，P?Q的真值为1。

3. 在运算表中的空白处填入适当符号，使?a , b , c? , *成为群。

* B．B , C．C , D．

a b c a b a a b c c c 4. 当n为 数时，Kn?n?3?必为欧拉图。

5. 某校有足球队员38人，篮球队员15人，排球队员20人，三队队员总数为58人，且其中只有3人同

4

时参加3种球队，那么仅仅参加两种球队的队员人数是 。 6. 命题公式??P?Q?的主析取范式为 。

7. 一棵无向树有两个2度顶点，一个3度顶点，三个4度顶点，则它的树叶数为 。 8．设P：我生病，Q：我去学校，命题“如果我生病，那么我不去学校”符号化为 。 9．P ,Q为两个命题，当且仅当 时，P?Q的值为0。

10. 设A , B , C , D是四个非空集合，则A?B?C?D的充分必要条件是 。 11. 在有理数集合Q上定义二元运算*：a*b?a?b?ab，则 Q , * 的幺元是 。 12. 设

L , ?是分配格，若对任意的a,b,c?L，都有a?b?a?c , a?b?a?c，

则 。

13. 某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，那么两次考试都得优的学生人数是 。

14. 将布尔表达式??a?c??c??b?b?c化简得 。

15. 设P：我有钱，Q：我去看电影，命题“当且仅当我有钱时，我才去看电影”符号化为 。

16. 设?a,b? , *是群，且a*a?b，则b*b? 。 17．命题公式?p??p????q??q??r?是永（ ）式。 18．P?Q的主析取范式中，含有（ ）个极小项。

?????a , b? , ?c , d , e? , ?f , g??，那么?所对应的19. 设集合A??a , b , c , d , e , f , g?，A上有一个划分???等价关系R应有（ ）个序偶。

20. 在有理数集合Q上定义二元运算*：a*b?a?b?ab，则 Q , * 的幺元是（ ）。

21. 一个（ ）称为布尔代数。

22．命题公式?p??p????q??q??r?是永（ ）式。 23．P?Q的主析取范式中，含有（ ）个极小项。

?a , b? , ?c , d , e? , ?f , g??，那么?所对应的24. 设集合A??a , b , c , d , e , f , g?，A上有一个划分???等价关系R应有（ ）个序偶。

25. 在有理数集合Q上定义二元运算*：a*b?a?b?ab，则 Q , * 的幺元是（ ）。

26. 一个（ ）称为布尔代数。

27．??P?Q???P?Q?的主析取范式是 。(写出一般

5

哈斯图为 。

6．设p：我们勤奋，q：我们好学，r：我们取得好成绩。命题“只要勤奋好学，我们就能取得好成绩”符号化为 。

7．某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，那么两次考试都得优的学生人数是 。

8. 设集合A??a , b , c ?，R是A上的二元关系，且R??a , b , b , c , c , a?，则R的对称闭包

s?R?= 。

9. 设A、B是集合，若A?2，B?3，则A到B的单射函数有 个。 10. 整数加法群的幺元是 。

11. 设L , ?是分配格，若对任意的a,b,c?L，都有a?b?a?c , a?b?a?c，则 。

12. 任何简单图中顶点的度数之和等于边数的 倍。 13. 当n为 数时，Kn必为欧拉图?n?2?。

14．设P：我有钱，Q：我去看电影，命题“如果我有钱，那么我就去看电影”符号化为 。

15．某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，那么两次考试都得优的学生人数是 。

16

16. 设集合A??a , b , c , d ?，R是A上的二元关系，且R??a , b , b , a , b , c , c , d , a , c?，则R的传递闭包t?R?= 。

17. 设A、B是集合，若A?2，B?3，则A到B的单射函数有 个。 18. 整数加法群的幺元是 。

19. 设L , ?是分配格，若对任意的a,b,c?L，都有a?b?a?c , a?b?a?c，则 。

20. 无向图G中具有一条欧拉回路，当且仅当G是连通的，并且所有顶点的度数都是 。

21. 若连通简单平面图G有4个顶点，3个面，则G有 条边。

B是集合，22．设A、其中A??则P?A??P?B?? 。 1 , 4?，B??2 , 4?，

23．集合A??a , b , c?上的关系R?? a , b , c , c , b , c ?的传递闭包t?R?? 。

第 页（共59页） 17

24. 设A是非空集合，则P(A),?中的幺元是 ，零元是 。

25. 若连通简单平面图G有6个顶点，3个面，则G有 条边。

26. 设L , ?是格，其中L??1 , 2 , 3 , 4 , 6 , 8 , 12 , 24?，?是整除关系，则3的补元是 ，6的补元是 。

27. 设A、B是集合，若A?2，B?3，则A到B的单射函数有 个。 28．设集合A??a?，则P?P?A??? 。

29．设集合A??a , b , c , d ?，R是A上的二元关系，且R??a , b , b , a , b , c , c , d , a , c?，则R的传递闭包t?R?= 。 30. 若连通平面简单图G有4个顶点，3个面，则G有 条边。

31. 设A是非空集合，则P(A),?中的幺元是 ，零元是 。 32. 设L , ?是格，其中L??1 , 2 , 3 , 4 , 6 , 8 , 12 , 24?，?是整除关系，则8的补元是 ，4的补元是 。

33.已知集合A和B，且A?n，B?m，则从A到B有 个二元关系，从A到B有 个映射。

二、单项选择题

1．下列集合运算中 是正确的。

??????????? A. ??????? B. ??,???C. ??,?????????????,???? D. ??,???????????? 2．下面 是重言式。

A. P??Q?R? B. ?P?R???P?Q?

C. ?P?Q???Q?R? D. ?P??Q?R?????P?Q???P?R??

18

3. ??P?Q???P?Q?的主析取范式是 A 。

A. ??P?Q???P??Q? B. ?P?Q???P??Q? C. ??P??Q???P?Q? D. ??P?Q????P?Q? 4. 若G , *是一个群，则运算“*”一定满足 。 A. 交换律 B. 消去律

C. 幂等律 D. 分配律

5．设I是整数集合，下列集合中 关于数的加法和乘法构成整环。 A．?2n n?I? B．?2n?1 n?I? C．?n n?0 , n?I? D．I 6．如下的哈斯图所示偏序集为格的是 。

Ａ Ｂ Ｃ Ｄ 7．设S??1 , 2 , 3 , 4 , 5?，则下列集合中等于S的是 。

A．?1 , 2 , 3 , 4 ? B．xx是有理数,x2?25 C．xx是正整数,x?5 D．xx是有理数,x?5 8．下列公式中， 是析取范式。 A. ??p?q?

B. ??p?q?

D. p?q

??????C. ?p?q???p

9. 下列语句中为命题的是 。

A. 今天是阴天； B. 你身体好吗？ C. 我真快乐； D. 请不要走。

10. 设G是连通简单平面图，G中有6个顶点8条边，则G的面的数目是 。 A．2个面 B．3个面 C．4个面 D．5个面 11. 设R，S是集合A上的二元关系，称关系S?y,x x,y?R为R的 关系。 A. 交 B. 并 C. 补 D.逆

19

??

12. 下面集合中, 关于数的减法是封闭的。

? B．? 2x x?Z ? A．N??全体自然数C．? 2x?1 x?Z ? D． x x是质数 13. 设A是有界格，若它也是有余格，只要 。

A. 每一个元素有一个余元 B. 每一个元素至少有两个余元 C. 每一个元素无余元 D. 每一个元素仅有一个余元 14．设集合E??0 , 1 , 2 , 3?，则下面集合与E相等的是 。 A．?x?R x?3?0? B．x?R x2??9 C．x?R x2?5x?6?0 D．?x?N 0?x?3? 15．下列公式中， 是关于两个命题变元p，q的极小项。 A．p??p?q B．?p?q C．?p?q D．?p?p?q 16. 下列语句中不是命题的是 。

A. 3是奇数 B. 请勿吸烟 C. 我是中学生 D. 4+3>5 17. 数的加法在下列 集合上是封闭的。

A．?0 , 1? B．??1 ， 1? C．?a?b a , b?Z? D．x x是奇数 18. 给定下列序列，可构成无向简单图的顶点度数序列的是 。

A. ?1 , 1 , 2 , 2 , 3? B. ?1 , 1 , 2 , 2 , 2? C. ?0 , 1 , 3 , 3 , 3? D. ?1 , 3 , 4 , 4 , 5?

????????19. 若G , *是一个群，则运算“*”一定满足 。 A. 交换律

B. 消去律

C. 幂等律

D. 分配律

20. 设R是非空集合A上的关系，则R的对称闭包s?R?= 。 A. R?R?1 B. IA?R C. R?IA D. R?R?1 21．下列集合运算中 是正确的。

??????????? A. ??????? B. ??,???

20

26．(10分) 用推理规则证明：A??B?C? , D?E?A , D?E?B?C 证明：(1) A??B?C? P (2) D?E?A P (3) D?E?B?C T(1)(2)I (4) D?E P (5) B?C T(3)(4)I

27．(10分) 设R是非空集合A上自反的二元关系，证明：R?1也是自反的。 证明：因为R是自反的，所以IA?R，则IA

28. (20分) 设G是整数加群，在G上定义：a*b?a?b?2，证明：G , *是交换群。 证明：由题设，运算*在G上是封闭的。

对任意的a,b,c?G，有

?1?R?1，故R?1也是自反的。

?a*b?*c??a?b?2?*c?a?b?2?c?2?a?b?c?4

a*?b*c??a*?b?c?2??a?b?c?2?2?a?b?c?4

则a*?b*c???a*b?*c，即运算*是可结合的。

对任意的a,b?G，有

a*b?a?b?2?b?a?2?b*a

所以运算*是可交换的。

? 2?G，对任意的a?G，有

2*a?a*2?a?2?2?a

所以2是关于运算*的幺元。

对任意的a?G，?4?a?G，有

a*?4?a???4?a?*a?a?4?a?2?2

所以关于运算*，元素a的逆元是4?a。 综上，G , *是交换群。

36

29. (15分) 设L , ? , ?是一个格，a , b?L，且a?b，令

S??x?L a?x?b?

其中?是格L中的偏序关系，证明：S , ? , ?是L , ? , ?的子格。 证明：对任意的x,y?S，则有a?x?b , a?y?b，从而有

a?a?x?y?b?b , a?a?x?y?b?b

即

a?x?y?b , a?x?y?b

因此x?y , x?y?L，故运算? , ?在S上是封闭的，所以S , ? , ?是L , ? , ?的子格。

30. 证明在格L , ? , ?中，?是格L中的偏序关系，a , b , c?L，若a?b?c，则有

?a?b???b?c???a?b???a?c?。

证明：因为a?b?c，所以

a?b?a，b?c?b，a?b?b，a?c?c

因此

?a?b???b?c??a?b?b，?a?b???a?c??b?c?b

故

?a?b???b?c???a?b???a?c?

31. (15分) 假设一家化工厂要将多种化学产品利用铁路从精炼厂运到炼油厂，但是根据EPA(美国环保署)的规定，这些化学产品不能全部都装在同一节车厢里运输，因为如果它们混和起来，就会产生剧烈反应，从而引发事故，为了使费用最低，厂长希望使用尽可能少的车厢，问最少使用多少车厢？其中共有六种化学产品，P1不能与P2、P4在同节车厢里运输，P2不能与P3或P3或P5一起运输，P3不能与P4一起运输，P5不能与P6一起运输。 解：在平面上画六个顶点分别表示六

兰6红5 种化学产

兰2 品，如果两种化学产品不能在一节车则在这两种产品所对应的顶点之间连而得到一个无向图，现对该图的顶点

37 厢中运输，一条边，从

红1 白3

着色，如图

兰4

所示，用了三种颜色，所以最少用三节车厢，第一节车厢装P2、P4和P6，第二节车厢装P3，第三节车厢装P1和P5。

32．(10分) 用推理规则证明：A??B?C? , D?E?A , D?E?B?C 证明：(1) A??B?C? P (2) D?E?A P (3) D?E?B?C T(1)(2)I (4) D?E P (5) B?C T(3)(4)I

33．(10分) 设R是非空集合A上自反的二元关系，证明：R?1也是自反的。 证明：因为R是自反的，所以IA?R，则IA

34. (20分) 设G是整数加群，在G上定义：a*b?a?b?2，证明：G , *是交换群。 证明：由题设，运算*在G上是封闭的。

对任意的a,b,c?G，有

?1?R?1，故R?1也是自反的。

?a*b?*c??a?b?2?*c?a?b?2?c?2?a?b?c?4

a*?b*c??a*?b?c?2??a?b?c?2?2?a?b?c?4

则a*?b*c???a*b?*c，即运算*是可结合的。

对任意的a,b?G，有

a*b?a?b?2?b?a?2?b*a

所以运算*是可交换的。

? 2?G，对任意的a?G，有

2*a?a*2?a?2?2?a

所以2是关于运算*的幺元。

对任意的a?G，?4?a?G，有

a*?4?a???4?a?*a?a?4?a?2?2

38

所以关于运算*，元素a的逆元是4?a。 综上，G , *是交换群。

35. (15分) 设L , ? , ?是一个格，a , b?L，且a?b，令

S??x?L a?x?b?

其中?是格L中的偏序关系，证明：S , ? , ?是L , ? , ?的子格。 证明：对任意的x,y?S，则有a?x?b , a?y?b，从而有

a?a?x?y?b?b , a?a?x?y?b?b

即

a?x?y?b , a?x?y?b

因此x?y , x?y?L，故运算? , ?在S上是封闭的，所以S , ? , ?是L , ? , ?的子格。

36. 证明在格L , ? , ?中，?是格L中的偏序关系，a , b , c?L，若a?b?c，则有

?a?b???b?c???a?b???a?c?。

证明：因为a?b?c，所以

a?b?a，b?c?b，a?b?b，a?c?c

因此

?a?b???b?c??a?b?b，?a?b???a?c??b?c?b

故

?a?b???b?c???a?b???a?c?

37. (15分) 假设一家化工厂要将多种化学产品利用铁路从精炼厂运到炼油厂，但是根据EPA(美国环保署)的规定，这些化学产品不能全部都装在同一节车厢里运输，因为如果它们混和起来，就会产生剧烈反应，从而引发事故，为了使费用最低，厂长希望使用尽可能少的车厢，问最少使用多少车厢？其中共有六种化学产品，P1不能与P2、P4在同节车厢里运输，P2不能与P3或P3或P5一起运输，P3不能与P4一起运输，P5不能与P6一起运输。

39

解：在平面上画六个顶点分别表示六品，如果两种化学产品不能在一节车则在这两种产品所对应的顶点之间连而得到一个无向图，现对该图的顶点所示，用了三种颜色，所以最少用三一节车厢装P2、P4和P6，第二节车厢节车厢装P1和P5。

兰4 红1 白3

兰6红5 兰2 种化学产厢中运输，一条边，从着色，如图节车厢，第装P3，第三

38．(10分)设?是从群G1 , *到群G2 , ?的同态映射，e1，e2分别是群G1 , *与G2 , ?的幺元，令

H??x?G1 ??x??e2?

证明：H , *是群G1 , *的子群。

证明：显然H?G1，由于??e1??e2，所以e1?H，因此H??。

对任意的x，y?H，则有

??x??e2，??y??e2

故

??x*y?1????x????y?1??e2????y???1?e2?1?e2

所以x*y?1?H，由子群判定定理，H , *是群G1 , *的子群。

39. (14分)设G,*是群，H是G的子群，在G上定义二元关系R如下：

对任意的a,b?G，a,b?R当且仅当a?1*b?H

证明：(1) R是G上的等价关系；

(2) 对任意的a?G，?a?R?aH。

证明：(1) 对任意的a?G，因为H是G的子群，所以e?a?1*a?H，有a,a?R，所以R是自反的。 对任意的a,b?R，则有a?1*b?H，因为H是G的子群，所以

?a有b,a?R，所以R是对称的。

?1*b??1?b?1*a?H

对任意的a,b，b,c?R，则有a?1*b?H，b?1*c?H，因为H是G的子群，所以

40

本文来源：https://www.bwwdw.com/article/u3s3.html