离散数学（本）2019年3月份试题
一、单项选择题（每小题3分，本题共15分）
1．设A＝｛1,2,3｝，B={1,2,3,4}，A到B的关系R＝｛〈x,y〉|
xÎA,yÎB，x=y｝，则R
=
（）
．
A.{<1,2>,<2,3>}
B.{<1,1>,<1,2>,<1,3>,<1,4>,<1,5>}
C.{<1,1>,<2,1>}
D.{<1,1>,<2,2>,<3,3
>}
2．设G为无向图，则下列结论成立的是
（）
．
A．无向图G的结点的度数等于边数的两倍．
B．无向图G的结点的度数之和等于边数的两倍．
C．无向图G的结点的度数等于边数．
D．无向图G的结点的度数之和等于边数．
3．无向图G是棵树，结点数为10，则G的边数是（）．
A.5
B.10
C.9
D.12
4．下列公式中，（）为永真式．
A．ØPÙØQ
«
Ø(PÚQ)
B．ØPÙØQ
«
Ø(PÙQ)
C．ØPÙØQ
«
PÚQ
D．ØPÙØQ
«
ØPÚØQ
5．下面的推理正确的是（）．
A．(1)
（“x）F（x）→G（x）
前提引入
(2)
F（y）→G（y）
US（1）．
B．(1)
（$x）F（x）→G（x）
前提引入
(2)
F（y）→G（y）
ES（1）．
C．(1)
（$x）(F（x）→G（x））
前提引入
(2)
F（y）→G（x）
ES（1）．
D．(1)
（“x）（F（x）→G（x））
前提引入
(2)
F（y）→
G（y）
US（1）．
二、填空题（每小题3分，本题共15分）
6．设集合A＝{a}，那么集合A的幂集是
．
7．设A={a,b}，B={1,2}，C={a,b}，从A到B的函数f={
>}，则g°
f等于
．
8．若图G=
a,b,c,d
}，E={
(a,b),(a,d),(b,c),(b,d)}，则该图中的割边为
．
9．设无向图G中存在欧拉回路，则G的奇数度数的结点数为
个．
10．设个体域D＝{1,2,3,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．设G是一个有6个结点14条边的连通图，则G为平面图．
五．计算题（每小题12分，本题共36分）
b
c
d
a
15．设关系R的关系图如下：
（1）写出R的关系表达式；
（2）判断R是否为等价关系，并说明理由．
16．图G=
(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)
}，对应边的权值依次为1、1、5、2、3及4．
（1）请画出G的图形
（2）写出G的邻接矩阵
（3）求出G权最小的生成树及其权值．
17．求（P∨Q）→R的析取范式与合取范式．
六、证明题（本题共8分）
18．设A，B，C均为任意集合，试证明：A
（B∪C)
=
(A-
B)
C
．
离散数学（本）2019年3月份试题
参考解答
一、单项选择题（每小题3分，本题共15分）
1．D
2．B
3．C
4．A
5．D
二、填空题（每小题3分，本题共15分）
6．{Æ,{a}}
7．{ >, >} 8．(b,c) 9．0 10．A(1) ∨A(2) ∨ A(3) ∨ A(4) 三、逻辑公式翻译（每小题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分） 不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．” （7分） 五．计算题（每小题12分，本题共36分） 15．解：（1）R={< a,b >,b,a >,a,c >,c,a >,c,d >,d,c >}． （4分） （2）不是等价关系 （8分） 因为该关系不满足自反性（或答：不满足传递性） （12分） o o o o a b c d 16．解：G的图形表示为： （3分） 邻接矩阵： （6分） o o o o a b c d 粗线表示的图是最小生成树，权为5： （12分） 17．（P∨Q）→R Û Ø（P∨Q）∨R （4分） Û (ØP∧ØQ)∨R （析取范式） （8分） Û (ØP∨R)∧(ØQ∨R) （合取范式） （12分） 六、证明题（本题共8分） 18．证明：设S= A （B∪C)，T= (A- B) C，若x∈S，则x∈A且xÏB∪C，即 x∈A，并且xÏB 且 xÏC，（2分） 由x∈A且xÏB，得x∈A B，又由xÏC得 x∈(A- B) C，即x∈T，（3分） 所以SÍT． （4分） 反之，若x∈T，则x∈(A- B) 且 xÏC，（5分） 由x∈(A- B)，得x∈A且xÏB，则得xÏB∪C，（6分） 即得x∈A且xÏB∪C，即x∈S，所以TÍS． （7分） 因此T=S． （8分）
点击咨询