离散数学-第三章：集合的基本概念和运算课件

第3章集合的基本概念和运算

§3.1集合的基本概念§3.2集合的基本运算§3.3集合中元素的计数关于集合的有趣的例子在一个僻静的孤岛上，住着一些人家，岛上只有一位理发师，该理发师专给那些并且只给那些自己不刮脸的人刮脸。那么谁给这位理发师刮脸？分析设C={x|x是不给自己刮脸的人}，b是这位理发师.一方面,如果bC，则b是不给自己刮脸的人；另一方面，由题意知，这位理发师b只给集合C中的人刮脸。所以b要给b刮脸，即bC;另一方面,如果bC，则b是要给自己刮脸的人；另一方面，由题意知，理发师只给自己不刮脸的人刮脸。所以b是不给自己刮脸的人，即bC。无论如何，都有bC和bC同时成立。这种情况称为罗素悖论。§3.1集合的基本概念1.集合的概念没有精确的定义,但一般认为一个集合指的是可确定的可分辨的事物构成的整体。元素：集合里所含的个体称为集合的元素。1）集合的三要素：确定性，无序性，互异性。2）集合的元素：可以是任意类型的事物，也可以为一个集合。例如：3）可以用树形结构把集合与元素之间的关系表示出来。在每层次上，把集合作为一个结点，它的元素则作为它的儿子。A{b,c}ad{{d}}bc{d}d注:2.集合之间的关系包含关系:相等关系:B为A的子集真子集:空集:定理1.空集是一切集合的子集.证明:任给一个集合A,只需证即可.事实上,由子集的定义,而右端的蕴涵式中因前件为假,所以整个蕴涵式对一切x为真,所以为真.3.集合全部子集

推论.空集是唯一的.证明:假设存在两个空集则由定理1知且从而例1.求A的全部子集.解:将A的子集从小到大分类;0元子集:1个,1元子集:个,2元子集:个,3元子集:个,注:一般的,对于n元子集A,它的m元子集共有个,所以不同的子集总数有:3.2集合的运算及性质一、集合的运算集合的运算，就是以给定集合为对象，按照确定的规则得到另外一些集合。1.集合的交定义1

设A，B为任意两集合，由集合A和B的所有共同元素组成的集合S,称为A和B的交集，记作A∩B。

S=A∩B={x|x∈A∧x∈B}用文氏图表示如下：EAB例：A={0,2,4,6,8},B={1,2,3,4,5,6},则:A∩B={2,4,6}2.集合的并定义2

设A，B为任意两集合，所有属于A或属于B的元素组成的集合S,称为A和B的并集，记作A∪B。

S=A∪B={x|x∈A∨x∈B}用文氏图表示如下：ABE例：设A={1,2,3,4},B={2,4,5}.则

A∪B={1,2,3,4,5}.并、交的推广两个集合的并交运算可推广至n个集合：A1∩A2∩

…∩An={x|x∈A1∧x∈A2∧

…∧x∈An}A1∪A2∪…∪An={x|x∈A1∨x∈A2∨…∨x∈An}可以把n个集合的交和并简记为和,即3.集合的补定义3

设A，B为任意两集合，所有属于A而不属于B的一切元素组成的集合S,称为B对于A的补集，或称相对补，记作A-B。

S=A-B={x|x∈A∧xB}={x|x∈A∧

(xB)}A-B也称为集合A和B的差。用文氏图表示如下：EAB例：设A={2,5,6},B={1,2,4,7,9},则A-B={5,6}定义4设E为全集，对任一集合A关于E的补E-A,称为集合A的绝对补集，记作~A.~A=E–A={x|x∈E∧xA}文氏图表示如下：EA定义5

设A，B为任意两个集合，A与B的对称差为集合S,其元素或属于A,或属于B,但不能既属于A又属于B,记作A⊕B。

A⊕B=(A–B)∪(B-A)或A⊕B=(A∪B)-(A∩B)用文氏图表示如下：EAB例：设A={a,b,e},B={a,c,d},则A-B={b,e},B-A={c,d}A⊕B={b,e,c,d}4.集合的对称差三、运算的性质任何代数运算都遵从一定的算律，集合运算也不例外。下面列出的是集合运算的主要算律,其中的A,B,C表示任意集合。1.集合运算的主要算律(1)幂等律A∪A=A A∩A=A(2)结合律 (A∪B)∪C=A∪(B∪C) (A∩B)∩C=A∩(B∩C)(3)交换律 A∪B=B∪A A∩B=B∩A(4)分配律 A∪(B∩C)=(A∪B)∩(A∪C) A∩(B∪C)=(A∩B)∪(A∩C)

