离散数学练习题复习资料修改.docx
2016留意事项：1、第一遍复习肯定要仔细按考试大纲要求将本学期所学习内容系统复习一遍。2、第二遍复习依据考试大纲的总结把重点内容再做复习。另外，把大纲中指定的例题及书后习题仔细做一做。检验一下主要内容的驾驭状况。3、第三遍复习把随后发去的练习题仔细做一做，检验一下复习状况，要仔细理解,留意做题思路与方法。离散数学综合练习题一、选择题1令: 今日下雪了，:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（ A ）。A. B. C. D. 2.设:是整数，:的肯定值，：大于等于；命题“全部整数的肯定值大于等于0”可符号化为（ B ）。A. B. C. D. 3.设:是人，:犯错误，命题“没有不犯错误的人”符号化为（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=，则下列陈述正确的是（ 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的满射，但不是单射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全部结点的度数之和为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. 下列公式是前束范式的是（ A ）。ABC D29. 设R为实数集，函数，则是（ D ）。A单射而非满射B满射而非单射 C双射D既不是单射，也不是满射30下列各图中既是欧拉图，又是汉密尔顿图的是（ C ）。A B C D12.设，则方程的解为（B）。AMNBMN CMÅN 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 棵不同构的生成树。6设，则复合函数=, =。7. 是一个群，其中，则当=6时，在中，2的阶为_3_, 3的阶为_2 。8设<A，>是格，其中A=1, 3,4，6，8，12，24，为整除关系，则1的补元是_24 _，3的补元是_8_。9设A=<1，3>，<3，5>，<4，4>，B=<1,3>,<4,5>,<5,5>,那么=1,3,4,5 ran= 3 _。 10. 设A=l,2,3,4,A上的二元关系R=<1,2>,<2,3>,<3,2>，S=<l,3>,<2,3>，<4，3>，则 <1,3>,<3,3> , <3,1>,<3,3> 。11设复合函数gf是从A到C的函数，假如gf是满射，那么_g _必是满射，假如gf是单射，那么_f _必是单射。12给出A=l，2上的一个等价关系，并给出其对应的划分。13设，上的二元关系，则的自反闭包，传递闭包 R 14设个体域是实数集，命题的真值为 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 。三、计算题（仅给出局部题目的解题思路，未给出答案自己完成）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）画出偏序集<A,>的哈斯图；（2）求A中的极大元；（3）求子集B=3, 6, 9的上确界与下确界。解：（1）哈斯图（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），<2，4>，<3，4)，<4，4>，<5，2>，求r(R)、s(R)和t(R)。解：r(R)=RIAs(R)=RR-1t(R)= <2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>,（2,2>,<5,5>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设为正整数，在上定义二元关系如下：当且仅当。证明：是一个等价关系。证明： 任取所以R自反的。任取所以R是对称的。任取 所以R是传递的。因此，R是等价关系。2设为正整数，在上定义二元关系如下：当且仅当。证明：是一个等价关系。证明： 任取所以R自反的。任取所以R是对称的。任取 所以R是传递的。因此，R是等价关系。3. 用一阶逻辑的推理理论证明： 4设代数系统，为模6加法。证明：关于运算构成群。证明：集合明显非空。 (1) ,从而集合关于运算是封闭的。 (2) ,有，故运算 是可结合的。 (3) , ,故0是中的幺元。 (4) ,因为,因此是的逆元 由此上知是群5设A是集合，P(A)是A的幂集合，是对称差运算， 证明<P(A), >构成群。五、应用题（未给出参考答案的自己完成）1. 构造下列推理的证明。 假如今日是星期一，则要进展英语或离散数学考试。假如英语教师有会，则不考英语。今日是星期一，英语教师有会，所以进展离散数学考试。（给答案）2. 构造下列推理的证明。小王是理科学生，则他的数学成果很好。假如小王不是文科学生，则他肯定是理科学生。小王的数学成果不好, 所以小王是文科学生。3.用一阶逻辑推理证明前提：， 结论： 证明：（1） 前提引入 （2） （1） （3） 前提引入 （4） （3） （5） （2）（4）析取三段论 （6） 前提引入 （7） （6） （8） （5）（7）假言推理 （9） （8） 4今有于7个人，已知下列事实： a会讲英语； b会讲英语和汉语； c会讲英语、意大利语和俄语；d 会讲日语和汉语； e 会讲德国和意大利语；f 会讲法语、日语和俄语； g 会讲法语和德语。试问这七个人应如何排座位，才能使每个人都能和他身边的人交谈？解：用结点表示人，用边表示连接的两个人能讲同一种语言，构造出图G如下：在G中存在着一条哈密顿回路如下，依据这条回路支配座位，就可以使每个人都能和他身边的人交谈。5 一次学术会议的理事会共有20个人参与，他们之间有的相互相识但有的相互不相识。但对随意两个人，他们各自相识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得随意一个人相识其旁边的两个人？依据是什么？
