资源描述
第 页 共 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，那么复合函数：=_ _。5. 已知命题公式( pq)(rT)，则它的对偶式为 。6. 设 F(x): x 是人，H(x,y)：x 与 y 一样高，则命题“不是所有的人都一样高”的符号化形式为 。7.设 A=3,6,9，集合 A 上的二元运算定义为： ab = 第 页 共 3 页 2mina,b，则集合 A 上运算的零元是_ _。8. 整数集 Z 中的运算*定义如下：a*b=a+b+3 ab，设 a 有逆元，则其逆元 a-1 为_ _。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如图所示为邮递员负责的街区图（长度单位为百米） ，邮局位于 V1 处，试设计一条邮递员的最短投递路线。 （5 分）V2V131 V3V6 V4V521V73111313171 1161511121第 页 共 3 页 36.已知函数 f： XY ， g：Y X，且复合关系 gf 为 X 上的恒等函数。证明 f 是单射函数，g 是满射函数。 （10 分）7.给定环，且 S R，S 定义为： S=a+b | a,b Q2其中 R 和 Q 分别为实数集和有理数集，+和分别为算术加法和乘法。试证明：是的子环。 （10 分）8设 G 是有 n 个结点和 m 条边连通的简单平面图，其中 n3，且 G 中没有长度为 3 的回路。证明 m2n-4。并依此证明 K3,3 不是平面图。 （10 分）9. 采用谓词逻辑推理理论证明：每个考生或者是勤奋的或者是聪明的，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。 （15 分）
展开阅读全文