(5)同一律 A∪Ø

＝A A∩E=A(6)零律

A∪E＝E

A∩Ø=Ø

(7)排中律 A∪~A=E(8)矛盾律

A∩~A=Ø(9)吸收律

A∪(A∩B)=A A∩(A∪B)=A(10)德摩根律

A-(B∪C)=(A-B)∩(A-C)

A-(B∩C)=(A-B)∪(A-C)

~(B∪C)=~B∩~C ~(B∩C)=~B∪~C ~Ø=E ~E=Ø(11)双重否定律

~~A=A(4)补差转换律A-B=A∩~B(6)对称差运算定律①交换律②结合律③∩对⊕满足分配律④⑤⑥(消去律)其它的结果:设A1、A2为集合公式，欲证A1=A2，只须证A1

A2∧A2

A1，也即证对任意的x,有

x∈A1

x∈A2和x∈A2x∈A1

成立，把这两个式子合到一起就是

x∈A1

x∈A2恒等式证明的两种思路：（1）根据定义进行证明（2）利用已有的集合恒等式证明新的恒等式总体上还是采用命题逻辑中的等值式，在叙述上采用半形式化的方法，其中⇔表示当且仅当，意即“等价”。例:证明德摩根律 证明~(B∪C)=~B∩~C证明：~(B∪C)={x|x~(B∪C)}={x|x(B∪C)}={x|x(B∪C)}={x|(xB∨xC)}={x|xB∧xC}={x|x~B∧x~C}=~B∩~C 练1：证明(A∪B)-C=(A-C)∪(B-C).证明:对于xx∈(A∪B)-C

⇔x∈(A∪B)

∧xC

⇔(

x∈A∨x∈B)∧xC

⇔(

x∈A∧xC)∨(x∈B∧xC)⇔x∈A-C∨x∈B-C

⇔x∈(A-B)∪(A-C)∴(A∪B)-C=(A-C)∪(B-C)练2：利用代入已知恒等式法证明

(A-B)∪(B-A)=(A∪B)-(A∩B).证明:(A-B)∪(B-A)=(A∩~B)∪(B∩~A)=

((A∩~B)∪B)∩((A∩~B)∪~A)=((A∪B)∩(~B∪B))∩((A∪~A)∩(~B∪~A))=((A∪B)∩E)∩(E∩(~B∪~A))=

(A∪B)∩(~B∪~A)=

(A∪B)∩~(B∩A)=

(A∪B)∩~(A∩B)=

(A∪B)-(A∩B)3.3集合中元素的计数定义3.3.1

如果存在nN,使得集合A与集合{x|xN∧x<n}={0,1,2,…,n-1}的元素个数相同，就说集合A的基数是n,记作cardA=n或|A|=n.所谓基数，是表示集合中所含元素多少的量。显然空集∅的基数是0。定义3.3.2

设A为集合，如果存在自然数n（0也是自然数）,使得cardA=n，则称集合A为有穷集，否则称A为无穷集。例{a,b,c,d}为有穷集，而N,Z,Q,R为无穷集。对有限集合A，P(A)=2|A|.例设某校有运动员总数为70人，其中足球队员38人，篮球队员35人，排球队员32人，其中有8人同时参加三个队，试求仅同时参加两个队的队员人数是几人？

则又

在文氏图中用A、B、C分别表示足球队员、篮球队员和排球队员的集合

解答案：仅同时参加两个队的队员人数是19人.

A38C32B35xyz8足球篮球排球定理3.3.2设A1,A2为有限集合，其元素个数分别是|A1|,|A2|,则|A1∪A2|=|A1|+|A2|-|A1∩A2|这个定理常称作包含排斥原理。推广1:推广2:包含排斥原理|A1∪A2|=|A1|+|A2|-|A1∩A2|推广2:A1A2E|A∪

B∪

C|=|A|+|B|+|C||A∩

B||B∩

C||A∩

C|+|A∩

B∩

C|，例:一个班20人，都至少会排球、网球和篮球中的一种，其中会打排球的有12人、会打网球的有6人、会打篮球的有14人，既会打排球又会打篮球的有6人，既会打网球又会打篮球的有5人，三种都会的有2人，问同时会排球和网