离散数学（本）2017年7月份试题
一、单项选择题（每小题3分，本题共15分）
1．设A={1,3,5,7,9｝，B={2,4,6}，A到B的关系R={
（）．
A．{<1,2>,<2,3>,<3,4>}
B．{<1,2>,<3,4>,<5,6>}
C．{<1,1>,<2,2>,<3,6>}
D．{<3,2>,<5,4>,<7,6>}
2．若集合A＝{a,b,c}，则下列表述正确的是（）．
A．{a,b
}ÍA
B．{a}ÎA
C．{a,b}ÎA
D．ÆÎA
3．设个体域为集合{1，2，3，4，5}，则公式(“x)($y)(x+y=5)的解释可为
（）．
A．存在一整数x有整数y满足x+y=5
B．对任一整数x存在整数y满足x+y=5
C．存在一整数x对任意整数y满足x+y=5
D．任一整数x对任意整数y满足x+y=5
4．设G为连通无向图，则（）时，G中存在欧拉回路．
A．G存在两个奇数度数的结点
B．G存在一个奇数度数的结点
C．G不存在奇数度数的结点
D．G存在偶数度数的结点
5．n阶无向完全图Kn的边数及每个结点的度数分别是（）．
A．n(n-1)与n
B．n(n-1)/2与n-1
C．n-1与n
D．n(n-1)与n-1
二、填空题（每小题3分，本题共15分）
6．设集合A={1,2,3}，B={2,3}，C={3,4}，则A∪(B-C)
=
．
7．设A={a，b}，B={1，2}，C={a，b}，从A到B的函数f={
>}，则g°
f等于
．
8．设G=
E
|=10，则G的结点度数之和为
．
9．设G是具有n个结点m条边k个面的连通平面图，则n+k
=
．
10．设个体域D＝{1,2,3}，A(x)为“x的2倍大于2”，则谓词公式（“x）A(x)的真值为
．
三、逻辑公式翻译（每小题6分，本题共12分）
11．将语句“如果他掌握了计算机的用法，那么他就能完成这项工作．”翻译成命题公式．
12．将语句“前天下雨，昨天还是下雨．”翻译成命题公式．
四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）
13．设A={
a，b，c
}，R={<
a，a
>,b，b
>,c，c，<
a，b
>，<
b，a
>，<
b，c
>，<
c，b
>}，则R是等价关系．
14．(“x)(P(x)∧Q(y)→R(x))中量词“的辖域为(P(x)∧Q(y))．
五．计算题（每小题12分，本题共36分）
15．设集合A={a,b,c,d
}，B={a,b}，试计算
（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)
．
离散数学（本）2017年7月份试题
参考解答
一、单项选择题（每小题3分，本题共15分）
1．D
2．A
3．B
4．C
5．B
二、填空题（每小题3分，本题共15分）
6．{1,2,3}
7．{ >, >} 8．20（或：2|E|） 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中包含< a，b >与< b，c >，但不包含< a，c >，故不满足传递性． （7分） 14．错误． （3分） 辖域为紧接量词“之后的最小子公式(P(x)∧Q(y)→R(x))． （7分） 五．计算题（每小题12分，本题共36分） 15．（1）AÈB={ a,b,c,d}； （4分） （2）A B={ c,d}； （8分） （3）A×B={ >, >} （12分） v1 o o o o v2 v3 v4 图一 16．（1）G的图形表示如图一所示： （3分） （2）邻接矩阵： （6分） （3） deg(v1)=3，deg(v2)=2，deg(v3)=3，deg(v4)=2 （9分） v1 o o o o v2 v3 v4 图二 （4）补图如图二所示： （12分） 17．用Kruskal算法求产生的最小生成树。步骤为： w(v1,v7) =1，选e1=v1v7 w(v3,v4) =3，选e2=v3v4 w(v2,v7) =4，选e3=v2v7 w(v3,v7) =9，选e4=v3v7 w(v4,v5) =18，选e5=v4v5 w(v1,v6) =22，选e6=v1v6 （6分） 最小生成树如图三所示： （9分） 图三 最小生成树的权C(T)= 1+3+4+9+18+22=57． （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分． 另，可以用真值表验证．
点击咨询