离散数学复习题及答案.docx

1、离散数学复习题及答案1. 写出命题公式 （P （P Q）的真值表。答案：2.证明 答案：3. 证明以下蕴涵关系成立： 答案：4. 写出下列式子的主析取范式：答案：5. 构造下列推理的论证：pq, pr, st, sr, t q答案：st 前提 t 前提s 拒取式I12sr 前提r 假言推理I11pr 前提p 拒取式I12pq 前提q 析取三段论I106. 用反证法证明：p(rs)q), p, s q7. 请将下列命题符号化：所有鱼都生活在水中。答案：令F( x )：x是鱼 W( x )：x生活在水中8. 请将下列命题符号化：存在着不是有理数的实数。答案：令 Q ( x )：x 是有理数 R (

2、 x )：x 是实数9. 请将下列命题符号化：尽管有人聪明，但并非一切人都聪明。答案：令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为10. 请将下列命题符号化：对于所有的正实数x,y，都有x+yx。答案：令P(x):x是正实数 S(x,y): x+yx11. 请将下列命题符号化：每个人都要参加一些课外活动。答案：令P(x):x是人 Q(y): y是课外活动 S(x,y):x参加y12. 请将下列命题符号化：某些人对某些药物过敏。答案：令P(x):x是人 Q(y): y是药 S(x,y):x对y过敏13. 求的对偶式:答案：14. 求下列谓词公式的前束范式：答案：15. 证明：

