离散数学（本）2018年10月份试题
一、单项选择题（每小题3分，本题共15分）
1．若集合A＝{1,2,3}，则下列表述不正确的是
（）．
A．1
ÎA
B．{1}ÌA
C．ÆÎA
D．{2}ÍA
2．设A={2,3｝，B
={3,4}，A到B的关系R
={
|
xÎA,yÎB，且x不大于y｝，则R
=
（）．
A．{<3,3>,<4,4>}
B．{<2,3>,<2,4>,<3,3
>,<3,4
>}
C．{<2,3>,<2,4>,<3,4>}
D．{<2,2>,<3,3>,<4,4>}
3．无向图G的结点的度数之和是24，则图G的边数为（）．
A．12
B．24
C．48
D．23
4．设连通平面图G有v个结点，e条边，r个面，则（）．
A．v
+
e
–
r
=
–
B．v
+
e
r=4
C．v
+
e
r=2
D．r
+
v
e
=2
5．设个体域D是实数集合，则命题($x)(“y)(x´y
=
y)的真值是（）．
A．T
B．
F
C．由y的取值确定
D．
不确定
二、填空题（每小题3分，本题共15分）
6．设集合A={a,b}，B={b,c}，C={c,d}，则(AÈ
B)–(BÇC)
=
．
7．设A={3，6}，B={1，6}，C={3，5}，从A到B的函数f={<3,1>,<6,6>}，从B到C的函数g={<1，3>,<6，5>}，则Dom(g°
f)
=
．
8．结点数相等是两个图同构的条件．
9．设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为4，则在G
-S中的连通分支数不超过
．
10．设个体域D＝{a,b}，则谓词公式(“x)Q(x)消去量词后的等值式为
．
三、逻辑公式翻译（每小题6分，本题共12分）
11．将语句“昨天是公休日，今天也是公休日．”翻译成命题公式．
12．将语句“如果今天是周五，则明天是周四．”翻译成命题公式．
四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）
13．如果A是集合B的元素，则A不可能是B的子集．
14．(“x)(A(x)→(B(y)
→C(z)))中的约束变元为y．
五．计算题（每小题12分，本题共36分）
15．设A={1，2，3}，R={
y
}，S={
16．设图G=
(a,c),(a,e),(b,d),(b,e),(c,e),(d,e)
}，对应边的权值依次为2、3、3、4、1及5，请画出G的图形、写出G的邻接矩阵并求出G权最小的生成树及其权值．
17．画一棵带权为1,2,3,4,5的最优二叉树,并计算该最优二叉树的权．
六、证明题（本题共8分）
18．试证明：P→Q
Þ
P→(P∧Q)
．
离散数学（本）2018年10月份试题
参考解答
一、单项选择题（每小题3分，本题共15分）
1．C
2．B
3．A
4．D
5．A
二、填空题（每小题3分，本题共15分）
6．{
a,b
}
7．{3，6}
8．必要
9．4
10．Q(a)∧Q(b)
三、逻辑公式翻译（每小题6分，本题共12分）
11．设P：昨天是公休日，Q：今天是公休日．
（2分）
则命题公式为：
P∧Q．
（6分）
12．设P：今天是周五，Q：明天是周四．
（2分）
则命题公式为：P→Q．
（6分）
四、判断说明题（每小题7分，本题共14分）
13．错误．
（3分）
反例：设A={1}，B={1,{1}}，则A是B的元素，也是B的子集．
（7分）
说明：举出符合条件的反例均给分．
14．错误．
（3分）
(“x)(A(x)→(B(y)
→C(z)))中的y是自由变元，约束变元为x．
（7分）
五．计算题（每小题12分，本题共36分）
15．R={<2,1>,<3,1>,<3,2>}
（3分）
S={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}
（6分）
R-1={<1,2>,<1,3>,<2,3>}
（9分）
s(S)={
<1,1>,<2,1>,<1,2>,<3,1>,<1,3>,<2,2>,<3,2>,<2,3>,<3,3>}
（12分）
说明：对于每一个求解项，如果基本求出了解，可以给对应1分．
16．G的图形表示为：
（3分）
邻接矩阵：
（6分）
如下为最小的生成树，权为10：
（9分）
（12分）
17．（10分）
权为1´3+2´3+3´2+4´2+5´2=33
（12分）
六、证明题（本题共8分）
18．证明：
（1）P→Q
P
（1分）
（2）P
P（附加前提）
（3分）
（3）Q
T（1）（2）I
（5分）
（4）P∧Q
T（2）（3）I
（7分）
（5）P→(P∧Q)
CP规则
（8分）
说明1：因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分。
说明2：另证如下：
设P→(P∧Q)为F，（1分）
则P为T，PQ为F。
（3分）
所以P为T，Q为F，（5分）
从而P→Q也为F。
（7分）
所以P→QP→(PQ)。
（8分）
说明3：可以用真值表验证。
点击咨询