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

《离散数学期末练习题带答案.docx》由会员分享，可在线阅读，更多相关《离散数学期末练习题带答案.docx（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、离散数学复习考前须知：1、 第一遍复习肯定要仔细按考试大纲要求将本学期所学习内容系统复习一遍。2、 第二遍复习依据考试大纲的要求对第一遍复习进展总结。把大纲中指定的例题及书后习题仔细做一做。检验一下主要内容的驾驭状况。3、第三遍复习把随后发去的练习题仔细做一做，检验一下第一普及第二遍复习状况，要仔细理解,留意做题思路及方法。离散数学综合练习题一、选择题1以下句子中， 是命题。A2是常数。 B这朵花多好看呀！ C请把门关上！D下午有会吗？2令: 今日下雪了，:路滑，r:他迟到了。那么命题“下雪路滑，他迟到了 可符号化为 。A. B. C. D. 3令今日下雪了，路滑，那么命题“虽然今日下雪了，但

2、是路不滑可符号化为 。 A. B. C. D. 4设:是鸟，:会飞，命题“有的鸟不会飞可符号化为 。A. B. C. D. 5.设:是整数，:的肯定值，：大于等于；命题“全部整数的肯定值大于等于0可符号化为 。A. B. C. D. :是人，:犯错误，命题“没有不犯错误的人符号化为。AB CD 7.以下命题公式不是永真式的是 。A. B. C. D. 8设为有理数；为实数。命题“任何有理数都是实数的符号化为 AB CD9.设个体域，及公式等价的命题公式是( )AB CD10.以下等价式不正确的选项是 。ABCD11. 设个体域，及公式等价的命题公式是( )AB CD12.设，那么以下陈述正确的

3、选项是 。A.B.C.D.13.有向图D是连通图，当且仅当 。A. 图D中至少有一条通路 B. 图D中有通过每个顶点至少一次的通路C. 图D的连通分支数为一D. 图D中有通过每个顶点至少一次的回路 14.设，那么以下是集合A的划分的是( )A.B. C.D. 15.以下谓词公式中是前束范式的是 。A B CD16.设，那么方程的解为。AMNBM N CMN C17.设是群，那么以下陈述不正确的选项是 。A. B. C. D. 18.在整数集合上，以下定义的运算满意结合律的是 。A. B. C. D. 19. 设简洁图G全部结点的度数之和为50，那么G的边数为 。( )A. 50B. 25C.

4、10D. 520.设简洁无向图是一个有5个顶点的4正那么图，那么有 条边。A. 4B. 5C. 10D. 20,上的等价关系 ，那么对应于的划分是 。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.设简洁无向

5、图是一个有6个顶点的5正那么图，那么有( )条边。A. 5B. 6C. 15D. 3027.图G如以下图所示，以下说法正确的选项是( )。Aa是割点B是点割集C是点割集Dc是割点28.格L是安排格的充要条件是L不含及下面哪一个选项同构的子格 。A链B钻石格C五角格D. 五角格及钻石格29.以下图是欧拉图的是 D 。30.给定一个有n个结点的无向树，以下陈述不正确的选项是 。A全部结点的度数2B无回路但假设增加一条新边就会变成回路C连通且，其中e是边数，v是结点数D无回路的连通图31. 设有5个元素，那么其幂集的元素总个数为 。AC. 50D. 532假设供选择答案中的数值表示一个简洁图中各个顶

6、点的度，能画出图的是 。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个结点，1条边的连通图 C. 每对结点之间都有通路的图 D.

7、 连通但删去一条边那么不连通的图37. 设简洁图G全部结点的度数之和为48，那么G的边数为( )A. 48B. 24C. 16D. 1238下面既是哈密顿图又是欧拉图的图形是 B 。39.以下必为欧拉图的是 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传

8、递的D反对称的45设是集合上的两个关系，其中，那么 是的 闭包。A自反B对称 C传递D自反、对称且传递闭包46. 以下公式是前束范式的是 。ABC D47. 设R为实数集，函数，那么是 。A单射而非满射B满射而非单射 C双射D既不是单射，也不是满射48以下各图中既是欧拉图，又是汉密尔顿图的是 C 。A B C D49以下四个格，是安排格的是 C 。50设集合, c上的关系如下，具有传递性的是 。A ,B ,C ,D 参考答案：假设有问题，可以到1#402或打 问一、选择题 二、填空题1命题公式的成真指派为 10 ，成假指派为_00，01，11。2. 命题公式的成真指派为00 10 11，成假指

