离散数学期末试卷（A）含答案

2007 ～ 2008学年第学期离散数学期末试卷（A）
年级专业 班级 学号 姓名____________
题号

二
三
四
总分
分





适年级专业：2006级软件工程专业
试卷说明：闭卷考试考试时间120分钟
单项选择题（20题题1分20分）
1．列语句中 命题C
A．年元旦会雪
B．1+110
C．嫦娥号太棒
D．嫦娥奔月神话已成现实
2．p«q合取范式 B
A．(pÚq)Ù(pÚØq) B．(pÚØq)Ù(ØpÚq)
C．(pÚq)Ù(ØpÚØq) D．(pÚq)Ù(ØpÚq)
3．p® q等值命题公式 D
A．ØpÙq B．pÚØq C．pÙØq D．ØpÚq
4．阶逻辑中量词 B
A．1 B．2 C．3 D．4
5．ØxA(x)Û C
A．ØxA(x) B．xØA(x) C．xØA(x) D．xA(x)
6．|A|4|P(A)| C
A．4 B．8 C．16 D．64
7．设ABC意集合集合称差运算具性质 D
A．AÅB BÅA B．(AÅB)ÅC BÅ(AÅC)
C．AÅA Æ D．AÅA A
8．二元关系 B
A．两集合笛卡积 B．序偶集合
C．映射集合 D．
9．面关函数叙述中正确 D
A．函数定满射 B．函数定单射
C．函数满射单射 D．函数特殊关系
10．半群中二元运算定满足 B
A．交换律 B．结合律 C．分配律 D．幂等律
11．环中 二元运算B
A． B．二 C．三 D．四
12．群独异点区 C
A．满足交换律 B．满足结合律
C．元素逆元 D．满足分配律
13．九阶轮图点色数 B
A．2 B．3 C．4 D．9
14．设NQZR分表示非负整数集理数集整数集实数集＋表示数加法面代数系统中 群A
A． B．
C．< Z ＋> D．
15．简单通路没 通路A
A．重复边 B．重复顶点 C．行边 D．环
16．设体域N（非负整数集）列公式真 B
A．y x (xy 1) B．y x (xy x)
C．x y (x+y0) D．x y (x > y)
17．非树定 B
A．正图 B．二部图 C．欧拉图 D．哈密顿图
18．环中 · 运算求满足 B
A．交换律 B．结合律 C．分配律 D．幂等律
19．集合A等价关系 应B
A．集合A子集 B．集合A划分
C．集合AA双射 D．集合AA单射
20．全序关系定 A
A．等价关系 B．偏序关系 C．线序关系 D．整关系
二填空题（10题题2分20分）
11． 设S(x)：x计算机学院学生L(x)：x学离散数学
计算机学院学生学离散数学符号化 ：
__ x(S(x)®L(x)) _____________________________________
12． 设A{abc}A等价关系R{} ÈIA
商集AR____ {{a b} {c}}
13．设B{Æ}幂集P(B) ___________ {Æ{Æ}}
14．xA(x) ÚyB(xy)前束范式____．uv (A(u) ÚB(xv)) xy(A(x) ÚB(uy))
15．设集合A{01}A定义二元运算____16_______
16．设A{1234}A关系R{<13><31><41>}ÈIA
t(R)__ {<13><31><41><43>} ÈIA
17．设函数f：N®Nf x 1函数h：N®Nh(x)x2+1
复合函数foh (x) _______(x 1)2+1
18．完全二部图Krs（r度d(Krs) _____ r ___
19．设棵树42度顶点33度顶点余顶点1度顶点
该树_______5___片树叶
20．命题公式Ø(p®(pÚq))成假赋值__00011011
三运算题（5题题8分40分）
21．求命题公式Ø(pÙØq) Ù (q Ú r)析取范式指出类型
解：Ø(pÙØq) Ù (q Ú r) Û (Øp Ú q ) Ù (q Ú r)
Û (Øp Ù r) Ú q Û (Øp Ù(Ø q Ú q ) Ù r) Ú ((Ø p Ú p ) Ù q Ù(Ø r Ú 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)
该公式满足式
22．设A{abcdef} A偏序关系：
R{} È IA
画出该偏序关系哈斯图求A极元极元元元
解：
极元def极元a元元a
23．设体域D{abc}消阶公式 x（F(x) ®yG(y)）中量词 述解释求真值：F(a) F(b)1 F(c) 0G(a)1 G(b)G(c)0
解：x（F(x) ®yG(y)）Û xF(x) ®yG(y)
Û（F(a) Ú F(b) Ú F(c)）®（G(a) Ú G(b) Ú G(c)）
Û（1 Ú 1 Ú 0）®（1 Ú 0 Ú 0）Û 1 ®1Û1
24．画棵叶带权1233567优二元树T计算树权W(T)
解： W(T) 71
25．设Z整数集合V< Z *>*二元运算定义：
x*yx+yxy
说明V含幺半群群
解：（1）*运算Z封闭：
（2）*运算结合意abcÎZ
a*(b*c) a*(b+cbc) a+ b+cbc a(b+cbc) a+b+cabacbc+abc
(a*b)*c (a+bab)*c a+bab+c (a+bab) c a+b+cabacbc+abc
a*(b*c) (a*b)*c
（3）*运算幺元0
（4）意xÎZx*11*x11零元没逆元
述知< Z *>含幺半群群
四证明题（3题20分）
26（10分）．阶逻辑中构造面推理证明：
前提：x(F(x) ®ØG(x)) x (G(x) Ú R(x))xØR(x)
结：xØF(x)
（10分）证 ① xØR(x) 前提引入
② ØR(c) ①EI
③ x (G(x) Ú R(x)) 前提引入
④ G(c) Ú R(c) ③ UI
⑤ G(c) ②④析取三段
⑥ x(F(x) ®ØG(x)) 前提引入
⑦ F(c) ®ØG(c) ⑥ UI
⑧ ØF(c) ⑤ ⑦拒取式
⑨ xØF(x) ⑧ EG
27（5分）．证明非空集合A关系RS反称RÇS反称
证 取x≠y
ÎRÇSÞÎRÙÎSÞÎRÙÎSÞÎRÇS
RÇS称
28（5分）．图G中恰两奇度顶点证明两奇度顶点必连通
证 反证法假设G中两奇度顶点uv连通uv分处G两连通分支G1G2中G1G2作独立图时均奇度顶点两奇度顶点必连通
2007 ～ 2008学年第学期离散数学期末试卷（A）
答 案
适年级专业：2006级软件工程专业
试卷说明：闭卷考试考试时间120分钟
单项选择题（20题题1分20分）
1C 2B 3D 4B 5C 6C 7D 8B 9D 10B
11B 12C 13B 14A 15A 16B 17B 18B 19B 20A
二填空题（10题题2分20分）
11． x(S(x)®L(x)) 12． {{a b} {c}}
13． {Æ{Æ}} 14．uv (A(u) ÚB(xv)) xy(A(x) ÚB(uy))
15． 16 16． {<13><31><41><43>} ÈIA
17． (x 1)2+1 18． s r
19． 5 20．00011011
三运算题（5题题8分40分）
21．解：Ø(pÙØq) Ù (q Ú r) Û (Øp Ú q ) Ù (q Ú r)
Û (Øp Ù r) Ú q Û (Øp Ù(Ø q Ú q ) Ù r) Ú ((Ø p Ú p ) Ù q Ù(Ø r Ú 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)
该公式满足式
22． 解：
极元def极元a元元a
23． 解：x（F(x) ®yG(y)）Û xF(x) ®yG(y)
Û（F(a) Ú F(b) Ú F(c)）®（G(a) Ú G(b) Ú G(c)）
Û（1 Ú 1 Ú 0）®（1 Ú 0 Ú 0）Û 1 ®1Û1
24． 解： W(T) 71
25． 解：（1）*运算Z封闭：
（2）*运算结合意abcÎZ
a*(b*c) a*(b+cbc) a+ b+cbc a(b+cbc) a+b+cabacbc+abc
(a*b)*c (a+bab)*c a+bab+c (a+bab) c a+b+cabacbc+abc
a*(b*c) (a*b)*c
（3）*运算幺元0
（4）意xÎZx*11*x11零元没逆元
述知< Z *>含幺半群群
四证明题（3题20分）
26（10分）证 ① xØR(x) 前提引入
② ØR(c) ①EI
③ x (G(x) Ú R(x)) 前提引入
④ G(c) Ú R(c) ③ UI
⑤ G(c) ②④析取三段
⑥ x(F(x) ®ØG(x)) 前提引入
⑦ F(c) ®ØG(c) ⑥ UI
⑧ ØF(c) ⑤ ⑦拒取式
⑨ xØF(x) ⑧ EG

27（5分）证 取x≠y
ÎRÇSÞÎRÙÎSÞÎRÙÎSÞÎRÇS
RÇS称
28（5分）
证 反证法假设G中两奇度顶点uv连通uv分处G两连通分支G1G2中G1G2作独立图时均奇度顶点两奇度顶点必连通
文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档