2020年北京化工大学博士研究生初试样题离散数学.pdf
第页共 3 页 1 北京化工大学 攻读博士学位研究生入学考试 离散数学样题 注意事项 1 答案必须写在答题纸上,写在试卷上均不给分。 2 答题时可不抄题,但必须写清题号。 3 答题必须用蓝、黑水笔或圆珠笔,用红色笔或铅笔均 不给分。 一、填空题(共 20 分,每小题 2 分 ) 1. 已知集合A 是由 6 个元素组成的集合, 那么集合A 上可以产生 个不同的划分。 2.已知集合A= , ,则A 的幂集 (A) = 。 3. 已知集合A =a,b,c ,d , A 上的二元关系R , , ,,则 R -1 = _ _。 4.设f (x )=2-x ,g(x )=2x 2 +1,那么复合函数: () ( ) f gx = _ _ _ _。 5. 已知命题公式 (p q)(r T) ,则它的对偶式 为 。 6.设F (x ) :x 是人,H (x ,y ) :x 与y 一样高,则命题“不是所有的 人都一样高”的符号化形式 为 。 7.设A =3 ,6,9, 集合A 上的二元运算 定义为: a b =m i n a,b, 则集合A 上运算的零元是_ _。 8. 整数集 Z 中的运算 *定义如下:a*b=a+b+3ab,设 a 有逆元, 则 其逆元a -1 为_ _。第页共 3 页 2 9.无向图G 的结点数n 和边数m 相等, 2 度和 3 度结点各 2 个, 其余结点均为悬挂点,则G 的边数m =_ _。 10.设T 是各边带权均为a 的带权图G = 的一棵最小生成树, 则其树权W (T )= _ _。 二、计算与证明题(共 80 分) 1求下面公式的主析取范式和主合取范式: (10 分) (p(qr ) (p(qr ) 2设T 是无向树,它有 40 个 1 度结点, 20 个 2 度结点,31 个 3 度结点, 且没有 6 度或 6 度以上结点, 问T 中有多少个 4 度结点, 多少个 5 度结点?说明理由。 (10 分) 3 把 2n 个人分成n 组,每组 2 人,求不同的分法数。 (5 分) 4求 1500 之间能被 3,5,7 中任一数整除的整数个数。 (5 分) 5 如图所示为邮递员负责的街区图(长 度单位为百米 ) ,邮局位 于V 1 处,试设计一条邮递员的最短投递路线。 (5 分) 6.已知函数f : X Y , g:Y X , 且复合关系g f 为X 上的恒等函 数。证明f 是单射函数,g 是满射函数。 (10 分) 7.给定环 ,且S R ,S 定义为: S=a+b 2 |a,b Q V 2 V 1 3 V 3 V 6 V 4 V 5 2 V 7 3 1 3 3 7 1 6 5 1 2第页共 3 页 3 其中 R 和 Q 分别为实数集和有理数集, + 和分别为算术加法和 乘法。试证明: 是 的子环。 (10 分) 8 设G 是有n 个结点和m 条边连通的简单平面 图,其中n 3 , 且 G 中没有长度为 3 的回路。证明m 2n-4 。并依此证明K 3 , 3 不 是平面图。 (10 分) 9. 采用谓词逻辑推理理论证明:每个考生或者是勤奋的或者是聪 明的,所有勤奋的人都将有所作为,但并非所有考生都将有所作 为,所以,一定有些考生是聪明的。 (15 分)