上海海事大学2011年1月离散数学期末考试题

1、-装 订 线-上 海 海 事 大 学 试 卷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)

2、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)布尔函数的真值

3、表如下：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的乘法表如下：ei

4、jkmnopeeijkmnopiijkepomnjjkeinmpokkeijopnmmmonpejiknnpmojekioonpmkiejppmonikje(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)