1、 第 2次作业 一、判断题（本大题共 20 分，共 10 小题，每小题 2 分） 1. 设人的集合 A上的朋友关系为 R，则 R是 A上的相容关系（ ） 2. 公式 xP(x) yQ(x,y) 前束范式为 x y(P(x) Q(x,y) （ ） 3. R是 A上的二元关系，当 R是反自反关系时， R的传递闭包也是反自反关系。（ ） 4. 为矛盾式。（ ） 5. 若集合 A上的二元关系 R是对称的， RC一定是对称的。（ ） 6. 交换群必是循环群。（ ） 7. 任何图中必有偶数个度数为奇数的结点。（ ） 8. 设 S=0,1,S是关于普通的加法和乘法运算，则 S上的加法与乘法运算满足封闭性、结
2、合性。（ ） 9. 为重言式。（ ） 10. 设是一个代数系统，且集合 A中元素的个数大于 1。如果该代数系统中存在幺元 e和零元 ，则 e 。（ ） 二、单项选择题（本大题共 30分，共 10 小题，每小题 3 分） 1. 在命题演算中，语句为真为假的一种性质称为（） A. 真值 B. 陈述句 C. 命题 D. 谓词 2. 设 i是虚数， 是复数乘法运算，则 G=是群，下列是 G的子群是（）。 A. B. -1, C. i, D. -i, 3. 对于复合命题 “ 如果天不下雨和我有时间，那么我将去镇上 ” ，设 P表示“ 天下雨 ” ， Q表示 “ 我将去镇上 ” ， R表示 “ 我有时间
3、” ，则以下符合化正确的是（ ） A. ( P R) Q B. P R Q C. P R Q D. R Q ） P 4. 下图是（ ）。 A. 欧拉图 B. 汉密尔顿图 C. 二部图 D. 树 5. 令 R(x)： x是实数， Q(x)： x是有理数。命题 “ 并非每个实 数都是有理数 ” ，其符号化为 ( )。 A. x(R(x) Q(x) B. x( R(x) Q(x) C. x(R(x) Q(x) x(R(x) Q(x) D. x(R(x) Q(x) x(R(x) Q(x) E. x(R(x) Q(x) x(R(x) Q(x) 6. 设 A是奇数集合，下列构成独异点的是（ ）。 A. B
4、. C. D. 7. 设 G是 n个顶点的无向简单图，则下列说法不正 确的是（）。 A. 若 G是树，则其边数等于 n-1 B. 若 G是欧拉图，则 G中必有割边 C. 若 G 中有欧拉路，则 G是连通图，且有零个或两个奇数度顶点 D. 若 G中任意一对顶点的度数之和大于等于 n-1,则 G中有汉密顿路 8. 谓词公式 x（ P(x)(yR(y)Q(x) 中变元 x是（ ）。 A. 自由变元 B. 约束变元 C. 既不是自由变元也不是约束变元 D. 既是自由变元也是约束变元 9. 下列各图是平面图的是（）。 A. B. C. D. 10. 设有完全 m叉树，其树叶数为 t，分枝点数为 i，则下
5、列成立的是 ( ) A. m=i+t B. t=i-1 C. :(m-1)i=t-1 D. (t-1)i=m-1 三、简答题（本大题共 6分，共 1 小题，每小题 6 分） 求谓词公式 x(F(x) G(x) ( xF(x) xG(x) 的前束范式。 四、计算题（本大题共 12 分，共 2 小题，每小题 6 分） 1. 判定下图是否能够一笔画，若不能，请说明为什么，若能，请标出路径。2. 设 S=1,2,3,4,6,12， D为 S上的整除关系， （ 1）试写出该关系并画出哈斯 图； （ 2）设子集 B=2,3,6，试求 B的最大元、最小元、极大元和极小元； （ 3）试求 B的上界、上确界、下
6、界和下确界。 五、作图题（本大题共 6分，共 1 小题，每小题 6 分） 求下图所示带权图的最小生成树： 六、证明题（本大题共 6分，共 1 小题，每小题 6 分） 设 R是集合 A上的自反、传递的二元关系，又设 T也是 A上的二元关系，且满足： T R R ，求证： T是 A上的等价关系。 七、多项选择题（本大题共 20分，共 5 小题，每小题 4 分） 1. 偏序关系需要满足哪些特点？（ ） A. 对称性 B. 反对称性 C. 自反性 D. 反自反性 E. 传递性 2. 以下叙述正确的是（ ）。 A. 的幂集没有任何元素 B. 整数集上关于加法运算的幺元是 0 C. 整数集上关于乘法运算的
7、幺元是 1 D. 整数集上的关于乘法运算的零元是 0 3. 相容关系需要满足的特性为：（ ） A. 对称性 B. 传递性 C. 自反性 D. 反对称性 4. 以下关系中哪些是 A B 的函数，其中 A=a,b,c B=1,2,3( ) A. , B. , C. , D. , 5. 设 Z是整数集合， +是一般加法，则下述函数中哪些是群（ Z， +）的自同态？（ ） A. f(x)=2x B. f(x)=1000x C. f(x)=|x| D. f(x)=0 答案： 一、判断题（ 20 分，共 10 题，每小题 2 分） 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 二、单项选择
8、题（ 30 分，共 10 题，每小题 3 分） 1. A 2. A 3. A 4. B 5. A 6. C 7. B 8. D 9. A 10. C 三、简答题（ 6分，共 1 题，每小题 6 分） 0. 参考答案： x(F(x) G(x) ( xF(x) xG(x) x( F(x) G(x) ( xF(x) xG(x) x( F(x) G(x) ( xF(x) xG(x) x(F(x) G(x) xF(x) xG(x) x(F(x) G(x) xG(x) xF(x) x(F(x) G(x) G(x) xF(x) x(F(x) G(x) ( G(x) G(x) xF(x) x(F(x) G(x
9、) x F(x) x(F(x) G(x) y F(y) x y(F(x) G(x) F(y) 解题方案： 评分标准： 4 1 四、计算题（ 12 分，共 2 题，每小题 6 分） 1. 参考答案： 可以一笔画（路径略） 解题方案： 评分标准： 2. 参考答案： （ 1）哈斯图为： （ 2） B的最大元为 6，最小元为 1，极大元为 6，极小元为 1. （ 3） B的上界为： 6， 12；上确界为 6；下界为： 1，下确界为 1. 解题方案： 评分标准： 五、作图题（ 6分，共 1 题，每小题 6 分） 0. 参考答案： 此图的最小生成树为： 该最小生成树的权为： 1+3+2+2+1=9 解题方案： 评分标准： 六、证明题（ 6分，共 1 题，每小题 6 分） 0. 参考答案： 解题方案： 评分标准： 七、多项选择题（ 20 分，共 5 题，每小题 4 分） 1. BCE 2. BCD 3. AC 4. BC 5. ABD
