离散数学复习资料-试卷-习题与答案全集.doc
《离散数学复习资料-试卷-习题与答案全集.doc》由会员分享,可在线阅读,更多相关《离散数学复习资料-试卷-习题与答案全集.doc(77页珍藏版)》请在咨信网上搜索。
1、离散试卷及答案离散数学总复习资料一、鸽笼原理与容斥原理1求证边长为1的正方形中放9个点,由这些点构成的三角形中,必有一个三角形面积小于。证:把该正方形均分成四个相同的小正方形,则由鸽笼原理知,必有一个小正方形内存在三个点,且这三个点构成的三角形面积小于。#2对一列个不同整数,任意排列,证明一定存在长为的上升子序列或下降子序列。证:设此序列为:,从开始上升子序列最长的长度为,下降子序列最长的长度为,每一个都对应了。若不存在长为的上升子序列或下降子序列,那么,形如的不同点对至多有个,而有个,则由鸽笼原理知,必有同时对应,由于,若,则至少比大1,若,则至少比大1,这均与矛盾。故原命题成立。#3求中不
2、被3、4、5整除的个数。解: 设表示中被3整除的数的集合,表示中被4整除的数的集合,表示中被5整除的数的集合,则, ,进而有故有即中不被3、4、5整除的个数为40。#4有100个学生,其中60个爱看小说,30个爱下棋,10个既爱看小说,又爱下棋,5个既爱看小说,又爱跳舞,没有既爱下棋,又爱跳舞的,三种活动都不爱的有10个,问有几个学生爱跳舞?解:设全体学生的集合为,爱看小说的学生集合为,爱下棋的学生集合为,爱跳舞的学生集合为,则依题意有, ,从而,。另一方面,根据容斥原理,我们有,即有,故,即有15个学生爱跳舞。#二、数理逻辑5求的主析取、主合取范式。解:取真为:(1,1),(0,0),(0,
3、1);故的主析取范式为;取假为:(1,0);故的主合取范式为:。6求的主析取、主合取范式。解:取真为:(1,1,1),(0,0,1),(0,1,1),(1,0,0),(1,0,1);故的主析取范式为; 取假为:(1,1,0),(0,1,0),(0,0,0);故的主合取范式为:。7(1)将式子“并非跑的最快的马吃的最多”翻译成用谓词和量词表达的逻辑式子。(2)将式子“爱因斯坦于1952年写完狭义与广义相对论浅说”翻译成用谓词和量词表达的逻辑式子。解:(1):马; :跑的最快的马; :吃的最多的马。上式表示为: (2)设:爱因斯坦; :1952; :狭义与广义相对论浅说; :于年写完;则原式子可翻
4、译成逻辑式子。8求下述公式的前束范式和Skolem标准形。解:=故该公式的前束范式为;Skolem标准形为。#9将下列命题符号化,并证明其论证是否正确。不存在白色的乌鸦;北京鸭是白色的。因此,北京鸭不是乌鸦。解:令是白色的;:是乌鸦;:是北京鸭。则上述命题可符号化为:下面,我们证明上述命题是正确的。(1) (P)(2) (US)(3) (CP)(4) (分离规则)(5) (量词转换律)(6) (US)(7) (T,(4)(8) (9) (UG)#三、二元关系10(1)举出正整数集上一种关系,它是等价关系但不是偏序关系;(2) 举出正整数集上一种关系,它是偏序关系但不是等价关系。(3)画出集合上
5、整除关系的Hasse图。(4)等价关系与划分关系解:(1)正整数集上模3的同余关系。(2)正整数集上的整除关系。(3) 24 12 8 6 4 3 2 111(1)举出正整数集上一种二元关系,它是等价关系又是偏序关系;(2) 画出的Hasse图 ,其中。解:(1)正整数集上的恒等关系。(2) 6 4 3 2 112设,定义上的一个二元关系如下:(1)画出的关系图,并写出的关系矩阵;(2)求,;(3)求,。解:(1) (2) (3) 又 故 13设是正整数集关于整除关系作成的偏序集,的子集,求的极小元、极大元、上界、下界、最小上界、最大下界。解:(略) 四图论14(1)画一个图,使它既有欧拉回路
6、,又有哈密顿回路;(2)画一个回路图,使它既无欧拉回路,又无哈密顿回路。解:(1) (2) 或 15(1)画一个图,使它有欧拉回路,无哈密顿回路;(2)画一个回路图,使它无欧拉回路,有哈密顿回路。解:(1) (2) 16证明小于30条边的简单平面图至少有一个顶点的度数小于5。证:(反证法)假设小于30条边的简单平面图中每一个顶点的度数大于等于5,从而此时顶点数与边数满足;另一方面,由于此时图的每一个区域至少由3条边围成,从而由Euler公式推论知,此时顶点数与边数满足;故有,进而有,这与已知条件产生矛盾。故小于30条边的简单平面图至少有一个顶点的度数小于5。#17证明具有6个顶点和12条边的连
7、通简单平面图,它的每个区域都是由三条边围成。证: 由题意及欧拉公式知,其区域数为。若有一个区域不是由三条边围成,则至少由4条边围成,从而8个区域至少需要25条边才能围成,即图中的边数不少于25/2=12.5, 这与已知条件12条边产生矛盾,故它的每个区域都是由三条边围成。#18设, 任意顶点的次(度)不少于2,且任意两个相邻区域只有一条公共边的简单平面图,证明其着色数不少于3。解:(略)19用算法寻找下图中顶点到的最短路径。 g 2 h 2 i 2 j 2 1 1 2 2 1 d 2 e 2 f 2 1 1 2 b 1 c 2 1 a解:从出发第一短的点为,距离为1,路径为;从出发第二短的点为
8、或,距离为2,路径为或;从出发第四短的点为或,距离为3,路径为或;从出发第五短的点为或或,距离为4,路径为或(或)或。故顶点到的最短路径为。#20求分别用前序、中序、后序遍历(周游)下图。 6 2 10 1 4 7 11 3 5 9 8 解:前序6-2-1-4-3-5-10-7-9-8-11 中序1-2-3-4-5-6-7-8-9-10-11 后序1-3-5-4-2-8-9-7-11-10-6 21求出下图的最小生成树。 21 1 2 1 22 1 3 3 2解: 1 1 1 1 1 1 2 1 或 1 2 2 2 22设7个字母在通讯中出现的频率如下, ,编一个相应的二元前缀码,使通讯中出现
9、的符号尽可能少,并画出对应的二元树。解:该二元前缀码对应的Huffman树为: 100 40 60 20 20 25 35 10 10 10 15 5 5 从而对应的二元前缀码为:。#23(10分)给定树叶的权分别为1,4,9,16,25,36,49,64,81,100,试构造一棵最优树。解:(略)24.握手原理及其应用。五代数系统与布尔代数24讨论下表给出集合上的运算是否具有交换律、结合律,并求出零元、幂等元。*012300000101232020230321解:根据上表运算结果的对称性知,上述运算满足交换律,又由上表的第二行与第二列知0是其零元, 再由上表的第三行与第三列知1是其幺元,并由
10、对角线上的具体结果知,仅有0与1是其幂等元。从而对,当中有一个为0或1时,均有;又,, ,。故上述运算满足结合律。#25设是一个半群,,对中每个中存在元素满足,则中存在幺元。证:依题意,存在满足。另一方面,任取中中存在元素满足,从而有 故有,进而有,即为中幺元。#26设是一个半群,证明如果是一个有限集,则在中存在元素,使得。解:由于是一个有限集,取中元素,故由鸽笼原理知,存在正整数满足。令,则,进而对任意的,也有。另一方面由于,故存在正整数满足,从而,进而有。令,有。#27求的所有子群及陪集,其中。解:其子群为。关于子群的陪集分别为;关于子群的陪集分别为;关于子群的陪集分别为;关于子群的陪集就
11、是其自身。#28求证有限群中周期大于2的元素个数必为偶数。证:因为根据群元素周期的定义知,每个元素与其逆元素的周期是一致的,而当该元素的周期大于2时,其逆元素与本身不同,故有限群中周期大于2的元素必是成对出现,从而其周期大于2的元素个数必为偶数。#29若是格中的元素,求证:。证:;又;进而有。#30若是格中的元素,求证:。证: ;又;进而有。#31.分配格与模格的刻画与关系。第1章 命题逻辑本章重点:命题与联结词,公式与解释,真值表,公式的类型及判定, (主)析取(合取)范式,命题逻辑的推理理论.一、重点内容1. 命题命题表述为具有确定真假意义的陈述句。命题必须具备二个条件:其一,语句是陈述句
12、;其二,语句有唯一确定的真假意义. 2. 六个联结词及真值表h“”否定联结词,P是命题,P是P的否命题,是由联结词 和命题P组成的复合命题.P取真值1,P取真值0,P取真值0,P取真值1. 它是一元联结词.h “”合取联结词,PQ是命题P,Q的合取式,是“”和P,Q组成的复合命题. “”在语句中相当于“不但而且”,“既又”. PQ取值1,当且仅当P,Q均取1;PQ取值为0,只有P,Q之一取0.h “”析取联结词,“”不可兼析取(异或)联结词, PQ是命题P,Q的析取式,是“”和P,Q组成的复合命题. PQ是联结词“”和P,Q组成的复合命题. 联结词“”或“”在一个语句中都表示“或”的含义,前者
13、表示相容或,后者表示排斥或不相容的或. 即“PQ”“(PQ)(PQ)”. PQ取值1,只要P,Q之一取值1,PQ取值0,只有P,Q都取值0. h “”蕴含联结词, PQ是“”和P,Q组成的复合命题,只有P取值为1,Q取值为0时,PQ取值为0;其余各种情况,均有PQ的真值为1,亦即10的真值为0,01,11,00的真值均为1. 在语句中,“如果P则Q”或“只有Q,才P,”表示为“PQ”.h “” 等价联结词,PQ是P,Q的等价式,是“”和P,Q组成的复合命题. “”在语句中相当于“当且仅当”,PQ取值1当且仅当P,Q真值相同.3. 命题公式、赋值与解释,命题公式的分类与判别 h命题公式与赋值,命
14、题P含有n个命题变项P1,P2,Pn,给P1,P2,Pn各指定一个真值,称为对P的一个赋值(真值指派). 若指定的一组值使P的真值为1,则这组值为P的真指派;若使P的真值为0,则称这组值称为P的假指派. h命题公式分类,在各种赋值下均为真的命题公式A,称为重言式(永真式);在各种赋值下均为假的命题公式A,称为矛盾式(永假式);命题A不是矛盾式,称为可满足式;判定命题公式类型的方法:其一是真值表法,任给公式,列出该公式的真值表,若真值表的最后一列全为1,则该公式为永真式;若真值表的最后一列全为0,则该公式是永假式;若真值表的最后一列既非全1,又非全0,则该公式是可满足式.其二是推导演算法. 利用
15、基本等值式(教材P.16的十六个等值式或演算律),对给定公式进行等值推导,若该公式的真值为1,则该公式是永真式;若该公式的真值为0,则该公式为永假式.既非永真,也非用假,成为非永真的可满足式.其三主析取(合取)范式法,该公式的主析取范式有2n个极小项(即无极大项),则该公式是永真式;该公式的主合取范式有2n个极大项(即无极小项),则该公式是永假式;该公式的主析取(或合取)范式的极小项(或极大项)个数大于0小于2n,,则该公式是可满足式.h等值式AB,命题公式A,B在任何赋值下,它们的真值均相同,称A,B等值。定理1 设F(A)是含命题公式A的命题,F(B)是用命题公式B置换F(A)中的A之后得
16、到的命题公式. 如果AB,则F(A)F(B). 4. 范式h 析取(合取)范式,仅有有限个简单合取式(析取式)构成的析取式(合取式),就是析取(合取)范式. h 极小项(极大项),n个命题变项P1,P2,Pn,每个变项或它的否定两者只有其一出现且仅出现一次,第i个命题变项或者其否定出现在从左起第i个位置上(无脚标时,按字典序排列),这样的简单合取式(析取式)为极小项(极大项). 以两个命题变项为例,m00=PQ,m01=PQ,m10=PQ,m11=PQ是极小项;M00=PQ,M01=PQ,M10=PQ,M11=PQ是极大项.h 主析取范式(主合取范式) 含有n个命题变项的命题公式,如果与一个仅
17、有极小项(极大项)的析取(合取)构成的析取(合取)范式等值,则该等值式称为原命题公式的主析取(合取)范式。每项含有n个命题变项(变项字母齐全)的合取式(析取式)的析取(合取)为主析取(合取)范式.任意命题公式都存在与之等值的范式,存在与之等值的主范式,且是惟一的. 求范式,包括求析取范式、合取范式、主析取范式和主合取范式. 关键有两点:其一是准确掌握范式定义;其二是巧妙使用基本等值式中的分配律、同一律和摩根律,结果的前一步适当使用幂等律. 求析取(合取)范式的步骤: 将公式中的联结词都化成,(即消去个数中的联结词,); 将否定联结词消去或移到各命题变项之前; 利用分配律、结合律等,将公式化为析
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 复习资料 试卷 习题 答案 全集
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。