离散数学期末考试试题(配答案).pdf

该【离散数学期末考试试题(配答案) 】是由【南】上传分享，文档一共【5】页，该文档可以免费在线阅读，需要了解更多关于【离散数学期末考试试题(配答案) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。技术师学院
模拟试题
科目:离散数学
考试形式:闭卷考试时间:120分钟
系别、班级::学号:
〔每题2分,共10分〕
xP(x)xQ(x)的前束式是__∃x∃yP(x)∨Q(y)__________。
1,2,3,4,5,A1,2,3,B2,5,那么A∩B=__{2}__,A_{4,5}____,
AB__{1,3,4,5}_____
a,b,c,Ba,b,那么(A)(B)__{{c},{a,c},{b,c},{a,b,c}}__________,
(B)(A)_____Φ_______。
〔N,+〕中,其单位元是0,仅有_1___有逆元。
,e条边,那么G有___e+2-n____个面。
〔每题2分,共10分〕
(QR)等价的公式是〔〕
〔A〕(PQ)R〔B〕(PQ)R〔C〕P(QR)〔D〕P(QR)
a,b,c,A上的二元关系Ra,a,b,b不具备关系()性质
(A)(A)传递性(B)反对称性(C)对称性(D)自反性
V,E中,结点总度数与边数的关系是()
(A)deg(v)2E(B)deg(v)E(C)deg(v)2E(D)deg(v)E
iiii
vVvV
,那么图D的边数为()
(A)n(n1)(B)n(n1)(C)n(n1)/2(D)n(n1)/2
,当且仅当()
(A)G的所有结点的度数都是偶数(B)G的所有结点的度数都是奇数
1/5
(C)G连通且所有结点的度数都是偶数(D)G连通且G的所有结点度数都是奇数。
〔共43分〕
qr的主合取式与主析取式。〔6分〕
解:主合取方式: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)=∑
1000

1011
a,b,c,d上的二元关系R的关系矩阵为M,求
R0000


0001
r(R),s(R),t(R)的关系矩阵,并画出R,r(R),s(R),t(R)的关系图。〔10分〕
3无向图G有12条边,G中有6个3度结点,其余结点的度数均小于3,问G中至少有多少个结
点?〔10分〕
2/5
解:∵G〔V,E〕,|E|=V,d〔Vi〕<3,
设至少有x个节点,由握手定理得:
2×12=∑d〔Vi〕<6×3+(x-6)×3
2<(x-6)=>x>8
故G中至少有9个节点。
4求下面两个图的最小生成树。〔12分〕
(z,)是否为格?说明理由。〔5分〕
解:〔Z,≤〕是格,理由如下:
对于任意a∈Z,a≤a成立,满足自反性;
对于任意a∈Z,b∈Z,假设a≤b且b≤a,那么a=b,满足反对称性;
对于任意a,b,c∈Z,假设a≤b,b≤c,那么a≤c,满足传递性;
而对于任意a,b∈Z,a≤b,b为最小上界,a为最大下界,故〔Z,≤〕是格。
〔注:什么是格?〕
3/5
〔共37分〕
B,(BC)C,(AD)D。〔10分〕
证明:
编号公式依据
〔1〕〔¬B∨C〕∧¬C前提
〔2〕¬B∨C,¬C〔1〕
〔3〕¬B〔2〕
〔4〕A→B〔3〕
〔5〕¬A〔3〕〔4〕
〔6〕¬〔¬A∧D〕前提
〔7〕A∨¬D〔6〕
〔8〕¬D〔5〕〔6〕
,f:RRR,f(a,b)ab,g:RRR,g(a,b)ab。求证:f和g
都是满射,但不是单射。〔10分〕
证明:要证f是满射,即∀y∈R,都存在〔x1,x2〕∈R×R,使f〔x1,x2〕=y,而f〔x1,x2〕
=x1+x2,可取x1=0,x2=y,即证得;
再证g是满射,即∀y∈R,,都存在〔x1,x2〕∈R×R,使g〔x1,x2〕=y,而g〔x1,x2〕=x1x2,
可取x1=1,x2=y,即证得;
最后证f不是单射,f〔x1,x2〕=f〔x2,x1〕取x1≠x2,即证得,同理:g〔x1,x2〕=g
〔x2,x1〕,取x1≠x2,即证得。
,每个结点的度数不是5就是6,求证:G中至少有5个6度结点或6个
5度结点。〔10分〕
证明:设G中至多有4个6度结点且5个5度结点,
∴d〔Vi〕=49不是偶数,
故它不是一个图,矛盾。
4/5
〔下面只供参考,个人答案〕
,期中任意两点间的距离至少是1,那么最多有300对点距离恰好为1。
〔7分〕
证明:设任意两点间的读书和恰好为1,那么满足:
∑d〔Vi〕=2e
d〔Vi〕≤6
∴6×100≥2e
e≤300
故最多只有300条边,即300对点距离恰好为1.
5/5