离散数学(本科)(.doc
- 文档编号:8858844
- 上传时间:2023-05-15
- 格式:DOC
- 页数:9
- 大小:670.50KB
离散数学(本科)(.doc
《离散数学(本科)(.doc》由会员分享,可在线阅读,更多相关《离散数学(本科)(.doc(9页珍藏版)》请在冰点文库上搜索。
《离散数学》复习资料2014年12月
一、单项选择题(每小题3分,本题共15分)
1.若集合A={1,2},B={1,2,{1,2}},则下列表述正确的是(A).
A.AÌB,且AÎBB.BÌA,且AÎBC.AÌB,且AÏBD.AËB,且AÎB
2.设有向图(a)、(b)、(c)与(d)如图一所示,则下列结论成立的是(D).
图一
A.(a)是强连通的B.(b)是强连通的
C.(c)是强连通的D.(d)是强连通的
3.设图G的邻接矩阵为
则G的边数为(B).
A.6B.5C.4D.3
4.无向简单图G是棵树,当且仅当(A).
A.G连通且边数比结点数少1B.G连通且结点数比边数少1
C.G的边数比结点数少1D.G中没有回路.
5.下列公式(C)为重言式.
A.ØPÙØQ«PÚQB.(Q®(PÚQ))«(ØQÙ(PÚQ))
C.(P®(ØQ®P))«(ØP®(P®Q))D.(ØPÚ(PÙQ))«Q
6.设A={a,b},B={1,2},R1,R2,R3是A到B的二元关系,且R1={,},R2={,,},R3={,},则(B)不是从A到B的函数.
A.R1和R2B.R2
C.R3D.R1和R3
7.设A={1,2,3,4,5,6,7,8},R是A上的整除关系,B={2,4,6},则集合B的最大元、最小元、上界、下界依次为(B).
A.8、2、8、2B.无、2、无、2
C.6、2、6、2D.8、1、6、1
8.若集合A的元素个数为10,则其幂集的元素个数为(A).
A.1024B.10C.100D.1
9.设完全图K有n个结点(n≥2),m条边,当(C)时,K中存在欧拉回路.
A.m为奇数B.n为偶数
C.n为奇数D.m为偶数
10.已知图G的邻接矩阵为
,
则G有(D).
A.5点,8边B.6点,7边
C.6点,8边D.5点,7边
11.无向完全图K3的不同构的生成子图的个数为(C)
(A)6(B)5
(C)4(D)3
12n阶无向完全图Kn中的边数为(A)
(A)(B)(C)n(D)n(n+1)
13.在图G=
Adeg(vi)=2½E½(B)deg(vi)=½E½
CD
二、填空题(每小题3分,本题共15分)
1.命题公式的真值是 1 .
2.若A={1,2},R={
3.已知一棵无向树T中有8个结点,4度,3度,2度的分支点各一个,T的树叶数为5.
4.("x)(P(x)→Q(x)∨R(x,y))中的自由变元为R(x,y)中的y.
5.设集合A={a,b},那么集合A的幂集是{Æ,{a,b},{a},{b}}
6.如果R1和R2是A上的自反关系,则R1∪R2,R1∩R2,R1-R2中自反关系有2个.
7.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去4条边后使之变成树.
8.无向图G存在欧拉回路,当且仅当G所有结点的度数全为偶数且连通
9.设连通平面图G的结点数为5,边数为6,则面数为3.
10.设个体域D={a,b},则谓词公式("x)A(x)∧($x)B(x)消去量词后的等值式为(A(a)∧A(b))∧(B(a)∨B(b)).
三、逻辑公式翻译(每小题6分,本题共12分)
1.将语句“雪是黑色的.”翻译成命题公式.
设P:
雪是黑色的,(2分)
则命题公式为:
P.
2.将语句“他不去学校.”翻译成命题公式.
解:
设P:
他去学校,
则命题公式为:
ØP.
3.将语句“小王是个学生,小李是个职员,而小张是个军人.”翻译成命题公式.
设P:
小王是个学生,Q:
小李是个职员,R:
小张是个军人.(2分)
则命题公式为:
P∧Q∧R.
4.将语句“如果所有人今天都去参加活动,则明天的会议取消.”翻译成命题公式.
解:
设P:
所有人今天都去参加活动,
Q:
明天的会议取消,
则命题公式为:
P®Q.
5.将语句“他去旅游,仅当他有时间.”翻译成命题公式.
解:
设P:
他去旅游,Q:
他有时间,
则命题公式为:
P®Q.
6.将语句“41次列车下午五点开或者六点开.”翻译成命题公式.
解:
设P:
41次列车下午五点开,Q:
41次列车下午六点开,(2分)
命题公式为:
(P∧ØQ)∨(ØP∧Q)
7.将语句“小张学习努力,小王取得好成绩.”翻译成命题
设P:
小张学习努力,Q:
小王取得好成绩,(2分)
则命题公式为:
PÙQ.
8.将语句“有人去上课.”翻译成谓词公式.
解:
设P(x):
x是人,Q(x):
x去上课,(1分)
($x)(P(x)ÙQ(x)
9.将语句“所有的人都学习努力.”翻译成命题公式.
解:
设P(x):
x是人,Q(x):
x学习努力,
"x)(P(x)®Q(x)).
四、判断说明题(每小题7分,本题共14分)判断下列各题正误,并说明理由.
1.设集合A={1,2,3,4},B={2,4,6,8},,判断下列关系f是否构成函数f:
,并说明理由.
(1)f={<1,4>,<2,2,>,<4,6>,<1,8>};
(2)f={<1,6>,<3,4>,<2,2>};
(3)f={<1,8>,<2,6>,<3,4>,<4,2,>}.
答:
(1)不构成函数因为,但没有定义,所以不构成函数
(2)不构成函数因为,但没有定义,所以不构成函数
(3)满足。
因为任意,都有且结果唯一。
2.若集合A={1,2,3}上的二元关系R={<1,1>,<2,2>,<1,2>},则
(1)R是自反的关系;
(2)R是对称的关系.
答:
(1)错误因为,所以R不是自反的
(2)错误因为,但是,所以R不是对称的
3.如果R1和R2是A上的自反关系,判断结论:
“R-11、R1∪R2、R1∩R2是自反的”是否成立?
并说明理由.
答:
成立因为任意,有
所以,,R-11、R1∪R2、R1∩R2是自反的
o
o
o
o
a
b
c
d
图一
o
o
o
g
e
f
h
o
4.若偏序集的哈斯图如图一所示,
则集合A的最大元为a,最小元不存在.
答:
错误,集合A没有最大元,也没有最小元
其中a是极大元
5.若偏序集的哈斯图如图一所示,则集合A的最大元为a,最小元不存在.
解:
正确
对于集合A的任意元素x,均有
6.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路..
答:
错误如果图G是无向图,且图G是连通的,同时结点度数都是偶数
7.设G是一个连通平面图,且有6个结点11条边,则G有7个面.
答案:
正确
定理,连通平面图G的结点数为v,边数是e,面数为r,则欧拉公式v-e+r=2成立
所以r=2-v+e=2-6+11=7
则G存在一条欧拉回路
8.设G是一个有6个结点14条边的连通图,则G为平面图.
解:
错误,不满足“设G是一个有v个结点e条边的连通简单平面图,若v≥3,则e≤3v-6.”9.命题公式ØPÙ(P®ØQ)ÚP为永真式.
解:
正确因为,由真值表
P
Q
ØP
ØQ
P®ØQ
ØP∧(P→ØQ)∨P
0
0
1
1
1
1
0
1
1
0
1
1
1
0
0
1
1
1
1
1
0
0
0
1
可知,该命题公式为永真式.
五.计算题(每小题12分,本题共36分)
1.设集合A={a,{b},c},B={{a},c},试计算
(1)(A∩B);
(2)(B-A);(3)(A∩B)×B.
解
(1)(A∩B)={c};
(2)(B-A)={{a}};
(3)(A∩B)×B={
2.设A={0,1,2,3,4,5,6},R={
解:
R={<0,0>}
S={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>}
R·S={<0,0>,<0,1>,<0,2>,<0,3>}
R-1={<0,0>}
S-1=S)
r(R)=IA.
3.图G=
(1)画出G的图形;
(2)写出G的邻接矩阵;
(3)求出G权最小的生成树及其权值.
解:
(1)G的图形表示为:
(3分)
(2)邻接矩阵:
(6分)
(3)粗线表示最小的生成树,
权为7:
4.设图G=
(1)画出G的图形表示;
(2)求出每个结点的度数;
(3)画出图G的补图的图形.
v1
v2
v3
v4
v5
o
o
o
o
o
解:
(1)关系图
(2)deg(v1)=2deg(v2)=3deg(v3)=4
deg(v4)=3v1
v2
v3
v4
v5
o
o
o
o
o
deg(v5)=2
(3)补图
5.设集合A={1,2,3,4},R={
(1)写出R的有序对表示;
(2)画出R的关系图;
(3)说明R满足自反性,不满足传递性.
解:
(1)R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}(3分)
°
°
°
°
1
2
3
4
(2)关系图为
(3)因为<1,1>,<2,2>,<3,3>,<4,4>均属于R,即A的每个元素构成的有序对均在R中,故R在A上是自反的。
因有<2,3>与<3,4>属于R,但<2,4>不属于R,所以R在A上不是传递的。
6.设集合A={1,2,3},R={<1,1>,<2,1>,<3,1>},S={<1,2>,<2,2>}试计算
(1)R·S;
(2)R-1;(3)r(R).
解:
(1)R·S=={<1,2>,<2,2>,<3,2>};(4分)
(2)R-1={<1,1>,<1,2>,<1,3>};(8分)
(3)r(R)={<1,1>,<2,2>,<3,3>,<2,1>,<3,1>}
7、求出如图一所示赋权图中的最小生成树(要求写出求解步骤),并求此最小生成树的权.
解用Kruskal算法求产生的最小生成树.步骤为:
选
选
选
选
选
选(6分)
最小生成树如图四所示:
(9分)
图四
最小生成树的权为:
w(T)=22+1+4+9+3+18=57.(12分)
8.试画一棵带权为2,3,3,4,5,的最优二叉树,并计算该最优二叉树的权.
o
o
o
o
o
o
o
o
o
2
3
3
4
5
5
10
7
17
解:
最优二叉树如图二所示.
(10分)
图二
权为2´3+3´3+3´2+4´2+5´2=39
9.设谓词公式,试
(1)写出量词的辖域;
(2)指出该公式的自由变元和约束变元.
(1)$x量词的辖域为,(2分)
"z量词的辖域为,(4分)
"y量词的辖域为.(6分)
(2)自由变元为中的y,以及中的z(9分)
约束变元为中的x与中的z,以及中的y.
10.设谓词公式,试
(1)写出量词的辖域;
(2)指出该公式的自由变元和约束变元.
(1)$x量词的辖域为,(3分)
"z量词的辖域为,(6分)
(2)自由变元为公式中的y与中的x,(9分)
约束变元为的x与z.
11.求命题公式(PÚQ)®(RÚQ)的主析取范式、主合取范式.
解:
P
Q
R
PÚQ
RÚQ
(PÚQ)®(RÚQ)
极小项
极大项
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
0
1
1
1
ØPÙØQÙØR
ØPÙØQÙR
ØPÙQÙØR
ØPÙQÙR
PÙØQÙR
PÙQÙØR
PÙQÙR
ØPÚQÚR
主析取范式(极小项析取):
(ØPÙØQÙØR)Ú(ØPÙØQÙR)Ú(ØPÙQÙØR)Ú(ØPÙQÙR)
Ú(PÙØQÙR)Ú(PÙQÙØR)Ú(PÙQÙR)
主合取范式(极大项合取):
ØPÚQÚR
12.求(P∨Q)→(R∨Q)的析取范式,合取范式.
解:
(P∨Q)→(R∨Q)
ÛØ(P∨Q)∨(R∨Q)(4分)
Û(ØP∧ØQ)∨(R∨Q)
Û(ØP∨R∨Q)∧(ØQ∨R∨Q)
Û(ØP∨R∨Q)析取、合取范式
六、证明题(本题共8分)
1.试证明集合等式AÇ(BÈC)=(AÇB)È(AÇC).
证明:
设S=A∩(B∪C),T=(A∩B)∪(A∩C),若x∈S,则x∈A且x∈B∪C,即x∈A且x∈B或x∈A且x∈C,
也即x∈A∩B或x∈A∩C,即x∈T,所以SÍT.
反之,若x∈T,则x∈A∩B或x∈A∩C,
即x∈A且x∈B或x∈A且x∈C
也即x∈A且x∈B∪C,即x∈S,所以TÍS.
因此T=S.
2.试证明($x)(P(x)∧R(x))Þ($x)P(x)∧($x)R(x).
证明:
(1)($x)(P(x)∧R(x))P
(2)P(a)∧R(a)ES
(1)
(3)P(a)T
(2)I
(4)($x)P(x)EG(3)
(5)R(a)T
(2)I
(6)($x)R(x)EG(5)
(7)($x)P(x)∧($x)R(x)T(5)(6)I
9
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 本科