3、答案：16. 用反证法证明：x(P(x)Q(x) , xP(x) xQ(x)答案：17. 证明：前提： x(C(x)W(x)R(x), x(C(x)Q(x).结论： x(Q(x)R(x).答案： (1) x(C(x)Q(x) 前提引入 (2) C(a)Q(a) (1)ES (3) C(a) (2)化简规则 (4) x(C(x)W(x)R(x) 前提引入 (5) C(a)W(a)R(a) (4)US (6) W(a)R(a) (3)(5)假言推理 (7) R(a) (6)化简规则 (8) Q(a) (2)化简规则 (9) R(a)Q(a) (7)(8)合取引入规则 (10) x(Q(x)R(x)

4、 (9)EG18. 判断：下列命题是否正确？答案： (1) (2) (3) (4) (5) (6) (7) (8) 19. 列出下列集合的元素 (1) x|xNt(t2,3x=2t) (2) x|xNts(t0,1s3,4txs) (3) x|xNt(t整除2xt)答案： (1) 4,6 (2) 1,2,3 (3) 3,4,520. S=0,1,2,3,4,5,6,7,8,9，A=2,4,5,6,8B=1,4,5,9，C=x|xZ+, 2x5答案：21. 一个学校有507，292，312和344个学生分别选择了A,B,C,D四门课程。有14人选了A和B，213人选了A和D，211人选了B和C

5、，43人选了C和D。没有学生同时选择A和C，也没有学生同时选择B和D。问共有多少学生在这四门课程中选了课？答案：解：画文氏图280+87+38+88 + 14+211+213+43=97422. 分别求下列集合的幂集(1) (2) (3)1,1答案： 解:(1) ()= 空集的幂集的基数为1 (2) ()=, 幂集的基数为2 (3) (1,1)=,1,1,1,1 23. A=0,1,B=1,2,C=3,4,5,求AB, BA, ABC, A2, C2 .答案： AB=(0,1),(0,2),(1,1),(1,2) BA=(1,0),(2,0),(1,1),(2,1) ABC= (0,1,3),

6、 (0,1,4), (0,1,5), (0,2,3), (0,2,4), (0,2,5), (1,1,3), (1,1,4), (1,1,5), (1,2,3), (1,2,4), (1,2,5) A2 = (0,0), (0,1), (1,0), (1,1) C2 = (3,3), (3,4), (3,5), (4,3), (4,4),(4,5),(5,3), (5,4),(5,5)24. 1. 设A=1,2,3, 4,5, 6,7,8,下列选项正确的是（C） A. 1A B. 1,2,3 A C. 4,5 A D. A 2. 设A=x|x3 x=0, B=x|x2 40,xz,C=x|y=

7、2x-1,D=x|x+y=5, xy=6则有 （A） A. A=B B. A=C C. C=D D. C=A25. 求关系的定义域和值域： 设A = 2，4，6，8，R是A上的小于关系，即当a, bA且a b时，（a, b）R，求R及D( R ),C( R )答案：R = （2，4）,（2，6）,（2，8）,（4，6）,（4，8）,（6，8）.R的定义域D( R ) =2，4，6，R的值域C( R ) = 4，6，8。26. 设A = a, b, c, d ,求A上的恒等关系。答案：IA= (a, a), (b, b), (c, c), (d, d)。27. 设A = 1,2,3,4,5, R

8、是A上的小于等于关系, 即当a b时, (a, b) R。求R的关系矩阵和关系图。答案：解:易知A上的小于等于关系为R = （1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,3), (2,4),(2,5),(3,3),(3,4),(3,5),(4,4),(4,5),(5,5)其关系矩阵为28. X=a,b,c，Y=1,2， 关系R=(a,1),(b,2),(c,1) S=(a,1),(b,1),(c,1)求RS、RS和R的补答案：29. 设A=1，2，3，B =a, b, c, d,C =x, y, z，R是A到B的二元关系，R = (1, a), (1, b),

9、(2, b), (3, c)，S是B到C的二元关系，S = (a, x), (b, x), (b, y), (b, z)。求复合关系RS的关系矩阵.答案：30. 答案：31. 设A = a,b,c，R是A上的二元关系， R = (a,a), (b,b), (a,b), (a,c), (c,a)， 问：R是自反的吗？是反自反的吗？是对称的吗？是反对称的吗？是可传递的吗？答案： 由于cA，而(c,c) ，所以R不是自反的。 由于(a,a)R，(b,b)R，所以R不是反自反的。 由于(a,b)R，而(b,a) ，所以R不是对称的。 由于(a,c)R，且(c,a)R，所以R不是反对称的。 由于(c,a

10、)R，且(a,c)R，但(c,c) ，所以R不是可传递的。 32. 设A=1,2,3，分析A上的下述5个关系具有哪些性质： L=, N=, S=, G=,答案：33. 设A = a, b, c, d，A上的关系，R = (a, b), (b, a), (b, c), (c, d) 求r(R)、s(R)、t(R)答案：34. A=a,b,c, R=(a,b),(b,c),(c,a)，求r(R), S(R)和t(R)答案：35. A=1,2,3,4，R=(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4),判断R是否是等价的。答案：36. 判断下列关系是否

11、为等价关系？(1) A=a,b,c,d， R=(a,a),(b,a),(b,b),(c,c),(d,d),(d,c)(2) A=1,2,3,4， R=(1,1),(1,2),(1,3),(2,1),(2,2),(3,1),(2,3),(3,3),(4,4),(3,2)答案：（1）（2）37. A=1,2,3,4在幂集(A)上定义的二元关系如下：R=(S,T)|S,T(A)，|S|=|T|，写出商集(A)/R。答案：解：首先求(A)。(A)=, 1,2,3,4 , 1,2,1,3 ,1,4 ,2,3 ,2,4 ,3,4, 1,2,3 ,1,2,4 ,1,3,4 ,2,3,4 , 1,2,3,4

12、共16个元素！38. 设集合X=2166，243，375，648，455X中的关系R为： R=(x,y)|x,yX，并且x和y中有相同数字问：R是不是相容关系？答案：39. A = 1，2，3，4，5，6，8，10，12，16，24，R是A上的整除关系，请画出的哈斯图。答案：40. 已知偏序集的哈斯图如图所示, 试求出集合A和关系R的表达式. 求 A 的极小元、最小元、极大元、最大元. 设 Bb,c,d, 求 B 的下界、上界、最大下界、最小上界.答案：极小元：a, b, c, g；极大元：a, f, h；没有最小元与最大元.B的下界和最大下界都不存在, 上界有d 和 f, 最小上界为 d.4

13、1. 以下关系矩阵所代表的关系是什么关系？答案：相容关系42. 设集合A = 1，2，3，4，5，6，8，10，12，16，24，R是A上的整除关系，请问关系R是否是偏序关系？是否是全序关系？画出的哈斯图，并根据图求集合A的极大极小元、最大最小元，设B=2，3，4，求集合B的上界、最小上界、下界、最大下界。答案：是偏序关系，不是全序关系。A的极大元：24,16,10A的极小元：1A的最大元：没有A的最小元：1B的上界：12,24B的最小上界：12B的下界：1B的最大下界：143. 找出如下哈斯图中的子集a,b,c、j,h和a,c,d,f的上界和下界。答案： a,b,c 上界：e,f,j,h 下

14、界：a j,h 上界：无 下界：f,d,e,b,c,a a,c,d,f 上界：f,j,h 下界：a44. 判断下列关系是否是映射？是否是单射？是否是满射？答案：映射（非单射、非满射）、映射（满射）映射（单射）、不是映射45. X=x1,x2,x3, Y=y1,y2, Z=z1,z2 f:XY，g:YZ，求h= gf答案：46. 下列哪些关系可以构成函数（映射）？a. f=(x,y)|x,yN, x+y10b. f=(x,y)|x,yR, x2=y答案：能不能47. 判断下列函数是单射、满射或双射？a. f:NN, f(x)=x+2;b. f:NN, f(x)=x (mod 2);c. f:N(

15、N), f(x)=x;答案：单射什么都不是单射48. f-1f = ？，ff-1= ？答案：f-1f =IA，ff-1= IB49. 构造下列函数的反函数：1.f(x)=sinx2.f(x)=x2 , x(-，0)3.A=1,2,3,B=a,b,c,f:AB, f=(1,a),(2,c),(3,b)答案：f-1(x)=arcsinxf-1(x)=-x1/2f-1=(a,1),(c,2),(b,3)50. 答案：51. 已知x=a,b,c ,Y=1,2,3,4 f:XY如图所示, 试构造函数g:YX,使得gf=Ix答案：g=(1,a),(2,c),(3,b),(4,a)52. 请给出图中各点的度

16、数，以及图的最大度数和最小度数。答案：d(v1)=4, d(v2)=4, d(v3)=2, d(v4)=1, d(v5)=3D(G)=4, d(G)=153. 请给出图中各点的出度和入，以及图的最大出度和最小入度。答案：d+(a)=4, d-(a)=1, d(a)=5,d+(b)=0, d-(b)=3, d(b)=3,+(D)=4, +(D)=0, -(D)=3, -(D)=1, (D)=5, (D)=3. 54. (3,3,3,4), (2,3,4,6,8)能成为图的度数序列吗?答案：不可能. 它们都有奇数个奇数.55. 已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于等于2, 问

17、G至少有多少个顶点?答案：设G有n个顶点. 由握手定理, 43+2(n-4)210解得 n856. 下面无向图中有几个顶点？(1) 16条边，每个顶点都是2度顶点(2) 21条边，3个4度顶点，其余的都是3度顶点(3) 35条边，每个顶点的度数至少为3的图最多有几个顶点？答案：57. 确定下列各图的出度、入度和度数答案：58. 判断下列图是否同构答案：是是不是是59. 下图中，1. 写出a,d,e的导出子图2. 画出它的一个生成子图3. 边集e4,e7,e6的导出子图答案：60. 试画出以下两个图的并图、交图和环和。答案：61. 判断下列各图是否是连通图：答案：是、不是62. 指出下列有向图的

18、连通性答案：强连通图单向连通图弱连通图强连通图单向连通图弱连通图63. 求下列图的强连通分支答案：64. （1）e5、e2 、e3、e6、e4是否是下图的边割集？（2）v5、v2 、v4、v3、v1 、v2、v2 、v3是否是下图的点割集？答案：（1）是、是、是、否（2）是、是、是、否、否65. 求出下图的全部割点和桥答案：66. 下列图是否是树？如果是，找出树的分枝结点和树叶。答案：不是、是分枝结点：e,f树叶：a, b, c, d, g, h67. 设一棵树T有2个度数为2的结点，1个度数为3的结点，3个度数为4的结点，求T有几片树叶。答案：68. 已知无向树T有5片树叶, 2度与3度顶点

19、各1个, 其余顶点的度数均为4. 求T的阶数n。答案：69. 求下列树的树根、树叶、树高、内点、分枝点、各个结点的层数答案：a是树根. b,e,f,h,i是树叶. c,d,g是内点. a,c,d,g是分枝点. a为0层;1层有b,c; 2层有d,e,f; 3层有g,h; 4层有i. 树高为4.70. 求下列树的树高、内点数、分枝点树、几叉树？答案：4、5、6、471. 下列树是不是完全二叉树？是不是满二叉树？答案：4叉树、完全3叉树72. 求下列二叉树的前序、中序、后序遍历答案：前序：a b d e h c f g i j中序：d b h e a f c i g j后序：d h e b f i j g c a73. 求下列二叉树的前序、中序、后序遍历答案：74. 构造下列数的排序二叉树：15, 3, 1, 6, 18, 7, 10, 20答案：75. 求树叶权为4，2，3，5，1的最优树。答案：最优树的权重W(T)为：13 + 23 + 32 + 42 + 52 =3376. 求带权图的最小生成树。答案：这棵最小生成树的权为:1+1+2+2+3+4=13.77. 求下图的邻接矩阵答案：78.写出下列表达式的“波兰表示式”(a 4b) c (7d + b) / (c + 5a)答案：先表示成二叉树的形式再对二叉树进行前序遍历即的波兰式为：/ a4bc +7db + c5a