《离散数学》复习题 单项选择题 1. 判断下列命题哪个正确 （B）。 A. 所有空集都不相等 B. {} C. 若A为非空集，则AA成立 D. 所有空集都不一定相等 2. 下列语句中是真命题的为（D）。 A. 我
《离散数学》复习题
单项选择题
1. 判断下列命题哪个正确 （B）。
A. 所有空集都不相等 B. {θ}≠θ
C. 若A为非空集，则A∈A成立 D. 所有空集都不一定相等
2. 下列语句中是真命题的为（D）。
A. 我正在说谎。 B. 如果2+3=5，那么雪是黑色的。
C. 严禁在教室里吸烟！ D. 如果2+3=8，那么雪是黑色。
3. 设A={a,{a}}，下列命题错误的是（B）。
A. {a}P(A) B. {a}P(A) C. { {a}}P(A) D. { {a}}P(A)
4. 设G是5个顶点的完全图，则从G中删去（A）条边可以得到树.
A. 6 B. 5 C. 10 D. 4.
5. 若A-B=θ,则下列哪个结论不可能正确（D）。
A. B. C. D.
6. 任意一个具有2个或以上元的半群，它（A）。
A. 不可能是群 B. 不一定是群
C. 一定是群 D. 是交换群
7. 判断下列命题正确的是（B）。
A. B.
C. D.
8. 设集合A = {1,2,3,4}, A上的关系R＝{(1,1),(2,3),(2,4),(3,4)}, 则R具有（B）。
A. 自反性 B. 传递性
C. 对称性 D. 以上答案都不对
9. 设G是连通平面图，有5个顶点，6个面，则G的边数是（A）。
A. 9条 B. 5条 C. 6条 D. 11条
10. 6阶有限群的任何子群一定不是（C）。
A. 2阶 B. 3阶 C. 4阶 D. 6阶
11. 下列建立在集合 的诸多关系中，满足传递性的是（B）。
A. B.
C. D.
12. 判断下列命题（A）为真。
A. A-B=B-A =＞ A=B B. 空集是任何集合的真子集
C. 空集只是非空集合的子集 D. 若A的一个元素属于B，则A=B
13. 在自然数集N上，下列（B）运算是可结合的。
A. a*b=a-b B. a*b=max{a,b} C. a*b=a+2b D. a*b=|a-b|
14. 无向图G中的边e是其割边的充要条件是（C）。
A. 边e不是平行边 B. 边e是平行边
C. 边e不包含在G的任意闭迹中 D. 边e不包含在G的任意闭回路中
15. 具有6个顶点，12条边的联通简单平面图中，每个面都是由（C）条边围成。
A. 2 B. 4 C. 3 D. 5
16. 给定下列数字序列，（C） 可以构成简单无向图的顶点度序列。
A. B.
C. D.
17. 在自然数集N上，下列哪种运算是可结合的（B）。
A. B.
C. D.
18. 设P：我去看电影，Q：我有时间，将命题“我去看电影，仅当我有时间”可符号化为（A）。
A. B.
C. D.
19. 设集合A={2,{a},3,4}，B = { {a},3,4,1}，E为全集，则下列命题正确的是（C）。
A. {2}A B. {a}A C. { {a}}BE D. { {a},1,3,4}B.
20. 设命题公式G＝(PQ)，H＝P(QP)，则G与H的关系是（A）。
A. GH B. HG C. G＝H D. 以上都不是
21. 设G是有n个结点m条边的连通平面图，且有k个面，则k等于（A）。
A. m-n+2 B. n-m-2 C. n+m-2 D. m+n+2
22. 设集合A={2,{a},3,4}，B = { {a},3,4,1}，E为全集，则下列命题正确的是（C）。
A. {2}A B. {a}A C. { {a}}BE D. { {a},1,3,4}B.
23. 设图G的相邻矩阵为上图所示，则G的顶点数与边数分别为（D)。
A. 4, 5 B. 5, 6 C. 4, 10 D. 5, 8.
24. 设命题公式G＝(PQ)，H＝P(QP)，则G与H的关系是（A ）。
A. GH B. HG C. G＝H D. 以上都不是
25. 给定下列数字序列，（C）可以构成简单无向图的顶点度序列。
A. （1,3,4,4,5） B.（1,1,2,2,3）
C. （1,1,2,2,2） D.（0,1,3,3,3）
26. 判断下列命题（ B）正确 。
A. 所有空集都不相等 B.
C. D. 非必要条件
27. 已知 是集合A上的两个等价关系，则下列一定还是等价关系的是（A ）。
A. B.
C. D.
28. 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是（C ）。
A. (1,2,2,3,4,5) B. (1,2,3,4,5,5)
C. (1,1,1,2,3) D. (2,3,3,4,5,6).
29. 下列哪些公式为永真蕴含式 （A）。
A. B.
C. D.
30. 设G是一棵树，n,m分别表示顶点数和边数，则（C）。
A. n=m B. m=n+1 C. n=m+1 D. 不能确定
31. 设G是一个哈密尔顿图，则G一定是（D）。
A. 欧拉图 B. 树 C. 平面图 D. 连通图
32. 在有n个顶点的联通图中，其边数（B）。
A. 最多有n-1条 B. 至少有n-1条
C. 最多有n条 D. 至少有n条
33. 下列哪个偏序集构成有界格（D）。
A. B.
C. D.
34. 下列哪些公式为永真蕴含式（A）。
A. B.
C. D.
35. 集合A={1,2,…,10}上的关系R={ |x+y=10,x,yA}，则R 的性质为（B）。
A. 自反的 B. 对称的 C. 传递的，对称的 D. 传递的
36. 具有6个顶点，12条边的联通简单平面图中，每个面都是由（C）条边围成。
A. 2 B. 4 C. 3 D. 5
37. 设全体域D是正整数集合，确定下列命题的真值（D）。
A. xy (xy=y) B. xy(x+y=y) C. xy(x+y=x) D. xy(y=2x)
38. 在有n个顶点的联通图中，其边数（B）。
A. 最多有n-1条 B. 至少有n-1条 C. 最多有n条 D. 至少有n条
39. 设无向图G有16条边且每个顶点的度数都是2，则图G有（D）个顶点。
A. 10 B. 4 C. 8 D. 16
40. 集合 上的关系 ，则R的性质为（B）。
A. 自反的 B. 对称的 C. 传递的，对称的 D. 传递的
二、多项选择题
1. 设有下列公式，请问哪几个是永真蕴涵式（CE）。
A. B. C.
D. E.
2. 下列哪些（ABC）为永真式。
A. B.
C. D.
E.
3. 判断下列命题（BD）为正确。
A. B.
C. D.
E.
4. 下列公式中（ BCD）是永真式。
A. B.
C. D.
E.
5. 判断下列语句是不是命题。若是，给出命题的真值（ABD）。
A. 北京是中华人民共和国的首都 B. 陕西师大是一座工厂
C. 你喜欢唱歌吗？ D. 若7+8＞18，则三角形有4条边
E. 前进！
三、计算题
1. 通过求主析取范式判断下列命题公式是否等价：
(1) G = (P∧Q)∨(P∧Q∧R)
(2) H = (P∨(Q∧R))∧(Q∨(P∧R))
2.设一阶逻辑公式：G = (xP(x)∨yQ(y))→xR(x)，把G化成前束范式.
3.利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。
4. 设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a, a),(a, c),(b, c),(c, d)}, S＝{(a, b),(b, c),(b, d),(d, d)}.
(1) 试写出R和S的关系矩阵；
(2) 计算R•S, R∪S, R－1, S－1•R－1.
5. 设A,B为任意集合，证明：(A-B)-C = A-(B∪C).
证明：(A-B)-C = (A∩~B)∩~C
= A∩(~B∩~C)
= A∩~(B∪C)
= A-(B∪C)
6. A, B为两个任意集合，求证：A－(A∩B) = (A∪B)－B
7.
单项选择题
1. 判断下列命题哪个正确 （B）。
A. 所有空集都不相等 B. {θ}≠θ
C. 若A为非空集，则A∈A成立 D. 所有空集都不一定相等
2. 下列语句中是真命题的为（D）。
A. 我正在说谎。 B. 如果2+3=5，那么雪是黑色的。
C. 严禁在教室里吸烟！ D. 如果2+3=8，那么雪是黑色。
3. 设A={a,{a}}，下列命题错误的是（B）。
A. {a}P(A) B. {a}P(A) C. { {a}}P(A) D. { {a}}P(A)
4. 设G是5个顶点的完全图，则从G中删去（A）条边可以得到树.
A. 6 B. 5 C. 10 D. 4.
5. 若A-B=θ,则下列哪个结论不可能正确（D）。
A. B. C. D.
6. 任意一个具有2个或以上元的半群，它（A）。
A. 不可能是群 B. 不一定是群
C. 一定是群 D. 是交换群
7. 判断下列命题正确的是（B）。
A. B.
C. D.
8. 设集合A = {1,2,3,4}, A上的关系R＝{(1,1),(2,3),(2,4),(3,4)}, 则R具有（B）。
A. 自反性 B. 传递性
C. 对称性 D. 以上答案都不对
9. 设G是连通平面图，有5个顶点，6个面，则G的边数是（A）。
A. 9条 B. 5条 C. 6条 D. 11条
10. 6阶有限群的任何子群一定不是（C）。
A. 2阶 B. 3阶 C. 4阶 D. 6阶
11. 下列建立在集合 的诸多关系中，满足传递性的是（B）。
A. B.
C. D.
12. 判断下列命题（A）为真。
A. A-B=B-A =＞ A=B B. 空集是任何集合的真子集
C. 空集只是非空集合的子集 D. 若A的一个元素属于B，则A=B
13. 在自然数集N上，下列（B）运算是可结合的。
A. a*b=a-b B. a*b=max{a,b} C. a*b=a+2b D. a*b=|a-b|
14. 无向图G中的边e是其割边的充要条件是（C）。
A. 边e不是平行边 B. 边e是平行边
C. 边e不包含在G的任意闭迹中 D. 边e不包含在G的任意闭回路中
15. 具有6个顶点，12条边的联通简单平面图中，每个面都是由（C）条边围成。
A. 2 B. 4 C. 3 D. 5
16. 给定下列数字序列，（C） 可以构成简单无向图的顶点度序列。
A. B.
C. D.
17. 在自然数集N上，下列哪种运算是可结合的（B）。
A. B.
C. D.
18. 设P：我去看电影，Q：我有时间，将命题“我去看电影，仅当我有时间”可符号化为（A）。
A. B.
C. D.
19. 设集合A={2,{a},3,4}，B = { {a},3,4,1}，E为全集，则下列命题正确的是（C）。
A. {2}A B. {a}A C. { {a}}BE D. { {a},1,3,4}B.
20. 设命题公式G＝(PQ)，H＝P(QP)，则G与H的关系是（A）。
A. GH B. HG C. G＝H D. 以上都不是
21. 设G是有n个结点m条边的连通平面图，且有k个面，则k等于（A）。
A. m-n+2 B. n-m-2 C. n+m-2 D. m+n+2
22. 设集合A={2,{a},3,4}，B = { {a},3,4,1}，E为全集，则下列命题正确的是（C）。
A. {2}A B. {a}A C. { {a}}BE D. { {a},1,3,4}B.
23. 设图G的相邻矩阵为上图所示，则G的顶点数与边数分别为（D)。
A. 4, 5 B. 5, 6 C. 4, 10 D. 5, 8.
24. 设命题公式G＝(PQ)，H＝P(QP)，则G与H的关系是（A ）。
A. GH B. HG C. G＝H D. 以上都不是
25. 给定下列数字序列，（C）可以构成简单无向图的顶点度序列。
A. （1,3,4,4,5） B.（1,1,2,2,3）
C. （1,1,2,2,2） D.（0,1,3,3,3）
26. 判断下列命题（ B）正确 。
A. 所有空集都不相等 B.
C. D. 非必要条件
27. 已知 是集合A上的两个等价关系，则下列一定还是等价关系的是（A ）。
A. B.
C. D.
28. 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是（C ）。
A. (1,2,2,3,4,5) B. (1,2,3,4,5,5)
C. (1,1,1,2,3) D. (2,3,3,4,5,6).
29. 下列哪些公式为永真蕴含式 （A）。
A. B.
C. D.
30. 设G是一棵树，n,m分别表示顶点数和边数，则（C）。
A. n=m B. m=n+1 C. n=m+1 D. 不能确定
31. 设G是一个哈密尔顿图，则G一定是（D）。
A. 欧拉图 B. 树 C. 平面图 D. 连通图
32. 在有n个顶点的联通图中，其边数（B）。
A. 最多有n-1条 B. 至少有n-1条
C. 最多有n条 D. 至少有n条
33. 下列哪个偏序集构成有界格（D）。
A. B.
C. D.
34. 下列哪些公式为永真蕴含式（A）。
A. B.
C. D.
35. 集合A={1,2,…,10}上的关系R={ |x+y=10,x,yA}，则R 的性质为（B）。
A. 自反的 B. 对称的 C. 传递的，对称的 D. 传递的
36. 具有6个顶点，12条边的联通简单平面图中，每个面都是由（C）条边围成。
A. 2 B. 4 C. 3 D. 5
37. 设全体域D是正整数集合，确定下列命题的真值（D）。
A. xy (xy=y) B. xy(x+y=y) C. xy(x+y=x) D. xy(y=2x)
38. 在有n个顶点的联通图中，其边数（B）。
A. 最多有n-1条 B. 至少有n-1条 C. 最多有n条 D. 至少有n条
39. 设无向图G有16条边且每个顶点的度数都是2，则图G有（D）个顶点。
A. 10 B. 4 C. 8 D. 16
40. 集合 上的关系 ，则R的性质为（B）。
A. 自反的 B. 对称的 C. 传递的，对称的 D. 传递的
二、多项选择题
1. 设有下列公式，请问哪几个是永真蕴涵式（CE）。
A. B. C.
D. E.
2. 下列哪些（ABC）为永真式。
A. B.
C. D.
E.
3. 判断下列命题（BD）为正确。
A. B.
C. D.
E.
4. 下列公式中（ BCD）是永真式。
A. B.
C. D.
E.
5. 判断下列语句是不是命题。若是，给出命题的真值（ABD）。
A. 北京是中华人民共和国的首都 B. 陕西师大是一座工厂
C. 你喜欢唱歌吗？ D. 若7+8＞18，则三角形有4条边
E. 前进！
三、计算题
1. 通过求主析取范式判断下列命题公式是否等价：
(1) G = (P∧Q)∨(P∧Q∧R)
(2) H = (P∨(Q∧R))∧(Q∨(P∧R))
2.设一阶逻辑公式：G = (xP(x)∨yQ(y))→xR(x)，把G化成前束范式.
3.利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。
4. 设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a, a),(a, c),(b, c),(c, d)}, S＝{(a, b),(b, c),(b, d),(d, d)}.
(1) 试写出R和S的关系矩阵；
(2) 计算R•S, R∪S, R－1, S－1•R－1.
5. 设A,B为任意集合，证明：(A-B)-C = A-(B∪C).
证明：(A-B)-C = (A∩~B)∩~C
= A∩(~B∩~C)
= A∩~(B∪C)
= A-(B∪C)
6. A, B为两个任意集合，求证：A－(A∩B) = (A∪B)－B
7.
