2023年12月25日发(作者：去年小考题数学试卷分数)
天津理工大学 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,G2V2,E2,且E2E1，如果 ，则称G2是G1的子图，如果 ，则称G2是G1的生成子图。
01111011．设图G的邻接矩阵为M=，则G的可达性矩阵为____ __.
10012．在偏序集
二、单项选择题（每小题2分，共20分）
1．设N为自然数集(含0)，函数F：N→N×N,F(n)=
(1)．满射，不是入射； (2)．入射，不是满射；
(3)．双射； (4)．不是入射，不是满射．
２．设R1和R2是集合Ａ上的任意两个关系，则下列命题为真的是（ ）．
(1)．若R1和R2是自反的，则R1R2也是自反的；
(2)．若R1和R2是非自反的，则R1R2也是非自反的；
1
天津理工大学 2007 年硕士研究生入学复试试题
考试科目：离散数学 共 ３ 页 第 ２ 页
(3)．若R1和R2是对称的，则R1R2也是对称的；
(4)．若R1和R2是传递的，则R1R2也是传递的．
３．下面哪个偏序集构成有界格（ ）．
(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)．
(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的幂集，是集合对称差运算。已知
２．设有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,yTx,yRy,xR。求证：T是A上的等价关系。
3
更多推荐
结点,命题,关系,下列,士兵,公式,具有,喜欢
发布评论