9、派为_01。3命题公式的成真指派为00 01 11 , 成假指派为_ 10。4公式约束变元为 ，自由变元为 。5公式约束变元为，自由变元为 。6设，那么， 。7设，上的关系，那么对称闭包 , ，传递闭包 ,。8.设*是集合上的二元运算，假设运算*满意结合律_，并且存在单位元_，那么称为独异点。9 设，那么， 。10.一棵无向树的顶点数及边数的关系是 1 。6阶无向连通图至多有 6 棵不同构的生成树。11设，那么复合函数=, =。12. 是一个群，其中，那么当=6时，在中，2的阶为3, 3的阶为_ 2 。13设是格，其中1, 3,4，6，8，12，24，为整除关系，那么1的补元是24 ，3的补元

10、是_8_。14设，,那么=1,3,4,5 3,5 。 15. 设l,2,3,4上的二元关系,，,，那么 , , , 。16设和是集合上的两个关系，那么= , ， = , 。 17设2, 4, 6，A上的二元运算*定义为：a*，那么在独异点中，单位元是 2 ，零元是 6 。18一棵无向树的顶点数n及边数m关系是 1 。设G是具有8个顶点的树，那么G中增加21 _条边才能把G变成完全图。19设复合函数是从A到C的函数，假如是满射，那么 必是满射，假如是单射，那么 _必是单射。20设是格，其中1, 3, 5, 9, 45，为整除关系，那么1的补元是45，3的补元是_ 5 _。21给出l，2上的一个等

11、价关系_,_，并给出其对应的划分_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.设fR(x)3R(x)=21,那么复合函数 24 , 27 。29.给定集合1,2,3,4,5，在集合A上定义两种关系：,，那么 , 。30设0，1，2，3，6，那么 0， 3，6_ ，0， 3，6

12、 ，31 设为模6加群，其中，那么2-3= 0 ，4-2= 4 。32一个结点为n的无向完全图，其边的数目为n(1)/2 ，顶点的度为 1 。33. 阶无向简洁图有条边，那么的补图中有 n(1)/2 条边。 参考答案：1_10_，00，01，11 2. 00 10 11， 01_ 3. _00 01 11, 104. ， 5. ， 6., 7.， 8. 结合律 ， 单位元9, ，c 101, 6 11. ,12. 3 , 2 13. _248 14. 1,3,4,5，_315. , 16. ， 17. 2 , 6 18. 1, _21 19. , 20. 45 , _5_ 21. , 22.

13、, 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(1)/2, 1 33. 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 1011122.命题公式1构造真值表；2用等值

14、演算法求公式的主析取范式。解：1真值表p q r0 0 000110 0 101010 1 010110 1 111001 0 011001 0 111001 1 011001 1 111002主析取范式 3求公式 的主合取范式及主析取范式。4构造命题公式的真值表。5. 一棵无向树有2结点的度为2， 1个结点的度为3，3个结点的度为4, 其余都是叶结点，问该树有几个叶结点？解：在一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结点数减1。依据这两点，可知树中各结点的度数总和=2*树中点数-1，设树叶有x个，于是，2*2+3+3*42*2+1+31得9。6.一棵无向树T有5片树叶，3个

15、2度分支点，其余的分支点都是3度顶点，问T有几个顶点？提示：类似上题求解。7.设，,，其中表示实数集。1求函数，；2哪些函数有反函数？假如有，求出这些反函数。解：1 2和有反函数，； 8.设Aa，b，c，R是A上的二元关系，且R，求r(R)、s(R)和t(R)。解：r(R),s(R)1=,t(R)= RR2R3=，9.设，为整除关系。1画出偏序集的哈斯图；2求A中的极大元；3求子集3, 6, 9的上确界及下确界。1623424954解：1哈斯图2A中的极大元为 24，54；微小元为1；最大元：无；最小元：13求子集3, 6, 9的上确界为54，下确界为3。10.设有向图如下图，用邻接矩阵完成以

16、下计算。1到长度小于或等于4的通路数；2到自身长度小于或等于4的回路数；3求出的可达矩阵，并说明的连通性。有向图的邻接矩阵为， ，1v1到v4长度小于或等于4的通路数为2v1到自身长度小于或等于4的回路数为3由可达矩阵可知D是单向连通的。 11设，给出幂集合对称差运算的运算表。12设，给出模6加运算的运算的运算表。14. 设A1，2，3，4，5，R是A上的二元关系，且R，求r(R)、s(R)和t(R)。解：r(R)s(R)1t(R)= ，,2,2,15.以下图为一连通赋权图，计算该图的最小生成树和权值。四、简答题1.设集合上的关系1画出的关系图，并写出的关系矩阵；2是否为等价关系？假设是，写出

