函授《离散数学》练习题

《离散数学》练习题一

一、单项选择题

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?。

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

1

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(?)))是 。

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

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

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

Ⅱ． ?p??q?r?????p?q???p?r??

3

Ⅲ． ?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人同时参加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的充分必要条件是 。

4

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的主析取范式中，含有（ ）个极小项。

19. 设集合A??a , b , c , d , e , f , g?，A上有一个划分????a , b? , ?c , d , e? , ?f , g??，那么?所对应的

等价关系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?的主析取范式是 。(写出一般

表示形式即可)

28．设集合A??a , b , c , d ?，R是A上的二元关系，且R??a , b , b , a , b , c , c , d , a , c?，则R的传递闭包t?R?? 。 29．设集合A??2 , 3 , 4 , 6 , 8 , 12 ?，R是A上的整除关系，则R的关系矩阵

MR? ，哈斯图为 。 30. 一个连通平面图有9个顶点，它们的度数分别为：2，2，2，3，3，3，4，4，5，则该图

5

共有 个面。

31. 集合A??a , b , c?上可以定义的二元运算的个数是 。

三、解答题

1.求带权值为 1, 3, 5, 5, 8, 12, 14, 19的最优二叉树。(只要最终结果，不要求中间过程)(8分)

2．求

的最小生成树。(只要最终结果，不要求中间过程。) (8分)

3.设G是平面图，有n个顶点，m条边，f个面，k个连通分支，证明：n?m?f?k?1 (10分)

4.化简下列布尔表达式。 (1) ?a?b??a?b?c??b?c? (2) a?b?c?a?b?c (8分)

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

?????????a?b???b?c???a?b???a?c?。 (8分)

6

6. 设A??a , b , c?，P?A?是A的幂集，?是集合的对称差运算，已知P?A? , ? 是群，在群P?A? , ? 中，求：(1) 关于运算?的幺元；(2) P?A?中每个元素的逆元；(3) 求元素x，使得?a??x??b?。 (9分)

7. 设?a , b , c , d? , *是半群，其运算表如下 (8分) 证明：?a , b , c , d? , *是循环群。

* a b a a b b b c c d d d c d a b c d

c d a b a c 8. 设R是集合A上的二元关系，若R是自反的和传递的，则R?R?R。 (8分)

7

9. 设S75,D是格，其中S75是75的的所有正因数的集合，D是S75上的整除关系，求S75中每个元素的余元素。 (8分)

10. 证明等价式：?P?Q???R?Q???P?R??Q。 (6分)

11.用推理规则证明：C?D , ?C?D???P , ?P??A??B? , ?A??B???R?S??R?S。

12．设R是非空集合A上的二元关系，令??IA?R?R?1，证明：?具有自反性，对称性。

13. 设G , *是独异点，并且对于G中的每一个元素x，都有x*x?e，其中e是幺元，证明：G , *是一个阿贝尔群。

14. 证明：循环群G??a?是交换群。

8

15. 设L , ? , ?是一个格，a , b?L，且a?b，令 S??x?L a?x?b? 其中?是格L中的偏序关系，证明：S , ? , ?是L , ? , ?的子格。

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

17. 给定树叶的权为1，4，9，16，25，36，49，64，81，100，试构造一棵最优二叉杩。

18. 证明：若无向图G是不连通的，则其补图G是连通的。

19．(10分)求带权1、2、3、4、5、6、7、8、9、10的最优二叉树。

c?a，则有

9

20. (10分) 设集合A??a , b , c?，R是A上的二元关系，R?a , a , a , b , a , c , c , b， 试求：(1) P?A?； (2) R的关系图与关系矩阵MR； (3) r?R?、s?R?、t?R?。

21．证明等价式：?P?Q?A?C???A?P?Q?C???A??P?Q???C。

22. 证明：树是一个偶图。

23. 设G , *是群，对任意的a?G，令H?x?G x*a?a*x，证明：H是G的子群。

24. 设R为实数集，f:R?R?R?R，对任意的x , y?R?R，定义：f证明：f是双射。

10

?????x , y??x?y,x?y

25. 设B,?,*是含幺环,且*满足等幂律,在B上定义运算+,·,ˉ如下:

a?b?a?b??a*b?, a?b?a*b, a?a?1

证明:B , ? , ? , , 0 , 1是一个布尔代数，其中0和1分别是关于运算?和*的幺元。

26．用推理规则证明： A??B?C? , D?E?A , D?E?B?C (10分)

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

