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

天津理工大学 2007 年硕士研究生入学复试试题

考试科目：离散数学 共 ３ 页 第 １ 页

一、填空题（每空1分，共25分）

1．无向图G具有一条欧拉回路，当且仅当G是 ，并且所有结点的度数都是 。

２．设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统的幺元是 ，零元是 。 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的真值表为 P 0 0 0 0 1 1 1 1 Q 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 A 0 0 1 0 1 1 0 0

则命题公式A的主析取范式（编码形式）为 。 8．一棵有6个叶结点的完全二叉树，有____个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。

9．在一棵根树中，有且只有一个结点的入度为_____，其余所有结点的入度均为_____。 10．设图G1=V1,E1,G2?V2,E2,且E2?E1，如果 ，则称G2是G1的子图，如果 ，则称G2是G1的生成子图。

?011??11011．设图G的邻接矩阵为M=???，则G的可达性矩阵为____ __.

??100??12．在偏序集中，其中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)=是( )。

(1)．满射，不是入射； (2)．入射，不是满射； (3)．双射； (4)．不是入射，不是满射．

２．设R1和R2是集合Ａ上的任意两个关系，则下列命题为真的是（ ）． (1)．若R1和R2是自反的，则R1?R2也是自反的； (2)．若R1和R2是非自反的，则R1?R2也是非自反的；

1

天津理工大学 2007 年硕士研究生入学复试试题

考试科目：离散数学 共 ３ 页 第 ２ 页 (3)．若R1和R2是对称的，则R1?R2也是对称的； (4)．若R1和R2是传递的，则R1?R2也是传递的．

３．下面哪个偏序集构成有界格（ ）．

(1)．?N,??； (2)．??2,3,4,6,12?,／?，其中／为整除关系；

(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． ６．设是环，则下列正确的是（ ）．

(1)．是交换群； (2)．是加法群； (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的幂集，?是集合对称差运算。已知是群。在群中，①找出其幺元。②找出任一元素的逆元。③求元素x使满足{a}?x={b}。 ２．设有6个城市V1，V2，…，V6，它们之间有输油管连通，其布置如下图,Si(数字)中Si为边的编号，括号内数字为边的权，它是两城市间的距离，为了保卫油管不受破坏， 在每段油管间派一连士兵看守，为保证每个城市石油的正常供应最少需多少连士兵看守?

2

天津理工大学 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上的二元关系，且满足：x,y?T?x,y?R?y,x?R。求证：T是A上的等价关系。

3