教辅- 离散数学复习资料 试卷 习题与答案全集.doc

离散数学总复习资料 一、鸽笼原理与容斥原理 1．求证边长为1的正方形中放9个点，由这些点构成的三角形中，必有一个三角形面积小于。 证：把该正方形均分成四个相同的小正方形，则由鸽笼原理知，必有一个小正方形内存在三个点，且这三个点构成的三角形面积小于。# 2．对一列个不同整数，任意排列，证明一定存在长为的上升子序列或下降子序列。 证：设此序列为：，从开始上升子序列最长的长度为，下降子序列最长的长度为，每一个都对应了。若不存在长为的上升子序列或下降子序列，那么，形如的不同点对至多有个，而有个，则由鸽笼原理知，必有同时对应，由于，若，则至少比大1，若，则至少比大1，这均与矛盾。故原命题成立。# 3．求中不被3、4、5整除的个数。 解： 设表示中被3整除的数的集合，表示中被4整除的数的集合，表示中被5整除的数的集合，则 ， ，进而有 故有 即中不被3、4、5整除的个数为40。# 4．有100个学生，其中60个爱看小说，30个爱下棋，10个既爱看小说，又爱下棋，5个既爱看小说，又爱跳舞，没有既爱下棋，又爱跳舞的，三种活动都不爱的有10个，问有几个学生爱跳舞？ 解：设全体学生的集合为，爱看小说的学生集合为，爱下棋的学生集合为，爱跳舞的学生集合为，则依题意有， ，，从而，。另一方面，根据容斥原理，我们有，即有，故，即有15个学生爱跳舞。# 二、数理逻辑 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）将式子“并非跑的最快的马吃的最多”翻译成用谓词和量词表达的逻辑式子。(2)将式子“爱因斯坦于1952年写完‘狭义与广义相对论浅说’”翻译成用谓词和量词表达的逻辑式子。 解：（1）：马； ：跑的最快的马； ：吃的最多的马。 上式表示为： （2）设：爱因斯坦； ：1952； ：‘狭义与广义相对论浅说’； ：于年写完；则原式子可翻译成逻辑式子。 8．求下述公式的前束范式和Skolem标准形。 解：= = = = = = 故该公式的前束范式为； Skolem标准形为。# 9．将下列命题符号化，并证明其论证是否正确。 不存在白色的乌鸦；北京鸭是白色的。因此，北京鸭不是乌鸦。 解：令是白色的；：是乌鸦；：是北京鸭。则上述命题可符号化为： 下面，我们证明上述命题是正确的。 （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） 24 12 8 6 4 3 2 1 11．(1)举出正整数集上一种二元关系,它是等价关系又是偏序关系;(2) 画出的Hasse图 ,其中。 解：（1）正整数集上的恒等关系。 （2） 6 4 3 2 1 12．设，定义