资源描述:
《离散数学期末试卷及答案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、一.判断题(共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.群的运算是可交换的。()7.自然数集关于数的加法和乘法构成环。()8.若无向连通图G中有桥,则G的点连通度和边连通度皆为1。()9.设A={a,b,c},则A上的关系R={,}是传递的。()10.设A、B、C为任意集合,则A
2、´(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中,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
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È{,},则R是A上的等价关系。求等价类[a]R、[c]R及商集A/R。24.求图示带权图中的最小生成树,并计算最小生成树的权。25.设R*为正实数集,代数系统、、中的运算依
4、次为普通加法、乘法和除法运算。试确定这三个代数系统是否为群?是群者,求其单位元及每个元素的逆元。四、证明题(共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个面的极大平面图,则r=2n-4。适用年级专业:2006级软件工程专业试卷说明:闭卷考试,考试时间120分钟一.判断题(共10小题,每题1分,共10分)在各题末尾的括号内画P表示正确,画Í表示错误:1.(P)2.(
6、Í)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分,共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。2
7、3.解:[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ÙØ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Î
8、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)又因