[离散数学文档1.docxVIP

本章学习目标：集合是一般数学及离散数学中的基本概念，几乎与现代数学的各个分支都有密切联系，并且渗透到很多科技领域。本章主要介绍集合的基本知识，通过本章学习，读者应该掌握以下内容：（1）集合的概念及表示方法（2）子集、空集、全集、补集、幂集等（3）集合的基本运算：交、并、补和对称差第1章集合定义1.1 如果集合A中的每一个元素都是集合B中的元素，则称A是B的子集，也可以说A包含于B，或者B包含A，这种关系写作A?B 或 B?A如果A不是B的子集，即在A中至少有一个元素不属于B时，称B不包含A，记作B?A 或 A?B1.2 集合之间的关系定义1.2 如果两个集合A和B的元素完全相同，则称这两个集合相等，记作A＝B。例如：A＝｛1，2，3，4｝B＝｛3，1，4，2｝ C＝｛x|x是英文字母且x是元音｝ D＝｛a，e，i，o，u｝显然有A＝B，C＝D1.2 集合之间的关系定义1.2 如果两个集合A和B的元素完全相同，则称这两个集合相等，记作A＝B。例如：A＝｛1，2，3，4｝B＝｛3，1，4，2｝ C＝｛x|x是英文字母且x是元音｝ D＝｛a，e，i，o，u｝显然有A＝B，C＝D1.2 集合之间的关系定理1.1 集合A和集合B相等的充分必要条件是A?B且B?A。定义1.3 如果集合A是集合B的子集，但A和B不相等，也就是说在B中至少有一个元素不属于A，则称A是B的真子集，记作A?B 或 B?A例如：集合A＝｛1，2｝，B＝｛1，2，3｝，那么A是B的真子集定义1.4 若集合U包含我们所讨论的每一个集合，则称U是所讨论问题的完全集，简称全集。1.2 集合之间的关系定义1.5 设A是有限集，由A的所有子集作为元素而构成的集合称为A的幂集，记作ρ(A)，即ρ(A)＝｛X|X?A｝。在A的所有子集中，A和这两个子集又叫平凡子集。例如：A＝｛1，2，3｝，则 ρ(A)＝｛，｛1｝，｛2｝，｛3｝，｛1，2｝，｛1，3｝，｛2，3｝，｛1，2，3｝｝定理1.2 设A是有限集，|A|=n，则A的幂集ρ(A)的基为2 n。证明：由排列组合知：|ρ(A)|=++又由二项式定理知：++=所以可得：|ρ(A)|= 2 n1.3 集合的运算1.3.1 集合的并运算定义1.6任意两个集合A、B的并，记作A∪B，它也是一个集合，由所有属于A或者属于B的元素合并在一起而构成的，即A∪B＝｛x | x属于A或x属于B｝例如，A＝｛a，b，c｝，B＝｛a，b，c，d，e｝，则A∪B＝｛a，b，c，d，e｝又如，A＝｛1，2，3，4，5｝，B＝｛1，3，5，7，9｝，则A∪B＝｛1，2，3，4，5，7，9｝集1.3.1合的并运算用文氏图表示集合之间的并运算：集1.3.1合的并运算用文氏图表示集合之间的并运算：用平面上的矩形表示全集U。用矩形内的圆表示U中的任一集合。图中表示了集合A和集合B的并集。阴影部分就是A∪B。1.3 集合的运算1.3.1 集合的并运算由集合并运算的定义可知，并运算具有以下性质：（1）幂等律：A∪A＝A（2）同一律：A∪?＝A（3）零律：A∪U＝U（4）结合律：(A∪B)∪C＝A∪(B∪C)（5）交换律：A∪B＝B∪A1.3 集合的运算1.3.2 集合的交运算集合定义1.7 任意两个集合A、B的交记作A∩B，它也是一个集合，由所有既属于A又属于B的元素构成，即A∩B ＝｛x | x属于A且x属于B｝例如，A＝｛a，b，c｝，B＝｛b，c，d，e｝，则A∩B＝｛b，c｝又如，A＝｛1，2，3，4，5｝，B＝｛1，3，5，7，9｝，则A∩B＝｛1，3，5｝1.3 集合的运算1.3.2 集合的交运算定理1.3设A，B，C是三个集合，则下列分配律成立：A∩（B∪C）＝（A∩B）∪（A∩C）A∪（B∩C）＝（A∪B）∩（A∪C）定理1.4设A，B为两个集合，则下列关系式成立：A∪（A∩B）＝AA∩（A∪B）＝A这个定理称为吸收律，读者可以用文氏图验证。1.3 集合的运算1.3.3 集合的补定义1.8设A、B是两个集合，A-B也是一个集合。它是由属于集合A但不属于集合B的所有元素组成的。A-B称为集合B关于A的补集(或相对补)。即Ａ-B＝｛x|x属于Ａ且x不属于B｝A-B也称为集合A和B的差集。例如，Ａ＝｛a，b，c｝，B＝｛a，b｝，则Ａ-B＝｛c｝又如，Ａ＝｛a，b，c，d｝，B＝｛a，b，e，f｝，则Ａ-B＝｛c，d｝1.3 集合的运算1.3.3 集合的补定义1.9 设U是全集，A是U的一个子集，称U-A为A关于全集的补集，也叫做A的绝对补集，简称为补集。记作~A。即U-Ａ＝｛x|x属于Ｕ且x不属