资源描述：
《离散数学复习资料 试卷 习题与答案全案备考资料.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、离散试卷及答案离散数学总复习资料一、鸽笼原理与容斥原理1．求证边长为1的正方形中放9个点，由这些点构成的三角形中，必有一个三角形面积小于。证：把该正方形均分成四个相同的小正方形，则由鸽笼原理知，必有一个小正方形内存在三个点，且这三个点构成的三角形面积小于。#2．对一列个不同整数，任意排列，证明一定存在长为的上升子序列或下降子序列。证：设此序列为：，从开始上升子序列最长的长度为，下降子序列最长的长度为，每一个都对应了。若不存在长为的上升子序列或下降子序列，那么，形如的不同点对至多有个，而有个，则由鸽笼原理知，必有同时对应，由于
2、，若，则至少比大1，若，则至少比大1，这均与矛盾。故原命题成立。#3．求中不被3、4、5整除的个数。解：设表示中被3整除的数的集合，表示中被4整除的数的集合，表示中被5整除的数的集合，则，，进而有故有即中不被3、4、5整除的个数为40。#4．有100个学生，其中60个爱看小说，30个爱下棋，10个既爱看小说，又爱下棋，5个既爱看小说，又爱跳舞，没有既爱下棋，又爱跳舞的，三种活动都不爱的有10个，问有几个学生爱跳舞？解：设全体学生的集合为，爱看小说的学生集合为，爱下棋的学生集合为，爱跳舞的学生集合为，则依题意有，，，从而，。另
3、一方面，根据容斥原理，我们有，即有，故，即有15个学生爱跳舞。#第72页共72页离散试卷及答案二、数理逻辑5．求的主析取、主合取范式。解：取真为：(1,1)，(0,0)，(0,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）将式子“并非跑的最快的马吃的最多”翻译成用谓词和量词表达的逻辑式子
4、。(2)将式子“爱因斯坦于1952年写完‘狭义与广义相对论浅说’”翻译成用谓词和量词表达的逻辑式子。解：（1）：马；：跑的最快的马；：吃的最多的马。上式表示为：（2）设：爱因斯坦；：1952；：‘狭义与广义相对论浅说’；：于年写完；则原式子可翻译成逻辑式子。8．求下述公式的前束范式和Skolem标准形。解：======故该公式的前束范式为；Skolem标准形为。#第72页共72页离散试卷及答案9．将下列命题符号化，并证明其论证是否正确。不存在白色的乌鸦；北京鸭是白色的。因此，北京鸭不是乌鸦。解：令是白色的；：是乌鸦；：是北京
5、鸭。则上述命题可符号化为：下面，我们证明上述命题是正确的。（1）（P）（2）（US）（3）（CP）（4）（分离规则）（5）（量词转换律）（6）（US）（7）（T，（4））（8）（9）（UG）#三、二元关系10．(1)举出正整数集上一种关系,它是等价关系但不是偏序关系;(2)举出正整数集上一种关系,它是偏序关系但不是等价关系。(3)画出集合上整除关系的Hasse图。（4）等价关系与划分关系解：（1）正整数集上模3的同余关系。（2）正整数集上的整除关系。（3）241286432111．(1)举出正整数集上一种二元关系,它是等价关
6、系又是偏序关系;(2)画出的Hasse图,其中。解：（1）正整数集上的恒等关系。第72页共72页离散试卷及答案（2）6432112．设，定义上的一个二元关系如下：（1）画出的关系图，并写出的关系矩阵；（2）求，；（3）求，，。解：（1）（2）（3）又故13．设是正整数集关于整除关系作成的偏序集，的子集，求的极小元、极大元、上界、下界、最小上界、最大下界。解：（略）四．图论14．（1）画一个图，使它既有欧拉回路，又有哈密顿回路；（2）画一个回路图，使它既无欧拉回路，又无哈密顿回路。解：（1）第72页共72页离散试卷及答案（2）
7、或15．（1）画一个图，使它有欧拉回路，无哈密顿回路；（2）画一个回路图，使它无欧拉回路，有哈密顿回路。解：（1）（2）16．证明小于30条边的简单平面图至少有一个顶点的度数小于5。证：（反证法）假设小于30条边的简单平面图中每一个顶点的度数大于等于5，从而此时顶点数与边数满足；另一方面，由于此时图的每一个区域至少由3条边围成，从而由Euler公式推论知，此时顶点数与边数满足；故有，进而有，这与已知条件产生矛盾。故小于30条边的简单平面图至少有一个顶点的度数小于5。#17．证明具有6个顶点和12条边的连通简单平面图，它的每个
8、区域都是由三条边围成。证：由题意及欧拉公式知，其区域数为。若有一个区域不是由三条边围成，则至少由4条边围成，从而8个区域至少需要25条边才能围成，即图中的边数不少于25/2=12.5,这与已知条件12条边产生矛盾，故它的每个区域都是由三条边围成。#18．设，任意顶点的次（度）不少于2，且任
