《离散数学》复习题
一、 单项选择题
1. 下列句子是原子命题的是 （ A ）
A. 大熊猫产在我国；
B. 2+x=5; D. 别讲话了！
C. 小王和小李是学生；
2. 设p：天下雨，q：我去新华书店，命题“除非天不下雨，我去新华书店”的符号化形式为 A．p→q
Ｂ．q→p
Ｃ．┐q→p Ｄ．┐p→q
B. P∨?P D. P→P∨Q
（ B ）
（ D ）
3. 以下命题不是重言式的有 （ A ）
A. P∧?P
C. (P→Q)?(?Q→?P)
4. 以下语句中不是命题的为
A．明天我要上门去谢你。 Ｃ．如果不说，我就不谢你。
A．(?x) M(x)
Ｂ．谢谢你给了我机会。 Ｄ．除非你做了，我才谢你
5．与?(?x) M(x) 等价的是
Ｂ．(?x) ?M(x)
Ｃ．(?x) M(x)
Ｄ．(?x) ?M(x)
（ D ）
6. 设P(x)为“x是大学生”，Q(x)为“x满30岁”。命题“所有大学生都不满30岁”写成谓词公式为 （ C ） A. ?x(P(x)∧Q(x)) B.? x(P(x)∧Q(x)) C.?x(P(x)→Q(x)) D.? x(P(x)→Q(x)) 7.公式 (?x) (P(x)→(?y)R(x, y))中，?x的辖域为
A．P(x)
Ｂ．(P(x)→(?y)R(x, y)) Ｄ．P(x)→(?y)
（ C ） ( A )
Ｃ. 8
Ｄ．9
Ｃ．P(x)和R(x, y)
（ B ）
8．设S={a, b, c},则S的幂集的元素的个数有 A．3 Ｂ．6
A．A∪(B×C)=(A∪B)×(A∪C)
9．以下等式中不正确的是： Ｃ．（A∪B)×C=(A×C)∪(A×C)
Ｄ(A×B)×C=A×(B×C)
Ｂ．A×(B∪C)=(A×B)∪(A×C)
10．设A={1, 2, 3, 4}, A上的等价关系R={<1, 2>, <2, 1>, <3, 4>, <4, 3>}∪IA, 则对应于R的A的划分是
A．{{1},{2, 3}, {4}} Ｃ．{{1},{2}, {3}, {4}} A．入射
－
( D )
Ｂ．{{1, 2},{3}, {4}} Ｄ．{{1,2}, {3, 4}}
( B )
1 / 21
11．设函数 f：{1，2}→{1}，则f是
B．满射
C．双射
D．非入射非满射
12．设Z是负正整数集合，+，－，*，△是普通数的加法、减法和平方运算，则能构成代
数系统是
( B ) A．< Z, +> Ｃ．< Z, *> 13．若
A. C.A．独异点
－－
－
B.
Ｂ．< Z, －> Ｄ< Z, △>
（ B ）
( A ) ( C )
－
他聪明， 他用功，则“他虽聪明但不用功”，可符号化为
D.
14. 若一个代数系统(A，*)满足运算封闭性及结合律，且有幺元，则它是
B．群
C．格
D．布尔代数
15．设G为无限群，则 A． G是交换群
Ｂ． G是循环群
Ｃ．G中每个元素都有逆元 A．1
Ｂ．3
Ｄ．G中每个元素的阶都是无限的 Ｃ. 1或3
Ｄ．0或2
( D )
16．在有3个结点的图中，度数是奇数的结点的个数为 ( D ) 17．在5阶图G中，若从结点v1到v4存在路，则从v1到v4的路中必存在路，其长度小于等于 A．1 A．5 A. C. A. C.
A．C．22．设
A．
C．
A．边数
Ｂ．2
B. D. B. 与没关系
B． B．D．
（ C ）
B．边数的一半
D．
（ C ）
（ A ）
Ｃ. 3 Ｃ. 15
与的关系为 ( B )
Ｄ．4 Ｄ．20
（ D ）
18．连通平面图G的面的次数之和为10，则其边数为 ( A )
Ｂ．10
19. 在自然数集合上，下列哪种运算不是可交换的
20. 设简单图的最大结点度数为，图的结点数为,则
D.
21．下列各项中错误的是
，下列各式成立的是
23．连通平面图G中，所有面的次数之和是
C．边数的两倍 24．无向图
A．奇数 C．素数
D．边数的一倍
的所有结点的度数都是
（ B ）
B．偶数 D．1
2 / 21
具有一条欧拉回路，那么图
25. 下列集合哪个是最小联结词集 （ D ）
A. C. A. C.
B.
与的关系为 （ B ）
与没关系
D.
B. D.
26. 设简单图的最大结点度数为，图的结点数为,则
27. 设集合A={1,2,3}，B={2,3,4,5}，C={2,4,8,16},D={1,2,3,4},设“|”是集合上的“整
除”关系，则下列偏序集中能构成格的是 A.
,则关系
（ B ） （ C ）
B.
上的二元关系
具有的性质是哪一个 A. 自反性 C. 传递性 A. C.
B. 对称性
D. 反对称性
D.
（ C ）
B.
29．判断下列各式中不是合式公式的是哪一个
30. 代数系统(S,?)中以下断言正确的是 （ C ）
A. 单位元与零元总是不相等； C. 单位元总有逆元；
B. 可能有二个左单位元和一个右单位元； D. 若S'?S，则(S',?)是(S,?)的子代数
31. 指出下列语句中哪个是原子命题 （ A ）
A. 苏州是中国的首都。 B. 王强不但聪明而且用功。
C. 明天下午我乘Z86次或K256次列车去北京。 D. 如果天不下雨，我就骑车上班。 32. 设
A. B. C. D．
，则下列哪个集合是从
的函数
（ C ）
33. 在谓词演算中，下列各式正确的是 （ A ）
A. B. C. D.
B.（A,ο）是可交换独异点
3 / 21
34. 设（A,+, ο）是整环，则以下断言错误的是 （ D ）
A. （A,+）是阿贝尔群