离散数学复习资料试卷习题与答案

离散数学总复习资料一、鸽笼原理与容斥原理1．求证边长为1的正方形中放9个点，由这些点构成的三角形中，必有一个三角形面积小于18。证：把该正方形均分成四个相同的小正方形，则由鸽笼原理知，必有一个小正方形内存在三个点，且这三个点构成的三角形面积小于18。#2．对一列21n个不同整数，任意排列，证明一定存在长为1n的上升子序列或下降子序列。证：设此序列为：2121,,,,,knaaaa，从ka开始上升子序列最长的长度为kx，下降子序列最长的长度为ky，每一个ka2(1,2,,1)kn都对应了(,)kkxy。若不存在长为1n的上升子序列或下降子序列，那么,kkxnyn，形如(,)kkxy的不同点对至多有2n个，而ka有21n个，则由鸽笼原理知，必有,ijaa2(11)ijn同时对应(,)iixy(,)jjxy，由于ijaa，若ijaa，则ix至少比jx大1，若ijaa，则iy至少比jy大1，这均与(,)iixy(,)jjxy矛盾。故原命题成立。#3．求}100,,2,1{中不被3、4、5整除的个数。解：设A表示}100,,2,1{中被3整除的数的集合，B表示}100,,2,1{中被4整除的数的集合，C表示}100,,2,1{中被5整除的数的集合，则20,25,33CBA6,5,8ACCBBA，1CBA，进而有CBAACCBBACBACBA601658202533故有4060100CBAUCBA即}100,,2,1{中不被3、4、5整除的个数为40。#4．有100个学生，其中60个爱看小说，30个爱下棋，10个既爱看小说，又爱下棋，5个既爱看小说，又爱跳舞，没有既爱下棋，又爱跳舞的，三种活动都不爱的有10个，问有几个学生爱跳舞？解：设全体学生的集合为U，爱看小说的学生集合为A，爱下棋的学生集合为B，爱跳舞的学生集合为C，则依题意有100,60,30,10,5,0UABABACBC，10ABC，BC，从而()ABCABC，1001090ABCUABC。另一方面，根据容斥原理，我们有ABCABCABACBCABC，即有90603010500C，故15C，即有15个学生爱跳舞。#二、数理逻辑5．求QP的主析取、主合取范式。解：QP取真为：(1,1)，(0,0)，(0,1)；故QP的主析取范式为)()()(QPQPQP；QP取假为：(1,0)；故QP的主合取范式为：QP。6．求RQP)(的主析取、主合取范式。解：RQP)(取真为：(1,1,1)，(0,0,1)，(0,1,1)，(1,0,0)，(1,0,1)；故RQP)(的主析取范式为)()()()()(RQPRQPRQPRQPRQP；RQP)(取假为：(1,1,0),(0,1,0),(0,0,0)；故RQP)(的主合取范式为：)()()(RQPRQPRQP。7．（1）将式子“并非跑的最快的马吃的最多”翻译成用谓词和量词表达的逻辑式子。(2)将式子“爱因斯坦于1952年写完‘狭义与广义相对论浅说’”翻译成用谓词和量词表达的逻辑式子。解：（1）x：马；)(xA：跑的最快的马；)(xB：吃的最多的马。上式表示为：))()((xBxAx（2）设a：爱因斯坦；b：1952；c：‘狭义与广义相对论浅说’；),,(zyxA：x于y年写完z；则原式子可翻译成逻辑式子),,(cbaA。8．求下述公式的前束范式和Skolem标准形。)()(),()(zQzyxPx解：)()(),()(zQzyxPx=)),()()()(())()(),()((yxPxzQzzQzyxPx=)),()()()(())()(),()((yxPxzQzzQzyxPx=)),()()()(())()(),()((yxPxzQzzQzyxPx=)),()()()(())(),()()((yxPzQxzzQyxPzx=)),()()()(())(),()()((yvPuQvuzQyxPzx=))),()(())(),()(()()()((yvPuQzQyxPvuzx故该公式的前束范式为))),()(())(),()(()()()((yvPuQzQyxPvuzx；Skolem标准形为)),,(()),((())(),((yzxgPzxfQzQyxP。#9．将下列命题符号化，并证明其论证是否正确。不存在白色的乌鸦；北京鸭是白色的。因此，北京鸭不是乌鸦。解：令xxP:)(是白色的；)(xQ：x是乌鸦；)(xR：x是北京鸭。则上述命题可符号化为：))()()(())()()(()),()()((xQxRxxPxRxxQxPx下面，我们证明上述命题是正确的。（1）))()()((xPxRx（P）（2）)()(yPyR（US）（3）)(yR（CP）（4）)(yP（分离规则）（5）))()()(())()()((xQxPxxQxPx（量词转换律）（6）)()(yQyP（US）（7）)(yQ（T，（4））（8）)()(yQyR（9）))()()((xQxRx（UG）#三、二元关系10．(1)举出正整数集上一种关系,它是等价关系但不是偏序关系;(2)举出正整数集上一种关系,它是偏序关系但不是等价关系。(3)画出集合}24,12,8,6,4,3,2,1{A上整除关系的Hasse图。（4）等价关系与划分关系解：（1）正整数集上模3的同余关系。（2）正整数集上的整除关系。（3）241286432111．(1)举出正整数集上一种二元关系,它是等价关系又是偏序关系;(2)画出{(,),,}RabababA的Hasse图,其中}6,4,3,2,1{A。解：（1）正整数集上的恒等关系。（2）6432112．设}4,3,2,1{A，定义A上的一个二元关系R如下：}4,3,3,2,1,2,2,1{R（1）画出R的关系图，并写出R的关系矩阵；（2）求2R，3R；（3）求)(Rr，)(Rs，)(Rt。解：（1）0000100001010010RM（2）}4,2,2,2,3,1,1,1{2R}3,2,1,2,4,1,2,1{3R（3）}}4,4,4,3,3,3,3,2,2,2,1,2,2,1,1,1{)(Rr}3,4,4,3,2,3,3,2,1,2,2,1{)(Rs又}4,2,2,2,3,1,1,1{4R故432)(RRRRRt}4,3,4,2,3,2,2,2,1,2,3,1,2,1,1,1{13．设,P是正整数集关于整除关系作成的偏序集，P的子集}6,5,4,3,2,1{T，求T的极小元、极大元、上界、下界、最小上界、最大下界。解：（略）四．图论14．（1）画一个图，使它既有欧拉回路，又有哈密顿回路；（2）画一个回路图，使它既无欧拉回路，又无哈密顿回路。解：（1）（2）或15．（1）画一个图，使它有欧拉回路，无哈密顿回路；（2）画一个回路图，使它无欧拉回路，有哈密顿回路。解：（1）（2）16．证明小于30条边的简单平面图至少有一个顶点的度数小于5。证：（反证法）假设小于30条边的简单平面图G中每一个顶点的度数大于等于5，从而此时顶点数v与边数e满足ve52；另一方面，由于此时图G的每一个区域至少由3条边围成，从而由Euler公式推论知，此时顶点数v与边数e满足63ve；故有656ee，进而有30e，这与已知条件产生矛盾。故小于30条边的简单平面图至少有一个顶点的度数小于5。#17．证明具有6个顶点和12条边的连通简单平面图，它的每个区域都是由三条边围成。证：由题意及欧拉公式知，其区域数为86122。若有一个区域不是由三条边围成，则至少由4条边围成，从而8个区域至少需要25条边才能围成，即图中的边数不少于25/2=12.5,这与已知条件12条边产生矛盾，故它的每个区域都是由三条边围成。#18．设(,),9,17GVEVE，任意顶点的次（度）不少于2，且任意两个相邻区域只有一条公共边的简单平面图，证明其着色数不少于3。解：（略）19．用算法寻找下图中顶点a到i的最短路径。g2h2i2j211221d2e2f2112b1c21a解：从a出发第一短的点为c，距离为1，路径为ca；从a出发第二短的点为b或e，距离为2，路径为ba或eca；从a出发第四短的点为h或f，距离为3，路径为heca或fca；从a出发第五短的点为i或d或j，距离为4，路径为ieca或dba（或deca）或jfca。故顶点a到i的最短路径为ieca。#20．求分别用前序、中序、后序遍历（周游）下图。6210147113598解：前序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-621．求出下图的最小生成树。21121221332解：11111121或122222．设7个字母在通讯中出现的频率如下，:35%,:20%,:15%,:10%,:10%,abcde:5%,:5%fg，编一个相应的二元前缀码，使通讯中出现的符号尽可能少，并画出对应的二元树。解：该二元前缀码对应的Huffman树为：1004060202025351010101555从而对应的二元前缀码为：11,01,101,100,001,0000,0001abcdefg。#23．（10分）给定树叶的权分别为1，4，9，16，25，36，49，64，81，100，试构造一棵最优树。解：（略）24.握手原理及其应用。五．代数系统与布尔代数24．讨论下表给出集合}3,2,1,0{A上的运算是否具有交换律、结合律，并求出零元、幂等元。*012300000101232020230321解：根据上表运算结果的对称性知,上述运算满足交换律,又由上表的第二行与第二列知0是其零元,再由上表的第三行与第三列知1是其幺元，并由对角线上的具体结果知，仅有0与1是其幂等元。从而对Azyx,,，当zyx,,中有一个为0或1时，均有)*(**)*(zyxzyx；又)2*2(*202*)2*2(，03*)2*2()3*2(*2，)2*3(*202*)3*2(，)3*3(*223*)3*2(，)2*2(*302*)2*3(，23*)2*3(,2)3*2(*3，)2*3(*322*)3*3(，)3*3(*333*)3*3(。故上述运算满足结合律。#25．设是,*)(A一个半群，Aa,对A中每个Ax,中存在元素vu,满足xavua**，则A中存在幺元。证:依题意，存在aavu,满足aavuaaa**。另一方面，任取A中Ax,中存在元素vu,满足xavua**，从而有xavuavuavuxaaa*)*(**)*(*xuauavuavxvaaa**)*()*(**故有aaaaaauuvvuv*,*，进而有aavu，即aavu为A中幺元。#26．设是,*)(A一个半群，证明如果A是一个有限集，则在A中存在元素a，使得aaa*。解：由于A是一个有限集，取A中元素b，故由鸽笼原理知，存在正整数ji满足jibb。令pij，则pipijibbbbb*，进而对任