离散数学文档1

《离散数学文档1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本章学习目标：集合是一般数学及离散数学中的基本概念，几乎与现代数学的各个分支都有密切联系，并且渗透到很多科技领域。本章主要介绍集合的基本知识，通过本章学习，读者应该掌握以下内容：（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如果两个集

2、合A和B的元素完全相同，则称这两个集合相等，记作A＝B。例如：A＝｛1，2，3，4｝B＝｛3，1，4，2｝C＝｛xx是英文字母且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＝｛xx是英文字母且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不相等，也就是说

3、在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)＝｛XX⊆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，

4、则A的幂集ρ(A)的基为2n。证明：由排列组合知：ρ(A)=Cn0+Cn1+…+Cnn又由二项式定理知：Cn0+Cn1+…+Cnn=2n所以可得：ρ(A)=2n1.3集合的运算1.3.1集合的并运算定义1.6任意两个集合A、B的并，记作A∪B，它也是一个集合，由所有属于A或者属于B的元素合并在一起而构成的，即A∪B＝｛xx属于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合的并

5、运算用文氏图表示集合之间的并运算：集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的元

6、素构成，即A∩B＝｛xx属于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是两个

7、集合，A-B也是一个集合。它是由属于集合A但不属于集合B的所有元素组成的。A-B称为集合B关于A的补集(或相对补)。即Ａ-B＝｛xx属于Ａ且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-Ａ＝｛xx属于Ｕ且x不属于Ａ｝例如，U＝｛xx是华北航天工业学院的学生｝，A＝｛xx

8、是华北航天工业学院的女学生｝，则~A＝｛xx是华北航天工业学院的男学生｝1.3集合的运算1.3.3集合的补集合的补运算有以下性质（1）双重否定律：~（~A）＝A（2