离散数学（本）2016年3月份试题
参考解答
一、单项选择题（每小题3分，本题共15分） 1．B 2．C 3．D 4．A 5．B 二、填空题（每小题3分，本题共15分） 6．{1, 2, 3, 5} 7．{,
10．真（或T，或1）
三、逻辑公式翻译（每小题6分，本题共12分）
11．设P：小王来学校， Q：他会参加比赛． （2分） 则命题公式为： P ? Q． （6分）
12．设P：今天天晴， Q：昨天下雨． （2分）
则命题公式为：P∧Q． （6分） 四、判断说明题（每小题7分，本题共14分）
13．错误． （3分）
R不是等价关系，因R中不包含<2，2 >，故不满足自反性． （7分） 14．错误． （3分） 辖域为紧接与量词?之后的最小子公式P(x)． （7分） 五．计算题（每小题12分，本题共36分）
15．解：（1）A?B={ b}； （4分）
（2）A ? B={ a, c}； （8分） （3）A×B={, ,
图一
（3分）
?0?0?（2）邻接矩阵： ?1??0??10101?0100??1010? （6分）
?0101?0010??（3）v1，v2，v3，v4，v5结点的度数依次为2，1，3，2，2． （9分） （4）补图如图二所示：
31
（12分）
图二
17．解：用Kruskal算法求产生的最小生成树。步骤为： w(v2,v6) =1，选(v2,v6) w(v4,v5) =1，选(v4,v5) w(v1,v6) =2，选(v1,v6) w(v3,v5) =2，选(v3,v5)
w(v2,v3) =4，选(v2,v3) （6分） 最小生成树如图三所示： v1 6 ? ? v2
42 1 5
9 v6 ? ? v3
2 3 5
7
? ? v （9分）
1 4 v5
图三
最小生成树的权w(T)=1+1+2+2+4=10． （12分） 六、证明题（本题共8分） 18．证明：
（1）┐┐(P?Q) P （1分） （2）P?Q T（1）E （3分） （3）（Q?R） P （4分） （4）┐R P （5分） （5）┐Q T（3）（4）I （6分） （6）┐P T（2）（5）I （8分） 说明：
1．因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分． 2．另，可以用真值表验证．
离散数学（本）2016年1月份试题
一、单项选择题（每小题3分，本题共15分）
32
1．若集合A＝{1, 2, 3, 4}，则下列表述正确的是 ( )． A．{1, 2}?A B．{1, 2, 3 } ? A
C．{1, 2, 3 }?A D．{1, 2, 3}?A
2．已知无向图G 的结点度数之和为10，则G的边数为（ ）． A．10 B．20 C．30 D．5
3．无向图G是棵树，结点数为10，则G的边数是（ ）． A. 5 B. 10 C. 9 D. 12
4．设A（x）：x是人，B（x）：x是学生，则命题“有的人是学生”可符号化为（ ）． A．(?x)(A(x)∧B(x)) B．┐(?x)(A(x) →B(x)) C．(?x)(A(x)∧B(x)) D．┐(?x)(A(x)∧┐B(x))
5．下面的推理正确的是（ ）．
A．(1) （?x）（F（x）→G（x）） 前提引入 (2) F（y）→ G（y） ES（1）． B．(1) （?x）F（x）→G（x） 前提引入 (2) F（y）→G（y） US（1）． C．(1) （?x）F（x）→G（x） 前提引入
(2) F（y）→G（y） US（1）．
D．(1) （?x）(F（x）→G（x）） 前提引入 (2) F（y）→G（x） ES（1）．
二、填空题（每小题3分，本题共15分）
6．设A={1，2}，B={ a, b, c }，则A?B的元素个数为 ． 7．有n个结点的无向完全图的边数为 ．
8．设无向图G中存在欧拉路，则G的奇数度数的结点数为 ． 9．设G是有10个结点的连通图，边数为20，则可从G中删去 条边后使之变成树．
10．设个体域D＝{1, 2, 3, 4}，则谓词公式(?x)A(x)消去量词后的等值式为 ．
三、逻辑公式翻译（每小题6分，本题共12分） 11．将语句“小明是个学生．”翻译成命题公式．
12．将语句“他上午去教室上课，下午去体育馆参加比赛．”翻译成命题公式．
四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）
13．存在集合A与B，可以使得A?B与A?B同时成立． 14．完全图K4不是平面图．
五．计算题（每小题12分，本题共36分） 15．设关系R的关系图如下，试
d
33
b
c
（1）写出R的关系表达式；
（2）判断R是否为等价关系，并说明理由．
16．设图G=
17．求?P∨（Q∧R）的合取范式与主合取范式．
六、证明题（本题共8分）
18．对任意集合A，B和C，试证明A? ( B?C ) =( A? B) ? ( A? C )．
34
离散数学（本）2016年1月份试题
参考解答
一、单项选择题（每小题3分，本题共15分） 1．B 2．D 3．C 4．C 5．A
二、填空题（每小题3分，本题共15分） 6．6 7．n(n-1)/2
8．两个或零个 （注：答“两个”也给3分） 9．11
10．A(1 ) ∧A(2) ∧ A(3) ∧ A(4)
三、逻辑公式翻译（每小题6分，本题共12分）
11．设P：小明是个学生． 则命题公式为：P． 12．设P：他上午去教室上课，
Q：他下午去体育馆参加比赛． 则命题公式为：P∧Q
四、判断说明题（每小题7分，本题共14分）
13．正确． 例：设A={a}，B={a，{a}} 则有A?B且A?B． 说明：举出符合条件的实例均给分．
14．错误． 完全图K4是平面图， 如K4可以如下图示嵌入平面．
五．计算题（每小题12分，本题共36分）
15．解：（1）R={< a, b >,< b, a >,< a, c >,< c, a >,< c, d >,< d, c >}．（2）不是等价关系 因为该关系不满足自反性（或答：不满足传递性） 16．解：（1）关系图
35
2分） 6分）
2分） 6分） 3分） 5分） 7分） 3分） 5分） 7分）
（4分） （8分）（12分） （ （ （ （ （ （ （ （ （ （