1、 第 3次作业 一、判断题（本大题共 20 分，共 10 小题，每小题 2 分） 1. 一个关系可以：既满足对称性，同时也满足反对称性（ ） 2. 连通图的最小生成树不一定是唯一的。 （ ） 3. b, c, a, aa, ac, abb是前缀码。（ ） 4. 欧拉定理的具体内容是：若一个连通图存在 0个或 2个奇数度结点，则该图中存在欧拉路。（ ） 5. 任何合式公式的主析取范式都是唯一的（如果存在的话）（ ）。 6. 设集合 A=a,b,c， A上的二元关系R=,，则 R是等价关系。（ ） 7. 一个群可以有多个等幂元。（ ） 8. 不存在既有欧拉回路又有汉密尔顿回路的图。（ ） 9. 为
2、重言式。（ ） 10. 设是一个代数系统，且集合 A中元素的个数大于 1。如果该代数系统中存在幺元 e和零元 ，则 e 。（ ） 二、单项选择题（本大题共 30分，共 10 小题，每小题 3 分） 1. 以下关系中是等价关系的是（ ） A. 房间之间的相邻关系 B. 三角形的相似关系 C. 朋友关系 D. 函数之间的合成关系 2. 设 G是连通平面图， G中有 6个顶点 8 条边，则 G的面的数目是（） A. 2个面 B. 3个面 C. 4个面 D. 5个面 3. 设无向图 G的边数为 m，结点数为 n，则 G是树等价于（） A. G连通且 m=n+1 B. G连通且 n=m+1 C. G连通
3、且 m=2n D. 每对结点之间至少有一条通路 4. 以下复合命题可以使用合取符号联结的是（ ） A. 我一边散步一边打电话。 B. 我打开门，走了进来。 C. 我和小刘是同事。 D. 如果 1+1=2，当且仅当桌子有 4条腿。 5. 下面哪一个图是树（ ）？ A. B. C. D. 6. 设 X=1,2,3,4,5,6,7,8,9，判定下面哪个是否是 X的划分（ ） A. 1,3,6， 2,8， 5,7,9 B. 1,5,7,2,4,8,9,3,5,6 C. 2,4,5,8,1,9,3,6,7 D. 1,2,3,5,4,6,8,9,3,5 7. 设 A是奇数集合，下列构成独异点的是（ ）。
4、A. B. C. D. 8. 下述集合对所给的二元运算封闭的是（ ）。 A. 正整数集合上的减法运算 B. 在全正实数集合上规定 o为： aob=ab-a-b,(a,bR+) C. 正整数集合上的二元运算 *： x*y=min(x,y) (a,bZ+) D. 全体 nn 实数可逆矩阵集合上的矩阵加法 9. 下列各图是平面图的是（）。 A. B. C. D. 10. 设 P,Q, R是命题公式，则 ( )。 A. P B. Q C. R D. 三、分析题（本大题共 8分，共 1 小题，每小题 8 分） 等值演算法求公式 （ pq ） （ pq ）的主合取范式 四、计算题（本大题共 8分，共 1
5、小题，每小题 8 分） 设 S=1,2,3,4,6,12， D为 S上的整除关系， （ 1）试写出该关系并画出哈斯图； （ 2）设子集 B=2,3,6，试求 B的最大元、最小元、极大元和极小元； （ 3）试求 B的上界、上确界、下界和下确界。 五、作图题（本大题共 6分，共 1 小题，每小题 6 分） 试画出结点数为 3的 （ 1）强连通图 （ 2）单向连通图 （ 3）弱连通图 （ 4）非连通图 六、证明题（本大题共 8分，共 1 小题，每小题 8 分） 构造下面推理的证明。 只要 A曾到过受害者房间并且 11点以前没离开， A就犯了谋杀罪。 A曾到过受害者房间。如果在 11点以前离开，看门人
6、会看见他。看门人没有看见他。所以 A犯了谋杀罪。 七、多项选择题（本大题共 20分，共 5 小题，每小题 4 分） 1. 下述集合对所给的二元运算封闭的是（ ） A. 正整数集合上的减法运算。 B. 正整数集合上的乘法运算。 C. 整数集合上的除法运算。 D. 负整数集合上的加法运算。 2. 设 B=1,2,3,4,5,C=6,7,8,9,10，以下哪些关系是从 B到 C的单 射函数。 （） A. f=, B. f=, C. f=, D. f=, E. f=, 3. 设 Z是整数集合， +是一般加法，则下述函数中哪些是群（ Z， +）的自同态？（ ） A. f(x)=2x B. f(x)=10
7、00x C. f(x)=|x| D. f(x)=0 4. 以下表达方式正确的是：（ ） A. 小明打开箱子并拿出一件衣服。 设 P：小明打开箱子； Q：小明拿出一件衣服。原命题表示为： P Q B. 如 果骑自行车，我就没法按时到校。 设 P：我骑自行车； Q：我按时到校；原命题可表示为： PQ C. 我打开门，走了进来。 设 M：我打开门； N：我走进来。 原命题为： MN D. 小红和小华是好朋友。 设 H：小红是好朋友； J：小华是好朋友；原命题为： H J 5. 设偏序集 的哈斯图如下所示，若 A的子集 B = 2,3,4,则元素为 B的极大元为 ( )。 A. 5 B. 6 C. 3
8、 D. 4 答案： 一、判断题（ 20 分，共 10 题，每小题 2 分） 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 二、单项选择题（ 30 分，共 10 题，每小题 3 分） 1. B 2. C 3. B 4. A 5. D 6. C 7. C 8. C 9. A 10. C 三、分析题（ 8分，共 1 题，每小题 8 分） 0. 参考答案： 解题方案： 评分标准： 四、计算题（ 8分，共 1 题，每小题 8 分） 0. 参考答案： （ 1）哈斯图为： （ 2） B的最大元为 6，最小元为 1，极大元为 6，极小元为 1. （ 3） B的上界为： 6， 12；上确界为 6；下界为： 1，下确界为 1. 解题方案： 评分标准： 五、作图题（ 6分，共 1 题，每小题 6 分） 0. 参考答案： 解题方案： 评分标准： 六、证明题（ 8分，共 1 题，每小题 8 分） 0. 参考答案： 解题方案： 评分标准： 七、多项选择题（ 20 分，共 5 题，每小题 4 分） 1. BD 2. AE 3. ABD 4. BC 5. CD
