离散数学南昌大学软件学院试卷(软件工程)(2)复习进程
- 格式：doc
- 大小：143.00 KB
- 文档页数：10
离散数学南昌大学软件学院试卷(软件工程)(2) 2007 ～ 2008学年第一学期《离散数学》期末试卷（B）
年级专业 班级 学号 姓名____________
题号 一 二 三 四 总分
得分
适用年级专业：2006级软件工程专业
试卷说明：闭卷考试，考试时间120分钟
一．判断题（共10小题，每题1分，共10分）
在各题末尾的括号内画表示正确，画表示错误：
1．设p、q为任意命题公式，则(pq)p p ( )
2．x(F(y)G(x)) F(y)xG(x)。 ( )
3．初级回路一定是简单回路。 ( )
4．自然映射是双射。 ( )
5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。
( )
6．群的运算是可交换的。 ( )
7．自然数集关于数的加法和乘法
8．若无向连通图G中有桥，则G的点连通度和边连通度皆为1。
( ) 9．设A={a,b,c},则A上的关系R={
10．设A、B、C为任意集合，则A(BC)=(AB)C。 ( )
二、填空题（共10题，每题3分，共30分）
11．设p：天气热。q：他去游泳。则命题“只有天气热，他才去游泳”可符号
化为 。
12．设M(x)：x是人。S(x)：x到过月球。则命题“有人到过月球”可符号
化为 。
13． pq的主合取范式是 。
14．完全二部图Kr,s（r < s）的边连通度等于 。
15．设A={a,b}，,则A上共有 个不同的偏序关系。
16．模6加群
17．设A={1,2,3,4,5}上的关系R={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>}，则R的传递闭包t(R) = 。.
18．已知有向图D的度数列为(2,3,2,3)，出度列为(1,2,1,1)，则有向图D的入度列为 。
19．n阶无向简单连通图G的生成树有 条边。
20．7阶圈的点色数是 。
三、运算题（共5小题，每小题8分，共40分） 21．求xF(x)yG(x,y)的前束范式。
22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G的顶点数。
23．设A={a,b,c,d,e,f}，R=IA{
24．求图示带权图中的最小生成树，并计算最小生成树的权。
25．设R*为正实数集，代数系统< R*,+>、< R*,·>、< R*,/>中的运算依次为普通加法、乘法和除法运算。试确定这三个代数系统是否为群？是群者，求其单位元及每个元素的逆元。
四、证明题（共3小题，共20分）
26 （8分）在自然推理系统P中构造下述推理的证明：
前题：p(qr)，sq， ps 结论：r
27 （6分）设
28．（6分）设G是n(3)阶m条边、r个面的极大平面图，则r=2n-4。
2007-2008学年第一学期《离散数学》期末试卷（B） 答 案
适用年级专业：2006级软件工程专业
试卷说明：闭卷考试，考试时间120分钟
一．判断题（共10小题，每题1分，共10分）
在各题末尾的括号内画表示正确，画表示错误：
1． () 2． () 3． () 4． () 5． ()
6． () 7． () 8． () 9． () 10． ()
二、填空题（共10题，每题3分，共30分）
11． qp 12．x(M(x) S(x))
13．(pq) (pq) 14． r
15． 3 16． 3
17．.R 18．（1,1,1,2）
19． n-1 20． 3
三、运算题（共5小题，每小题8分，共40分）
21．解：xF(x)yG(x,y) xF(x)yG(w,y)
x(F(x)yG(w,y))
xy (F(x) G(w,y))
22．解：设图G有n个顶点m条边，则
2m=2(2+3)+4(n-4)，即22=10+4(n-4)
解之得n=7。
23．解：[a]R={a,b}，[c]R={c}，[d]R={d}，[e]R={e}，[f]R={f}， A/R={{a,b},{c},{d},{e},{f}}
24．解：最小生成树T如图中红线所示，W(T) = 12
25． 解：仅< R*,·>是群。其单位元为1。任意x R*，其逆元为1/x。
四、证明题（共3小题，共20分）
26 证明：① ps 前提引入
② p ①，化简
③ p(qr) 前提引入
④ qr ②③，假言推理
⑤ s ①，化简
⑥ sq 前提引入
⑦ q ⑤⑥，假言推理
⑧ r ④⑦，析取三段论
27 （6分）证：设e是G的单位元，gG, eg=ge，所以eH,故H非空。
（1）a,bH, gG，有ag=ga, bg=gb,那么
(ab)g=a(bg)= a(gb)=(ag)b=(ga)b=g(ab)
所以abH。 （2）aH, gG，有ag=ga，a-1G。
a-1g=a-1ge=a-1gaa-1= a-1(ga)a-1=a-1(ag)a-1
=(a-1a)ga-1=ega-1=ga-1
所以，a-1H。
根据子群判定定理一，H是G的子群。
28．（6分）证：极大平面图一定是连通图，由欧拉公式
r=2+m-n ………….(1)
又因为极大平面图每面的次数皆为3，从而
2m=3r……………….(2)
由(1)、(2)式联立解得
r=2n-4。
