1、2016 注意事项：1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。2、第二遍复习按照考试大纲的总结把重点内容再做复习。另外，把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。3、第三遍复习把随后发去的练习题认真做一做，检验一下复习情况，要认真理解,注意做题思路与方法。离散数学综合练习题一、选择题1令 : 今天下雪了， :路滑，r:他迟到了。则命题“下雪路滑，他迟到了” pq可符号化为（ A ）。A. B. qrpqrC. D. 2.设 : 是整数， : 的绝对值， ： 大于等于 ；命题“所有整()Px()fx(,)Lxyy数的绝对值大于等于 0”可符号
2、化为 （ B ）。A. B. ,0Lf(),0PfxC. D. ()()xx()x3.设 : 是人， : 犯错误，命题“没有不犯错误的人”符号化为（D） 。FGA B ()(xx()()xFGxC D ) *4.下列命题公式不是永真式的是（ A ） 。A. B. ()pq()pqC. D. 5设 p：我们划船，q：我们跳舞，命题“我们不能既划船又跳舞” 符号化正确的是（ B ） 。A. B. ()pqC. D. 6设 :x 为有理数； :x 为实数。命题“任何有理数都是实数”的符号化()R()Q为（ A ）A B ()()xRQxC D()()7. 设个体域 ，与公式 等价的命题公式是( C
3、),DabxAA B ()aAbC D()8无向图 G 有 20 条边， 4 个 6 度顶点，2 个 5 度顶点，其余均为 2 度顶点，则 G 一共有（ C ）个顶点。A.7 B.8 C.9 D.10*9.设集合 A=c, c，下列命题是假命题的为（ C ）。A. B. C. D.()P()PA()cPA()cPA10.设 X= ，则下列陈述正确的是（ C ） 。,aA. B. ,aXC. D.,11.有向图 D 是连通图，当且仅当（ D ） 。A. 图 D 中至少有一条通路 B. 图 D 中有通过每个顶点至少一次的通路C. 图 D 的连通分支数为一D. 图 D 中有通过每个顶点至少一次的回路
4、 12.设 A=a,b,c，则下列是集合 A 的划分的是( B )A. B. ,bc ,abcC. D. a13.下列谓词公式中是前束范式的是（ D ） 。A B ()()xFxG()()xFyGC D,PyQ,PQx14. 设简单图 G 所有结点的度数之和为 50，则 G 的边数为（ B ） 。A. 50 B. 25C. 10 D. 515.设集合 , 上的等价关系1,234A1,3,2,R，则对应于 的划分是（ A ） 。4,IUA. B. , ,4C. D. ,16. 设 ，则 是1,23,1,2,3XYabcdfabcf( C )。A从 X 到 Y 的双射B从 X 到 Y 的满射，但不
5、是单射C从 X 到 Y 的单射，但不是满射D从 X 到 Y 的二元关系，但不是从 X 到 Y 的映射17.下列图是欧拉图的是（ D ） 。18.给定一个有 n 个结点的无向树，下列陈述不正确的是（ A ） 。A所有结点的度数2B无回路但若增加一条新边就会变成回路C连通且 ，其中 e 是边数，v 是结点数1evD无回路的连通图19若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是（ 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)20. 设 则其幂集 的元素总个数为（ C ） 。,Aa()PA
6、A. 3 B. 4C. 8 D. 1621. 设简单图 G 所有结点的度数之和为 48，则 G 的边数为( B )A. 48 B. 24C. 16 D. 1222下面既是哈密顿图又是欧拉图的图形是（ B ） 。23.下列必为欧拉图的是（ D ）A.有回路的连通图 B.不可以一笔画的图C.有 1 个奇数度结点的连通图 D.无奇数度结点的连通图24.二部图 是（ B ） 。3,KA.欧拉图 B. 哈密顿图 C.平面图 D. 完全图25下列所示的哈斯图所对应的偏序集中能构成格的是（ C ） 。A. B.C. D.26.设集合 ，A 上的关系 ，则 R 是（ B ,abc,Raca）A自反的 B对称的
7、C传递的 D反对称的27设 是集合 上的两个关系，其中12,R,abcd1,ab， ，则 是bcd2,cbd2R的（ B ）闭包。1A自反 B对称 C传递 D自反、对称且传递闭包28. 下列公式是前束范式的是（ A ） 。A B()(,)(xyFzxGy()()()xFyGHzC D,x29. 设 R 为实数集，函数 ， ，则 是（ D ） 。:fR25ffA单射而非满射 B满射而非单射 C双射 D既不是单射，也不是满射30下列各图中既是欧拉图，又是汉密尔顿图的是（ C ） 。A B C D12.设 ，则方程 的解为（B） 。12|()0,|()0MxfNxf12()0fxAM N BM NC
8、MN CM-N13.设 是群，则下列陈述不正确的是（ C ） 。,GAA. B. 1()a nmaC. D. 1b 11()nba二、填空题1命题公式 的成真指派为 00 01 11, 成假指派为_10_。()pq2公式 约束变元为 x,y ，自由变元()()(,)xyPQxzyRx为 x,z 。3设 ， ，则 , ， a,b 。,Aab,BabAB4设 ， 上的关系 ，则对称闭包c,ba，传递闭包 。()sR,()tR,ab5.一棵无向树的顶点数 与边数 的关系是 n-1 。6 阶无向连通图至nm多有 6 棵不同构的生成树。6设 ， ，则复合函数 = , = 。()1fx2()gx()fgx
9、2(1)()gfx217. 是一个群，其中 ， ，则当,nZ0,12,nZn modyn=6 时，在 中， 2 的阶为_3_, 3 的阶为 _2 。6,8设是格，其中A=1, 3,4，6，8，12， 24，为整除关系，则1的补元是_24 _，3的补元是_8_。9设 A=， ，B=,那么=1,3,4,5 ran = 3 _。 dom()AB()AB10. 设 A=l,2,3,4,A上的二元关系 R=,，S=,，则 , , , 。R1()RS11设复合函数 g f 是从 A 到 C 的函数，如果 g f 是满射，那么_g _必是满 射，如果 g f 是单射，那么_f _必是单射。12给出 A=l，
10、2 上的一个等价关系 ，并给出其对应的划分1,2,。1,213设 ， 上的二元关系 ，则 的自,abcd,RabdbR反闭包 ，传递闭包 R ()rRAI()t14设个体域是实数集，命题 的真值为 1 ；命题3x的真值为 0 。2(10)x15.设 fRR,f(x)=x+3,gRR,g(x)=2x+1,则复合函数 ,(fg)x=24+。(gf)x=27+16 设 为模 6 加群，其中 ，则 2-3= 0 ，4 -2= 4 。6,Z60,1234,5Z17一个结点为 n 的无向完全图，其边的数目为 n(n-1)/2 ，顶点的度为 n-1 。18. 已知 阶无向简单图 有 条边，则 的补图 中有
11、n(n-1)/2-m 条边。 GmG19.设 是 个顶点的完全图，则K 5有_10 _条边，每个顶点的度数为n_4_。20.一个班有 40 个人，在第一次考试中有 26 人得优秀，在第二次考试中有 21人得优秀，如果两次考试都得优秀的有 17 人，两次考试都没有得优秀的人数为 10 ，至少有一次得优秀的人数为 30 。三、计算题（仅给出部分题目的解题思路，未给出答案自己完成）1.已知命题公式 ()()pqr（1）构造真值表；（2）用等值演算法求公式的主析取范式。解：（1）真值表p q r pqpr()pr()()qpr0 0 0 0 0 1 10 0 1 0 1 0 10 1 0 1 0 1
12、10 1 1 1 1 0 01 0 0 1 1 0 01 0 1 1 1 0 01 1 0 1 1 0 01 1 1 1 1 0 0（2）主析取范式012()()()()()r()(r)pqrprqqrppqm2求公式 的主合取范式及主析取范式。()()pr3.设 ， , ，2:,()fRfx:,()4gRx3:,()1hRx其中 表示实数集。（1）求函数 ， ；ff（2） 哪些函数有反函数？如果有，求出这些反函数。,fgh解：（1） 22()()4)()814xffxx2fg（2） 和 有反函数， ；gh11:,()R13:,()x4.设 ， 为整除关系。,346925A（1）画出偏序集的哈
13、斯图；（2）求 A 中的极大元；（3）求子集 B=3, 6, 9的上确界与下确界。解：（1）哈斯图（2）A 中的极大元为 24，54；极小元为 1；最大元：无；最小元：1（3）求子集 B=3, 6, 9的上确界为 54，下确界为 3。5.设有向图 如图所示，用邻接矩阵计算 到 长度小于或等于 3 的通路数。D1v4解：有向图的邻接矩阵为， 102A2013A，31040123v1 到 v3 长度小于或等于 3 的通路数为3()1402iia6设 ，给出模 6 加运算的运算的运算表。60,1234,5Z解：运算 的运算表为0 1 2 3 4 50 0 1 2 3 4 51 1 2 3 4 5 0
14、2 2 3 4 5 0 13 3 4 5 0 1 24 4 5 0 1 2 35 5 0 1 2 3 4参看教材 P197-198 例 9.4 与 9.57. 设 A1，2，3，4，5，R是A上的二元关系，且R（2，1， ， ，求r(R)、s(R)和t(R)。解：r(R)=RI As(R)=RR -1t(R)= ，,（2,2,8. 一棵（无向）树有 2 结点的度为 2， 1 个结点的度为 3，3 个结点的度为 4, 其余都是叶结点，问该树有几个叶结点？解：在一个有限图中，各结点的度数总和是边数的 2 倍；而树中的边数为结点数减 1。根据这两点，可知树中各结点的度数总和=2*（树中点数-1），设
15、树叶有 x 个，于是，2*2+3+3*4+x=2*（2+1+3+x-1）得 x=9。四、简答题1. 设 是 A= 上的二元关1,3(4,2,31,),41R,234系。（1）画出 R 的关系图；（2）写出 R 的关系矩阵；（3）讨论 R 的性质。（4）R 是否为函数解：（1）R的关系图（2）R的关系矩阵 01（3）R非自反、非反自传、对称、非反对称 、非传递的 （4）R 不是函数，不满足函数单值性的要求。2.设集合 上的关系654321，A(1,31,62,R=（1 ）画出 的关系图，并写出 的关系矩阵；（2） 是否为等价关系？若是，写出 的所有等价类。解：（1）R 的关系图为（2）R的关系矩阵 1010由关系图可以看出 是等价关系。等价类为：R1361,2,54或写为：A/R=1,3,6,2,5,43判断下图是否为二部图？若是，找出它的互补结点子集。它是否为哈密顿图？若是，找出一条哈密顿回路。 四、证明题1设 为正整数 ，在 上定义二元关系 如下：,|AxyAR当且仅当 。,Ruvxyuv证明： 是一个等价关系。证明： 任取 ,xy,AxyRxy所以 R 自反的。任取 ,xyuv,xyvuxyuvRxy所以 R 是对称的。任取 ,xyvst,uRtxyvst,st所以 R 是传递的。因此，R 是等价关系。hfigabecdj
