2007.1离散数学试卷B

： 名 姓 线 ： 号 学 订 ： 业 专 装 ：院 学广东工业大学考试试卷 ( B ) 课程名称: 离散数学 考试时间: 2007 年 1 月 26 日 (第 21 周 星期五 ) 题 号 一 二 三 四 五 六 七 八 九 十 总分 评卷得分 评卷签名 复核得分 复核签名 一、单项选择题(本大题共8小题，每小题2分，共16分) 1、下列语句中为命题的是 [ ] A、天气真暖和啊！ B、请别生气。 C、你还记得我吗！ D、我是老王。 2、设 P 表示“天下大雨”，Q 表示“他在室内运动”，将命题“如果天不下雨，他一定不会在室内运动”符号化为： [ ] A、P→Q B、P∧Q C、┐P→＞Q D、┐P∨Q 3、在自然数集N上，下列哪种运算是可结合的？ [ ] A a*b=a-b B a*b=max{a,b} C a*b=a+2b D a*b=|a-b| 4、设A={1,2,3} B={a, b, c}下列关系中为映射的是 [ ] A、{<1,a><2,b><3,a>} B、{<1,a><2,c><1,b>} C、{<1,c><3,a>} D、{<1,a><2,a><2,c>} 5、集合A={1,2,…,10}上的关系R={|x+y=10,x,y?A}，则R 的性质为[ ] A 自反的 B 对称的 C传递的，对称的 D反自反的 6、一棵树有 2 个2 次结点，1个 3 次结点，3 个4 次结点，则 1 次结点数目是： [ ] A、5 B、7 C、9 D、8 广东工业大学试卷用纸，共 6 页，第 1 页

7、任何图中必定有偶数个： [ ] A、度数为偶数的结点 B、入度为偶数的结点 C、度数为奇数的结点 D、出度为奇数的结点 8、在右图描述的偏序集中，{b, c, d}的上确界是 [ ] A、{a, b} B、{b} C、{a} D、{f} 二、填空题(本大题共10小题，每空3分，共24分) 9、 两个重言式的析取是_____________ 式， 一个重言式和一个永假式的合取式是_____________ 式。 10、公式 ┐(P∨Q) ←→(P∧Q) 的主析取范式是_____________。 第8题图 11、令A = {?}，则A的子集是_____________ 12、(?x)(P(x)∨( y)R(y))→Q(x))中?x)的辖域是_____________。 13、在代数系统 中，Z是整数集合，+运算是普通加法，则(?2)?3 = _____________。 14、设 A={a, b}，则 P (A)= _____________ 15、已知 Π={{a}{b, c}}是A={a, b, c}的一个划分，由 Π决定的 A上的一个等价关系是_____________。 16、已知群 G的阶是 8，G只能有_____________阶非平凡子群。 三、 简答及证明(本大题共6小题，每小题10分，共60分) 17、(10分) 设A，B，C为集合，证明A∩(B－C)=(A－C)∩(B－C) 18、(10分)已知带权图G，如题图所示．试求图G的最小生成树，并计算该生成树 ? 的权。 19、(10分)集合Ａ＝｛111、122、341、456、795、893｝， 1 9 2 当a、b∈A，且a、b中至少有一个数字相同时， ? 8 ? 7 ? (a，b) ∈R， 5 6 试画出R的关系图，并写出R的所有最大相容类。 4 10 ? 3 20、(10分)设R是实数集，在R上定义二元运算*， ?x, y ?R – {?12}，定义 x*y=x+y+2xy 判断是否为可交换群，并给出证明。 21、(10分)作出权值为7，8，9，12，16的最优树，并求改最优树的权值 22、(10分)有120位学生参加考试，这次考试有A、B和C三道题。考试结果如下：有12位学生3道题都做对了，20位学生做对了A题和B题，16位学生做对了A和C，28位做对了B和C，做对A题的学生有48位学生，做对B题的56位学生，还有16位学生一道题也没做对。试求做对C题的学生有多少位？ ? 第18题图 第六题图 广东工业大学试卷用纸，共 6 页，第 2 页

课程名称:

离散数学B卷标准答案

考试时间: 第 21 周星期五 ( 2007年1月 26日)

一、单项选择题(本大题共8小题，每小题2分，共16分)

1 D 二、填空题(本大题共8小题，每空3分，共24分)

1.重言、永假 2. (P ? ￢Q) ? (￢P? Q) 3. ?,{?} 4. P(x) ? (?y)R(y)

5. 6 6. {?,{a}, {b}, {a, b}} 7. {, , , , } 8. 4

三、(8分)

解：设做对A题的学生构成集合A，做对B题的学生构成集合B ，做对C题的学生构成 集合C，由题意有：

︱A︱＝48；︱B︱＝56； 并可求得：

|A∩B∩C︱＝12； 1分 ︱A∩B︱＝20； 1分 ︱A∩C︱＝16， 1分 ︱B∩C︱＝28， 1分 ︱A∪B∪C︱＝16； 1分 ︱A∪B∪C︱＝120－16＝104； 1分

由容斥原理可知：

︱A∪B∪C︱＝︱A︱＋︱B︱＋︱C︱－︱A∩B︱－︱A∩C︱

－︱B∩C︱＋︱A∩B∩C︱ 1分 故：

︱C︱＝20＋16＋28＋104－12－48－56＝52 1分

四、(10分)

证明：① n阶无向简单图的顶点度数只可能为0, 1, 2, ??, n – 1

中的某个值。 2分

②当存在度数为0的顶点时，不可能存在度数为n – 1的顶点，顶点度数 只可能为0, 1, 2, ??, n – 2，共n – 1种可能； 1分 因为有n个顶点，有n – 1种情况，所以由鸽洞定理得，必有2个或2个 以上的顶点度数相同。 2分 ③当存在度数为n – 1的顶点时，不可能存在度数为0的顶点，顶点度数 只可能为1, 2, ??, n – 1，共n – 1种可能； 1分

广东工业大学试卷用纸，共 6 页，第 3 页

2 C 3 B 4 A 5 A 6 C 7 C 8 B 因为有n个顶点，有n – 1种情况，所以由鸽洞定理得，必有2个或2个 以上的顶点度数相同。 2分 综上所述，在无相简单途中，必至少有2个顶点的度数相对。 2分

五、(10分)

1) 5分

111 122 341 893 456 795

2) 由关系图可知最大相容类：

{111, 122, 341} 1分 {341, 456} 1分 {341, 893} 1分 {456, 893} 1分 {795, 893} 1分 六、(12分)

解：① 封闭性。 3分

∵对于?x, y? R – {?12}，x*y=x+y+2xy?R，现证明x+y+2xy ≠??1?y12，反证法。

假设x+y+2xy =?12，则x?112??，与x ? R – {?}矛盾， 21?2y2∴二元运算*在R上是封闭的。

② 可结合性对于?a, b, c?R， 2分

(a * b) * c = (a + b + 2ab) * c

= a + b + 2ab + c + 2ac + 2bc + 4abc

a * (b * c) = a * ( b + c + 2bc)

= a + b + c + 2bc + 2ab + 2ac + 4abc

∴二元运算*在R上满足结合律。

广东工业大学试卷用纸，共 6 页，第 4 页