离散数学(本)2016年7月份试题
一、单项选择题(每小题3分,本题共15分)
1.若集合A={1,2,3,4},B={1,3,5},则下列表述正确的是
().
A.A=B
B.B
ÌA
C.B
¹A
D.B
Í
A
2.设A={1,2,3},B={2,4,6},A到B的关系R={〈x,y〉|
2x=y},则R=
().
A.{<1,3>,<2,4>,<3,5>}
B.{<2,1
>,<4,3>,<6,5>}
C.{<1,1>,<2,2>,<3,3>}
D.{<1,2>,<2,4>,<3,6>}
3.无向图G是棵树,边数是10,则G的结点度数之和是().
A.20
B.9
C.10
D.11
4.下面的推理正确的是().
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)
US(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).
5.设个体域为整数集,则公式“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
二、填空题(每小题3分,本题共15分)
6.设集合A={1,2,3},B={2,3,4},C={3,4,5},则B∪(A–C)等于
.
7.设A={1,2},B={2,3},C={3,4},从A到B的函数f
={<1,2>,<2,3>},从B到C的函数g={<2,3>,<3,4>},则Ran(g°
f)等于
.
8.两个图同构的必要条件包括结点数相等、边数相等与
.
9.设G是连通平面图,v,e,r分别表示G的结点数,边数和面数,v值为5,e值为4则r的值为
.
10.设个体域D={1,2,3,4},则谓词公式($x)A(x)消去量词后的等值式为
.
三、逻辑公式翻译(每小题6分,本题共12分)
11.将语句“昨天下雨,今天仍然下雨.”翻译成命题公式.
12.将语句“若不下雨,我们就去参加比赛.”翻译成命题公式.
四、判断说明题(判断各题正误,并说明理由.每小题7分,本题共14分)
13.若图G是一个欧拉图,则图G中存在欧拉路.
14.无向图G的结点数比边数多1,则G是树.
五.计算题(每小题12分,本题共36分)
15.设集合A={1,2,3,4}上的关系:
R={<1,2>,<2,3>,<3,4>},S={<1,1>,<2,2>,<3,3>},试计算(1)R·S;
(2)R
-1;
(3)r(RÇS).
16.图G=
(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)
},对应边的权值依次为1、1、5、2、3及4,请画出G的图形、写出G的邻接矩阵并求出G权最小的生成树及其权值.
17.求Ø(P∨Q)∨R的析取范式与主合取范式.
六、证明题(本题共8分)
18.设A,B,C均为任意集合,试证明:A
Ç(B
C)
=
(AÇ
B)
-(A
ÇC).
离散数学(本)2016年1月份试题
参考解答
一、单项选择题(每小题3分,本题共15分)
1.C
2.D
3.A
4.D
5.B
二、填空题(每小题3分,本题共15分)
6.{1,2,3,4}
7.{3,4}
8.度数相同的结点数相等
9.1
10.A(1)
∨A(2)
∨
A(3)
∨
A(4)
三、逻辑公式翻译(每小题6分,本题共12分)
11.设P:昨天下雨,Q:今天下雨.
(2分)
则命题公式为:P∧Q.
(6分)
12.设P:下雨,Q:我们去参加比赛.
(2分)
则命题公式为:ØP→Q.
(或
Ø
Q→P)
(6分)
四、判断说明题(每小题7分,本题共14分)
13.正确.
(3分)
因为若图G是一个欧拉图,则图中存在欧拉回路.
(5分)
按定义知,欧拉回路也是欧拉路.
(7分)
14.错误.
(3分)
反例:如图G的结点数比边数多1,但不是树.
(或:按定义有:无向图G是树当且仅当无向图G是连通图且边数比结点数少1.)
(7分)
说明:举出符合条件的反例均给分.
五.计算题(每小题12分,本题共36分)
15.解:(1)R·S
=={<1,2>,<2,3>};
(4分)
(2)R
-1={<2,1>,<3,2>,<4,3>};
(8分)
(3)r(RÇS)={<1,1>,<2,2>,<3,3>,<4,4>}
(12分)
16.解:G的图形表示为:
(3分)
邻接矩阵:
(6分)
粗线表示的图是最小的生成树,权为5:
(9分)
(12分)
17.解:Ø(P∨
Q)∨R
Û(ØP∧ØQ)∨R
析取范式
(5分)
Û(ØP∨R)∧(ØQ∨R)
(7分)
Û((ØP∨R)∨(Q∧ØQ))∧
(ØQ∨R)
(9分)
Û((ØP∨R)∨(Q∧ØQ))∧
((ØQ∨R)∨(P∧ØP))
(10分)
Û(ØP∨R
∨Q)
∧
(ØP∨R
∨ØQ)
∧
(ØQ∨R∨P)
∧
(ØQ∨R∨ØP)
(11分)
Û
(P∨ØQ∨R)∧(ØP∨Q∨R)∧(ØP∨ØQ∨R)
主合取范式
(12分)
六、证明题(本题共8分)
18.证明:
设S=
A
Ç(B
C),T=(AÇ
B)
-(A
ÇC),若x∈S,则x∈A且x∈B
-C,即
x∈A,并且x∈B
且
xÏC,(2分)
所以x∈(AÇ
B)且xÏ(A
ÇC),得x∈T,(3分)
所以SÍT.
(4分)
反之,若x∈T,则x∈(AÇB)
且
xÏ(A
ÇC),(5分)
即x∈A,x∈B,且x
ÏC,则得x∈B
-C,(6分)
即得x∈A
Ç(B
C),即x∈S,所以TÍS.
(7分)
因此T=S.
(8分)
另,可以用恒等式替换的方法证明.