离散数学（本）2016年3月份试题
一、单项选择题（每小题3分，本题共15分）
1．设A={1,3,5,7｝，B={2,4,6}，A到B的关系R={
|
y=x+3}，则R为
（）．
A.{<3,2>,<5,4>,<7,6>}
B.{<1,4>,<3,6>}
C.{<1,2>,<3,4>,<5,6>}
D.{<1,3>,<3,3>,<5,3>,<7,3>}
2．若集合A＝{a,b,c}，则下列表述不正确的是（）．
A．Æ
ÍA
B．aÎA
C．{a}ÎA
D．{a,b,c}ÍA
3．设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))
4．设G为连通无向图，则（）时，G中存在欧拉回路．
A．G不存在奇数度数的结点
B．G存在偶数度数的结点
C．G存在一个奇数度数的结点
D．G存在两个奇数度数的结点
5．n阶无向完全图Kn的边数是（）．
A.n(n-1),B.n(n-1)/2
C.n-1
D.n(n-1)
二、填空题（每小题3分，本题共15分）
6．设集合A={1,2,3}，B={2,3,4}，C={3,4,5}，则A∪(C-B)等于
．
7．设A={a,b}，B={1,2}，C={a,b}，从A到B的函数f={
>}，则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．将语句“如果小王来学校，则他会参加比赛．”翻译成命题公式．
12．将语句“今天天晴，昨天下雨．”翻译成命题公式．
四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）
13．设A={1，2，3
}，R={<1，1
>,<1，2
>，<2，1
>,<3，3
>}，则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=
}，试
（1）给出G的图形表示；
（2）写出其邻接矩阵；
（3）求出每个结点的度数；
（4）画出其补图的图形．
17．试利用Kruskal算法求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权．
o
o
o
o
o
v6
v1
v2
v5
v3
o
v4
六、证明题（本题共8分）
18．试证明：┐┐(P®Q)∧┐R
∧（Q®R）Þ
┐P．
离散数学（本）2016年3月份试题
参考解答
一、单项选择题（每小题3分，本题共15分）
1．B
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：今天天晴，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={ (12分） 16．解：（1）G的图形表示如图一所示： （3分） 图一 （2）邻接矩阵： （6分） （3）v1，v2，v3，v4，v5结点的度数依次为2，1，3，2，2． （9分） （4）补图如图二所示： （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分） o o o o o v6 v1 v2 v5 v3 o v4 最小生成树如图三所示： （9分） 图三 最小生成树的权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．另，可以用真值表验证．
点击咨询