《2016离散数学练习题-(答案修改)》由会员分享，可在线阅读，更多相关《2016离散数学练习题-(答案修改)（12页珍藏版）》请在金锄头文库上搜索。
1、2016注意事项：1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。2、第二遍复习按照考试大纲的总结把重点内容再做复习。另外，把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。3、第三遍复习把随后发去的练习题认真做一做，检验一下复习情况，要认真理解,注意做题思路与方法。离散数学综合练习题一、选择题1令: 今天下雪了，:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（ A ）。A. B. C. D. 2.设:是整数，:的绝对值，：大于等于；命题“所有整数的绝对值大于等于0”可符号化为（ B ）。A. B. C. D. 3.设:是人，:犯错误，命
2、题“没有不犯错误的人”符号化为（D）。AB CD *4.下列命题公式不是永真式的是（ A ）。A. B. C. D. 5设p：我们划船，q：我们跳舞，命题“我们不能既划船又跳舞”符号化正确的是（ B ）。A. B. C. D. 6设:x为有理数；:x为实数。命题“任何有理数都是实数”的符号化为（ A ）AB CD7. 设个体域，与公式等价的命题公式是( C )AB CD8无向图G有20条边，4个6度顶点，2个5度顶点，其余均为2度顶点，则G一共有（ C ）个顶点。A.7B.8C.9D.10*9.设集合A=c, c，下列命题是假命题的为（ C ）。A. B. C. D.10.设X=，则下列陈述正
3、确的是（ C ）。A.B.C.D.11.有向图D是连通图，当且仅当（ D ）。A. 图D中至少有一条通路 B. 图D中有通过每个顶点至少一次的通路C. 图D的连通分支数为一D. 图D中有通过每个顶点至少一次的回路 12.设A=a,b,c，则下列是集合A的划分的是( B )A.B. C.D. 13.下列谓词公式中是前束范式的是（ D ）。A B CD14. 设简单图G所有结点的度数之和为50，则G的边数为（ B ）。A. 50B. 25C. 10D. 515.设集合,上的等价关系 ，则对应于的划分是（ A ）。A. B. C. D. 16. 设，则是( C )。A从X到Y的双射B从X到Y的满射，
4、但不是单射C从X到Y的单射，但不是满射D从X到Y的二元关系，但不是从X到Y的映射17.下列图是欧拉图的是（ D ）。18.给定一个有n个结点的无向树，下列陈述不正确的是（ A ）。A所有结点的度数2B无回路但若增加一条新边就会变成回路C连通且，其中e是边数，v是结点数D无回路的连通图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 ）。A. 3B. 4C. 8D. 1621. 设简单图G所有结点的度
5、数之和为48，则G的边数为( B )A. 48B. 24C. 16D. 1222下面既是哈密顿图又是欧拉图的图形是（ B ）。23.下列必为欧拉图的是（ D ）A.有回路的连通图B.不可以一笔画的图C.有1个奇数度结点的连通图D.无奇数度结点的连通图24.二部图 是（ B ）。A.欧拉图 B. 哈密顿图 C.平面图 D. 完全图25下列所示的哈斯图所对应的偏序集中能构成格的是（ C ）。A.B.C.D.26.设集合，A上的关系，则R是（ B ）A自反的B对称的C传递的D反对称的27设是集合上的两个关系，其中，则 是的（ B ）闭包。A自反B对称 C传递D自反、对称且传递闭包28. 下列公式是前
6、束范式的是（ A ）。ABC D29. 设R为实数集，函数，则是（ D ）。A单射而非满射B满射而非单射 C双射D既不是单射，也不是满射30下列各图中既是欧拉图，又是汉密尔顿图的是（ C ）。A B C D12.设，则方程的解为（B）。AMNBMN CMN CM-N13.设是群，则下列陈述不正确的是（ C ）。A. B. C. D. 二、填空题1命题公式的成真指派为 00 01 11, 成假指派为_10_。2公式约束变元为 x,y ，自由变元为 x,z 。3设，则 , ， a,b 。4设，上的关系，则对称闭包，传递闭包。5.一棵无向树的顶点数与边数的关系是 n-1 。6阶无向连通图至多有 6
7、棵不同构的生成树。6设，则复合函数=, =。7. 是一个群，其中，则当=6时，在中，2的阶为_3_, 3的阶为_2 。8设是格，其中A=1, 3,4，6，8，12，24，为整除关系，则1的补元是_24 _，3的补元是_8_。9设A=，B=,那么=1,3,4,5 ran= 3 _。 10. 设A=l,2,3,4,A上的二元关系R=,，S=,，则 , , , 。11设复合函数gf是从A到C的函数，如果gf是满射，那么_g _必是满射，如果gf是单射，那么_f _必是单射。12给出A=l，2上的一个等价关系，并给出其对应的划分。13设，上的二元关系，则的自反闭包，传递闭包 R 14设个体域是实数集，
8、命题的真值为 1 ；命题的真值为 0 。15.设fRR,f(x)=x+3,gRR,g(x)=2x+1,则复合函数,。16 设为模6加群，其中，则2-3= 0 ，4-2= 4 。17一个结点为n的无向完全图，其边的数目为 n(n-1)/2 ，顶点的度为 n-1 。18. 已知阶无向简单图有条边，则的补图中有 n(n-1)/2-m条边。 19.设是个顶点的完全图，则K5有_10_条边，每个顶点的度数为_4_。20.一个班有40个人，在第一次考试中有26人得优秀，在第二次考试中有21人得优秀，如果两次考试都得优秀的有17人，两次考试都没有得优秀的人数为 10 ，至少有一次得优秀的人数为 30 。三、
9、计算题（仅给出部分题目的解题思路，未给出答案自己完成）1.已知命题公式（1）构造真值表；（2）用等值演算法求公式的主析取范式。解：（1）真值表p q r0 0 000110 0 101010 1 010110 1 111001 0 011001 0 111001 1 011001 1 11100（2）主析取范式 2求公式 的主合取范式及主析取范式。3.设，,，其中表示实数集。（1）求函数，；（2）哪些函数有反函数？如果有，求出这些反函数。解：（1） （2）和有反函数，； 4.设，为整除关系。（1）画出偏序集的哈斯图；（2）求A中的极大元；（3）求子集B=3, 6, 9的上确界与下确界。解：（1
10、）哈斯图（2）A中的极大元为 24，54；极小元为1；最大元：无；最小元：1（3）求子集B=3, 6, 9的上确界为54，下确界为3。5.设有向图如图所示，用邻接矩阵计算到长度小于或等于3的通路数。解：有向图的邻接矩阵为， ，v1到v3长度小于或等于3的通路数为6设，给出模6加运算的运算的运算表。解：运算的运算表为012345001234511234502234501334501244501235501234参看教材P197-198例9.4 与9.57. 设A1，2，3，4，5，R是A上的二元关系，且R（2，1，2，5），3，4)，求r(R)、s(R)和t(R)。解：r(R)=RIAs(R)=
11、RR-1t(R)= ，,（2,2,8. 一棵（无向）树有2结点的度为2， 1个结点的度为3，3个结点的度为4, 其余都是叶结点，问该树有几个叶结点？解：在一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结点数减1。根据这两点，可知树中各结点的度数总和=2*（树中点数-1），设树叶有x个，于是，2*2+3+3*4+x=2*（2+1+3+x-1）得x=9。四、简答题1. 设是A=上的二元关系。（1）画出R的关系图；（2）写出R的关系矩阵；（3）讨论R的性质。（4）R是否为函数解：（1）R的关系图 （2）R的关系矩阵 （3）R非自反、非反自传、对称、非反对称 、非传递的 （4）R不是函数，不满足函数单值性的要求。2.设集合上的关系（1）画出的关系图，并写出的关系矩阵；（2）是否为等价关系？若是，写出的所有等价类。解：（1）R的关系图为 （2）R的关系矩阵 由关系图可以看出是等价关系。等价类为： 或写为：A/R=1,3,6,2,5,43判断下图是否为二部图？若是，找出它的互补结点子集。它是否为哈密顿图？若是，找出一条哈密顿回路。 四、证明题1设为正整数，在上定义二元关系如下：当且仅当。证明：
