一、填空题
1 设集合 A,B ，其中 A ＝ {1,2,3}, B= {1,2},
则 A - B ＝ ________{3}____________;
(A) - (B) ＝ _____{{3},{1,3},{2,3},{1,2,3}}_______ .
n
2. 2. 设有限集合 A, |A| = n, 则 | (A ×A)| = __ 22
2 = {( a,2),
3. 设集合 A = { a, b}, B = {1, 2}, 则从 A 到 B 的所有映射是 __ (b,2)}, = {( a,1), (b,2)},
3
1 = {( a,1), (b,1)},
= {( a,2), ( b,1)};_, 其中双射的是 ____
4
,
3 4
._
4. 已 知 命 题 公 式 G ＝ (P Q) ∧ R ， 则 G 的 主 析 取 范 式 是 ______(P ∧ Q ∧ R)__________________.
5.设 G 是完全二叉树， G 有 7 个点，其中 点数为 _______3_________.
4 个叶点，则 G 的总度数为 ___12_______ ，分枝
6 设 A 、B 为两个集合 , A= {1,2,4}, B = {3,4},
则从 A B ＝_______{4}__________________;
A B＝ _____{1, 2, 3, 4}____________;A － B ＝ ____{1, 2}_________________ .
__自反性；对称性；
3. 7. 设 R 是集合 A 上的等价关系，则 R 所具有的关系的三个特性是
传递性 _______________________________.
8. 设命题公式 G＝ (P
(Q R))，则使公式 G 为真的解释有 ____(1, 0, 0)________ ， ___
_(1, 0, 1)_________, ____(1, 1, 0)______________________.
9. 设集合 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)}__________,R 2?R1 =___{(2,4),(3,3),(4,2)}_______, R12 =_____{(2,2),(3,3)}__________________.
4. 10. 设有限集 A, B ， |A| = m, |B| = n, 则 | | (A B)| = ___2 m n_____.
11 设 A,B,R 是三个集合， 其中 R 是实数集， A = {x | -1 ≤x≤ 1, x R}, B = {x | 0 ≤ x < 2, x R}, 则 A-B = _{x | -1 ≤ x < 0, x R}_______ , B-A = __{x | 1 < x < 2, x
A ∩ B =
R}_____ ,
___{x | 0 ≤ x≤ 1, x R}_______________________ , .
5. 13. 设集合 A ＝ {2, 3, 4, 5, 6} ，R 是 A 上的整除，则 R 以集合形式 (列举法 )记为 __{(2, 2),(2,
4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}_____________________________ .
xQ(x) ，则 G 的前束范式是 __ x( P(x)∨Q(x))_.
6. 14. 设一阶逻辑公式 G = xP(x)
15.设 G 是具有 8 个顶点的树，则 G 中增加 __21_______条边才能把 G 变成完全图。 16. 设谓词的定义域为 { a, b}, 将表达式
xR(x) → xS(x) 中量词消除，写成与之对应的命题公 式是 ____(R(a)∧ R(b)) → (S(a)∨ S(b))_______________________.
17. 设集合 A ＝ {1, 2, 3, 4} ， A 上的二元关系 R＝ {(1,1),(1,2),(2,3)}, S ＝ {(1,3),(2,3),(3,2)} 。则
R S＝ _{(1, 3),(2, 2)}_____________________________,
R2＝ ___{(1, 1),(1, 2),(1, 3)}.______________________.
二、选择题
1 设集合 A={2,{a},3,4} ， B = {{a},3,4,1} ， E 为全集，则下列命题正确的是 ( C )。 (A){2}
A
(B){a}
A
(C)
{{a}}
B E (C)对称性
(D){{a},1,3,4}
B.
).
2 设集合 A={1,2,3},A
(A) 自反性
( B )。 (A) 下界
上的关系 R＝ {(1,1),(2,2),(2,3),(3,2),(3,3)} ，则 R 不具备 ( D (B) 传递性
(D) 反对称性
3 设半序集 (A, ≤ )关系≤的哈斯图如下所示，若
(B) 上界
(C) 最小上界
A 的子集 B = {2,3,4,5}, 则元素
(D) 以上答案都不对
6 为 B 的
6
4 下列语句中， ( B)是命题。
(A) 请把门关上 (C)x + 5 > 6
(B) 地球外的星球上也有人 (D) 下午有会吗？
D ＝{a,b},
5 3
4 2 1
5 设 I 是如下一个解释：
P( a, a) P(a,b) P(b,a) P(b,b) 1
).
0
1
0
x yP(x,y).
则在解释 I 下取真值为 1 的公式是 ( D
(A) x yP(x,y) (A)(1,2,2,3,4,5)
(B) x yP(x,y) (B)(1,2,3,4,5,5)
(C) xP(x,x)(D)
(C)(1,1,1,2,3)
6. 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是
( C ).
(D)(2,3,3,4,5,6).
7. 设 G、 H 是一阶逻辑公式， P 是一个谓词， G＝ xP(x), H ＝ xP(x), 则一阶逻辑公式 G H 是 ( C ).
(A) 恒真的 (A)G H (A)A ＝ B (A) 自反性 (B) 恒假的 (B)H
G
(C)可满足的 (C)G ＝H (C)B A
(D)前束范式 .
8 设命题公式 G＝ (P
Q)，H ＝P (Q
)时 A － B＝ B. P)，则 G 与 H 的关系是 ( A ) 。 (D) 以上都不是 .
9 设 A, B 为集合，当 ( D
(B)A B (D)A ＝ B＝ . (C)对称性
10 设集合 A = {1,2,3,4}, A 上的关系 R＝ {(1,1),(2,3),(2,4),(3,4)},
则 R 具有 ( B)。
(B) 传递性 (D)以上答案都不对 {a,b,c}(D){a,b} {a,b,c}
11 下列关于集合的表示中正确的为( B)。
(A){a} {a,b,c}(B){a} {a,b,c} (C)
12 命题 xG(x) 取真值 1 的充分必要条件是 ( ).
(A) 对任意 x， G(x) 都取真值 1. (B) 有一个 x0，使 G(x 0 )取真值 1.
(C) 有某些 x，使 G(x 0)取真值 1. (D) 以上答案都不对 .
13. 设 G 是连通平面图，有 5 个顶点， 6 个面，则 G 的边数是 ( A ).
(A) 9 条 (A)6
(B) 5 条
(C) 6 条
(D) 11 条 .
)条边可以得到树 .
14. 设 G 是 5 个顶点的完全图，则从
G 中删去 ( A
(B)5
(C)10 (D)4.
0 1 1 1 1
15. 设图 G 的相邻矩阵为
1 0 1 0 0 ，则 G 的顶点数与边数分别为 ( D ). 1 1 0 1 1 1 0 1 0 1 1 0 1 1 0
(A)4, 5
(B)5, 6 (C)4, 10 (D)5, 8.
三、计算证明题
1.设集合 A ＝ {1, 2, 3, 4, 6, 8, 9, 12} ， R 为整除关系。
(1) 画出半序集 (A,R) 的哈斯图；
(2) 写出 A 的子集 B = {3,6,9,12} 的上界，下界，最小上界，最大下界；
(3) 写出 A 的最大元，最小元，极大元，极小元。
12
8
6
9
4
2
3
(1)
1
(2) B 无上界，也无最小上界。下界
1, 3; 最大下界是 3.
(3) A 无最大元，最小元是 1，极大元 8, 12, 90+; 极小元是 1.
2. 设集合 A ＝ {1, 2, 3, 4} ， A 上的关系 R＝ {(x,y) | x, y A 且 x y}, 求
(1) 画出 R 的关系图； (2) 写出 R 的关系矩阵 .
R = {(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.
(1)
1 4
2 3
1 0 0 0 1 1 0 0 (2) M R 1 1 1 0 1 1 1 1
3. 设 R 是实数集合，
, , 是 R 上的三个映射， (x) = x+3, (x) = 2x, (x) ＝
映射 ? ， ? , ? ,
? ， ? ? .
(1) ? ＝ ( (x)) ＝ (x)+3 ＝ 2x+3 ＝ 2x+3.
(2) ? ＝ ( (x)) ＝ (x)+3 ＝ (x+3)+3 ＝x+6, (3) ? ＝ ( (x)) ＝ (x)+3 ＝ x/4+3, (4) ? ＝ ( (x)) ＝ (x)/4 ＝2x/4 = x/2,
(5) ? ? ＝ ?( ? )＝ ? +3＝ 2x/4+3 ＝x/2+3.
试求复合
x/4,
4. 设 I 是如下一个解释： D = {2, 3},
a
b f (2) f (3) P(2, 2)
P(2, 3) 3
2
3
2
0
0
试求 (1) P(a, f (a))∧ P(b, f (b));
(2) x y P (y, x).
(1) P(a, f (a))∧ P(b, f (b)) = P(3, f (3)) ∧ P(2, f (2))
= P(3, 2)∧ P(2, 3)
= 1∧ 0 = 0.
(2) x y P (y, x) = x (P (2, x)∨ P (3, x))
= (P (2, 2) ∨ P (3, 2))∧ (P (2, 3) ∨P (3, 3))
= (0 ∨1)∧ (0∨ 1)
= 1∧ 1
= 1.
5. 设集合 A ＝ {1, 2, 4, 6, 8, 12} ， R 为 A 上整除关系。
(1) 画出半序集 (A,R) 的哈斯图；
(2) 写出 A 的最大元，最小元，极大元，极小元；
(3) 写出 A 的子集 B = {4, 6, 8, 12} 的上界，下界，最小上界，最大下界1)
8
12
4
6
2
1
(2) 无最大元，最小元 1，极大元 8, 12; 极小元是 1. (3) B 无上界，无最小上界。下界
1, 2; 最大下界 2.
6. 设命题公式 G = (P→ Q)∨ (Q∧( P→R)), 求 G 的主析取范式。 G = (P→ Q)∨ (Q∧ ( P→R))
= ( P∨ Q) ∨ (Q∧ (P∨ R))
P(3, 2) P(3, 3)
1
1
.
= (P∧ Q)∨(Q∧ (P∨R))
= (P∧ Q)∨(Q∧ P)∨ (Q∧ R)
= (P∧ Q∧ R) ∨ (P∧ Q∧ R)∨(P∧ Q∧ R)∨ (P∧ Q∧ R)∨ (P∧ Q∧R)∨ ( P∧ Q∧ R)
= (P∧ Q∧ R) ∨ (P∧ Q∧ R)∨(P∧ Q∧ R)∨ (P∧ Q∧ R)∨ ( P∧Q∧ R)
= m3∨ m4∨ m5 ∨ m6∨ m7 = (3, 4, 5, 6, 7).
7. (9 分 )设一阶逻辑公式： G = ( xP(x)∨ yQ(y))→
xR(x)，把 G 化成前束范式 .
G = ( xP(x)∨ yQ(y)) → xR(x)
= ( xP(x)∨ yQ(y))∨ xR(x)
= (
xP(x)∧ yQ(y))∨ xR(x)
= ( x P(x)∧ y Q(y))∨ zR(z)
= x y z(( P(x)∧ Q(y))∨ R(z))
9. 设 R 是集合 A = {a, b, c, d}. R
是 A 上的二元关系 , R = {(a,b), (b,a), (b,c), (c,d)},
(1) 求出 r(R), s(R), t(R) ；
(2) 画出 r(R), s(R), t(R) 的关系图 .
(1) r(R) ＝ R∪ IA ＝ {(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d)},
－
s(R)＝ R∪ R1＝ {(a,b), (b,a), (b,c), (c,b) (c,d), (d,c)},
t(R) ＝ R∪R2∪ R3∪R4＝ {(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)} ；
(2) 关系图 :
d
a b
d a b
a
c
b
d c t(R)
c r(R)
s(R)
11. 通过求主析取范式判断下列命题公式是否等价：
(1) G = (P ∧Q) ∨ ( P∧ Q∧ R) (2) H = (P ∨(Q ∧ R))∧ (Q∨ ( P∧ R)) G＝ (P∧Q) ∨ ( P∧ Q∧ R)
＝ (P∧ Q∧ R)∨ (P∧ Q∧R)∨ ( P∧ Q∧ R)
＝ m6∨ m7∨ m3
《离散数学》试题及答案详解.doc
