离散数学南昌大学软件学院试卷(软件工程)(2)复习进程.doc

《离散数学南昌大学软件学院试卷(软件工程)(2)复习进程.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、离散数学南昌大学软件学院试卷(软件工程)(2)2007～2008学年第一学期《离散数学》期末试卷（B）年级专业班级学号姓名____________题号一二三四总分得分适用年级专业：2006级软件工程专业试卷说明：闭卷考试，考试时间120分钟一．判断题（共10小题，每题1分，共10分）在各题末尾的括号内画P表示正确，画Í表示错误：1．设p、q为任意命题公式，则(pÙq)ÚpÛp()2．"x(F(y)®G(x))ÛF(y)®$xG(x)。()3．初级回路一定是简单回路。()4．自然映射是双射。()5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。()6．群的运算是可交换的。()

2、7．自然数集关于数的加法和乘法构成环。()8．若无向连通图G中有桥，则G的点连通度和边连通度皆为1。()9．设A={a,b,c},则A上的关系R={,}是传递的。()10．设A、B、C为任意集合，则A´(B´C)=(A´B)´C。()二、填空题（共10题，每题3分，共30分）11．设p：天气热。q：他去游泳。则命题“只有天气热，他才去游泳”可符号化为。12．设M(x)：x是人。S(x)：x到过月球。则命题“有人到过月球”可符号化为。13．p«q的主合取范式是。14．完全二部图Kr,s（r

3、偏序关系。16．模6加群中，4是阶元。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È{

4、,}，则R是A上的等价关系。求等价类[a]R、[c]R及商集A/R。24．求图示带权图中的最小生成树，并计算最小生成树的权。25．设R*为正实数集，代数系统、、中的运算依次为普通加法、乘法和除法运算。试确定这三个代数系统是否为群？是群者，求其单位元及每个元素的逆元。四、证明题（共3小题，共20分）26（8分）在自然推理系统P中构造下述推理的证明：前题：p®(qÚr)，Øs®Øq，pÙØs结论：r27（6分）设是群，H={a

5、aÎGÙ"gÎG，a*g=g*a},则是G的子群。28．（6分）设G是n(³3)阶m条边、r个面

6、的极大平面图，则r=2n-4。2007-2008学年第一学期《离散数学》期末试卷（B）答案适用年级专业：2006级软件工程专业试卷说明：闭卷考试，考试时间120分钟一．判断题（共10小题，每题1分，共10分）在各题末尾的括号内画P表示正确，画Í表示错误：1．(P)2．(Í)3．(P)4．(Í)5．(Í)6．(Í)7．(Í)8．(P)9．(P)10．(Í)二、填空题（共10题，每题3分，共30分）11．q®p12．$x(M(x)ÙS(x))13．(ØpÚq)Ù(pÚØq)14．r15．316．317．.R18．（1,1,1,2）19．n-120．3三、运算题（共5小题，每小题8分，共4

7、0分）21．解：$xF(x)®$yG(x,y)Û$xF(x)®$yG(w,y)Û"x(F(x)®$yG(w,y))Û"x$y(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)=1225．解：仅是群。其单位元为1。任意xÎR*，其逆元为1/x。四、证明题（共3小题，共20分）26证明：①p

8、ÙØs前提引入②p①，化简③p®(qÚr)前提引入④qÚr②③，假言推理⑤Øs①，化简⑥Øs®Øq前提引入⑦Øq⑤⑥，假言推理⑧r④⑦，析取三段论27（6分）证：设e是G的单位元，"gÎG,e*g=g*e，所以eÎH,故H非空。（1）"a,bÎH,"gÎG，有a*g=g*a,b*g=g*b,那么(a*b)*g=a*(b*g)=a*(g*b)=(a*g)*b=(g*a)*b=g*(a*b)所以a*bÎH。（2）"aÎH,"gÎG，有a*g=g*a，a-1ÎG