离散数学总复习资料

一、鸽笼原理与容斥原理

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）               

11．(1)举出正整数集上一种二元关系,它是等价关系又是偏序关系;(2) 画出的Hasse图 ,其中。

解：（1）正整数集上的恒等关系。

（2）

12．设，定义上的一个二元关系如下：

（1）画出的关系图，并写出的关系矩阵；（2）求，；（3）求，，。

解：（略）

13．设是正整数集关于整除关系作成的偏序集，的子集，求的极小元、极大元、上界、下界、最小上界、最大下界。

解：（略）

四．图论

14．（1）画一个图，使它既有欧拉回路，又有哈密顿回路；（2）画一个回路图，使它既无欧拉回路，又无哈密顿回路。

  

                  

15．（1）画一个图，使它有欧拉回路，无哈密顿回路；（2）画一个回路图，使它无欧拉回路，有哈密顿回路。

16．证明小于30条边的简单平面图至少有一个顶点的度数小于5。

证：（反证法）假设小于30条边的简单平面图中每一个顶点的度数大于等于5，从而此时顶点数与边数满足；另一方面，由于此时图的每一个区域至少由3条边围成，从而由Euler公式推论知，此时顶点数与边数满足；故有，进而有，这与已知条件产生矛盾。故小于30条边的简单平面图至少有一个顶点的度数小于5。#

17．证明具有6个顶点和12条边的连通简单平面图，它的每个区域都是由三条边围成。

证：由题意及欧拉公式知，其区域数为。若有一个区域不是由三条边围成，则至少由4条边围成，从而8个区域至少需要25条边才能围成，即图中的边数不少于25/2=12.5, 这与已知条件12条边产生矛盾，故它的每个区域都是由三条边围成。#

18．设，任意顶点的次（度）不少于2，且任意两个相邻区域只有一条公共边的简单平面图，证明其着色数不少于3。

解：（略）

19．用算法寻找下图中顶点到的最短路径。             

解：从出发第一短的点为，距离为1，路径为；从出发第二短的点为或，距离为2，路径为或；从出发第四短的点为或，距离为3，路径为或；从出发第五短的点为或或，距离为4，路径为或（或）或。故顶点到的最短路径为。#

20．求分别用前序、中序、后序遍历（周游）下图。                 

 解：前序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．求出下图的最小生成树。

22．设7个字母在通讯中出现的频率如下， ，编一个相应的二元前缀码，使通讯中出现的符号尽可能少，并画出对应的二元树。解：该二元前缀码对应的Huffman树为：

             

从而对应的二元前缀码为：。#

23．（10分）给定树叶的权分别为1，4，9，16，25，36，49，64，81，100，试构造一棵最优树。

解：（略）

24.握手原理及其应用。

五．代数系统与布尔代数

24．讨论下表给出集合上的运算是否具有交换律、结合律，并求出零元、幂等元。

解：根据上表运算结果的对称性知,上述运算满足交换律,又由上表的第二行与第二列知0是其零元, 再由上表的第三行与第三列知1是其幺元，并由对角线上的具体结果知，仅有0与1是其幂等元。从而对，当中有一个为0或1时，均有；又，，，，，, ，，。故上述运算满足结合律。#

25．设是一个半群，,对中每个中存在元素满足，则中存在幺元。

证:依题意，存在满足。另一方面，任取中中存在元素满足，从而有

 

故有，进而有，即为中幺元。#

26．设是一个半群，证明如果是一个有限集，则在中存在元素，使得。

解：由于是一个有限集，取中元素，故由鸽笼原理知，存在正整数满足。令，则，进而对任意的，也有。另一方面由于，故存在正整数满足，从而，进而有。令，有。#

27．求的所有子群及陪集，其中。

解：其子群为。关于子群的陪集分别为；关于子群的陪集分别为；关于子群的陪集分别为；关于子群的陪集就是其自身。#

28．求证有限群中周期大于2的元素个数必为偶数。

证：因为根据群元素周期的定义知，每个元素与其逆元素的周期是一致的，而当该元素的周期大于2时，其逆元素与本身不同，故有限群中周期大于2的元素必是成对出现，从而其周期大于2的元素个数必为偶数。#

29．若是格中的元素，求证：。

证：；又；

进而有。#

30．若是格中的元素，求证：。

证： ；又；

进而有。#

31.分配格与模格的刻画与关系。