28．设G是整数加群，在G上定义：a*b?a?b?2，证明：G , *是交换群。(20分)

29．设L , ? , ?是一个格，a , b?L，且a?b，令S??x?L a?x?b? 其中?是格L中的偏序关系，证明：S , ? , ?是L , ? , ?的子格。(15分)

11

30．给定树叶的权为1，4，9，16，25，36，49，64，81，100，试构造一棵最优二叉杩。(10分)

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

P1不能与P2、P4在同节车厢里运输，P2不能与P4一起运输，P3或P3或P5一起运输，P3不能与P5不能

与P6一起运输。(15分)

32．用推理规则证明： A??B?C? , D?E?A , D?E?B?C (10分)

33．设R是非空集合A上自反的二元关系，证明：R

12

?1也是自反的。(10分)

34．设G是整数加群，在G上定义：a*b?a?b?2，证明：G , *是交换群。(20分)

35．设L , ? , ?是一个格，a , b?L，且a?b，令S?x?L a?x?b 其中?是格L中的偏序关系，证明：S , ? , ?是L , ? , ?的子格。(15分)

36．给定树叶的权为1，4，9，16，25，36，49，64，81，100，试构造一棵最优二叉杩。(10分)

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

??P1不能与P2、P4在同节车厢里运输，P2不能与P4一起运输，P3或P3或P5一起运输，P3不能与P5不能

与P6一起运输。(15分)

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

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

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

13

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。

40．(10分)用推理规则证明：P , P??Q??R?S???Q?S。

41. (10分)设G?V , E是n阶简单无向图，n是大于2的奇数，如果G中有k个奇数度的顶点，那么G的补图G中奇数度的顶点也是k个。

42. (12分)设f是从格L1 , ?1到格L2 , ?2的满同态映射，证明：若L1 , ?1是有界格，则

格L2 , ?2也是有界格。

43．设在一次国际会议上有7个人，各懂的语言如下：

a：英语 b：英语和西班牙语 c：英语、汉语和俄语

d：日语和西班牙语 e：德语和汉语 f：法语、日语和俄语 g：法语和德语

(1) 用无向简单图描述以上事实；

(2) 他们中间是否任何两个人可对话(必要时通过别人作翻译)。

44．设S30 , D是格，其中S30是30的所有正因数的集合，D是S30上的整除关系，则 (1) 求每个元素的余元素；

(2) S30 , D是否为有余格，是否为分配格？并说明理由。

14

《离散数学》练习题二

一、填空题

1．幂集P(P(P(?)))是 。 2．集合A??a , b?上可以定义的二元运算的个数是 。

3．集合A??a , b , c?上的关系R?? a , b , c , c , b , c ?的传递闭包t?R?? 。 4．一个连通平面图有8个顶点，它们的度数分别为：2，2，3，3，3，4，4，5，则该图共有 个面。

R是A上的整除关系，5．设集合A??3 , 4 , 6 , 8 , 12 , 36?，则R的关系矩阵MR? ，哈斯图为 。

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. 任何简单图中顶点的度数之和等于边数的 倍。

15

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?? 。

17 第 页（共29页）

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

25. 若连通简单平面图G有6个顶点，3个面，则G有 条边。 26. 设L , ?是格，其中L??1 , 2 , 3 , 4 , 6 , 8 , 12 , 24?，?是整除关系，则3的补元是 ，6的补元是 。

B是集合，27. 设A、若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.

18

??,??????????????

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??

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. 交换律 分配律

5．设I是整数集合，下列集合中 关于数的加法和乘法构成整环。

A．?2n n?I? B．?2n?1 n?I? C．?n n?0 , n?I? D．I

6．如下的哈斯图所示偏序集为格的是 。

B. 消去律

C. 幂等律 D.

Ａ Ｂ Ｃ Ｄ

19

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

B．xx是有理数,x2?25 C

D．xx是有理数,x?5

8．下列公式中， 是析取范式。 A. ??p?q?

B. ??p?q?

D. p?q

．

．

?1 , 2 , 3 , 4 ?

???xx是正整数,x?5?

??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.逆

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

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

A. 每一个元素有一个余元 B. 每一个元素至少有两个余元

C. 每一个元素无余元 D. 每一个元素仅有一个余元

20

??

9．设R是非空集合A上的二元关系，若R是自反的，证明：t?R?是自反的。

10. 设R为实数集，?：R?R?R，对任意的x,y?R?R，令??x,y??x?y，证明：?是满射，并说明?不是单射。

11. 证明：任一序集都是格。

