华中科技大学离散课件-(5).ppt

离散数学;第一章;例如：;关于集合的概念有两点需要主意：;例如：;;二、集合的表示方法;列举法表示集合的两个例子：;描述法表示集合：;三、空集和集合的基数;四、悖论;理发师的悖论：在一个小镇上，有一个理发师在自己的理发店里定了一个规矩P:“他只给该城那些不给自己理发的人理发”。;悖论产生的原因：;1.2集合的子集;定义1-3:;集合的包含关系具有如下几条性质：;⑴用反证法。〔设结论不成立，推出矛盾〕;〔3〕这里采用第1种方法〔直接用定义推导〕;1.3幂集;分析：前面介绍了，A的子集是A的一部分，那么由A中i个元素组成的子集有个，若A有n个元素，于是有：;二、列举幂集的一种特殊方法;B000=ΦB001={2}B010={5};定义1-6:;定义1-7：设有集合A、B，A与B的并集记作

A∪B＝{u|u∈A或u∈B};定义1-8：设有集合A、B，A与B的交集，记作：

A∩B＝{u|u∈A且u∈B};例：A={2,5,6}B={3,4,2}C={1};定义1-9设有集合A、B，所有属于B而不属于A的元素组成的集合，称为A相对于B的补集，记作B-A。即;定义1-10集合A相对于全集合U的补集称为A的补集，记作A。即;A

;例：给定以下正整数集合N的子集：;证明：;例:在一个班级的50个学生中，有26个人在离散数学考试中取得了优秀的成绩；有21人在程序设计考试中取得了优秀的成绩，假设有17人两次考试中都没有取得优秀的成绩，问有多少个学生在两次考试中都取得了优秀？;但是Φ∈2A－B;四、集合运算的定律;互补律;上面的定律都可以根据定义证明，我们选择一个来证明。;下面看关于差运算的几个有用结论;⑶;⑷;例试证明对任意集合A、B、C，等式(A-B)∪(A-B)=A;因为结合律成立，对任意集合A、B、C有：;1.5集合成员表;并、交集的成员表

根据集合的并和交运算的定义，全集合U中的元素u可分为如下四种情形：

（1），

（2），

（3），

（4）??;设A是全集合U的子集，根据补集的定义，全集合U中的元素可分为两种情形，

（1）若，则

（2）若，则;例：由A、B、C所产生的集合(A∪B)∩(A∪C)的成员表;上面的成员表有23＝8行。它相应于u在A、B、C中的23种可能的成员/非成员情况。把标记A、B、C列中的一行数α1α2α3称作α1α2α3行。在上面的成员表中，由于直接标(A∪B)∩(A′∪C)不直观，于是把中间过程产生的集合也标出来。;设A、B、C是任意集合，试问等式S=T是否成立？;1.6集合分划与覆盖;由定义可以看出，集合A上的一个分划必定是A的一个覆盖；反之，A的覆盖未必是A的分划。;例A＝{1,2,3,4,5,6,7,8,9},其子集的集合有

(1)∏1={{1,3,5},{2,4,6,8},{5,7,9}}

(2)∏2={{1,3,5},{2,6},{4,8,9}}

(3)∏3={{1,3,5},{2,4,6,9},{7,9}}

(4)∏4={{1,3,5},{7,9},{2,4},{6,8}}

问这些哪些是A的分划？哪些是A的覆盖？;例如：A∩B，A∩B，A∩B，A∩B是由A，B产生的全部最小集。由A、B产生的全部最小集含有22＝4个，因为由两个位置，每个位置有两种选择。;例如：A1∩A2∩A3∩A4表示为M1001;命题：M