离散数学作业一、选择题1、下列语句中哪个是真命题（C ）。

A ．我正在说谎。

B ．如果1+2=3，那么雪是黑色的。

C ．如果1+2=5，那么雪是白色的。

D ．严禁吸烟！2、设命题公式))((r q p p G →∧→=，则G 是（ C ）。

A. 恒假的B. 恒真的C. 可满足的D. 析取范式 3、谓词公式),,(),,(z y x yG x z y x F ∃∀→中的变元x （ C ）。

A ．是自由变元但不是约束变元 B ．既不是自由变元又不是约束变元 C ．既是自由变元又是约束变元 D ．是约束变元但不是自由变元4、设A={1，2，3}，则下列关系R 不是等价关系的是（C ）A ．R={<1，1>，<2，2>，<3，3>}B ．R={<1，1>，<2，2>，<3，3>，<2，3>，<3，2>}C ．R={<1，1>，<2，2>，<3，3>，<1，4>}D ．R={<1，1>，<2，2>，<3，3>，<1，2>，<1，3>，<2，3>，<2，1>，<3，1>，<3，2>} 5、设R 为实数集，映射σ=R →R ，σ（x ）= -x 2+2x-1，则σ是（ D ）。

A ．单射而非满射 B ．满射而非单射 C ．双射 D ．既不是单射，也不是满射 6、下列二元运算在所给的集合上不封闭的是（ D ） A. S={2x-1|x ∈Z +}，S 关于普通的乘法运算 B. S={0，1}，S 关于普通的乘法运算 C. 整数集合Z 和普通的减法运算D. S={x | x=2n ，n ∈Z +}，S 关于普通的加法运算7、*运算如下表所示，哪个能使（{a,b}，*）成为含幺元半群（ D ）b a b b a a b a * b b b a a a b a * a a b a a a b a * a b b b a a b a *A B C D8、下列图中是欧拉图的是（ A ）。

A B C D 9、下列各组数中,能构成无向图的度数列是（ D ） A ．1,1,1,2,4 B ．1,2,3,4,5 C ．0,1,0,2,4 D ．1,2,3,3,510、一棵树有2个4度顶点，3个3度顶点，其余都是树叶，则该树中树叶的个数是（ B ）A .8 B.9 C. 10 D. 11 11、“所有的人都是要死的。

苏格拉底是人，所以苏格拉底是要死的。

”则该句话（B ）A ．不是命题B ．是真命题C ．是假命题D ．是悖论12、一个公式在等价意义下，下面哪个写法是唯一的（ C ）。

A ．析取范式 B ．合取范式 C ．主析取范式 D ．以上答案都不对 13、设论域E={a, b}，且P(a,a)=1 P(a,b)=0 P(b,a)=1 P(b,b)=0 则在下列公式中真值为1的是（ D ）A.∃x ∀yP(x,y)B.∀x ∀yP(x,y)C.∀xP(x,x)D. ∀x ∃yP(x,y) 14、设集合A={1, 2, 3 }，A 上的关系R={<1, 1 >,<2, 2 > }，则R 不具有（ A ）性质。

A.自反性B.对称性C.传递性D. 反对称性 15、设集合A={a,b,c,d},B={1,2,3,4},则从A 到B 的函数f={<a,2>,<b,1>,<c,3 >,<d,2 >}是（ D ）。

A. 双射函数 B. 单射函数C. 满射函数D. 即不是满射又是不是单射函数 16、下面给出的一阶逻辑等值式中，（ B ）是错的。

A.);()())()((x xB x xA x B x A x ∃∨∃⇔∨∃ B.);()())()((x xB x xA x B x A x ∀∨∀⇔∨∀ C.));(()(x A x x xA ⌝∃⇔⌝∀D.)).(()(x B A x x xB A →∀⇔∀→17、下列各代数系统中，不含零元素的是 （ C ）A ．>*<),(R M n ， )(R M n 是全体n 阶实矩阵集合，*是矩阵乘法运算。

B ．><Y ),(S p ，)(S p 是集合S 的幂集合，Y 是集合的并运算。

C ．>+<,R ，R 是有理数集，+是数的加法运算。

D ．><ο,I ，I 是整数集，ο是数的乘法运算。

18、 设图G 是有6个顶点的连通图，总度数为20，则从G 中删去（ B ）边后使之变成树。

A .10 B. 5 C. 3 D. 2 19、在具有n 个结点的无向连通图中，（B ）。

A. 恰好有n 条边B. 恰好有n-1条边C. 最多有n 条边D. 至少有n 条边 20、下列图是欧拉图的是（ C ）21. 半群、群及独异点的关系是………………………………………………（ D ）（A ）{群}⊂{独异点}⊂{半群} （B ）{独异点}⊂{半群}⊂{群} （C ）{独异点}⊂{群}⊂{半群} （D ）{半群}⊂{独异点}⊂{群}22. 设集合A={1, 2, 3 }，A 上的关系R={<1, 1 >,<2, 2 >,<3,3>}，则R 不具有下列性质中的……………………………………………………………… （D ） (A) 自反性 (B) 对称性 (C) 传递性 (D) 反自反性 23. 以下图中哪个是欧拉图…………………………………………… （D ）24．*运算如下表所示，哪个能使<{a,b }，*>成为含幺元半群…………（D ）b a b b a a b a * b b b a a a b a * a a b a a a b a * a b b b a a b a *(A) (B) (C) (D)25. 设P：张三可以做这件事，Q：李四可以做这件事。

命题“张三或李四可以做这件事”符号化为…………………………………………………（A）(A) Q(~~QP∨~ P∨ (B) QP~∨ (C) QP↔ (D) )26.27. G是连通的平面图，有5个顶点，6个面，则G的边数为……………（C）(A) 6 (B) 5 (C) 9 (D) 1128.下列句子中是命题的有……………………………………………（D）(A) 上课时请不要说话! (B) 我在说谎.（C）你吃饭了吗？（D）上海是中国的首都.29. 以下命题公式中，为永假式的是( C )(A) p→(p∨q∨r) (B) (p→┐p)→┐p（C）┐(q→q)∧p （D）┐(q∨┐p)→(p∧┐p) 30. 图的生成子图为……………………………（C）(A) (B) (C) (D)31.如下图所示的有界格中，元素b的补元是( D )（A）a（B）0（C）c（D）d32. 设A={a,b,c}，则下列是集合A的划分的是( D )（A） {{b,c},{c}} （B）{{a,b},{a,c}} （C）{{a,b},c} （D）{{a},{b,c}}33. 整数集合Z上“＜”关系的自反闭包是关系（D）(A) = (B)≠ (C)＞ (D) ≤34. 下列式子正确的是 ( B )(A) ∅∈∅ (B)∅⊆∅ (C){∅}⊆∅ (D){∅}∈∅35.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( A )（A ）<{1},·> （B ）〈{-1},·〉 （C ）〈{i},·〉 （D ）〈{-i},·〉 36.集合A={1，2}的幂集P(A)的基数是…………………………………………（ D ）（A ） 0 （B ） 1 （C ） 2 （D ） 437. 下列哪个联结词运算不可交换？………………………………………（A ） (A) → (B) ↔ (C) ∨ (D) ∧38. 设集合A={1，2，3，…，10},下列定义的哪种运算关于集合A 是不封闭的 (D ) (A) x*y=max{x,y} (B) x*y=(x,y) 即x,y 的最大公约数(C) x*y=min{x,y} (D) x*y=[x,y] 即x,y 的最小公倍数 39.设R 为实数集，函数f ：R →R ，f(x)=2x ，则f 是（ B ）A ．满射函数B ．单射函数C ．双射函数D ．非单射非满射40. 若<A ,*>是一个代数系统,且满足结合律,则<A ,*>必为…………………（A ） (A) 半群 (B) 独异点 (C) 群 (D) 交换群41. 设R 是A 上的等价关系,即R 是……………………………………………（D ） （A ）反自反的,对称的，传递的 （B ）自反的,反对称的, 传递的 （C ）反自反的,反对称的,传递的 （D ） 自反的,对称的,传递的42．下列哪一组命题公式是等价的……………………………………………（B ） (A) Q P ~~∧，Q P ∨ (B) )(A B A →→，)~(~B A A →→ (C) )(Q P Q ∨→，)(~Q P Q ∨∧ (D) )(~B A A ∧∨，B43.设S={0,1},则S ……………………………………………………………（A ） （A ）在普通乘法下封闭，在普通加法下不封闭; （B ）在普通加法和乘法下都封闭；（C ）在普通加法下封闭，在普通乘法下不封闭； （D ）在普通加法和乘法下都不封闭；44. 下面谓词公式是前束范式的是 （ A ）A. ))(),((z A y x B z y x →∃∀∀B. ),((y x B y x ∃⌝∀C. ))(),((z A y x B z y x ∧⌝∃∀∃D. ))(),((y yB y x B x ∃→∀ 45. 整数集合Z 上“＜”关系的自反闭包是关系（D ）(A)= (B)≠ (C)＞ (D)≤11.下列图既是欧拉图,又是哈密顿图的是………………………………（C ）46. 设A={a,b,c}，A 上二元关系R={〈a,a 〉，〈b,b 〉,〈a,c 〉}，则关系R 的对称闭包S(R)是( C )(A) R ∪IA (B) R (C) R ∪{〈c,a 〉} (D) R ∩IA 47. 下列式子正确的是( B ) (A) ∅∈∅ (B)∅⊆∅(C) {∅}⊆∅ (D) {∅}∈∅48. 下列句子是命题的是( C )(A) 水开了吗? (B) 这朵花多好看呀！ (C) 2是常数。