《2015年离散数学(第二次)作业》由会员分享，可在线阅读，更多相关《2015年离散数学(第二次)作业（7页珍藏版）》请在金锄头文库上搜索。
1、第第 2 2 次作业次作业 一、判断题（本大题共一、判断题（本大题共 2020 分，共分，共 1010 小题，每小题小题，每小题 2 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. 设
2、S=0,1,S 是关于普通的加法和乘法运算，则 S 上的加法与乘法运算满足 封闭性、结合性。（ ）9. 为重言式。（ ） 10. 设是一个代数系统，且集合 A 中元素的个数大于 1。如果该代数系统中存 在幺元 e 和零元，则 e。（ ） 二、单项选择题（本大题共二、单项选择题（本大题共 3030 分，共分，共 1010 小题，每小题小题，每小题 3 3 分）分） 1. 在命题演算中，语句为真为假的一种性质称为（） A. 真值 B. 陈述句 C. 命题 D. 谓词 2. 设 i 是虚数，是复数乘法运算，则 G=是群，下列是 G 的 子群是（）。 A. B. -1, C. i, D. -i, 3.
3、 对于复合命题“如果天不下雨和我有时间，那么我将去镇上”，设 P 表示 “天下雨”，Q 表示“我将去镇上”，R 表示“我有时间”，则以下符合化正确 的是（ ） 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)
4、E. x(R(x) Q(x) x(R(x) Q(x) 6. 设 A 是奇数集合，下列构成独异点的是（ ）。 A. B. 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. 既是自由变元也
5、是约束变元9. 下列各图是平面图的是（）。 A. B. C. D. 10. 设有完全 m 叉树，其树叶数为 t，分枝点数为 i，则下列成立的是( ) A. m=i+t B. t=i-1 C. :(m-1)i=t-1 D. (t-1)i=m-1 三、简答题（本大题共三、简答题（本大题共 6 6 分，共分，共 1 1 小题，每小题小题，每小题 6 6 分）分） 求谓词公式 x(F(x) G(x) ( xF(x) xG(x) 的前束范式。四、计算题（本大题共四、计算题（本大题共 1212 分，共分，共 2 2 小题，每小题小题，每小题 6 6 分）分） 1. 判定下图是否能够一笔画，若不能，请说明为
6、什么，若能，请标出路径。2. 设 S=1,2,3,4,6,12，D 为 S 上的整除关系， （1）试写出该关系并画出哈 斯图； （2）设子集 B=2,3,6，试求 B 的最大元、最小元、极大元和极小元；（3）试求 B 的上界、上确界、下界和下确界。 五、作图题（本大题共五、作图题（本大题共 6 6 分，共分，共 1 1 小题，每小题小题，每小题 6 6 分）分）求下图所示带权图的最小生成树：六、证明题（本大题共六、证明题（本大题共 6 6 分，共分，共 1 1 小题，每小题小题，每小题 6 6 分）分） 设 R 是集合 A 上的自反、传递的二元关系，又设 T 也是 A 上的二元关系，且满 足：
7、TR R，求证：T 是 A 上的等价关系。七、多项选择题（本大题共七、多项选择题（本大题共 2020 分，共分，共 5 5 小题，每小题小题，每小题 4 4 分）分） 1. 偏序关系需要满足哪些特点？（ ） A. 对称性 B. 反对称性 C. 自反性 D. 反自反性 E. 传递性 2. 以下叙述正确的是（ ）。 A. 的幂集没有任何元素 B. 整数集上关于加法运算的幺元是 0 C. 整数集上关于乘法运算的幺元是 1 D. 整数集上的关于乘法运算的零元是 0 3. 相容关系需要满足的特性为：（ ） A. 对称性 B. 传递性 C. 自反性 D. 反对称性 4. 以下关系中哪些是 A B 的函数，
8、其中 A=a,b,c B=1,2,3( ) A. , B. , C. , D. , 5. 设 Z 是整数集合，+是一般加法，则下述函数中哪些是群（Z，+）的自同态？ （ ） A. f(x)=2x B. f(x)=1000xC. f(x)=|x| D. f(x)=0答案：答案：一、判断题（一、判断题（2020 分，共分，共 1010 题，每小题题，每小题 2 2 分）分） 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 二、单项选择题（二、单项选择题（3030 分，共分，共 1010 题，每小题题，每小题 3 3 分）分） 1. A 2. A 3. A 4. B 5. A 6. C
9、 7. B 8. D 9. A 10. C 三、简答题（三、简答题（6 6 分，共分，共 1 1 题，每小题题，每小题 6 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) x F(x) x(F(x) G(x) y F(y)
10、 x y(F(x) G(x) F(y) 解题方案：解题方案：评分标准：评分标准： 4 1四、计算题（四、计算题（1212 分，共分，共 2 2 题，每小题题，每小题 6 6 分）分）1. 参考答案：参考答案： 可以一笔画（路径略） 解题方案：解题方案：评分标准：评分标准：2. 参考答案：参考答案： （1）哈斯图为： （2）B 的最大元为 6，最小元为 1，极大元为 6，极小元为 1. （3）B 的上界为： 6，12；上确界为 6；下界为：1，下确界为 1. 解题方案：解题方案：评分标准：评分标准：五、作图题（五、作图题（6 6 分，共分，共 1 1 题，每小题题，每小题 6 6 分）分）0. 参考答案：参考答案： 此图的最小生成树为：该最小生成树的权为：1+3+2+2+1=9 解题方案：解题方案：评分标准：评分标准：六、证明题（六、证明题（6 6 分，共分，共 1 1 题，每小题题，每小题 6 6 分）分）0. 参考答案：参考答案：解题方案：解题方案：评分标准：评分标准：七、多项选择题（七、多项选择题（2020 分，共分，共 5 5 题，每小题题，每小题 4 4 分）分） 1. BCE 2. BCD 3. AC 4. BC 5. ABD
