2013年4月考试离散数学第二次作业一、单项选择题（本大题共50分，共 25 小题，每小题 2 分）1. 下列语句中为命题的是（）A. 暮春三月，江南草长.B. 这是多么可爱的风景啊！C. 大家想做什么，就做什么，行吗？D. 请勿践踏草地！2. 2.设G是n个顶点的无向简单图，则下列说法不正确的是（）A. 若G是树，则其边数等于n-1B. 若G是欧拉图，则G中必有割边C. 若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点D. 若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路3. 集合|A|=3，|B|=2，则A B上不同的函数个数为（）。

A. 3+2个B. 32个C. 2*3个D. 23个4. 设A-B=φ，则以下正确的是（）。

A. A＝BB. A⊆BC. B⊆AD. 以上都不对5. 设R为实数集，函数f：R→R，f(x)=2x，则f是（）A. 满射函数B. 入射函数C. 双射函数D. 非入射非满射6. 设B={a,b,c},C={1,2,3,4}，以下哪个关系是从B到C的单射函数？（）A. f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>}B. f={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>}C. f={<1,7>,<2,7>,<4,9>,<3,8>}D. f={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>}E.f={<1,7>,<5,10>,<2,6>,<4,8>,<3,9>}7. 下述*运算为实数集上的运算，其中可交换且可结合的运算是（）。

A. a*b=a+2b B. a*b=a+b-ab C. a*b=a D. a*b=|a+b|8. 在下列命题中，为真的命题是（）A. 汉密顿图一定是欧拉图B. 无向完全图都是欧拉图C. 度数为奇数的结点个数为0个或2个的连通无向图G可以一笔画出D. 有割点的连通图是汉密顿图9. 设p:小李努力学习，q:小李取得好成绩，命题“只有小李努力学习，他才能取得好成绩”的符号化形式为（）。

A. B. C.D.10. 若个体域为整数集，下列公式中哪个值为真？（）A. ∀x y(x+y=0)B. y∀x(x+y=0)C. x∀y(x+y=0)D. ∀x∀y(x+y=0)11. 若X是Y的子集，则一定有（）。

A. X不属于Y B. X∈Y C. X真包含于Y D. X∩Y=X12. 下列各图是平面图的是（）。

A. B.C. D.13. 函数的复合满足（）A. 交换律B. 结合律C. 幂等律D. 分配律14. 设论域为整数集合，下列真值为真的公式为（）。

A.B. C. D.15. 设A={Φ}，B=P（P（A）），以下不正确的式子是（）。

A. {{Φ}，{{Φ}}，{Φ，{Φ}}}包含于BB. {{{Φ}}}包含于BC. {{Φ，{Φ}}}包含于BD. {{Φ}，{{Φ，{Φ}}}}包含于B16. 设有完全m叉树，其树叶数为t，分枝点数为i，则下列成立的是( )A. m=i+tB. t=i-1C. :(m-1)i=t-1D. (t-1)i=m-117. 所有使命题公式为真的赋值为（）。

A. 010，100，101，110，111B. 010，100，101，111C. 全体赋值D. 不存在18. 下面哪个命题是假命题？（）A. 如果2是偶数，那么一个公式的析取范式唯一B. 如果2是偶数，那么一个公式的析取范式不唯一C. 如果2是奇数，那么一个公式的析取范式唯一D. 如果2是奇数，那么一个公式的析取范式不唯一19. 下列关系矩阵所对应的关系有反自反性的是（）。

A. B.C. D.20. 以下叙述正确的是：（）。

A. Φ的幂集没有任何元素。

B. 整数集上关于加法运算的幺元是0。

C. 整数集上的任何元素x关于乘法运算均有逆元1/x。

D. 整数集上的关于乘法运算的幺元是0。

21. 结点数为奇数且所有结点的度数也为奇数的连通图必定是（）A. 欧拉图B. 汉密尔顿图C. 非平面图D. 不存在的22. 命题公式P→ Q∧ R的对偶式为？（）A. P →（ Q ∨R ）B. P ∧（ Q ∨R ）C. ⎤P ∨（ Q ∧R ）D. ⎤ P∧（Q∨ R）23. 设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}}24. 设i是虚数，·是复数乘法运算，则G=<{i,-i,1,-1},•>是群，下列是G的子群是（）。

A.B. 〈{-1},•〉C. 〈{i},•〉D. 〈{-i},•〉25. 谓词公式∀x（P(x)∨(yR(y))→Q(x)中变元x是（）。

A. 自由变元B. 约束变元C. 既不是自由变元也不是约束变元D. 既是自由变元也是约束变元二、多项选择题（本大题共18分，共 6 小题，每小题 3 分）1. 以下叙述正确的是（）。

A. 的幂集没有任何元素B. 整数集上关于加法运算的幺元是0C. 整数集上关于乘法运算的幺元是1D. 整数集上的关于乘法运算的零元是02. 在下列命题中，为真的命题是（）A. 具有6个结点的无向完全图共有15条边。

B. 无向完全图都是欧拉图。

C. 度数为奇数的结点个数为0个或2个的连通无向图G可以一笔画出。

D. 有割点的连通图是汉密顿图。

3. 以下叙述正确的是（）。

A. 若A＝{φ,1,2}，则A的幂集有8个元素 B.朋友关系是等价关系 C. 具有5个顶点的完全图，需要删去6条边才能得到树D. 集合B = {{a},3,4,1}，E为全集，则φ{{a}}B E4. 设Z是整数集合，+是一般加法，则下述函数中哪些是群（Z，+）的自同态？（）A. f(x)=2xB. f(x)=1000xC. f(x)=|x|D. f(x)=05. 设偏序集<,≤> 的哈斯图如下所示，若A的子集B = {2,3,4},则元素为B的极大元为( )。

A. 5B. 6C. 3D. 46. 设T是一棵具有n个结点m条边（n2）的树，则T（）。

A. 连通 B. 包含有环 C. m=n-1 D. 至少有两个度为1的结点三、判断题（本大题共32分，共 16 小题，每小题 2 分）1. 同一谓词公式，指定不同的论域，其真值不一定相同。

（）2. 任何一棵非平凡树至少有两片树叶（）3. K5的点连通度为4，边连通度为4。

（）4. 任何合式公式的主析取范式都是唯一的（如果存在的话）（）。

5. “他打开箱子走了进来”。

是一个原子命题（）6. P(A)*P(B)＝P(A*B)A,B为任意集合（）7. 任意一个谓词公式都与一个前束范式等价。

（）8. A、B是集合，则命题A⊆B和B⊆A可能同时成立。

（）9. 能一笔画出的图一定是欧拉图。

（）10. 为矛盾式。

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

（）12. 交换群必是循环群。

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

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

（）15. 为重言式。

（）16. 设是一个代数系统，且集合A中元素的个数大于1。

如果该代数系统中存在幺元e和零元，则e。

（）答案：一、单项选择题（50分，共 25 题，每小题 2 分）1. A2. B3. D4. A5. B6. D7. B8. C9. A 10. A 11. D 12. A 13. B14. A 15. D 16. C 17. A 18. B 19. B 20. B 21. D 22. D 23. C 24. A 25.D二、多项选择题（18分，共 6 题，每小题 3 分）1. BCD2. AC3. ACD4. ABD5. CD6. ACD三、判断题（32分，共 16 题，每小题 2 分）1. √2. √3. √4. √5. ×6. ×7. √8. √9. × 10. √ 11. √ 12. × 13. × 14. √ 15. √ 16. √。