离散数学总复习资料一、鸽笼原理与容斥原理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）将式子“并非跑的最快的马吃的最多”翻译成用谓词和量词表达的
