离散数学2009-2010第一学期期末试卷及参考答案

承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。 徐州师范大学2009—2010学年第一学期考试卷

专业 班级 学号 学生签名： 试卷编号： （ A ）卷

离散数学 课程 课程类别：必修 考试日期： 月 日 开卷(范围：可带含课程内容的手写的不超过A4大小的纸一张） 题号 一 二 三 四 五 六 七 八 九 题分 得分 总分 累分人签100 名 注意事项：1、本试卷共 8 页（其中试题4页），总分 100 分，考试时间 120 分钟。

2、所有答案必须填在答题纸上，写在试卷上无效； 3、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。

一、单项选择题 （2分×10=20分）

1．下列语句是命题的有[ ]。

A. x2?2y?1 ；

B. 2010年的国庆节是晴天； C. 青年学生多么朝气蓬勃呀！ D. 学生不准吸烟!

2．若一个代数系统是独异点（含幺半群），则以下选项中一定满足的是[ ]。 A. 封闭性，且有零元; B. 结合律，且有幺元； C. 交换性，且有幺元; D. 结合律，且每个元素有逆元. 3．Z是整数集合，下列函数都是Z→Z的映射，则[ ]是单射而非满射函数。

A．? (x) =0 B．? (x) =x2 C．? (x) =2x D．? (x) =x 4. 与命题p ? (p?q)等值的公式是 [ ]。

A. p； B. q； C. p?q； D. p?q.

1

5. 设M={a,b,c}，M上的等价关系R={,,,,}确定的集合M的划分是[ ]。

A.{{a},{b},{c}} B.{{a,c},{b,c}} C.{{a,c},{b}} D.{{a},{b,c}} 6. 设D：全总个体域，F(x)：x是花，M(x) ：x是人，H(x,y)：x喜欢y ，则命题“每个人都喜欢某种花”的逻辑符号化为[ ]。 A. ?x(M(x)??y(F(y)?H(x,y))； B. ?x(M(x)??y(F(y)?H(x,y))； C. ?x(M(x)??y(F(y)?H(x,y))； D. ?x(M(x)??y(F(y)?H(x,y)). 7. 下列图中，不是哈密顿图的为[ ]。

A B C D

8. 下列四组数据中，能作为某个4阶无向简单图的度序列的为[ ]。 A. 1,2,3,4 ； B. 2,2,2,3； C. 1,1,2,3； D. 1,1,1,3. 9. 3阶无向完全图（K3）有[ ]个非同构的生成子图。

A. 5 B. 4 C. 3 D. 2 10. 下列选项中与A∪B=A等价的是____________。

A．A∩B=A B．B ?A C．A∪B=B D．A－B＝Φ

二、填空题（2分×10=20分）

1. 设集合A＝{a, b}，B={a, c}，则 A?(B－A)=_____ 。(?为对称差) 2. 设p：我努力学习，q：我取得好成绩，命题“除非我努力学习，否则我不能取

得好成绩。”的符号化形式为 。

3. 设解释I如下，个体域D={1,2}，F(1,1)=(2,2)=0，F(1,2)=F(2,1)=1，在解释I下， ?xF(x,2) 的真值为 。

2

4. 谓词公式 ?xF(x)∧?xG(x) 的前束范式为 。 5. 设Z6={0,1,2,3,4,5}，?为模6加法，即?x,y? Z6 ，x?y=(x+y)mod 6，若有方程：1 ? x ? 3=2，则x=_________________。

6. 等价关系满足自反性、对称性和 三个性质。 7. 设函数f(x)=2x，g(x)= x2+1, 则fog =____________________。

8. 无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为 。 9. 设A为集合，且|A|=3，则A上最多可定义 个不同的二元关系。 10. 设A为非空有限集，P(A)为幂集，则代数系统?P(A),??中的幺元为 _____ 。

三、综合题（第1、2题每题10分，其余每题8分，共60分）

1. 构造下面推理的证明：（10分）

前提：p→(q?r)，?s→?r，p??s； 结论：q.

2. 求公式(p→q) ?(q→r)的主析取范式、主合取范式、成真赋值。（10分）

3. 设集合A={a,b,c,d}，R是A上的二元关系，R={ , , , }；(8分) （1）画出R的关系图； （2）求R2；

（3）求出R的自反闭包r(R)、对称闭包s(R)。

4. 设S={1 , 2 , 3 , 4, 6 , 8 , 12}，“?”为S上的整除关系。（8分） 问：（1）偏序集?S　,??的Hass图如何？

（2）偏序集?S　,??的极小元、最小元、极大元、最大元是什么? （3）在偏序集?S　,??中，B={4,6}的上确界、下确界是什么？

3

5. 已知某有向图G的邻接矩阵如下：（8分）

v1?1?v20A??v3?0?v4?0201011010??0? 1??0?

问：（1）画出图G。

（2）试用邻接矩阵求G中长度小于等于2的通路的条数，其中回路有几条？

（3）该图是为强连通图还是弱连通图？

n6. 设集合G?{3n?Z}（其中：?是普通乘法，Z是整数集），问集合G和乘法运算

?构成何种代数系统（半群、独异点还是群）？ 说明理由。（8分）

7. 图G是一个简单的连通平面图，顶点数为8，其无限面的次数为5，其余面都为三角形（次数为3），计算平面图G的边数和面数。（8分）

4

受弊作 因 和 籍 学 除 开 被 将 者考： 人他签名代生或学考 代 人 他 请 道 知还。 ，果 性后 重切严一号的的学 弊起 作引 、此 纪由 违担 试承 考愿 道， 知位 ，学级律士班纪学 场予 考授 守不 遵将 格处分 严上 将以 我及 ：过 诺记业承到专徐州师范大学2009—2010学年第一学期考试卷

答题纸（参考答案）

离散数学 课程 课程类别：必修

题号 一 二 三 四 五 六 七 八 九 十 总分 计分人题分 20 20 60 100 签名 得分 一、单项选择题 (每小题2分，共20分)

题号 1 2 3 4 5 6 7 8 9 10 答案 B B C A D C A D B B

二、填空题(每小题2分，共20分)

1 {a, b, c} 2 ?p→?q或q→p 3. 1或 真 4. ?x?y (F(x)∧G(y)) 5. 4 6. 传递性 7． 2（x2+1） 8. 偶数 9. 29

或 512 10. ?

三、综合题（第1、2题10分，第3-7题每题8分，共60分）

1．

第1小题答案： 得分 评阅人 证明：① p??s 前提引入 ② p ①化简 ③ p→(q?r) 前提引入 ④ q?r ②③假言推理 注意：答案与题号必须对应 ⑤ ?s→?r 前提引入 ⑥ ?s ①化简 ⑦ ?r ⑤⑥假言推理 ⑧ q ④⑦析取三段论 5

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