天津大学研究生考试离散数学试卷及答案解析

1天津理工大学2007年硕士研究生入学复试试题考试科目：离散数学共３页第１页一、填空题（每空1分，共25分）1．无向图G具有一条欧拉回路，当且仅当G是，并且所有结点的度数都是。２．设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统Z,*的幺元是，零元是。3．某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是，其关系矩阵是。4．一个格称为布尔代数，如果它是______格和______格.设〈B,∧,∨,′，0，1〉是布尔代数，对任意的a∈B,有a∨a′=____,a∧a′=______。5．谓词公式(x)(y)（P(x,y)∨R(y)）→Q(y)，则其约束变元是________，自由变元是________。6．设G是n个结点m条边的连通平面图，则当n≥3时必有成立。7．设命题公式A的真值表为PQR000001010011100101110111A00101100则命题公式A的主析取范式（编码形式）为。8．一棵有6个叶结点的完全二叉树，有____个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。9．在一棵根树中，有且只有一个结点的入度为_____，其余所有结点的入度均为_____。10．设图G1=1222211EE,E,VG,E,V且，如果，则称G2是G1的子图，如果，则称G2是G1的生成子图。11．设图G的邻接矩阵为M=001011110，则G的可达性矩阵为______.12．在偏序集Z,≤中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除关系，则集合D={2,3,4,6}的极大元是，极小元是，上确界是，下确界是。二、单项选择题（每小题2分，共20分）1．设N为自然数集(含0)，函数F：N→N×N,F(n)=n,n+1是()。(1)．满射，不是入射；(2)．入射，不是满射；(3)．双射；(4)．不是入射，不是满射．２．设1R和2R是集合Ａ上的任意两个关系，则下列命题为真的是（）．(1)．若1R和2R是自反的，则1R2R也是自反的；(2)．若1R和2R是非自反的，则1R2R也是非自反的；2天津理工大学2007年硕士研究生入学复试试题考试科目：离散数学共３页第２页(3)．若1R和2R是对称的，则1R2R也是对称的；(4)．若1R和2R是传递的，则1R2R也是传递的．３．下面哪个偏序集构成有界格（）．(1)．,N；(2)．,12,6,4,3,2／，其中／为整除关系；(3)．,Z；(4)．),(A；其中Ａ＝｛ａ，ｂ，ｃ｝，)(A为Ａ的幂集．４．设个体域是正整数集，则下列公式中真值为真的公式是()．(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)．P→┐Q；(2)．P∨┐Q；(3)．P∧Q；(4)．P∧┐Q．６．设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)．e2(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使满足{a}x={b}。２．设有6个城市V1，V2，…，V6，它们之间有输油管连通，其布置如下图,Si(数字)中Si为边的编号，括号内数字为边的权，它是两城市间的距离，为了保卫油管不受破坏，在每段油管间派一连士兵看守，为保证每个城市石油的正常供应最少需多少连士兵看守?3天津理工大学2007年硕士研究生入学复试试题考试科目：离散数学共３页第３页输油管道总长度越短，士兵越好防守。求他们看守的最短管道的长度。(要求写出求解过程)３．公安人员审理某珠宝商店的钻石项链的失窃案，已知侦察结果如下：（1）营业员A或B盗窃了钻石项链（2）若B作案，则作案时间不在营业时间（3）若A提供的证词正确，则货柜未上锁（4）若A提供的证词不正确，则作案发生在营业时间（5）货柜上了锁试问：作案者是谁？要求写出推理过程。４．设Ａ={1,2,4,6,8,12,18,72},”/”为A上的整除关系,(1)．说明〈Ａ，／〉是否为偏序集，若是，画出其哈斯图；(2)．说明〈Ａ，／〉是否为格？为什么？(3)．说明〈Ａ，／〉是否构成布尔代数？为什么？５．求命题公式((P∨Q)→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上的二元关系，且满足：Rx,yRy,xTy,x。求证：T是A上的等价关系。