发布时间 : 星期日 文章离散数学复习题(5.30日更新)更新完毕开始阅读76832d7124c52cc58bd63186bceb19e8b9f6ec46
56. 设A={a,b,c},则A?A的双射共有( )。
A.3个
B.6个
C.8个
D.9个
D.既非入射也非满射
57. 设N是自然数集，R是实数集，函数f：Ｎ→R，f(n)=lgn是( )。
A.满射但非入射
B.入射但非满射
C.双射
58. 设A={1, 2, 3, 4, 5, 6}, B={a, b, c, d, e}，以下哪一个关系是从A到B的满射函数( )。
A. f={<1, a>, <2, b>, <3, c>, <4, d>, <5, e>} B. f={<1, e>, <2, d>, <3, c>, <4, b>, <5, a>, <6, e>} C. f={<1, a>, <2, b>, <3, c>, <4, a>, <5, b>, <6, c>} D. f={<1, a>, <2, b>, <3, c>, <4, d>, <5, e>, <1, b>} 59. 如右图2的最大入度是( )。
A. 0 A. 5
B. 1 B. 6
C. 2 C. 7
D. 3 D. 8
D. E′≠E且V′≠V D. 0或2
图2
60. 设有一个无向连通图，共有6个结点、且每个结点的度均为2，则它的边数为( )。 61. 设图G′=
A. V′≠V但E′=E A. 0
B. V′=V B. 1
C. E′=E
62. 在有3个结点的图中，度为奇数的结点个数为( )。
C. 1或3
63. 下列各有向图是强连通图的是( )。
A B C D 64. 在有n个结点的连通图中，其边数( )。
A．最多有n-1条 A. 6
B．至少有n-1条 B. 9
C．最多有n条 C. 12
D．至少有n条 D. 18
65. 设简单图G所有结点的度数之和为36，由G的边数为( )。
66. 设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点
数是( )。 A．3 A.8
B．4 B.16
C．5 C.4
D．6 D.32
67. 无向图G中有16条边，且每个结点的度数均为2，则结点数是( )
68. 设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点
数是( ) A．3
B．4
C．5
D．6
69. 设有向图G有5个结点，4条边，且有一条有向路经过每个结点一次，则图G满足的最大
连通性是( )。 A.不连通
B.弱连通
C.单侧连通
D.强连通
70. 下列各图是无向完全图的是( )
A B C D 71. 给定n个结点的一个图，它还是一个树的下列说法中，( )是不对的。 ．．
A.无回路的连通图 72. 下列是树的是( )。 ．
B.无回路但若增加一条新边就会变成回路 D.连通且边数=结点数-1
C.所有结点的度数≥2
a b c d e
f
A
a b c d e f
B
a b c d e f
C
a b c d e f
D
二、解答题：
1. 第一章与第二章所布置的所有的课后作业。 2. 试构造命题公式(P?(Q∧R))??P的真值表。 3. 用真值表法求?(P?Q)?(P??Q)的主析取范式。 4. 用等值演算法求?(P?Q)?(P??Q)的主合取范式。 5. 求(P?Q)?R的主析取范式。
6. 利用真值表判断公式((?P∨Q)∧(Q?R)) ??(P∧?R)是否为重言式。
7. 分别用真值表法与等值演算法判断这两个公式是否等价：?(A?B)，(A∧?B)∨(?A∧B)。 8. 利用谓词符号化句子：“并不是所有的大学生都是共产党员”。 9. 求公式?((?x)F(x,y)?(?y)G(x,y))∨(?x)H(x)的前束范式。
10. 给定个体域D={a,b},F(a,b)=1,F(a,b)=0,F(b,a)=0,F(b,b)=1,试求(?x)(?y)F(x,y)的真值。 11. 用谓词逻辑将命题符号化：有些运动员只钦佩某些教练。
12. 如果论域是集合{a,b,c}，试消去给定公式中的量词：(?y)(?x)(x+y=0)。 13. 对任意集合A, B, C，确定下列各命题是否为真，并证明之。
1) 如果A?B及B?C，则A?C； 2) 如果A?B及B?C，则A?C。
14. 确定下列集合的幂集：a) {a, {a}}；b) {{1, {2,3}}}；c) {?, a, {b}}；d) ?(?)；e) ?(?(?))。 15. 设某集合有101个元素，试问：
1) 可构成多少个子集?
2) 其中有多少个子集的元素为奇数? 3) 是否会有102个元素的子集?
16. 设A={0,1}, B={1,2}, 确定下列集合：a) A?{1}?B；b) (B?A)2。 17. 设A={a, b}, 构成集合?(A)?A。
18. 在一个有n个元素的集合上，可以有多少个不同的关系。
19. 对{0, 1, 2, 3, 4, 5, 6}上的二元关系R={ 20. 设P={<1,2>, <2,4>, <3,3>}和Q={<1,3>, <2,4>, <4,2>}，找出P∪Q, P∩Q, dom(P), dom(Q), ran(P), ran(Q), dom(P∩Q), ran(P∩Q)。 21. 分析集合A={1,2,3}上的下述五个关系。 R ={<1,1>, <1,2>, <1,3>, <3,3>} S ={<1,1>, <1,2>, <2,1>, <2,2>, <3,3>} T ={<1,1>, <1,2>, <2,2>, <2,3>} ?=空关系 A?A=全域关系 判断上述A上的关系是不是 a)自反的，b)对称的，c)可传递的，d)反对称的。 22. 设集合A={a, b, c, d}，A上的关系R={ 法求出R的自反闭包、对称闭包和传递闭包。 23. 设R1和R2是A上的任意关系，说明以下命题的真假，并予以证明。 a) 若R1和R2是自反的，则R1?R2也是自反的。 b) 若R1和R2是反自反的，则R1?R2也是反自反的。 c) 若R1和R2是对称的，则R1?R2也是对称的。 d) 若R1和R2是传递的，则R1?R2也是传递的。 24. R是A上的一个二元关系，如果R是自反的，则Rc一定是自反的吗？如果R是对称的， 则Rc一定是对称的吗？如果R是传递的，则Rc一定是传递的吗？ 25. 设集合为{3, 5, 15}，{1, 2, 3, 6, 12}，{3, 9, 27, 54}，偏序关系为整除，画出这些集合的偏序 关系图，并指出哪些是全序关系。 26. 在偏序集 16, 24, 32, 36}的极大元，极小元，最大元，最小元，上确界和下确界。 27. 设A={1,2,3,4}，给定A上二元关系R={<1,2>, <1,3>, <2,3>,<3,4>}，求r(R), s(R)。 28. 若集合A={{1,{2,3}}, {2}}的幂集为P(A)，集合B={{?,2},{2}}的幂集为P(B)，求P(A)∩P(B)。 29. 对于集合A，设|A|=3，共有多少种不同的划分?试举例说明。 30. 4个元素的集合共有多少个不同的划分？ 31. 给定集合S ={1, 2, 3, 4, 5}，找出S上的等价关系R，此关系R能够产生划分{{1, 2}, {3}, {4, 5}} 并画出关系图。 32. 根据右图所示的有向图，写出邻接矩阵和关系R，并求出R的自反 闭包和对称闭包。 33. 设集合A={a, b, c, d}，A上的关系R={ a) 用矩阵运算和作图方法求出R的自反闭包、对称闭包和传递闭包。 34. 设有集合A={a,b,c,d}，B={2,3,4}，C={x,y,z}。A到B的关系 ?1 = {< a,2>, B到C的关系 ?2 = {<2,x>,<3,y>,<4,x>,<4,z>}，设?3=?2-1??1-1，求?3。 35. 设A＝{2, 4, 8, 16, 24, 32, 36, 40, 48}，R为A上整除关系，试画 (自反性、反自反性、对称性、反对称性、传递性)。 37. 设集合P={x1, x2, x3, x4, x5}上的偏序关系如右图所示，找出P中的 最大元素，最小元素，极大元素，极小元素。找出子集{x2, x3, x4}，{x3, x4, x5}和{x1, x2, x3}的上界、下界、上确界、下确界。 关系图，并指出哪些是全序关系。 39. 在右图中给出一个有向图，试求该图的邻接矩阵，并求出可达性矩 阵和距离矩阵。 40. 设A、B是两个集合，|A|=2, |B|=3。由A?B能生成多少个不同的 函数?由B?A能生成多少个不同的函数? 之和，问至少要执行几次加法指令? 42. 写出右图相对于完全图的补图。 43. 试画出结点数为4的: (1)强连通图；(2)单向连通图；(3)弱连通图；(4)非连 v3 v4 x2 x4 x1 x3 x5 38. 设集合为{3, 5, 15}，{1, 2, 3, 6, 12}，{3, 9, 27, 54}，偏序关系为整除，画出这些集合的偏序 v2 v1 v5 41. 假设有一台计算机，它有一条加法指令，可计算3个数之和。如果要求9个数x1, x2,…, x9