离散数学南昌大学软件学院试卷(软件工程)(2)

2007～2008学年第一学期《离散数学》期末试卷（B）年级专业班级学号姓名____________题号一二三四总分得分适用年级专业：2006级软件工程专业试卷说明：闭卷考试，考试时间120分钟一．判断题（共10小题，每题1分，共10分）在各题末尾的括号内画表示正确，画表示错误：1．设p、q为任意命题公式，则(pq)pp()2．x(F(y)G(x))F(y)xG(x)。()3．初级回路一定是简单回路。()4．自然映射是双射。()5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。()6．群的运算是可交换的。()7．自然数集关于数的加法和乘法N，+，构成环。()8．若无向连通图G中有桥，则G的点连通度和边连通度皆为1。()9．设A={a,b,c},则A上的关系R={a,b,a,c}是传递的。()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（rs）的边连通度等于。15．设A={a,b}，,则A上共有个不同的偏序关系。16．模6加群Z6，中，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{a,b,b,a}，则R是A上的等价关系。求等价类[a]R、[c]R及商集A/R。24．求图示带权图中的最小生成树，并计算最小生成树的权。25．设R*为正实数集，代数系统R*,+、R*,·、R*,/中的运算依次为普通加法、乘法和除法运算。试确定这三个代数系统是否为群？是群者，求其单位元及每个元素的逆元。四、证明题（共3小题，共20分）26（8分）在自然推理系统P中构造下述推理的证明：前题：p(qr)，sq，ps结论：r27（6分）设G,是群，H={a|aGgG，ag=ga},则H,是G的子群。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．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分，共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．解：[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．解：仅R*,·是群。其单位元为1。任意xR*，其逆元为1/x。四、证明题（共3小题，共20分）26证明：①p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。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-1H。根据子群判定定理一，H是G的子群。28．（6分）证：极大平面图一定是连通图，由欧拉公式r=2+m-n………….(1)又因为极大平面图每面的次数皆为3，从而2m=3r……………….(2)由(1)、(2)式联立解得r=2n-4。