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

2016全新精品资料-全新公文范文-全程指导写作 –独家原创 1 / 11
离散数学（本）2017年3月份试题（含答案）
离散数学（本）2Dom(g°
f)等于
．
8．结点数相等与边数相等是两个图同构的
条件．
9．设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为4，则在G
2016全新精品资料-全新公文范文-全程指导写作 –独家原创 5 / 11
-S中的连通分支数不超过
．
10．设个体域D＝{a,
b,
c}，则谓词公式($x)P(x)消去量词后的等值式为
．
三、逻辑公式翻译（每小题6分，本题共12分）
11．将语句“小李前天去工厂劳动，昨天休息．”翻译成命题公式．
12．将语句“如果他去开会，则我去开会．”翻译成命题公式．
四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）
13．集合的元素可以是集合．
14．($x)(P(x)→Q(y)∧R(z))中的约束变元为y．
五．计算题（每小题12分，本题共36分）
15．设A={1，2，3}，R={|xÎA，yÎA且x
+y
>4}，S={|xÎA，yÎA且x，其中，结点集V={a,
b,
c,
d,
e}，边集E={
(a,
2016全新精品资料-全新公文范文-全程指导写作 –独家原创 6 / 11
b),
(a,
c),
(a,
e),
(b,
c),
(b,
d),
(b,
e),
(c,
e),
(d,
e)
}，对应边的权值依次为1、1、3、2、3、6、1及5，请画出G的图形、写出G的邻接矩阵并求出G权最小的生成树及其权值．
17．画一棵带权为2,
2,
2,
3,
4的最优二叉树,
并计算该最优二叉树的权．
2016全新精品资料-全新公文范文-全程指导写作 –独家原创 7 / 11
六、证明题（本题共8分）
18．试证明：P→Q
Þ
P→(P∧Q)
．
离散数学（本）2017年3月份试题解答
(供参考)
一、单项选择题（每小题3分，本题共15分）
1．D
2．C
3．B
4．A
5．D
二、填空题（每小题3分，本题共15分）
6．{
a,
b
}
7．{2，3}
8．必要
9．4
10．P(a
)
∨P(b)
2016全新精品资料-全新公文范文-全程指导写作 –独家原创 8 / 11
∨
P(c)
三、逻辑公式翻译（每小题6分，本题共12分）
11．设P：小李前天去工厂劳动，Q：小李昨天休息．
（2分）
则命题公式为：
P∧Q．
（6分）
12．设P：他去开会，
Q：我去开会．
（2分）
则命题公式为：P→Q．
（6分）
四、判断说明题（每小题7分，本题共14分）
13．正确．
（3分）
例：集合{{1}}中的元素{1}是集合．
（7分）
说明：举出符合条件的例均给分．
14．错误．
（3分）
($x)(P(x)→Q(y)∧R(z))中的y是自由变元，约束变元为x．
（7分）
五．计算题（每小题12分，本题共36分）
2016全新精品资料-全新公文范文-全程指导写作 –独家原创 9 / 11
15．
R={,
,
}
（3分）
S={,
,
}
（6分）
R-1={,
,
}
（9分）
s(S)={
,
,
,
,
,
}
（12分）
说明：对于每一个求解项，如果基本求出了解，可以给对应1分．
16．解：G的图形表示为：
2016全新精品资料-全新公文范文-全程指导写作 –独家原创 10 / 11
（3分）
邻接矩阵：
（6分）
粗线表示最小的生成树：
（9分）
权为6
（12分）
17．
（10分）
权为2´3+2´3+2´2+3´2+4´2=30
（12分）
六、证明题