第二篇：离散数学总复习资料3

离散数学总复习资料

一、鸽笼原理与容斥原理

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．设，定义上的一个二元关系如下：

（1）画出的关系图，并写出的关系矩阵；（2）求，；（3）求，，。

解：（1）

                                                     

（2）                                   

                                         （3）        

                          

又                                      

故                                               

13．设是正整数集关于整除关系作成的偏序集，的子集，求的极小元、极大元、上界、下界、最小上界、最大下界。

解：（略）

  

四．图论

14．（1）画一个图，使它既有欧拉回路，又有哈密顿回路；（2）画一个回路图，使它既无欧拉回路，又无哈密顿回路。

解：（1） 

                

 

（2）   

 

                                 或

                  

15．（1）画一个图，使它有欧拉回路，无哈密顿回路；（2）画一个回路图，使它无欧拉回路，有哈密顿回路。

解：（1） 

                        

 

（2）   

 

                  

16．证明小于30条边的简单平面图至少有一个顶点的度数小于5。

证：（反证法）假设小于30条边的简单平面图中每一个顶点的度数大于等于5，从而此时顶点数与边数满足；另一方面，由于此时图的每一个区域至少由3条边围成，从而由Euler公式推论知，此时顶点数与边数满足；故有，进而有，这与已知条件产生矛盾。故小于30条边的简单平面图至少有一个顶点的度数小于5。#

17．证明具有6个顶点和12条边的连通简单平面图，它的每个区域都是由三条边围成。

证：由题意及欧拉公式知，其区域数为。若有一个区域不是由三条边围成，则至少由4条边围成，从而8个区域至少需要25条边才能围成，即图中的边数不少于25/2=12.5, 这与已知条件12条边产生矛盾，故它的每个区域都是由三条边围成。#

18．设，任意顶点的次（度）不少于2，且任意两个相邻区域只有一条公共边的简单平面图，证明其着色数不少于3。

解：（略）

19．用算法寻找下图中顶点到的最短路径。             

              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

                      a

解：从出发第一短的点为，距离为1，路径为；从出发第二短的点为或，距离为2，路径为或；从出发第四短的点为或，距离为3，路径为或；从出发第五短的点为或或，距离为4，路径为或（或）或。故顶点到的最短路径为。#

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个字母在通讯中出现的频率如下， ，编一个相应的二元前缀码，使通讯中出现的符号尽可能少，并画出对应的二元树。解：该二元前缀码对应的Huffman树为：

                                 100

                             40            60

                          20      20   25       35

                       10      10    10      15

                     5      5                           

从而对应的二元前缀码为：。#

23．（10分）给定树叶的权分别为1，4，9，16，25，36，49，64，81，100，试构造一棵最优树。

解：（略）

24.握手原理及其应用。

五．代数系统与布尔代数

24．讨论下表给出集合上的运算是否具有交换律、结合律，并求出零元、幂等元。

解：根据上表运算结果的对称性知,上述运算满足交换律,又由上表的第二行与第二列知0是其零元, 再由上表的第三行与第三列知1是其幺元，并由对角线上的具体结果知，仅有0与1是其幂等元。从而对，当中有一个为0或1时，均有；又，，，，，, ，，。故上述运算满足结合律。#

25．设是一个半群，,对中每个中存在元素满足，则中存在幺元。

证:依题意，存在满足。另一方面，任取中中存在元素满足，从而有

 

故有，进而有，即为中幺元。#

26．设是一个半群，证明如果是一个有限集，则在中存在元素，使得。

解：由于是一个有限集，取中元素，故由鸽笼原理知，存在正整数满足。令，则，进而对任意的，也有。另一方面由于，故存在正整数满足，从而，进而有。令，有。#

27．求的所有子群及陪集，其中。

解：其子群为。关于子群的陪集分别为；关于子群的陪集分别为；关于子群的陪集分别为；关于子群的陪集就是其自身。#

28．求证有限群中周期大于2的元素个数必为偶数。

证：因为根据群元素周期的定义知，每个元素与其逆元素的周期是一致的，而当该元素的周期大于2时，其逆元素与本身不同，故有限群中周期大于2的元素必是成对出现，从而其周期大于2的元素个数必为偶数。#

29．若是格中的元素，求证：。

证：；又；

进而有。#

30．若是格中的元素，求证：。

证： ；又；

进而有。#

31.分配格与模格的刻画与关系。