12. 求带权1，2，3，4，5，6，7，8，9，10的最优二叉树。

13. 设H , *和K , *都是群G , *的子群，令

HK??h*k h?H , k?K?，KH??k*h k?K , h?H?

证明HK , *是G , *的子群的充要条件是HK?KH。

14. 设R为实数集，?：R?R?R，对任意的x,y?R?R，令??x,y??x?y，证明?是满射，并说明?不是单射。

15．设A、B是命题公式，试用两种方法分别证明等价式：??A?B??A??B。

16. 证明：三个元素以上的链不是有余格。

17. 求带权1，2，3，4，5，6，7，8，9，10的最优二叉树。

26

18．设R是非空集合A上的二元关系，若R是自反的，证明：s?R?是自反的。

19. 设A?m?n2 m , n?I ，其中I是整数集合，证明：A , ? , ? 是整环，其中运算“+”和“〃 ”是关于数的普通加法和乘法。

20．(10分)用推理规则证明：A?B?C?D，D?E?F?A?F。

21. (20分) 设B,?,*是含幺环,且*满足等幂律,在B上定义运算+,〃,?如下:

??a?b?a?b??a*b?, a?b?a*b, a?a?1

证明:B , ? , ? , , 0 , 1是一个布尔代数，其中0和1分别是关于运算?和*的幺元。

22. (15分)证明：在Kn?n?5?中任意删去n?3条边后所得到的图是哈密尔顿图。 23．(5分) Gladbrook饲料公司有7个谷物箱，要通过谷物管道将它们连接起来，以使谷物能从任意一个箱子转移到其它箱子，为了使建造费用最少，希望建造尽可能少的管道，在两个箱子之间建造管道的费用(以10万美元计)由下表给出，其中“-”表示不能建造管道，应该怎样建造管道才能使费用最少。

24．(15分)给定群I6 , ?6，其中

3 4 5 6 7 - 7 - - 4 - 2 1 1 - 2 - - 2 - 2 - 5 2 - 3 1 1 1 - 2 4 3 - 4 6 5 2 6 - 7 3 I6??0 , 1 , 2 , 3 , 4 , 5?，?6是I6上的模6加法运算，试求： (1) I6的所有生成元； (2) I6的所有子群； (3) 每个子群的所有右陪集。

27

25. (5

分)设集合A??a , b , c?，R是A上的二元关系，

R??a , a , a , b , a , c , c , b?，试求R的关系图与关系矩阵MR。

分)设集合A??a , b , c?，R是A上的二元关系，

