离散数学期末考试题.doc

-装 订 线-上 海 海 事 大 学 试 卷2010 2011 学年第一学期期末考试 离散数学 （A卷）班级 学号 姓名 总分 题 目得 分阅卷人1.(5)2.(6)在150位学生中，有109位同学在PASCAL,BASIC,C+中至少学习一门。假设45人学BASIC，61人学PASCAL，53人学C+，18人学BASIC和PASCAL，15人学BASIC和C+，23人学PASCAL和C+。(a)多少人三门语言都学？(b)多少人只学BASIC?(c)多少人一门都不学？3.(5)已知前提为：结论为：给出逻辑推理的过程。4.(6)设B=1,2,3,4,5，A=BB,定义A上的关系R如下：(u,v)R(x,y)当且仅当u-v=x-y.(a) 证明R是等价关系。(b) 找出(2,3).（c）计算A/R.5.(6)设定义f:ST如下：(a) 证明f是单射的。(b) 证明f是满射的。(c) f有反函数吗？若有的话，求出反函数。(d) 写出的表达式和他的定义域和值域。(e) 是单射的吗？说明原因。6.(5)设A=a,b,c,d且A上的关系R的矩阵如下(a) 证明R是偏序关系。(b) 画出R的哈斯图。7.(6)设D105代表正整数105的所有正约数的集合上由整除关系构成的格。(a) 画出此格的哈斯图。(b) 写出每个元素的补元素(c) 此格是否布尔代数？写出它的原子集合。8.(6)布尔函数的真值表如下：xyzf(x,y,z)00000010010101101001101111011110写出f对应的析取范式并尽量化简。9.(5)完成下表使得二元运算满足交换律和幂等率。*abcacbcb10.(5)设G是一个群，幺元是e. 证明若G中存在x使得x2=x，则x=e.11.(5)设f是G1到G2的满同态，G2是阿贝尔群。证明ker(f)包含了G1中所有形式为的元素，其中a,b是G1中的任意元素。12.(6)设S=1,-1,i,-i,且G=(S,普通复数乘法)(a) 证明H=1，-1是G的子群。(b) 确定H的所有左陪集。(c) 证明G和Z4同构13.(6)有8个元素的群G的乘法表如下：eijkmnopeeijkmnopiijkepomnjjkeinmpokkeijopnmmmonpejiknnpmojekioonpmkiejppmonikje(a) 写出G中阶数是2的元素。(b) 写出G中具有4个元素的子循环群及其生成元。(c) 写出一个G中具有4个元素的非循环子群。(d) 列出G的所有3阶子群。如果没有的话说明理由。14.(6)已知简单有向图G=如下图所示：v1v5v3v2v4(a) 用矩阵运算的方法找出所有长度为2的路。(b) 用Warshall方法求出可达矩阵，再根据可达矩阵求图G的强分图。15.(6)一个艺术展览安排在如下图所示的5个房间中（图中已标注）。是否有一条路恰好经过每个门一次看完展览？如果有的话，在下图上描出路径。1234516.(5)画出K5中的没有公共边的两个汉密尔顿回路，17.(6)一颗根树(T,v0)如下图所示：v0v1v3v2v4v5v10v6v7v8v9(a) T的高度是多少？(b) 列出T的树叶。(c) 包含v4的子树有多少？(d) 列出v7的兄弟节点。(e) 把T转化成二叉树。18.(5)用Kruskal算法求出下图的最小生成树。按照选择次序列出生成树的各条边。ACEDGBF465442334752参考答案1. (a) 1,2,3,4,.(b) , -3,-2,-1,0B.(c) 2,4(d) A(e) (2,6,10,14,)2(a) 6.(b) 18.(c) 41.3.4.(a)u-v=u-v,(u,v)R(u,v),即R是自反的。如果(u,v)R(x,y),则u-v=x-y,即x-y=u-v,故(x,y)R(u,v),所以R是对称的。如果(u,v)R(x,y)且(x,y)R(w,z),则u-v=x-y=w-z,故(u,v)R(w,z),所以R是传递的。(b)(2,3)=(2,3),(1,2),(3,4),(4,5).(c)A/R=(2,3),(2,4),(2,5),(2,2),(2,1),(3,1),(4,1),(5,1),(1,5)【注：代表元素不必相同，但须写够9个等价类】5.(a)设f(x1)=f(x2),则，x1+1=x2+1,即x1=x2.(b)任意yT，y0,所以存在x=y2-1S,且f(x)=.(c)由(a)和(b)可知，f是双射函数。f-1(x)=y2-1,yT.(d)(e)是单射的。因为f是单射的，所以x1x2时，f(x1)f(x2)，因此f(f(x1)f(f(x2).6.(a)因为MR的主对角线元素全为1，所以R自反。因为mij=1时，mji=0，所以R是反对称的。【此处要有运算过程】，所以R是传递的。(b)哈斯图如下：cdab7.(a)哈斯图如下：1375152135105(b)1=105;3=35;5=21;7=15;15=7;21=5;35=3;105=1.(c)因为此格和同构，所以是布尔代数。原子集合A=3,5,7.8.析取范式是，化简后的表达式为：。9.*abcaacbcbbcbc其中表示同时为a,b或c均可.10.设x2=x，则x-1(xx)=x-1x,即(x-1x)x=e，所以x=e.11.考虑f(aba-1b-1)=f(a)f(b)f(a-1)f(b-1)=f(a)f(a-1)f(b)f(b-1) =f(a)(f(a)-1f(b)(f(b)-1=ee=e【e是G2的幺元】.所以 aba-1b-1|a,bG1ker(f).12.(a) H=1,-1关于复数乘法是封闭的，所以H是子群。(b)H的左陪集有两个，1,-1和i,-i.(c)G和Z4是同构的。定义双射函数如下：f:GZ4使得f(1)=0,f(i)=1, f(-1)=2, f(-i)=3,比较两个运算表表明f是保持运算的。13.(a)j,m,n,o,p(b)只有一个：=e,i,j,k.(c)符合要求的子群有两个：e,j,m,n和e,j,o,p(d)没有3个元素的子群，因为3不能整除8.【依据是拉格朗日定理】14.(a)G的邻接矩阵A为：故长度为2的路径共有8条。【不具体列出亦可】(b)由Warshall算法获得可达矩阵如下：，所以强分图为：G1=v1,v2,v3;G2=v4,v515.有欧拉路，但没有欧拉回路。路径如下所示：【有多种走法，只要