离散数学总复习资料.pdf
1/10 离散数学总复习资料 一、鸽笼原理与容斥原理 1求证边长为 1 的正方形中放 9 个点，由这些点构成的三角形中，必有一个三角形面积小于18。证：把该正方形均分成四个相同的小正方形，则由鸽笼原理知，必有一个小正方形内存在三个点，且这三个点构成的三角形面积小于18。#2对一列21n 个不同整数，任意排列，证明一定存在长为1n的上升子序列或下降子序列。证：设此序列为：2121,kna aaa，从ka开始上升子序列最长的长度为kx，下降子序列最长的长度为ky，每一个ka2(1,2,1)kn都对应了(,)kkxy。若不存在长为1n的上升子序列或下降子序列，那么,kkxn yn，形如(,)kkxy的不同点对至多有2n个，而ka有21n 个，则由鸽笼原理知，必有,ija a2(11)ijn 同时对应(,)iix y(,)jjxy，由于ijaa，若ijaa，则ix至少比jx大 1，若ijaa，则iy至少比jy大 1，这均与(,)iix y(,)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,33CBA 6,5,8ACCBBA，1CBA，进而有 CBAACCBBACBACBA 601658202533 故有4060100CBAUCBA 即100,2,1中不被 3、4、5 整除的个数为 40。#2/10 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 3/10（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）4/10（8）)()(yQyR （9）)()()(xQxRx （UG）#三、二元关系 10(1)举出正整数集上一种关系,它是等价关系但不是偏序关系;(2)举出正整数集上一种关系,它是偏序关系但不是等价关系。(3)画出集合24,12,8,6,4,3,2,1A上整除关系的 Hasse 图。（4）等价关系与划分关系 解：（1）正整数集上模 3 的同余关系。（2）正整数集上的整除关系。（3）24 12 8 6 4 3 2 1 11(1)举出正整数集上一种二元关系,它是等价关系又是偏序关系;(2)画出(,),Rab ababA的 Hasse 图,其中6,4,3,2,1A。解：（1）正整数集上的恒等关系。（2）6 4 3 2 1 12设4,3,2,1A，定义A上的一个二元关系R如下：4,3,3,2,1,2,2,1R（1）画出R的关系图，并写出R的关系矩阵；（2）求2R，3R；（3）求)(Rr，)(Rs，)(Rt。解：（1）5/10 0000100001010010RM （2）4,2,2,2,3,1,1,12R 3,2,1,2,4,1,2,13R （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,14R 故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,1T，求T的极小元、极大元、上界、下界、最小上界、最大下界。解：（略）四图论 14（1）画一个图，使它既有欧拉回路，又有哈密顿回路；（2）画一个回路图，使它既无欧拉回路，又无哈密顿回路。解：（1）（2）或 15（1）画一个图，使它有欧拉回路，无哈密顿回路；（2）画一个回路图，使6/10 它无欧拉回路，有哈密顿回路。解：（1）（2）16证明小于 30 条边的简单平面图至少有一个顶点的度数小于 5。证：（反证法）假设小于30条边的简单平面图G中每一个顶点的度数大于等于5，从而此时顶点数v与边数e满足ve52；另一方面，由于此时图G的每一个区域至少由 3 条边围成，从而由 Euler 公式推论知，此时顶点数v与边数e满足63 ve；故有656ee，进而有30e，这与已知条件产生矛盾。故小于 30条边的简单平面图至少有一个顶点的度数小于 5。#17证明具有 6 个顶点和 12 条边的连通简单平面图，它的每个区域都是由三条边围成。证：由题意及欧拉公式知，其区域数为86122。若有一个区域不是由三条边围成，则至少由 4 条边围成，从而 8 个区域至少需要 25 条边才能围成，即图中的边数不少于 25/2=12.5,这与已知条件 12 条边产生矛盾，故它的每个区域都是由三条边围成。#18设(,),9,17GVE VE，任意顶点的次（度）不少于 2，且任意两个相邻区域只有一条公共边的简单平面图，证明其着色数不少于 3。解：（略）19用算法寻找下图中顶点a到i的最短路径。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 7/10 a 解：从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求分别用前序、中序、后序遍历（周游）下图。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求出下图的最小生成树。2 1 1 2 1 2 2 1 3 3 2 解：1 1 1 1 1 1 2 1 或 1 2 2 2 22 设 7 个字母在通讯中出现的频率如下，:35%,:20%,:15%,:10%,:10%,abcde:5%,:5%fg，编一个相应的二元前缀码，使通讯中出现的符号尽可能少，并画8/10 出对应的二元树。解：该二元前缀码对应的 Huffman 树为：100 40 60 20 20 25 35 10 10 10 15 5 5 从而对应的二元前缀码为：11,01,101,100,001,0000,0001abcdefg。#23（10 分）给定树叶的权分别为 1，4，9，16，25，36，49，64，81，100，试构造一棵最优树。解：（略）24.握手原理及其应用。五代数系统与布尔代数 24讨论下表给出集合3,2,1,0A上的运算是否具有交换律、结合律，并求出零元、幂等元。*0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1 解：根据上表运算结果的对称性知,上述运算满足交换律,又由上表的第二行与第二列知 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,中存在9/10 元素vu,满足xavua*，从而有 xavuavuavuxaaa*)*(*)*(*xuauavuavxvaaa*)*()*(*故有aaaaaauuvvuv*,*，进而有aavu，即aavu 为A中幺元。#26设是,*)(A一个半群，证明如果A是一个有限集，则在A中存在元素a，使得aaa*。解：由于A是一个有限集，取A中元素b，故由鸽笼原理知，存在正整数ji 满足jibb。令pij，则pipijibbbbb*，进而对任意的iq，也有pqqbbb*。另一方面由于1p，故存在正整数k满足ikp，从而pkpkpbbb*，进而有pkpkpbbb*ppkpbbb*kpkpbb*。令kpba，有aaa*。#27求),(66Z的所有子群及陪集，其中yxyx6。解：其子群为64321,4,2,0,3,0,0ZHHHH。关于子群01H的陪 集 分 别 为5,4,3,2,1,0；关 于 子 群3,02H的 陪 集 分 别 为5,2,4,1,3,0；关于子群4,2,03H的陪集分别为5,3,1,4,2,0；关于子群64ZH的陪集就是其自身。#28求证有限群中周期大于 2 的元素个数必为偶数。证：因为根据群元素周期的定义知，每个元素与其逆元素的周期是一致的，而当该元素的周期大于 2 时，其逆元素与本身不同，故有限群中周期大于 2 的元素必是成对出现，从而其周期大于 2 的元素个数必为偶数。#29若cba,是格),(A中的元素，求证：)()()(cabacba。证：bacbabcb)(,；又cacbaccb)(,；进而有)()()(cabacba。#30若cba,是格),(A中的元素，求证：)()()(cbacaba。证：)(,cbabacbb；又)(,cbacacbc；进而有)()()(cbacaba。#10/10 31.分配格与模格的刻画与关系。