17、的全部等价类。解：1R的关系图为132 5642R的关系矩阵 由关系图可以看出是等价关系。等价类为： 或写为：1,3,6,2,5,42. 设是上的二元关系。1画出R的关系图；2写出R的关系矩阵；3探讨R的性质。1解：1R的关系图 2342R的关系矩阵 3R非自反、非反自传、对称、非反对称 、非传递的 4R不是函数，不满意函数单值性的要求。3设1,2,3,4,5,6,7,8,9,10，R是A上的二元关系，A 10 说明R具有哪些性质。解：, , , , , , , 易知 R既不是自反也不是反自反的R是对称的 R不是反对称的 R不是传递的。4推断以下图是否为二部图？假设是，找出它的互补结点子集。它

18、是否为哈密顿图？假设是，找出一条哈密顿回路。 5.推断以下图G是否是二部图？假设是，找出它的互补结点子集。它是否为哈密顿图？假设是，找出一条哈密顿回路。 6.设，为A上的整除关系。1是否为偏序集，假设是，画出其哈斯图；2是否为格？说明理由；135945解：1是偏序集。哈斯图为：2是格。因为偏序集中的随意两个元素均有上、下确界。 四、证明题1用一阶逻辑的推理理论证明： 前提：， 结论： 证明：1 前提引入 2 1 3 前提引入 4 3 5 24析取三段论 4分6 前提引入 7 6 8 57假言推理 9 8 3分2设是非空集合,是全部从到的双射函数的集合, 是函数的复合运算。证明：是群。证明：由于

19、集合是非空的，,因此非空 。(1) ,因为和都是到的双射函数，故也是到的双射函数，从而集合关于运算 是封闭的。 (2) ,由函数复合运算的结合律有，故运算 是可结合的。 (3) 上的恒等函数也是到的双射函数即,且有, 故 是中的幺元。 (4) ,因为是双射函数，故其逆函数是存在的，也是到的双射函数，且有,因此是的逆元 由此上知是群 3设代数系统，为模6加法。证明：关于运算构成群。证明：集合明显非空。 (1) ,从而集合关于运算是封闭的。 (2) ,有，故运算 是可结合的。 (3) , ,故0是中的幺元。 (4) ,因为,因此是的逆元 由此上知是群4设A是集合，P(A)是A的幂集合，是对称差运算

20、， 证明构成群。 提示：参考2、3证明题完成。5设为正整数，在上定义二元关系如下：当且仅当。证明：是一个等价关系。证明： 任取所以R自反的。任取所以R是对称的。任取 所以R是传递的。因此，R是等价关系。6.设R是A上的关系，假如R满意以下两条件：1对于随意的， 都有，2假设, , 那么有， 证明：R是等价关系 证明： 任取1由条件1得,所以是自反的。 2由条件1、2得所以是对称的。 3由条件1、2得 所以是传递的。五、应用题仅给出第7题的参考答案,未给出参考答案的自己完成1. 构造以下推理的证明。 假如今日是星期一，那么要进展英语或离散数学考试。假如英语老师有会，那么不考英语。今日是星期一，英

21、语老师有会，所以进展离散数学考试。2. 构造以下推理的证明。小王是理科学生，那么他的数学成果很好。假如小王不是文科学生，那么他肯定是理科学生。小王的数学成果不好, 所以小王是文科学生。3假如甲是冠军，那么乙或丙将得亚军；假如乙得亚军，那么甲不能得冠军； 假如丁得亚军，丙不能得亚军；事实是甲已得冠军。因此丁不能得亚军。参照作业：P54 17,184.用一阶逻辑推理证明每个喜爱步行的人都不喜爱骑自行车，每个人或喜爱骑自行车或者喜爱乘汽车。有的人不喜爱乘汽车，所以，有的人不喜爱步行个体域为人类集合解: 令喜爱步行, 喜爱骑自行车, 喜爱乘汽车前提：， 结论： 证明：1 前提引入 2 1 3 前提引入

22、 4 3 5 24析取三段论 6 前提引入 7 6 8 57假言推理 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