2013年4月考试离散数学第一次作业一、单项选择题（本大题共50分，共 25 小题，每小题 2 分）1. 下列关系中为等价关系的是（）A. 朋友关系B. 父子关系C. 住在同一街区的邻居关系D. 买卖关系2. 集合A上的相容关系所得关系矩阵M(R)的对角线元素（）。

A. 全为1B. 全为0C. 有的是1，有的是0D. 有的是23. 完全图的结点数目为（）时，有欧拉回路。

A. 3B. 为奇数C. 为偶数D. 104. 下面哪一个图是树（）？A.B.C.D.5. 任何无向图中结点间的连通关系是（）A. 偏序关系B. 等价关系C. 相容关系D. 拟序关系6. 若集合A的基数为７，则其幂集的基数|P(A)|是多少？（）A. 107B. 70C. 27D. 177. 若R和S是集合A上的两个关系，则下述结论正确的是（）A. 若R和S是自反的，则RoS是自反的。

B. 若R和S是对称的，则RoS是对称的。

C. 若R和S是反自反对称的，则RoS是反自反的。

D. 若R和S是传递的，则RoS是传递的。

8. 设A是整数集，下列说法正确的是（）。

A. B.C. D.9. 设P：我去踢球，Q：明天下雨，命题“如果我踢球，当且仅当明天不下雨”的符号化表示为（）。

A. P→QB. Q→PC.D. P Q10. 以下哪个不是最小联结词组？（）A. { ∧，⎤}B. { ∨，⎤}C. { ∧，∨，→}D. {⎤，→ }11. 集合A={1，2，… ，10}上的关系R={|x+y=10,x∈A,y∈A}，则R的性质为（）。

A. 自反的B. 对称的C. 传递的、对称的D. 反自反的、传递的12. 下面哪一个命题是命题“2是偶数或-3是负数”的否定？（）A. 2是偶数或-3不是负数B. 2是奇数或-3不是负数C. 2不是偶数且-3不是负数D. 2是奇数且-3不是负数13. 对于下面某个偏序集的哈斯图，其中集合{a,b,c,e}的最大元是（）A. cB.dC.eD.无14. 下述集合对所给的二元运算封闭的是（）。

A. 正整数集合上的减法运算B. 在全正实数集合上规定o为：aob=ab-a-b,(a,b∈R+)C. 正整数集合上的二元运算*：x*y=min(x,y) (a,b∈Z+)D. 全体n×n实数可逆矩阵集合上的矩阵加法15. 下面哪个命题是假命题？（）A. 如果1是奇数，那么一个公式的析取范式唯一B. 如果1是奇数，那么一个公式的析取范式不唯一C. 如果1是偶数，那么一个公式的析取范式唯一D. 如果1是偶数，那么一个公式的析取范式不唯一16. 函数的复合满足（）A. 交换律B. 结合律C. 幂等律D. 分配律17. 设论域为整数集合，下列真值为真的公式为（）。

A.B. C. D.18. 下列关系矩阵所对应的关系有反自反性的是（）。

A. B.C. D.19. 以下叙述正确的是（）A. 关系R是反自反的，当且仅当在关系矩阵中主对角线元素值为1。

B. 关系R是对称的，当且仅当在关系矩阵中主对角线元素值为1。

C. 关系R是对称的，当且仅当在关系图中任意两个结点之间若有有向边关联，则边应该成对出现。

D. 关系R是传递的，当且仅当在关系矩阵中的元素关于主对角线元素对称。

20. 设P,Q, R是命题公式，则( )。

⎤ A. P B. Q C.R D.21. 下面哪几组公式是等价的？（）A. ⎤P ∧⎤Q, P ∨QB. A → (B → A), ⎤A → (A →⎤B)C. Q →⎤P, ⎤Q ∨PD. ⎤ A∨ (A∧ B), B22. 设A={1,2,3}, b={a,b},下列各二元关系中是A到B的函数的是（）A. R={,,}B. R={,,,}C. R={,}D. R={,,,}23. Q∧ (P∨⎤ Q) 主合取范式为（）A. ⎤P ∨QB. P ∧⎤QC. (P ∨Q) ∧(P ∨⎤Q) ∧( ⎤P ∨Q)D. (P∧ Q)∨ (P∧⎤ Q)∨ (⎤ P∧ Q)24. 下图哪个能一笔画？（）A.B.C.D.25. 设G=为无环的无向图，|V|=6,|E|=16,则G是（）A. 完全图B. 零图C. 简单图D. 多重图二、多项选择题（本大题共30分，共 10 小题，每小题 3 分）1. 以下命题哪几个是真的？（）A. 地球是一个覆盖了大气层的蓝色星球。

