离散数学学习指导书

《离散数学学习指导书》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第1章集合1.1集合1.1.1基本知识点：集合、元素、基数、包含、子集、集合相等、空集、全集、幂集等。基本理论：两个集合相等的充分必要条件是它们的元素相同；如果有限集合A有个元素，则幂集合有个元素。基本计算：判断一个元素是否属于某个集合；判断两个集合是否具有包含关系；求一个集合的幂集；1.1.2重点与难点(1)集合与元素：集合是一个不能精确定义的基本概念，通常把具有某种共同性质的事物归纳成一个整体，就形成一个集合，一般用大写字母等表示集合的名称。把组成集合的事物称为元素，一般用小写字母等表示。(2)集合的表示方法：集合通常有两种

2、表示方法，即列举法、描述法。(3)包含与子集：对任意两个集合和，若对任意的，必有，则称被包含，或者包含，记作。若则称是的子集。(4)空集、全集和幂集：不包含任何元素的集合称为空集，记作。在一定范围内所有集合均为某一集合的子集，则称该集合为全集，记为。由集合的所有子集所构成的集合称为集合的幂集，记为。典型题解例1：下面是用列举法表示的集合：有时列出集合中所有元素是不现实或不可能的，如上面的和，但只要在省略号前或后列出一定数量的元素，能使人们一看就能了解那些元素属于这个集合就可以。例2：下面是用描述法表示的集合：54例3：集合与集合

3、没有区别，集合与集合没有区别，即，。例4：试证空集是唯一的。证明：(1)假设存在空集和，由于空集是任何集合的子集，即和；这样，根据集合相等的定义就有，即空集是唯一的。例5设，则的子集有：0元子集1个：空集；一元子集3个：；二元子集三个：；三元子集一个：。所以的幂集为一般地说，对于含有个元素的集合，它的0元子集有个，1元子集有个，…，元子集有个，…，元子集有个。这样，根据二项式公式，子集的总数，也即是幂集的元素的个数为1.2集合的运算和文氏图1.2.1基本知识点：基本概念：集合的交、并、补、差和对称差运算、文氏图。基本理论：集合的

4、运算及其性质；补集的唯一性定理。基本计算：计算集合的交、并、补、差和对称差等；用集合运算的性质判断两个集合是否相等；用文氏图表示集合。1.2.2重点与难点：(1)集合运算的定义：(2)集合运算的性质：设是全集的任意子集，则交换律：，结合律：分配律：，54等幂律：，同一律：，零一律：，互补律：，对合律：吸收律：，德·摩根律：，(3)文氏图：UABAUABUAUABUABUAB由文氏图容易看出下列关系成立：，，，典型题解例1设，，全集，则例2证明分配律：54证明：因为所以例3证明证明：1.3分划和细分1.3.1基本知识点：基本概念：

5、分划、分划块、细分、真细分。基本理论：集合的分划就是将集合中的元素划分成几块，使得的每一个元素必须在某一块中，也仅在一块中。基本计算：求集合的分划。典型题解例1设，按照中元素是奇数或者偶数来区分，可将中元素分划为两块：因此是集合的一个分划。按照中元素能被2整除、被3整除或被5整除来区分，又可将中元素分为三块：54因此也是集合的一个分划。按照中元素能被2整除、被3整除或被4整除来区分，可得到的如下几个非空子集：因此不是集合的一个分划，原因之一是集合中有公共元素。由上例子可知集合的分划并不唯一。54第2章关系2.1笛卡儿积与关系2.

6、1.1基本知识点基本概念：笛卡尔积，关系，二元关系，关系的性质基本理论：关系的定义及表示；关系的性质(自反性、反自反性，对称性、反对称性、可传递性)基本计算：关系的表示；关系与关系的交、并、补、差运算。2.1.2重点与难点笛卡尔积：设是任意的集合，所有有序元组的集合，称为的笛卡尔积，用表示，其中，即：关系：笛卡尔积的任意一个子集称为元关系，它是个集合，其元素是元组；当时，称为到上二元关系。当时称为集合上的二元关系，简称关系。若，也可记作，称与有关系。若，则记作。特殊及常见的关系(1)空关系：；(2)集合上的普遍关系：；(3)集合

7、上的恒等关系：(4)整数集合上的整除关系：(5)整数集合上的同余关系：(6)实数集上的小于关系：(7)幂集合上的包含关系关系的表示方法(1)集合表示法：列举法和描述法；(2)矩阵表示法：用矩阵表示由有限集到有限集的关系；(3)关系图表示法：用有向图来表示有限集合上的关系；(4)次序图：用无向图来特定地表示有限集上的偏序关系。关系的集合运算54关系是集合，因此关系的交、并、差、补运算与集合的运算一致；另一方面关系与关系矩阵一一对应，因此可以用关系矩阵的布尔运算代替关系的运算。2.2关系的复合、关系的逆、关系的性质、闭包运算2.2.

8、1基本知识基本概念：关系的复合，关系的逆，关系的性质与关系的闭包基本性质：(1)关系复合的性质(1)设，，，则有(2)设，则：，，这里(3)关系的逆运算具有以下性质：，，，(4)设是集合上的二元关系，则关系的性质可以描述为：(i)具有自反性(ii)具有对称性(i