离散数学期末练习题带答案.doc

离散数学复习注意事项：1、 第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。2、 第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。离散数学综合练习题一、选择题1下列句子中，（ ）是命题。A2是常数。 B这朵花多好看呀！ C请把门关上！D下午有会吗？2令: 今天下雪了，:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（ ）。A. B. C. D. 3令今天下雪了，路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）。 A. B. C. D. 4设:是鸟，:会飞，命题“有的鸟不会飞”可符号化为（ ）。A. B. C. D. 5.设:是整数，:的绝对值，：大于等于；命题“所有整数的绝对值大于等于0”可符号化为（ ）。A. B. C. D. 6.设:是人，:犯错误，命题“没有不犯错误的人”符号化为（）。AB CD 7.下列命题公式不是永真式的是（ ）。A. B. C. D. 8设:x为有理数；:x为实数。命题“任何有理数都是实数”的符号化为（ ）AB CD9.设个体域，与公式等价的命题公式是( )AB CD10.下列等价式不正确的是（ ）。ABCD11. 设个体域，与公式等价的命题公式是( )AB CD12.设X=，则下列陈述正确的是（ ）。A.B.C.D.13.有向图D是连通图，当且仅当（ ）。A. 图D中至少有一条通路 B. 图D中有通过每个顶点至少一次的通路C. 图D的连通分支数为一D. 图D中有通过每个顶点至少一次的回路 14.设A=a,b,c，则下列是集合A的划分的是( )A.B. C.D. 15.下列谓词公式中是前束范式的是（ ）。A B CD16.设，则方程的解为（）。AMNBM N CMN CM-N17.设是群，则下列陈述不正确的是（ ）。A. B. C. D. 18.在整数集合上，下列定义的运算满足结合律的是（ ）。A. B. C. D. 19. 设简单图G所有结点的度数之和为50，则G的边数为（ ）。( )A. 50B. 25C. 10D. 520.设简单无向图是一个有5个顶点的4正则图，则有（ ）条边。A. 4B. 5C. 10D. 2021.设集合,上的等价关系 ，则对应于的划分是（ ）。A. B. C. D. 22.设集合,上的等价关系 ，则对应于的划分是（ ）。A. B. C. D. 23.设是群，则下列陈述不正确的是（ ）。A. B. C. D. 24.，下列定义的运算关于集合是不封闭的是（ ）。A. ，即的较大数B. ，即的较小数C. ，即的最大公约数D. ，即的最小公倍数25. 设，则是( )。A从X到Y的双射B从X到Y的满射，但不是单射C从X到Y的单射，但不是满射D从X到Y的二元关系，但不是从X到Y的映射26.设简单无向图是一个有6个顶点的5正则图，则有( )条边。A. 5B. 6C. 15D. 3027.图G如下图所示，以下说法正确的是( )。Aa是割点Bb,c是点割集Cb,d是点割集Dc是割点28.格L是分配格的充要条件是L不含与下面哪一个选项同构的子格（ ）。A链B钻石格C五角格D. 五角格与钻石格29.下列图是欧拉图的是（ D ）。30.给定一个有n个结点的无向树，下列陈述不正确的是（ ）。A所有结点的度数2B无回路但若增加一条新边就会变成回路C连通且，其中e是边数，v是结点数D无回路的连通图31. 设有5个元素，则其幂集的元素总个数为（ ）。A. 32B.25C. 50D. 532若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是（ ）。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)33. 设则其幂集的元素总个数为（ ）。A. 3B. 4C. 8D. 1634. 在实数集合R上，下列定义的运算中不可结合的是（ ）。A. B. C. D. 35. 无向图G是欧拉图，当且仅当（ ）。A. G的所有结点的度数全为偶数B. G中所有结点的度数全为奇数 C. G连通且所有结点度数全为奇数 D. G连通且所有结点度数全为偶数36.下列不一定是树的是（ ）A. 无回路的连通图D B. 有n个结点，n-1条边的连通图 C. 每对结点之间都有通路的图 D. 连通但删去一条边则不连通的图37. 设简单图G所有结点的度数之和为48，则G的边数为( )A. 48B. 24C. 16D. 1238下面既是哈密顿图又是欧拉图的图形是（ B ）。39.下列必为欧拉图的是（ ）A.有回路的连通图B.不可以一笔画的图C.有1个奇数度结点的连通图D.无奇数度结点的连通图40.二部图 是（ ）。A.欧拉图 B. 哈密顿图 C.平面图 D. 完全图41下列所示的哈斯图所对应的偏序集中能构成格的是（ C ）。A.B.C.D.42.设简单无向图是一个有6个顶点的3正则图，则有( )条边。A. 3B. 6C. 9D. 1843下列式子为矛盾式的是（ ）。AB CD 44.设集合，A上的关系，则R是（ ）A自反的B对称的C传递的D反对称的45设是集合上的两个关系，其中，则 是的（ ）闭包。A自反B对称 C传递D自反、对称且传递闭包46. 下列公式是前束范式的是（ ）。ABC D47. 设R为实数集，函数，则是（ ）。A单射而非满射B满射而非单射 C双射D既不是单射，也不是满射48下列各图中既是欧拉图，又是汉密尔顿图的是（ C ）。A B C D49下列四个格，是分配格的是（ C ）。50设集合A=a,b, c上的关系如下，具有传递性的是（ ）。A R=,B R=,C R=,D R=参考答案：（若有问题，可以到1#402或打电话问）一、选择题AAAAB DACAA CCDBD BCDBC ABBDC CBDDA ACCDD BBBDB CCCBB ADCCD二、填空题1命题公式的成真指派为 10 ，成假指派为_00，01，11_。2. 命题公式的成真指派为00 10 11，成假指派为_01_。3命题公式的成真指派为00 01 11 , 成假指派为_ 10_。4公式约束变元为 x,y ，自由变元为 x,z 。5公式约束变元为_x,y_，自由变元为_x,z_ 。6设，则， a,b 。7设，上的关系，则对称闭包 , ，传递闭包 ,。8.设*是集合上的二元运算，若运算*满足_结合律_，并且存在_单位元_，则称为独异点。9 设，则， a,b,c 。10.一棵无向树的顶点数与边数的关系是 m=n-1 。6阶无向连通图至多有 6 棵不同构的生成树。11设，则复合函数=, =。12. 是一个群，其中，则当=6时，在中，2的阶为_3_, 3的阶为_ 2 。13设是格，其中A=1, 3,4，6，8，12，24，为整除关系，则1的补元是_24 _，3的补元是_8_。14设A=，B=,那么=1,3,4,5 ran= 3,5 。 15. 设A=l,2,3,4,A上的二元关系R=,，S=,，则 , , , 。16设和是集合上的两个关系，则= , ， = , 。 17设A=2, 4, 6，A上的二元运算*定义为：a*b=maxa,b，则在独异点中，单位元是 2 ，零元是 6 。18一棵无向树的顶点数n与边数m关系是 m= n-1 。设G是具有8个顶点的树，则G中增加_21 _条边才能把G变成完全图。19设复合函数gf是从A到C的函数，如果gf是满射，那么_ g_必是满射，如果gf是单射，那么_f _必是单射。20设是格，其中A=1, 3, 5, 9, 45，为整除关系，则1的补元是_45_，3的补元是_ 5 _。21给出A=l，2上的一个等价关系_,_，并给出其对应的划分_1,2_。22设，上的二元关系，则的自反闭包，传递闭包 R 23命题公式的成真赋值为 01 10 11 ，成假赋值为 00 。24公式的成真赋值是 00,11 。成假赋值 01 10 25公式的成真赋值是 01 11 。成假赋值 00 10 26公式的成假赋值是 01 10 。成假赋值 00 11 27设个体域是实数集，命题的真值为 1 ；命题的真值为 0 。28.设fRR,f(x)=x+3,gRR,g(x)=2x+1,则复合函数 2x+4 , 2x+7 。29.给定集合A=1,2,3,4,5，在集合A上定义两种关系：R=,S=,，则 , 。30设A=0，1，2，3，6，则domR= 0， 3，6_ ，ranR=_0， 3，6 ，31 设为模6加群，其中，则2-3= 0 ，4-2= 4 。32一个结点为n的无向完全图，其边的数目为n(n-1)/2 ，顶点的度为 n-1 。33. 已知阶无向简单图有条边，则的补图中有 m- n(n-1)/2 条边。 参考答案：1_10_，00，01，11 2. 00 10 11， 01_ 3. _00 01 11, 104. _x,y ，x,z_ 5. _x,y ，x,z_ 6., a,b 7.， 8. 结合律 ， 单位元9, a,b，c 10.n-1, 6 11. ,12. 3 , 2 13. _24_,_8_ 14. 1,3,4,5，_315. , 16. ， 17. 2 , 6 18. m= n-1, _21 19. _g , _f_ 20. 45 , _5_ 21. , 22. , 23. 01 10 11，0024. 00，11 ,01，10 25. 01，11 ,00，10 26. 01 10 , 00 11 27. 1 , 0 28. , 29. , 30. 0， 3，6, 0， 3，6 31. 0 , 4 32. n(n-1)/2, n-1 33. m- n(n-1)/2 三、计算题（仅给出部分题目的解题思路，未给出答案自己完成）1. 已知命题公式（1）构造真值表（2）求出公式的主析取范式解题思路：（1）真值表p q r0 0 010010 0 110010 1 011000 1 111001 0 001001 0 101111 1 001001 1 10111（2）2.已知命题公式（1）构造真值表；（2）用等值演算法求公式的主析取范式。解：（1）真值表p q r0 0 000110 0 101010 1 010110 1 111001 0 011001 0 111001 1 011001 1 11100（2）主析取范式 3求公式 的主合取范式及主析取范式。4构造命题公式的真值表。5. 一棵（无向）树有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。6.一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点？提示：类似上题求解。7.设，,，其中表示实数集。（1）求函数，；（2）哪些函数有反函数？如果有，求出这些反函数。解：（1） （2）和有反函数，； 8.设Aa，b，c，R是A上的二元关系，且R，求r(R)、s(R)和t(R)。解：r(R)=RIA=,s(R)=RR-1=,t(R)= RR2R3=，9.设，为整除关系。（1）画出偏序集的哈斯图；（2）求A中的极大元；（3）求子集B=3, 6, 9的上确界与下确界。1623424954解：（1）哈斯图（2）A中的极大元为 24，54；极小元为1；最大元：无；最小元：1（3）求子集B=3, 6, 9的上确界为54，下确界为3。10.设有向图如图所示，用邻接矩阵完成以下计算。（1）到长度小于或等于4的通路数；（2）到自身长度小于或等于4的回路数；（3）求出的可达矩阵，并说明的连通性。有向图的邻接矩阵为， ，（1）v1到v4长度小于或等于4的通路数为（2）v1到自身长度小于或等于4的回路数为（3）由可达矩阵可知D是单向连通的。 11设，给出幂集合对称差运算的运算表。12设，给出模6加运算的运算的运算表。参看教材P167例9.4 与9.514. 设A1，2，3，4，5，R是A上的二元关系，且R，求r(R)、s(R)和t(R)。解：r(R)=RIAs(R)=RR-1t(R)= ，,（2,2,15.下图为一连通赋权图，计算该图的最小生成树和权值。四、简答题1.设集合上的关系（1）画出的关系图，并写出的关系矩阵；（2）是否为等价关系？若是，写出的所有等价类。解：（1）R的关系图为132 564（2）R的关系矩阵 由关系图可以看出是等价关系。等价类为： 或写为：A/R=1,3,6,2,5,42. 设是A=上的二元关系。（1）画出R的关系图；（2）写出R的关系矩阵；（3）讨论R的性质。1解：（1）R的关系图 234（2）R的关系矩阵 （3）R非自反、非反自传、对称、非反对称 、非传递的 （4）R不是函数，不满足函数单值性的要求。3设A=1,2,3,4,5,6,7,8,9,10，R是A上的二元关系，R=|x,yA x+y=10 说明R具有哪些性质。解：R=, , , , , , , 易知 R既不是自反也不是反自反的R是对称的 R不是反对称的 R不是传递的。4判断下图是否为二部图？若是，找出它的互补结点子集。它是否为哈密顿图？若是，找出一条哈密顿回路。 5.判断下图G是否是二部图？若是，找出它的互补结点子集。它是否为哈密顿图？若是，找出一条哈密顿回路。 6.设，为A上的整除关系。（1）是否为偏序集，若是，画出其哈斯图；（2）是否为格？说明理由；135945解：（1）是偏序集。哈斯图为：（2）是格。因为偏序集中的任意两个元素均有上、下确界。 四、证明题1用一阶逻辑的推理理论证明： 前提：， 结论： 证明：（1） 前提引入 （2） （1） （3） 前提引入 （4） （3） （5） （2）（4）析取三段论 （4分）（6） 前提引入 （7） （6） （8） （5）（7）假言推理 （9） （8） （3分）2设是非空集合,是所有从到的双射函数的集合, 是函数的复合运算。证明：是群。证明：由于集合是非空的，,因此非空 。(1) ,因为和都是到的双射函数，故也是到的双射函数，从而集合关于运算 是封闭的。 (2) ,由函数复合运算的结合律有，故运算 是可结合的。 (3) 上的恒等函数也是到的双射函数即,且有, 故 是中的幺元。 (4) ,因为是双射函数，故其逆函数是存在的，也是到的双射函数，且有,因此是的逆元 由此上知是群 3设代数系统，为模6加法。证明：关于运算构成群。证明：集合显然非空。 (1) ,从而集合关于运算是封闭的。 (2) ,有，故运算 是可结合的。 (3) , ,故0是中的幺元。 (4) ,因为,因此是的逆元 由此上知是群4设A是集合，P(A)是A的幂集合，是对称差运算， 证明构成群。 提示：参考2、3证明题完成。5设为正整数，在上定义二元关系如下：当且仅当。证明：是一个等价关系。证明： 任取所以R自反的。任取所以R是对称的。任取 所以R是传递的。因此，R是等价关系。6.设R是A上的关系，如果R满足以下两条件：（1）对于任意的aR， 都有aRa，（2）若aRb, aRc, 则有bRc， 证明：R是等价关系 证明： 任取（1）由已知条件（1）得,所以是自反的。 （2）由已知条件（1）、（2）得所以是对称的。 （3）由已知条件（1）、（2）得 所以是传递的。五、应用题（仅给出第7题的参考答案,未给出参考答案的自己完成）1. 构造下列推理的证明。 如果今天是星期一，则要进行英语或离散数学考试。如果英语老师有会，则不考英语。今天是星期一，英语老师有会，所以进行离散数学考试。2. 构造下列推理的证明。小王是理科学生，则他的数学成绩很好。如果小王不是文科学生，则他一定是理科学生。小王的数学成绩不好, 所以小王是文科学生。3如果甲是冠军，则乙或丙将得亚军；如果乙得亚军，则甲不能得冠军； 如果丁得亚军，丙不能得亚军；事实是甲已得冠军。因此丁不能得亚军。参照作业：P54 17,184.用一阶逻辑推理证明每个喜欢步行的人都不喜欢骑自行车，每个人或喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所以，有的人不喜欢步行（个体域为人类集合）解: 令喜欢步行, 喜欢骑自行车, 喜欢乘汽车前提：， 结论： 证明：（1） 前提引入 （2） （1） （3） 前提引入 （4） （3） （5） （2）（4）析取三段论 （6） 前提引入 （7） （6） （8） （5）（7）假言推理 （9） （8） 5今有于7个人，已知下列事实： a会讲英语； b会讲英语和汉语； c会讲英语、意大利语和俄语；d 会讲日语和汉语； e 会讲德国和意大利语；f 会讲法语、日语和俄语； g 会讲法语和德语。试问这七个人应如何排座位，才能使每个人都能和他身边的人交谈？解：用结点表示人，用边表示连接的两个人能讲同一种语言，构造出图G如下：英英英汉俄法德阳意日期英英汉意法德阳日期在G中存在着一条哈密顿回路如下，根据这条回路安排座位，就能够使每个人都能和他身边的人交谈。6 一次学术会议的理事会共有20个人参加，他们之间有的互相认识但有的互相不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人？根据是什么？ 7.设有7个城市，任意两个城市之间直接通信线路及通信线路预算造价如带权图所示，试给出一个设计方案，使得各城市间能够通信，而且总造价最低。写出求解过程，并计算出最低总造价。 解：带权图中边表示通信路，边上的数字表示修建该通信线路所需费用，于是求解此题便成为求权图中的最小生成树问题。 按避圈算法，对图中各边的权值按由小到大的顺序排序， 取,， ，则求解最小生成树如下图所示： 图中最小生成树的权为: +=1+1+2+2+3+5=14