离散数学（本）2018年1月份试题
一、单项选择题（每小题3分，本题共15分）
1．设A={1,2,3,4｝，B={2,3,4}，A到B的关系R={
xÎA,yÎB，且x+y=5｝，则R=
（）．
A．{<1,2>,<1,3>,<2,3>}
B．{<1,4>,<2,3>,<3,2>}
C．{<1,1>,<2,2>,<3,2>}
D．{<3,2>,<2,4>,<3,4>}
2．若集合A＝{a,b,c,d}，则下列表述正确的是（）．
A．ÆÎA
B．{a}ÎA
C．{a,b,c,d
}ÎA
D．{a,b
}ÍA
3．设个体域为整数集，则公式(“x)($y)(x-y=2)的解释可为
（）．
A．存在一整数x有整数y满足x-y=2
B．存在一整数x对任意整数y满足x-y=2
C．对任一整数x存在整数y满足x-y=2
D．任一整数x对任意整数y满足x-y=2
4．n阶无向完全图Kn的边数及每个结点的度数分别是（）．
A．n(n-1)与n
B．
n(n-1)与n-1
C．n-1与n
D．n(n-1)/2与n-1
5．设G为连通无向图，则（）时，G中存在欧拉回路．
A．G不存在奇数度数的结点
B．G存在一个奇数度数的结点
C．G存在两个奇数度数的结点
D．G存在偶数度数的结点
二、填空题（每小题3分，本题共15分）
6．设集合A={x
|
x是小于4的正整数}，用集合的列举法A=
．
7．设A={1，2}，B={a，b}，C={1，2}，从A到B的函数f={<1，a>,<2，b>}，从B到C的函数g={
f
=
．
8．设G=
．
9．设G是具有n个结点m条边k个面的连通平面图，则n+k
=
．
10．设个体域D＝{2,3,4}，A(x)为“x小于3”，则谓词公式（“x）A(x)的真值为
．
三、逻辑公式翻译（每小题6分，本题共12分）
11．将语句“如果今天下雨，那么明天的比赛就要延期．”翻译成命题公式．
12．将语句“地球是圆的，太阳也是圆的．”翻译成命题公式．
四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）
13．设A={
a，b，c，d}，R={<
a，b
>,b，a
>，<
a，a
>，<
b，b
>，<
c，c
>}，则R是等价关系．
14．(“x)(P(x)∧Q(y))→R(x)中量词“的辖域为(P(x)∧Q(y))．
五．计算题（每小题12分，本题共36分）
15．设集合A={a,b,c}，B={
b,c,d
}，试计算
（1）AÈB；
（2）A
B；
（3）A×B．
16．设G=
（1）给出G的图形表示；
（2）写出其邻接矩阵；
（3）求出每个结点的度数；
（4）画出其补图的图形．
17．试利用Kruskal算法求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权．
六、证明题（本题共8分）
18．试证明：P→Q
Þ
P→
Ø
(P→
ØQ)
．
离散数学（本）2018年1月份试题
参考解答
一、单项选择题（每小题3分，本题共15分）
1．B
2．D
3．C
4．D
5．A
二、填空题（每小题3分，本题共15分）
6．{1,2,3}
7．{<1，2
>,<2，1
>}
8．15
9．m
10．假（或F，或0）
三、逻辑公式翻译（每小题6分，本题共12分）
11．设P：今天下雨，Q：明天的比赛就要延期．
（2分）
则命题公式为：
P
®
Q．
（6分）
12．设P：地球是圆的，Q：太阳是圆的．
（2分）
则命题公式为：P∧Q．
（6分）
四、判断说明题（每小题7分，本题共14分）
13．错误．
（3分）
R不是等价关系，因R中不含
（7分）
14．正确．
（3分）
辖域为紧接量词“之后的最小子公式(P(x)∧Q(y))．
（7分）
五．计算题（每小题12分，本题共36分）
15．（1）AÈB={
a,b,c,d}；
（4分）
（2）A
B={
a}；
（8分）
（3）A×B={
>,
>,c,d>}
（12分）
v1
v2
v3
v4
o
o
o
o
16．（1）G的图形表示如图一所示：
图一
（3分）
（2）邻接矩阵：
（6分）
（3）
deg(v1)=3，deg(v2)=2，deg(v3)=3，deg(v4)=2
（9分）
v1
v2
v3
v4
o
o
o
o
（4）补图如图二所示：
图二
（12分）
17．用Kruskal算法求产生的最小生成树．步骤为：
w(v1,v7)=1
选e1=v1v7
w(v7,v4)=1
选e2=v7v4
w(v1,v6)=2
选e3=v1v6
w(v3,v4)=3
选e4=v3v4
w(v2,v7)=4
选e5=v2v7
w(v5,v7)=5
选e6=v5v7
（6分）
最小生成树如图三所示：
（9分）
图三
最小生成树的权W(T)=1+1+2+3+4+5=16．
（12分）
说明：用其它方法，结果正确参照给分．
六、证明题（本题共8分）
18．证明：
（1）P→Q
P
（1分）
（2）P
P（附加前提）
（2分）
（3）Q
T（1）（2）I
（4分）
（4）P∧Q
T（2）（3）I
（5分）
（5）Ø
(ØP∨ØQ)
T（4）E
（6分）
（6）Ø
(P→
ØQ)
T（5）E
（7分）
（7）P→Ø
(P→
ØQ)
CP规则
（8分）
说明：因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分．
另，可以用真值表验证．
点击咨询