离散数学（本）2016年3月份试题（含答案）.doc

2016全新精品资料-全新公文范文-全程指导写作 –独家原创 1 / 14
离散数学（本）2016年3月份试题（含答案）
离散数学（本）2
．
7．设A={a,
b}，B={1,
2}，C={a,
b}，从A到B的函数f={1>,
}，从B到C的函数g={,
}，则g°
f等于
．
8．对于任意的无向图，其所有结点的度数之和等于该图的边数的
．
9．设G是具有n个结点m条边k个面的连通平面图，则n+k
-2等于
．
10．设个体域D＝{1,
2,
3,
4}，A(x)为“x等于4”，则谓词公式($x)A(x)真值为
．
三、逻辑公式翻译（每小题6分，本题共12分）
11．将语句“如果小王来学校，则他会参加比赛．”翻译成命题公式．
2016全新精品资料-全新公文范文-全程指导写作 –独家原创 5 / 14
12．将语句“今天天晴，昨天下雨．”翻译成命题公式．
四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）
13．设A={1，2，3
}，R={,
，,
}，则R是等价关系．
14．(“x)P(x)∧Q(y)→R(x)中量词“的辖域为P(x)∧Q(y)．
五．计算题（每小题12分，本题共36分）
15．设集合A={a,
b,
c}，B={{a,
b
},
b}，试计算
（1）AÇB；
（2）A
-
B；
（3）A×B．
16．设G=，V={v1,
v2,
v3,
2016全新精品资料-全新公文范文-全程指导写作 –独家原创 6 / 14
v4,
v5}，E={(v1,v3)
,
(v1,v5)
,
(v2,v3)
,
(v3,v4)
,
(v4,v5)
}，试
（1）给出G的图形表示；
（2）写出其邻接矩阵；
（3）求出每个结点的度数；
（4）画出其补图的图形．
17．试利用Kruskal算法求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权．
o
o
o
o
o
v6
v1
2016全新精品资料-全新公文范文-全程指导写作 –独家原创 7 / 14
v2
v5
v3
o
v4
1
6
2
4
5
7
9
3
1
5
2
六、证明题（本题共8分）
18．试证明：┐┐(P®Q)∧┐R
∧（Q®R）Þ
┐P．
离散数学（本）2016年3月份试题
参考解答
一、单项选择题（每小题3分，本题共15分）
1．B
2016全新精品资料-全新公文范文-全程指导写作 –独家原创 8 / 14
2．C
3．D
4．A
5．B
二、填空题（每小题3分，本题共15分）
6．{1,
2,
3,
5}
7．{,
}
8．两倍
9．m
10．真（或T，或1）
三、逻辑公式翻译（每小题6分，本题共12分）
11．设P：小王来学校，
Q：他会参加比赛．
（2分）
则命题公式为：
P
®
Q．
（6分）
12．设P：今天天晴，
2016全新精品资料-全新公文范文-全程指导写作 –独家原创 9 / 14
Q：昨天下雨．
（2分）
则命题公式为：P∧Q．
（6分）
四、判断说明题（每小题7分，本题共14分）
13．错误．
（3分）
R不是等价关系，因R中不包含，故不满足自反性．
（7分）
14．错误．
（3分）
辖域为紧接与量词“之后的最小子公式P(x)．
（7分）
五．计算题（每小题12分，本题共36分）
15．解：（1）AÇB={
b}；
（4分）
（2）A
-
B={
a,
c}；
（8分）
（3）A×B={,
2016全新精品资料-全新公文范文-全程指导写作 –独家原创 10 / 14
,
,
,
,
}
(12分）
16．解：（1）