B. x+5>6C. 如果雪是黑的，当且仅当桌子会走路。

D. 高校应该以教书育人为本。

2. 偏序关系需要满足哪些特点？（）A. 对称性B. 反对称性C. 自反性D. 反自反性E. 传递性3. 下图中是连通图的是（）A.B.C.D.4. 设B={1,2,3,4,5},C={6,7,8,9,10}，以下哪些关系是从B到C的单射函数。

（）A. f={,,,,}B. f={,,,,}C. f={,,,}D. f={,,,,}E. f={<1,7>,<5,10>,<2,6>,<4,8>,<3,9>}5. 下面哪一个偏序集（其中均略去了反映自反关系的序偶）能构成格？（）A. A={a,b,c,d} R={<d,c>,<c,b>,<b,a>,<d,b>,<d,a>}B. A={a,b,c,d,e}, R={,<b,a>,<c,b>,<d,b>,<e,c>,<e,d>,<e,b>}C. A={a,b,c,d,e,f,g}, R={<b,a>,<d,a>,<c,d>,<f,e>,<g,f>}D. A={1,2,3,4} R={<1,2>,<1,3>,<2,4>,<3,4>}6. 下面联结词集合中，哪些是最小联结词组？（）A. { ⎤，∧}B. { ⎤，→ }C. { ⎤，∧，∨}D.7. 设Z是整数集合，+是一般加法，则下述函数中哪些是群（Z，+）的自同态？（）A. f(x)=2xB. f(x)=1000xC. f(x)=|x|D. f(x)=08. 设集合A={1,2,3,…10}，下面定义的哪种运算关于集合A是封闭的（）A. x*y=max{x,y}B. x*y=min{x,y}C. x*y=GCD(x,y) 即x,y的最大公约数D. x*y=LCM(x,y) 即x,y的最小公倍数9. 设T是一棵具有n个结点m条边（n2）的树，则T（）。

A. 连通 B. 包含有环 C. m=n-1 D. 至少有两个度为1的结点10. 以下叙述正确的是（）。

A. 若A＝{φ,1,2}，则A的幂集有8个元素 B.朋友关系是等价关系 C. 具有5个顶点的完全图，需要删去6条边才能得到树D. 集合B = {{a},3,4,1}，E为全集，则φ{{a}}B E三、判断题（本大题共20分，共 10 小题，每小题 2 分）1. 如果A⇔ B，则A∧ C⇔ B∧ C，A∨ C⇔ B∨ C。

（）2. 设人的集合A上的朋友关系为R，则R是A上的相容关系（）3. 任何一棵非平凡树至少有两片树叶（）4. 一个不是自反的关系一定是反自反的。

（）5. 集合A上的等价关系确定了A的一个划分。

（）6. 若f：N N, f(x)=x2+2，则f是满射函数。

（）7. 若集合A上的二元关系R是对称的，R C一定是对称的。

（）8. A、B、C是任意命题公式，如果，一定有。

（）9. 不存在既有欧拉回路又有汉密尔顿回路的图。

（）10. 任何图中必有偶数个度数为奇数的结点。

（）答案：一、单项选择题（50分，共 25 题，每小题 2 分）1. C2. B3. B4. D5. B6. C7. A8. C9. C 10. C 11. B 12. C 13. D14. C 15. A 16. B 17. A 18. B 19. C 20. C 21. B 22. A 23. C 24. D 25.D二、多项选择题（30分，共 10 题，每小题 3 分）1. AC2. BCE3. A4. AE5. BD6. ABD7. ABD8. ABC9. ACD 10. ACD三、判断题（20分，共 10 题，每小题 2 分）1. √2. √3. √4. ×5. √6. ×7. √8. ×9. × 10. √。