天津大学研究生考试离散数学试卷及答案解析(4页).doc
-天津大学研究生考试离散数学试卷及答案解析-第 3 页天津理工大学 2007 年硕士研究生入学复试试题考试科目：离散数学 共 页 第 页 一、填空题（每空1分，共25分）1无向图G具有一条欧拉回路，当且仅当G是 ，并且所有结点的度数都是 。设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统<Z,*>的幺元是 ，零元是 。3某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是 ，其关系矩阵是 。4一个格称为布尔代数，如果它是_格和_格.设B,，0，1是布尔代数，对任意的aB,有aa=_, aa=_。5谓词公式(x)( y)（P(x,y)R(y)）Q(y)，则其约束变元是_，自由变元是_。6设G是n个结点m条边的连通平面图，则当n3时必有 成立。7设命题公式A的真值表为PQR000001010011100101110111A00101100则命题公式A的主析取范式（编码形式）为 。 8一棵有6个叶结点的完全二叉树，有_个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_个叶结点。9在一棵根树中，有且只有一个结点的入度为_，其余所有结点的入度均为_。10设图G1=，如果 ，则称G2是G1的子图，如果 ，则称G2是G1的生成子图。11设图G的邻接矩阵为M=，则G的可达性矩阵为_ _. 12在偏序集<Z,>中，其中Z=1,2,3,4,6,8,12,14，是Z中的整除关系，则集合D=2,3,4,6的极大元是 ，极小元是 ，上确界是 ，下确界是 。 二、单项选择题（每小题2分，共20分） 1设N为自然数集(含0)，函数F：NN×N,F(n)=<n,n+1>是( )。(1)满射，不是入射； (2)入射，不是满射；(3)双射； (4)不是入射，不是满射设和是集合上的任意两个关系，则下列命题为真的是（ ）(1)若和是自反的，则也是自反的；(2)若和是非自反的，则也是非自反的；天津理工大学 2007 年硕士研究生入学复试试题考试科目：离散数学 共 页 第 页 (3)若和是对称的，则也是对称的；(4)若和是传递的，则也是传递的下面哪个偏序集构成有界格（ ）(1)；(2)，其中为整除关系；(3)；(4)；其中，为的幂集设个体域是正整数集，则下列公式中真值为真的公式是( )(1)(x)(y)(x·y=0) (2) (x)(y)(x·y=1)(3)( x)(y)(x·y=2) (4)(x)(y)(z)(x-y=z)设P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）(1)PQ； (2)PQ； (3)PQ； (4)PQ设<A,*,>是环，则下列正确的是（ ）(1)<A,>是交换群； (2)<A,*>是加法群；(3)对*是可分配的； (4)*对是可分配的设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ）(1)2个面；(2)4个面；(3)3个面； (4)5个面下面哪个哈斯图构成分配格（）设完全二叉树有片叶子。条边，则有（）(1)>2(t-1)；(2)e<2(t-1)；(3)e=2(t-1)；(4)e=2(t+1)10下列各图是平面图的是( )三、简答题（每小题6分，共30分）1设A=a,b,c ，P（A）是A的幂集，是集合对称差运算。已知<P(A),>是群。在群<P(A),>中，找出其幺元。找出任一元素的逆元。求元素x使满足ax=b。设有6个城市V1，V2，V6，它们之间有输油管连通，其布置如下图,Si(数字)中Si为边的编号，括号内数字为边的权，它是两城市间的距离，为了保卫油管不受破坏，在每段油管间派一连士兵看守，为保证每个城市石油的正常供应最少需多少连士兵看守?天津理工大学 2007 年硕士研究生入学复试试题考试科目：离散数学 共 页 第 页 输油管道总长度越短，士兵越好防守。求他们看守的最短管道的长度。(要求写出求解过程)公安人员审理某珠宝商店的钻石项链的失窃案，已知侦察结果如下：（1）营业员A或B盗窃了钻石项链（2）若B作案，则作案时间不在营业时间（3）若A提供的证词正确，则货柜未上锁（4）若A提供的证词不正确，则作案发生在营业时间（5）货柜上了锁试问：作案者是谁？要求写出推理过程。设=1,2,4,6,8,12,18,72,”/”为A上的整除关系,(1)说明，是否为偏序集，若是，画出其哈斯图；(2)说明，是否为格？为什么？(3)说明，是否构成布尔代数？为什么？求命题公式 (PQ)R)P的主析取范式和主合取范式。四证明题（共25分） （8分）设Q是有理数集，在Q×Q定义运算为 ,b,y=ax,ay+b，(1)证明Q×Q,是独异点；(2)Q×Q中元素,b是否有逆元，若有，求出,b的逆元（6分）证明当每个结点的度数大于等于3时，不存在有7条边的连通简单平面图。 （6分）符号化下列命题并推证其结论任何人如果他喜欢音乐,他就不喜欢体育每个人或者喜欢体育，或者喜欢美术有的人不喜欢美术因而有的人不喜欢音乐（设M(x)：x喜欢音乐，S(x)：x喜欢体育，(x)：喜欢美术）4（分）设R是集合A上的自反、传递的二元关系，又设T也是A上的二元关系，且满足：。求证：T是A上的等价关系。
