离散数学期末试卷及答案.doc

一判断题（共10小题，每题1分，共10分）在各题末尾的括号内画P表示正确，画表示错误：1设p、q为任意命题公式，则(pq)p p ( )2x(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加群中，4是 阶元。 17设A=1,2,3,4,5上的关系R=,，则R的传递闭包t(R) = 。. 18已知有向图D的度数列为(2,3,2,3)，出度列为(1,2,1,1)，则有向图D的入度列为 。 19n阶无向简单连通图G的生成树有 条边。 207阶圈的点色数是 。 三、运算题（共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,，则R是A上的等价关系。求等价类aR、cR及商集A/R。24求图示带权图中的最小生成树，并计算最小生成树的权。25设R*为正实数集，代数系统、中的运算依次为普通加法、乘法和除法运算。试确定这三个代数系统是否为群？是群者，求其单位元及每个元素的逆元。四、证明题（共3小题，共20分）26 （8分）在自然推理系统P中构造下述推理的证明： 前题：p(qr)，sq， ps结论：r27 （6分）设是群，H=a| aG gG，a*g=g*a,则是G的子群28（6分）设G是n(3)阶m条边、r个面的极大平面图，则r=2n-4。适用年级专业：2006级软件工程专业试卷说明：闭卷考试，考试时间120分钟一判断题（共10小题，每题1分，共10分）在各题末尾的括号内画P表示正确，画表示错误：1 (P) 2 () 3 (P) 4 () 5 ()6 () 7 () 8 (P) 9 (P) 10 ()二、填空题（共10题，每题3分，共30分）11 qp 12$x(M(x) S(x)13(pq) (pq) 14 r15 3 16 317.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) 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解：aR=a,b，cR=c，dR=d，eR=e，fR=f，A/R=a,b,c,d,e,f24解：最小生成树T如图中红线所示，W(T) = 1225 解：仅是群。其单位元为1。任意x R*，其逆元为1/x。四、证明题（共3小题，共20分）26 证明： ps 前提引入 p ，化简 p(qr) 前提引入 qr ，假言推理 s ，化简 sq 前提引入 q ，假言推理 r ，析取三段论27 （6分）证：设e是G的单位元，gG, e*g=g*e，所以eH,故H非空。（1）a,bH, gG，有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*bH。（2）aH, gG，有a*g=g*a，a-1G。a-1*g=a-1*g*e=a-1*g*a*a-1= a-1*(g*a)*a-1=a-1*(a*g)*a-1=(a-1*a)*g*a-1=e*g*a-1=g*a-1所以，a-1H。根据子群判定定理一，