离散数学知识点总结 一、各章复习要求与重点
第一章 集 合
[复习知识点]
1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集
2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan律等），文氏（Venn）图 3、序偶与迪卡尔积
本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 [复习要求]
1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。 2、掌握集合的表示法和集合的交、并、差、补等基本运算。 3、掌握集合运算基本规律，证明集合等式的方法。 4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。 [本章重点习题]
P5~6，4、6； P14~15，3、6、7； P20，5、7。 [疑难解析] 1、集合的概念
因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n。 2、集合恒等式的证明
通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在A?B?A?~B证明中的特殊作用。 [例题分析]
例1 设A，B是两个集合，A={1，2，3}，B={1，2}，则?(A)??(B)? 。 解
?(A)?{?,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
?(B)?{?,{1},{2},{1,2}}
于是?(A)??(B)?{{3},{1,3},{2,3},{1,2,3}}
例2 设A??a,b,?a,b?,??，试求：
(1)A??a,b?； (2)A??； (3)A????； (4)??a,b???A； (5)??A； (6)????A。
解 (1)A??a,b????a,b?,?? (2)A???A (3)A??????a,b,?a,b?? (4)??a,b???A?? (5)??A?? (6)????A?? 例3 试证明?A?~B???~A?B???A?B???~A?~B? 证明
?A?~B???~A?B????A?~B??~A????A?~B??B????A?~A???~B?~A?????A?B???~B?B??
?????~A?~B?????A?B??????A?B???~A?~B?
第二章 二元关系
[复习知识点]
1、关系、关系矩阵与关系图 2、复合关系与逆关系
3、关系的性质（自反性、对称性、反对称性、传递性） 4、关系的闭包（自反闭包、对称闭包、传递闭包） 5、等价关系与等价类
6、偏序关系与哈斯图（Hasse）、极大/小元、最大/小元、上/下界、最小上界、最大下界 7、函数及其性质（单射、满射、双射） 8、复合函数与反函数
本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射的概念 [复习要求]
1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。
2、掌握求复合关系与逆关系的方法。
3、理解关系的性质（自反性、对称性、反对称性、传递性），掌握其判别方法（定义、矩阵、图）。 4、掌握求关系的闭包 （自反闭包、对称闭包、传递闭包）的方法。
5、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/
小元、上/下界、最小上界、最大下界的求法。
6、理解函数概念：函数、函数相等、复合函数和反函数。 7、理解单射、满射、双射等概念，掌握其判别方法。 [本章重点习题]
P25，1；P32~33，4，8，10； P43，2，3，5； P51~52，5，6； P59，1，2； P64，3； P74~75，2，4，6，7； P81，5，7； P86，1，2。 [疑难解析] 1、关系的概念
关系的概念是第二章全章的基础，又是第一章集合概念的应用。因此，学生应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。 2、关系的性质及其判定
关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。对于四种性质的判定，可以依据教材中P49上总结的规律。这其中对传递性的判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。另一点是介绍一种判定传递性的“跟踪法”，即若
?a1,a2??R,?a2,a3??R,??,?ai?1,ai??R，则?a1,ai??R。如若?a,b??R,?b,a??R，则有
?a,a??R，且?b,b??R。
３、关系的闭包
在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记三个定理的结论：定理2，
r?R??R?IA；定理3， s?R??R?R；定理4，推论 t?R???Ri。
?1ni?1４、半序关系及半序集中特殊元素的确定
理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大（小）元，极大（小）元也就容易了。这里要注意，最大（小）元与极大（小）元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同样。 ５、映射的概念与映射种类的判定
映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数。 [例题分析]
例1 设集合A??a,b,c,d?，判定下列关系，哪些是自反的，对称的，反对称的和传递的：
R1???a,a?,?b,a??R5???a,c?,?b,d??R2???a,a?,?b,c?,?d,a??R3???c,d??R4???a,a,?,?b,b?,?c,c??解：均不是
自反的；R4是对称的；R1 ,R2 ,R3 , R4 ,R5是反对称的；R1 ,R2 ,R3 , R4 ,R5是传递的。
1,2,3,4,5?，A上的二元关系R为 例2 设集合A?? R???1,1?,?2,2?,?3,3?,?3,4?,?4,4?,?5,3?,?5,4?,?5,5?? （１）写出R的关系矩阵，画出R的关系图； （２）证明R是A上的半序关系，画出其哈斯图；
（３）若B?A，且B??2,3,4,5?，求B的最大元，最小元，极大元，极小元，最小上界和最大下界。 解 （1）R的关系矩阵为
?1??0 MR??0??0?0?0000??1000?0110? R的关系图略
?0010?0111?? （2）因为R是自反的，反对称的和传递的，所以R是A上的半序关系。(A,R)为半序集， (A,R)的哈斯图如下
。4 。1
。3 。2
。5
(3) 当B??2,3,4,5?，B的极大元为2，4；极小元为2，5；B无最大元与最小元；B也无上界与下界，更无最小上界与最大下界。
第三章 命题逻辑
[复习知识点]
１、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题
２、命题公式与解释，真值表，公式分类（恒真、恒假、可满足），公式的等价 ３、析取范式、合取范式，极小（大）项，主析取范式、主合取范式