26. (5

R??a , a , a , b , a , c , c , b?，试求R的关系图与关系矩阵MR。

27. (15分)给定群I15 , ?15，其中I15??0 , 1 , 2 , ? , 14?，?15是I15上的模15加法运算，试求：

(1) I15的所有生成元； (2) I15的所有子群； (3) 每个子群的所有右陪集。

28．(5分)试用克鲁斯卡尔算法求下列表格所确定的权图的最小支撑树。

v1 / 479 1463 2007 695 283 v2 479 / 966 1567 666 301 v3 1463 966 / 837 998 1267 v4 2007 1567 837 / 1213 1724 v5 695 666 998 1213 / 412 v6 283 301 1267 1724 412 / v1 v2 v3 v4 v5 v6 29．(15分)证明：如果G是一个具有奇数个顶点的偶图，则G不是哈密尔顿图。

30．(10分)用推理规则证明：?A?B，C??B?A??C

31．(20分) 设B , ? , ? , , 0 , 1是一个布尔代数，在B上定义运算*，×如下：

a*b?a?b?a?b，a?b?a?b

证明:B , * , ? 是含幺交换环。

28

29

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. 交换律 D. 分配律

20. 设R是非空集合A上的关系，则R的对称闭包s?R?= 。 A. R?R?1 B. IA?R C. R?IA D.

R?R?1

B. 消去律 C. 幂等律

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

A. ??????? B.

??,??????????????

21

C. ??,?????????????,???? D.

??,????????????

22．下面的二元关系中， 具有传递性。

A. 父子关系 B. 朋友关系 C. 集合的包含关系 D. 实数的不相等关系 23. 设Z是整数集，且设f:Z?Z?Z，对每一个a,b?Z?Z，有

f?a,b??a2b， 元素0的原象的集合为 。

A．??0??Z???Z??0?? B．Z??0?

C．?0??Z D．??0??Z???Z??0?? 24. 数的加法在下列集合中 上是封闭的。

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

??25. 设无向树T由3个3度顶点，2个2度顶点。其余顶点都是树叶，则T有 片树叶。

A. 3 B. 4 C. 5 D. 6 26. 设命题P，Q的真值是0，命题R，S的真值是1，则下列公式中真值为1的是 。

A. R?P B. Q?S C. P?S D.

Q?R

27．设M?? x f1(x)?0?，N?? x f2(x)?0?，则方程f1(x)?f2(x)?0的解集是 。

22

A．M?N B．M?N C．M?N D．M?N

28．设R是非空集合A上的关系，则R的对称闭包s?R?= 。 A. IA?R B. R?IA C. R?R?1 D.

R?R?1

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

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

30. 给定下列序列，可构成无向简单图的顶点度数序列的是 。 A. ?1 , 1 , 2 , 2 , 3? B. ?1 , 1 , 2 , 2 , 2? C. ?0 , 1 , 3 , 3 , 3? D. ?1 , 3 , 4 , 4 , 5? 31. 设Z是整数集，且设f:Z?Z?Z，对每一个a,b?Z?Z，有

??f?a,b??a2b， 元素0的原象的集合为 。 A．??0??Z???Z??0?? B．Z??0?

C．?0??Z D．??0??Z???Z??0?? 32. 命题公式P??Q?P?为 。

A.重言式 B.可满足式 C.矛盾式 D.等价式 三、判断题

1．若A?B，则必有A?B?B。( )

2．一个不是自反的关系，一定是反自反的。( )

23

3. 凡陈述句都是命题。( ) 4．有限半群必存在等幂元。( )

5. 任何非平凡无向图中的奇数度顶点的个数是偶数。( )

6．设A，B，C，D均为非空的集合，已知A?B且C?D，则一定有

A?C?B?D。( )

7．一个不是自反的关系，一定是反自反的。( ) 8. “王兰和王英是姐妹”是复合命题。( )

9. 设L , ? , ? 是代数格，它所诱导的偏序格为L , ?，则对任意的a,b?L，

a?b?b当且仅当a?b?a。( )

10．任何非平凡树T都至少有两片树叶。( )

11．设A,?是偏序集，B是A的非空子集，若B有上界，则B必有最小上界。( )

12. 在有界分配格中，一个元素若有补元，则补元一定是唯一的。( ) 13. “王兰和王英是姐妹”是复合命题。( ) 14．若半群存在左幺元，则左幺元是唯一的。( )

15. 具有两个或多个元素的格中不存在以自身为补元的元素。( ) 16. 两个无向图同构的充分必要条件是它们的顶点个数与边的个数分别相等。( )

四、解答题

??10??10???10???10??1．(10分) 设G????01?? , ??0?1?? , ??0?1?? , ??01???，G上的二元运算为矩

??????????阵的乘法运算，求 (1) G , *的运算表； (2) G , *的所有子群；

24

2. (14分) 设G , *是一个群，定义集合G上的一个关系R如下：

R? x , y x , y?G , ?a?G , ?y?a*x*a?1

??证明：R是集合G上的一个等价关系。

3. (12分)设f是从格L1 , ?1到格L2 , ?2的满同态映射，证明：若L1 , ?1是

有界格，则格L2 , ?2也是有界格。 4.

(10

分

)

试

用

推

理

规

则

证

明

：

??P?Q????R?S? ， ?Q?P???R ，R?P?Q

5. (10分) 设G是连通简单图，其中每个顶点的度数都是偶数，则对于任一顶点v，图G??v?的连通分支数小于等于v的度数的一半。

6．设S45 , D是格，其中S45是45的所有正因数的集合，D是S45上的整除关系，则

(1) 求每个元素的余元素；

(2) S45 , D是否为有余格，是否为分配格？并说明理由。

7．洛杉矶地区有7家汽车旅游公司，在一天中每家公司最多参观下列景点中的

三个不同景点，这些景点是好莱坞、贝弗利山、迪斯尼乐园和通用电影制片厂，同一天中，参观一个景点的旅游公司不能超过一个，第一家旅游公司只参观好莱坞，第二家公司只参观好莱坞和迪斯尼乐园，第三家公司只参观通用电影制片厂，第四家只参观迪斯尼乐园和通用电影制片厂，第五家只参观好莱坞和贝弗利山，第六家只参观贝弗利山和通用电影制片厂，第七家只参观迪斯尼乐园和贝弗利山。请问这些游览可以只安排在星期一、星期三和星期五吗？

8．设A、B是命题公式，试用两种方法分别证明等价式：??A?B??A??B。

25

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