电大历年离散数学试题汇总文档格式.docx
- 文档编号:3955569
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:50
- 大小:227.38KB
电大历年离散数学试题汇总文档格式.docx
《电大历年离散数学试题汇总文档格式.docx》由会员分享,可在线阅读,更多相关《电大历年离散数学试题汇总文档格式.docx(50页珍藏版)》请在冰点文库上搜索。
则集合A的最大元为a,极小元不存在.
错误.(3分)
对于集合A的任意元素x,均有<
x,a>
R(或xRa),所以a是集合A中的最大元.(5分)
但按照极小元的定义,在集合A中b,c,d均是极小元.(7分)
14.┐P∧(P→┐Q)∨P为永假式.
┐P∧(P→┐Q)∨P是由┐P∧(P→┐Q)与P组成的析取式,
如果P的值为真,则┐P∧(P→┐Q)∨P为真,(5分)
如果P的值为假,则┐P与P→┐Q为真,即┐P∧(P→┐Q)为真,
也即┐P∧(P→┐Q)∨P为真,
所以┐P∧(P→┐Q)∨P是永真式.(7分)
另种说明:
只要其中一项为真,则整个公式为真.(5分)
可以看到,不论P的值为真或为假,┐P∧(P→┐Q)与P总有一个为真,
所以┐P∧(P→┐Q)∨P是永真式.(7分)
或用等价演算┐P∧(P→┐Q)∨PT
五.计算题(每小题12分,本题共36分)
15.设集合A={1,2,3,4},R={<
x,y>
|x,yA;
|xy|=1或xy=0},试
(1)写出R的有序对表示;
(2)画出R的关系图;
(3)说明R满足自反性,不满足传递性.
15.
(1)R={<
1,1>
<
2,2>
3,3>
4,4>
1,2>
2,1>
2,3>
3,2>
3,4>
4,3>
}(3分)
(2)关系图如图二:
图二(6分)
(3)因为<
均属于R,即A的每个元素构成的有序对均在R中,故R在A上是自反的.(9分)
因有<
与<
属于R,但<
2,4>
不属于R,所以R在A上不是传递的.
(12分)
16.设图G=<
V,E>
,V={v1,v2,v3,v4,v5},E={(v1,v2),(v1,v3),(v2,v4),(v3,v5),(v4,v5)},试
(1)画出G的图形表示;
(2)写出其邻接矩阵;
(3)求出每个结点的度数;
(4)画出图G的补图的图形.
16.
(1)关系图如图三:
(3分)
(2)邻接矩阵
(6分)
(3)deg(v1)=2
deg(v2)=2
deg(v3)=2
deg(v4)=2
deg(v5)=2(9分)
(4)补图如图四
17.求PQ∧R的合取范式与主析取范式.
P→(R∧Q)
┐P∨(R∧Q)(4分)
(┐P∨Q)∧(┐P∨R)(合取范式)(6分)
P→(R∧Q)
┐P∨(R∧Q)
(┐P∧(┐Q∨Q))∨(R∧Q)(7分)
(┐P∧┐Q)∨(┐P∧Q)∨(R∧Q)(8分)
((┐P∧┐Q)∧(┐R∨R))∨(┐P∧Q)∨(R∧Q)(9分)
(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q)∨(R∧Q)(10分)
(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨((┐P∧Q)∧(┐R∨R))∨(R∧Q)
(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(┐P∧Q∧R)∨(R∧Q)
(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨
(┐P∧Q∧R)∨((┐P∨P)∧(R∧Q))
(┐P∧Q∧R)∨(P∧R∧Q)(主析取范式)(12分)
说明:
此题解法步骤多样,若能按正确步骤求得结果,均可给分.
六、证明题(本题共8分)
18.设连通无向图G有14条边,3个4度顶点,4个3度顶点,其它顶点的度数均小于3,试说明G中可能有的顶点数.
证明:
可利用数列可图化及握手定理解答
顶点度数和为214=28,(2分)
28-(34+43)=4,则知其他顶点度数和为4,(4分)
对于有限图,若无零度顶点,则除4度及3度顶点外,可能的顶点情况有:
2个2度点;
1个2度点和2个1度点;
4个1度点,(6分)
即对应图的顶点数分别至少为9、10、11.(8分)
2011年7月
一、单项选择题(每小题3分,本题共15分)1.A2.C3.C4.D5.B
1.若集合A={1,{1},{2},{1,2}},则下列表述正确的是().
A.{2}AB.{1,2}A
C.1AD.2A
2.设G为无向图,则下列结论成立的是().
A.无向图G的结点的度数等于边数的两倍.
B.无向图G的结点的度数等于边数.
C.无向图G的结点的度数之和等于边数的两倍.
D.无向图G的结点的度数之和等于边数.
3.图G如图一所示,以下说法正确的是().
A.{(a,b)}是边割集
B.{a,c}是点割集
C.{d}是点割集
D.{(c,d)}是边割集
图一
4.设集合A={1},则A的幂集为().
A.{{1}}B.{1,{1}}
C.{,1}D.{,{1}}
5.设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))
6.命题公式
的真值是 真(或T,或1) .
7.若无向图T是连通的,则T的结点数v与边数e满足关系v=e+1时,T是树.
8.无向图G是欧拉图的充分必要条件是G是连通的且结点度数都是偶数.
9.设集合A={1,2}上的关系R={<
},则在R中仅需加入一个元素<
1,1>
,就可使新得到的关系为自反的.
10.(x)(P(x)→R(y)∨S(z))中的约束变元有x.
三、逻辑公式翻译(每小题6分,本题共12分)
11.将语句“雪是黑色的.”翻译成命题公式.
雪是黑色的,(2分)
则命题公式为:
P.(6分)
12.将语句“如果明天下雨,则我们就在室内上体育课.”翻译成命题公式.
如果明天下雨,Q:
我们在室内上体育课,(2分)
PQ.(6分)
四、判断说明题(每小题7分,本题共14分)
13.设集合A={1,2},B={3,4},从A到B的关系为f={<
1,3>
,<
1,4>
},则f是A到B的函数.
因为A中元素1有B中两个不同的元素与之对应,故f不是A到B的函数.(7分)
14.设G是一个连通平面图,有5个结点9条边,则G有6个面.
正确.(3分)
因G是一个连通平面图,满足欧拉定理,有v-e+r=2,
所以r=2-(v-e)=2-(5-9)=6(7分)
五.计算题(每小题12分,本题共36分)
15.试求出P→(R∧Q)的合取范式.
P→(R∧Q)┐P∨(R∧Q)(6分)
(┐P∨R)∧(┐P∨Q)(合取范式)(12分)
16.设A={{1},{1,2},1},B={1,2,{2}},试计算
(1)(A∩B)
(2)(A∪B)(3)(A∩B)A.
(1)(A∩B)={1}(4分)
(2)(A∪B)={1,2,{1},{2},{1,2}}(8分)
(3)(A∩B)A=(12分)
17.试画一棵带权为2,3,3,4,5,的最优二叉树,并计算该最优二叉树的权.
最优二叉树如图二所示.
(10分)
图二
权为23+33+32+42+52=39(12分)
18.试证明:
若R与S是集合A上的对称关系,则R∩S也是集合A上的对称关系.
设x,yA,因为R对称,所以若<
R,则<
y,x>
R.(2分)
因为S对称,所以若<
S,则<
S.(4分)
于是若<
R∩S则<
R且<
S
即<
S(6分)
也即<
R∩S,故R∩S是对称的.(8分)
中央广播电视大学2010—2011学年度第一学期“开放本科”期末考试
离散数学(本)试题
2011年1月
一、单项选择题(每小题3分,本题共15分)1.A2.D3.B4.D5.C
1.若集合A={a,{1}},则下列表述正确的是().
A.{1}AB.{1}A
C.{a}AD.A
2.设图G=<
V,E>
,vV,则下列结论成立的是().
A.deg(v)=2EB.deg(v)=E
C.
D.
3.如图一所示,以下说法正确的是().
A.(e,c)是割边B.(d,e)是割边
C.(b,a)是割边D.(b,c)是割边
4.命题公式(P∨Q)的合取范式是().
A.PB.(P∧Q)
C.(P∨P)D.(P∨Q)
5.下列等价公式成立的为().
A.PQPQB.QPPQ
C.PPQQD.PPQ
6.设集合A={0,1,2},B={1,2,3,4,},R是A到B的二元关系,
则R的有序对集合为 {<
1,2>
2,1>
2,2>
} .
7.设G是连通平面图,v,e,r分别表示G的结点数,边数和面数,则v,e和r满足的关系式v-e+r=2.
8.设G=<
是有20个结点,25条边的连通图,则从G中删去6条边,可以确定图G的一棵生成树.
9.无向图G存在欧拉回路,当且仅当G所有结点的度数全为偶数且连通.
10.设个体域D={1,2},则谓词公式
消去量词后的等值式为A
(1)A
(2).
11.将语句“如果小李学习努力,那么他就会取得好成绩.”翻译成命题公式.
12.将语句“小张学习努力,小王取得好成绩.”翻译成命题公式.
11.设P:
小李学习努力,Q:
小李会取得好成绩,(2分)
PQ.(6分)
12.设P:
小张学习努力,Q:
小王取得好成绩,(2分)
13.如果R1和R2是A上的自反关系,则R1R2是自反的.
14.如图二所示的图中存在一条欧拉回路.
13.正确.(3分)
R1和R2是自反的,xA,<
x,x>
R1,<
R2,
则<
R1R2,
所以R1R2是自反的.(7分)
14.正确.(3分)
因为图G为连通的,且其中每个顶点的度数为偶数.(7分)
15.设A={{2},1,2},B={1,{1,2}},试计算
(1)(AB);
(2)(A∩B);
(3)A×
B.
16.设G=<
,V={v1,v2,v3,v4,v5},E={(v1,v3),(v2,v3),(v2,v4),(v3,v4),(v3,v5)},试
(1)给出G的图形表示;
(2)写出其邻接矩阵;
(3)求出每个结点的度数;
(4)画出其补图的图形.
17.设谓词公式
,试
(1)写出量词的辖域;
(2)指出该公式的自由变元和约束变元.
15.
(1)AB={2,{2}}(4分)
(2)A∩B={1}(8分)
(3)A×
B={<
{2},1>
{2},{1,2}>
1,{1,2}>
,
<
2,{1,2}>
}(12分)
16.
(1)G的图形表示如图三:
(2)邻接矩阵:
(3)v1,v2,v3,v4,v5结点的度数依次为1,2,4,2,1(9分)
(4)补图如图四:
17.
(1)x量词的辖域为
,(2分)
z量词的辖域为
(4分)
y量词的辖域为
.(6分)
(2)自由变元为
中的y,以及
中的z(9分)
约束变元为
中的x与
中的z,以及
中的y.(12分)
18.试证明集合等式A(BC)=(AB)(AC).
18.证明:
设S=A(BC),T=(AB)(AC),若x∈S,则x∈A或x∈BC,(1分)
即x∈A或x∈B且x∈A或x∈C.(2分)
也即x∈AB且x∈AC,(3分)
即x∈T,所以ST.(4分)
反之,若x∈T,则x∈AB且x∈AC,(5分)
即x∈A或x∈B且x∈A或x∈C,(6分)
也即x∈A或x∈BC,即x∈S,所以TS.(7分)
因此T=S.(8分)
一、单项选择题(每小题3分,本题共15分)1.D2.B3.C4.A5.B
1.若集合A={a,b},B={a,{a,b}},则().
A.ABB.AB
C.ABD.AB
2.集合A={x|x为小于10的自然数},集合A上的关系R={<
x,y>
|x+y=10且x,y
A},则R的性质为().
A.自反的B.对称的
C.传递且对称的D.反自反且传递的
3.设有向图(a)、(b)、(c)与(d)如图一所示,则下列结论成立的是().
A.(a)仅为弱连通的B.(b)仅为弱连通的
C.(c)仅为弱连通的D.(d)仅为弱连通的
4.设图G的邻接矩阵为
则G的边数为().
A.5B.6C.7D.8
5.下列公式()为永真式.
A.PQPQB.(P(QP))(P(PQ))
C.(Q(PQ))(Q(PQ))D.(P(PQ))Q
6.设集合A={1,2,3},那么集合A的幂集是{,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.
7.设A={a,b},B={1,2},作f:
A→B,则不同的函数个数为4.
8.若A={1,2},R={<
|xA,yA,x+y<
4},则R的自反闭包为{<
}.
9.无向连通图在结点数v与边数e满足e=v-1关系时是树.
10.(x)(A(x)→B(x))∨C(x,y)中的自由变元为C(x,y)中的x与y.
11.将语句“他们去旅游,仅当明天天晴.”翻译成命题公式.
12.将语句“今天没有下雪.”翻译成命题公式.
他们去旅游,Q:
明天天晴,(2分)
P→Q.(6分)
今天下雪,(2分)
P.(6分)
13.汉密尔顿图一定是欧拉图.
存在汉密尔顿图不是欧拉图.(5分)
反例见图二.
(7分)
14.下面的推理是否正确,试予以说明.
(1)(x)(F(x)→G(y))前提引入
(2)F(y)→G(y)ES
(1).
1、错误.(3分)
(2)应为F(a)→G(y),换名时,约束变元与自由变元不能混淆.(7分)
15.设A={0,1,2,3,4,5,6},R={<
|xA,yA且x+y<
1},S={<
|xA,yA且x+y3},试求R,S,RS,R-1,S-1,r(R).
R={<
0,0>
}(2分)
S={<
0,1>
0,2>
0,3>
1,0>
2,0>
3,0>
}(4分)
RS={<
}(6分)
R-1={<
}(8分)
S-1=S(10分)
r(R)=IA.(12分)
16.画一棵带权为1,2,2,3,6的最优二叉树,计算它们的权.
14
最优二叉树如图四:
8
6
5
3
2
1
图四(10分)
权为:
13+23+23+33+61=30(12分)
注:
其他正确的最优二叉树参照给分.
17.求(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)析取、合取范式(12分)
注:
其他正确答案参照给分.
18.试证明集合等式A(BC)=(AB)(AC).
设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,所以ST.(4分)
反之,若x∈T,则x∈A∩B或x∈A∩C,
即x∈A且x∈B或x∈A且x∈C
也即x∈A且x∈B∪C,即x∈S,所以TS.
2010年7月
一、单项选择题(每小题3分,本题共15分)1.B2.D3.B4.C5.B
1.若集合A={1,{2},{1,2}},则下列表述正确的是().
A.2AB.{1}A
2.已知一棵无向树T中有8个顶点,4度、3度、2度的分支点各一个,T的树叶数为
().
A.6B.4C.3D.5
3.设无向图G的邻接矩阵为
A.1B.7C.6D.14
4.设集合A={a},则A的幂集为().
A.{{a}}B.{a,{a}}
C.{,{a}}D.{,a}
5.下列公式中()为永真式.
A.ABABB.AB(AB)
C.ABABD.AB(AB)
的真值是 假(或F,或0) .
7.若无向树T有5个结点,则T的边数为4.
8.设正则m叉树的树叶数为t,分支数为i,则(m-1)i=t-1.
},则在R中仅需加一个元素<
,就可使新得到的关系为对称的.
10.(x)(A(x)→B(x,z)∨C(y))中的自由变元有z,y.
11.将语句“今天上课.”翻译成命题公式.
今天上课,(2分)
则命题公式为:
12.将语句“他去操场锻炼,仅当他有时间.”翻译成命题公式.
他去操场锻炼,Q:
他有时间,(2分)
14.设G是一个有4个结点10条边的连通图,则G为平面图.
13.错误.(3分)
因为A中元素2没有B中元素与之对应,故f不是A到B的函数.(7分)
14.错误.(3分)
不满足“设G是一个有v个结点e条边的连通简单平面图,若v≥3,则e≤3v-6.”
15.试求出(P∨Q)→(R∨Q)的析取范式.
(P∨Q)→(R∨Q)┐(P∨Q)∨(R∨Q)(4分)
(┐P∧┐Q)∨(R∨Q)(8分)
(┐P∧┐Q)∨R∨Q(析取范式)(12分)
16.设A={{1},1,2},B={1,{2}},试计算
(1)A∩B
(2)A∪B(3)A(A∩B).
(1)A∩B={1}(4分)
(2)A∪B={1,2,{1},{2}}(8分)
(3)A(A∩B)={{1},2}(12分)
17.图G=<
,其中V={a,b,c,d},E={(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)},对应边的权值依次为1、2、3、1、4及5,试
(1)画出G的图形;
(2)写出G的邻接矩阵;
(3)求出G权最小的生成树及其权值.
(1)G的图形表示如图一所示:
(3)最小的生成树如图二中的粗线所示:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 电大 历年 离散数学 试题 汇总