2021-04离散数学自考

1、2021-04 离散数学自考全国 2021年 4月高等教育自学考试离散数学试题 课程代码： 02324一、单项选择题 (本大题共 15小题，每题 1 分，共 15分) 在每题列出的四个选 项中只有一个选项符合题目要求的。请将其代码填写在题后的括号内。错选、多项选择或未选均无 分。 1. 以下不是平面图的是 ()2. 无向图 G 中有 16 条边，且每个结点的度数均为2，那么结点数是 ( ) A.8 B.16 C.4D.323. 如以下图所示的有界格中，元素 b 的补元是 ( ) A.a B.0 C.c D.d4. 设 G ,* 是群，且 |G|>1 ，那么以下命题不成立的是 ( ) A.

2、G 中有幺元 B.G 中有 零元C.G 中任一元素有逆元D.G 中除了幺元外无其他幂等元5. 设 Z 是整数集合，那么下面定义的二元运算不能使 Z 与 构成代数系统的是 ( ) A.i j=|i-j|,? i,j Z B.i j=i j -j 2 , ? i,j Z C.i j=i/j, ? i,j Z D.i j=i2+j2+1, ? i,j Z6. 设A是非空集合，P(A)是A的幂集，Q是集合交运算，那么代数系统P(A), n> 的幺元是(A.P(A) B. 0 CA D.|7. 设N为自然数集(含0)，函数F : N f N X N,F(n)=是()A. 满射，不是入射 B. 入射

3、，不是满射 C. 双射D. 不是入射，不是满射8. 设 A=a,b,c ，那么以下是集合 A 的划分的是 ( )A.b,c,c B.a,b,a,c C.a,b,c D.a,b,c 9. 设集合X=0,1,2,3 ，R 是 X 上的二元关系， R=, ，那么 R 的关系矩阵 M R 是( )?1?1A ?0?0010010010 ?1?00? B. ?11?1?001011000 ?1? C. 0?1?0?1?0?1001101011 ?0? D. 1?0?1?0?0?1100011010 ?1? 1?0?10. 以下命题中，不正确的选项是()A.0 0 , 0 B. 0 0 , 0 C. 0

4、? 0 , 0 D. 0 ? 0 , 0 11. 设个体域是正整数集，那么以下公式中真值为真的公式是 ( )A. ( ? x)( ? y)(x y=0) B.(? x)( ? y)(x y=1) C.( ? x)( ? y)(x y=2)D.(? x)( ? y)( ? z)(x-y=z)12. 令 F(x):x 是金属， G(y):y 是液体， H(x,y):x 可以溶解在 y 中，那么命题“任何金属可以溶解在某种液体中可符号化为()A.(? x)(F(x) A(?y)(G(y) A H(x,y)B. (? x)( ? (x)F(x) -(G(y) -H(x,y) C.(? x)(F(x)

5、( ? y)(G(y) A H(x,y)D. (? x)(F(x) -(? y)(G(y) -H(x,y)13. 在个体域 D=a,b 中，与公式 (? x)A(x) 等价又不含量词的公式是 ( )A.A(a) A A(b) B.A(a) A(b) C.A(a) V A(b) DA(b) A(a) 14.以下句子是命题的是()A. 水开了吗 ? B.x>1.5C. 再过 5000 年，地球上就没水了。 D. 我正在说谎A.110 ，111，100 B.110 ，101， 011 C. 所有指派 D. 无二、填空题 (本大题共 20个空，每空 1分，共 20 分)16. 有向图D如下：D的

6、邻接矩阵A=(aij ) 3 x 3,贝V a 1仁,a32=。17. 一个连通平面图 G 有 10 条边， G 中度为 1 的顶点有 2 个，其余是度为 6 的顶点，贝 G 中共有 _个顶点， 个面。18. 设B, A , V，0, 1是布尔代数，对任意的a B,有aV a ' =,a A a ' =。19.设G , *是群，假设G中存在一个元素a ,使得G中任意元素都可由 a 的幂生成，贝称该群是 ，元素 a 称为该群的 。 20. 设X=1,2,3 上的关系 R 的关系图如下，从关系图可知 R 具有， 和传递性等性质。21. 设A=2,3,6,12, W是A上的整除关系，

7、那么偏序集A ,<的最大元是，极小元是 。22. 设A=0 , 0 ,B=0,1,所有从 A到B的双射函数是f1=,f2= 。23. 谓词公式(？x)( ? y) (P(x,y) V R(y) -Q(y)，那么其约束变元是 ，自由变元是 。24. 合取范式具有形式 A 1 A A 2 A , A A n (n > 1),其中 A 1 , A 2 , , , A n是由及其 所组成的析取式。25. 设命题 P 为“明天上午 8 点下雨， Q 为“明天上午 8 点下雪， R 为“我去学校，那么“如果明天上午 8 点不下雨且不下雪那么我去学校可表示为公式 ；而“只有当明天上午 8 点不下

8、雪并且不下雨时我才去学校可表示为公式 。三、计算题 (本大题共 6小题，共 30分)26. (5分) 一棵树有 2个 4度结点， 3个3度结点，其余结点是叶子，求该树的叶子数。27. (6分)设A=a,b,c,d,G= 是交换群,a是G的单位元。G的运算表如下：求 x 1,x 2345628. (4分) 设集合 A=1,3,5,7,9,11,13,15,A 上的一个划分S=1,15,3,9,11,13,5,7。 试求由 S 导出的 A 上的等价关系 R 。29. 4 分 设 A=a,b,c,d,R=,试用关系图表示 R 及 R 的传递闭包30. (5 分)求公式(？ x) ? (F(x) f(

9、 ? y)G(,xy,z) -( ? z)H(x,y,z)的前束范式31. 6分作出命题公式p f q V r q的真值表，并写出其主析取范式。四、证明题 本大题共 3小题，共 20分32. 8分证明 A f Bf C,C A D f E, n F f DAn E| -Af Bf F成立。33. 6分 证明：如果一个有向图 G 是弱连通图且是欧拉图，那么 G 是强连通图。34. 6分设G,*是群，a G , N=ah-1a|h G,证明N , *是G ,*的子群。五、应用题 本大题共 2小题，共 15分35. 6分 某发电厂 a 要向 b,c,d,e 四个地点送电，发电厂可以和 b,c,d 直接架接电线，地点 e 可以和 b 与 d 直接架设电线，其他由于地理原因无法直接架设电线，在a,b,c,d 和e之间架设电线时不能有回路存在，否