3. 设 R 是集合 A 上的等价关系， 则 R 所具有的关系的三个特性是答案：
自反性；对称性；传递性 .
4. 设集合 A＝{1,2,3,4}, A 上的关系
R1 = {(1,4),(2,3),(3,2)}, R 1 = {(2,1),(3,2),(4,3)},
Байду номын сангаас
则 R1 R2=__{(1,3),(2,2),(3,1)}; R12=___{(2,2),(3,3)}.
C. 入度为奇数的结点；
D.
出度为奇数的结点 .
23. 设 G 为有 n 个结点的无向完全图，则 G 的边数为
(2, c ), (3, b )}
（A ） （B ） （B ）
（C ）
A. n(n 1) B ． n(n 1) C.
n(n 1) 2 D. (n 1) 2
24. 在有 n 个结点的连通图 G 中，其边数
为（
）B
A. 正则图
B. 完全图
C. 连通图
D. 强连通图
17. 给定 n 个结点的一个图，它还是一个树的下列说法中， （
A. 无回路的连通图
B. 无回路但若增加一条新边就会变成回路
C. 连通且 e=v-1 ，其中 e 是边数， v 是结点数
D. 所有结点的度数 ≥２
）是不对的。 D
18. 设 p 为真 q 为假， r 为真，下列为假的式子为
(C) ? x? y(x + y = )
(D) ? x?y ( x + y = )
31. 谓 词 公 式 ? x(P(x) ∧? xQ(x, y) → ? yR( x, y)) ∨ A( x, y) ， 以 下 陈 述 错 误 的 是 （ C ）。
(A) x 的辖域是 P(x) xQ ( x, y) yR(x, y)
《离散数学》期末复习题
一．选择题：
1. 下列句子为真命题的是 （） A (a) 能整除 7 的正整数只有 1 和 7 本身。
(b) 胡戈由于导演了 “无极 ”而于 2005 年获得奥斯卡金像奖。
(c) 买两张星期五去 “大剧院 ”音乐会的票。
(d) 地球是宇宙中惟一存在生命的星球。
2 ．下列语句中是真命题的是（
）D
A．我正在说谎
B．严禁吸烟
C．如果 1+2=3 ，那么雪是黑的
D． 如果 1+2=5 ，那么雪是黑的
3 ．设 P：我们划船， Q：我们跑步。命题 “我们不能既划船又跑步
A． P ∧ Q
B． P ∨ Q
C． （ P Q）
D． （ P ∨ Q ）
4 ．命题公式（ P∧（ P→Ｑ））→Ｑ是（
）B
A．矛盾式
B．任何两个不同结点都有边相连且无平行边及环的图称为完全图
C．具有经过每条边一次且仅一次回路的图称为哈密尔顿图
D ．具有经过每个结点一次且仅一次回路的图称为欧拉图
27.设 D 是有向图，则 D 强连通的充分必要条件为 .
(C )
A ．略去 D 中各边方向后所得到的无向图是连通的
B． D 是单向连通图，且改变它的各边方向后所得到的有向图也是单向连通图
R2 R1
5. 设有限集 A, B， |A| = m, |B| = n, 则 | | (A B)| = _2m n._
6. 设 G 是具有 8 个顶点的树，
则 G 中增加 ___21___条边才能把 G 变成完全图。
7. 设集合 A＝{1, 2, 3, 4} ， A 上的二元关系
R＝ {(1,1),(1,2),(2,3)},
12. 设树 T 中有 7 片树叶， 3 个 3 度结点，其余都是 4 度结点，则 T 中有
解 用握手定理和树的性质列出方程求解，设有
x 个 4 度结点，
7 9 4x 2(7 3 x 1) ， x 1
个 4 度结点 .
13.设 A＝ {1,2},B={x,y}, 则 AB={<1,x>,<1,y>,<2,x>,<2,y>} 。 14. 集合 A { a, b} 的 ( A) { ,{ a}, { b}, { a, b}} ； 。
A. 最多 n 1条；
B
．至少 n 1 条；
C. 最多 n 条；
D.
至少 n 条.
25. 任何无向图 G 中结点间的连通关系是
A. 偏序关系；
B
．等价关系；
C. 既是偏序关系又是等价关系；
D. 既不是偏序关系也不是等价关系
（B ） （B ） .
26.对于无向图，下列说法中正确的是 .
（B ）
A ．不含平行边及环的图称为完全图
A) (p
q) r 为（）真
（） B
B) (p q)
r 为（） 假
C) p D) p
(q r) 为（）真 (q r) 为（） 真
19. 从 X = {1, 2, 3} 到 Y = { a, b, c } 的函数 f = {(1, a ),
是
A) 一对一的，并且是对 Y 映上的。 （）真
B) 一对一的，但不是对 Y 映上的。
A) 自反的、非对称的；
B) 自反的、非传递的
C) 对称的、非传递的；
D) 自反的、对称的和传递的
10 、 令 X={1,2, … ,10} 。 定义 xRy 的意义是 3 整除 x-y 。则关系 R 是 （） D
A) 自反的、非对称的；
B) 自反的、非传递的
C) 对称的、非传递的
D) 自反的、对称的和传递的
B． 蕴含式
C．重言式
D．等价式
”符号化为（
5 ．在公式（
） F（ x， y ）→（ y） G（x ， y ）中变元 x 是（
A．自由变元 B． 约束变元 C．既是自由变元，又是约束变元 D．既不是自由变元，又不是约束变元 6 、下列语句不是命题的是（） A A. xP(x,y) B. xP(x)
）B
11 、下列 S 不是集合 X＝{1, 2, 3, 4, 5, 6, 7, 8}
的一个划分的是 （） D
A) S＝ {{1, 4, 5}, {2, 6}, {3}, {7, 8}}
B) S＝ {{1, 4}, {2, 6}, {3,5}, {7, 8}}
C) S＝ {{1, 4, 5}, {2,3, 6}, {7, 8}}
D． A(b) A(a)
37.设 A={a,b,c} ，则下列是集合 A 的划分的是 ( )
A. {{ b,c},{ c}}
B. {{ a},{ b,c}}
C.{{ a,b},{ a, c}}
D. {{ a, b}, c}
38.下列谓词公式中是前束范式的是（
）。
A ． xF ( x) ( x)G (x)
C) 不是一对一的。
D) 不是对 Y 映上的。 20. 仅由孤立点组成的图称为
A. 零图； B ．平凡图； C. 完全图； D. 多重图 .
21. 仅由一个孤立点组成的图称为
A. 零图； B ．平凡图； C. 多重图； D. 子图 .
22. 在任何图 G 中必有偶数个
A. 度数为偶数的结点；
B
．度数为奇数的结点；
）A
A.x 是约束出现， y 是约束出现， z 是自由出现 B.x 是约束出现， y 既是约束出现又是自由出现， C.x 是约束出现， y 既是约束出现又是自由出现， D.x 是约束出现， y 是约束出现， z 是约束出现
z 是自由出现 z 是约束出现
16. 在简单无向图 G= V , E 中，如果 V 中的每个结点都与其余的所有结点邻接，则该图称
C． D 的任意两个不同的结点都可以相互到达
D． D 是完全图
28.对于无向图 G，以下结论中 不正确 的是 .
（A ）
A ．如果 G 的两个不同结点是连接的，则这两个结点之间有初级回路
B．如果 G 的两个不同结点是连接的，则这两个结点之间至少有一条短程
C．如果 G 是树，则任何两个不同结点之间有且仅有一条初级通路
(B) x 的辖域是 Q(x,y) (C) R(x,y)中的 x 是自由出现
(D)此公式等值于 ? z( P( z) ∧ ? xQ( x, y) → ? yR( z, y)) ∨ A( x, y)
32.设 A,B,C 为任意集合 ,下列表达正确的是 ( A )。
(A)
(B) A－ B＝
A＝B
(C)A B＝ A C B＝ C
为
.
pq
9. 设 p :天下雨， q : 我骑自行车上班，则命题“如果天不下雨
化为
.
pq
, 但老王还是来了”符号化 , 我就骑自行车上班”符号
10. 设 p, q 的真值为 0，r , s 的真值为 1，则命题公式 ( p r ) ( q s) 的真值为 .0
11. 设 p, q 的真值为 0， r 的真值为 1，则命题公式 p ( q r ) 的真值为 .0
C. （ ） F（ x ，y ） →（
D.
x ( x 2 - 1 > 0)
y ）G（ x ， y ）
）B
7. 集合 X = { a , b, c , d } 上的关系 R = {( a, a), ( b , c ), ( c, b), ( d , d )} 是 （） D
A) 自反的、 B) 传递的、 C) 等价的
S＝{(1,3),(2,3),(3,2)} 。
则 R S＝_{(1, 3),(2, 2)};
=___{(2,4),(3,3),(4,2)};
R2＝__{(1, 1),(1, 2),(1, 3)}.
8、使命题公式 P (P Q)成假的赋值是 10 设 p : 天气很冷， q : 老王还是来了，则命题“虽然天气很冷