离散数学集合

集合的基本概念和运算第三章§3.1集合的基本概念一、集合：一些可确定的可分辨的事物构成的整体。用大写字母A,B,C,……标记。如：(1)26个英文字母的集合；(2)坐标平面上所有点的集合。规定：(i)元素之间彼此相异；(ii)没有次序关系。组成一个集合的每一个特定的事物，叫做集合的元素，用小写字母a,b,c,……标记。常用集合记号：N：自然数集(包括0)；Z：代表整数集；Q：有理数集；R：实数集；C：复数集；

：空集(不含任何元素)；U：全集二、常用集合三、集合的表示方法：(1)列举法：A={a,b,c,d}可以看出a

A，但e

A(2)描述法：用谓词概括该集合中元素的属性，即：A={x|P(x)}如：A={x|x

Z

3<x6}两个集合间的关系(1)子集：如果B中每个元素都是A中元素，则B

A。(2)相等集：如果A

B且B

A，则A=B。符号化：B

A(x)(x

B

x

A)，显然：(i)S

S，(ii)对任意集合A，

A。符号化：A=B

A

B

B

A四、集合之间的关系(3)真子集：如果B

A

且B

A，则B

A。(4)幂集：集合A的全体子集构成的集合，记作P(A)。符号化：P(A)={B|B

A

}，n元集A的幂集P(A)中含2n个元素。例3.1

计算以下幂集(1)P(

)(2)P({,{}})(3)P({1,{2,3}})解：(1)P(

)={}(为什么不是?)(2)P({,{}})={, }(3)P({1,{2,3}})={, }方法：先写子集；再写含一个元素的子集；再写含二个元素的子集；……{},{{}},{,{}}{1},{2,3},{1,{2,3}}§3.2集合的基本运算并：A∪B={x|x

A

x

B}交：A∩B={x|x

A

x

B}，若A∩B=，则称A与B不交相对补：A

B={x|x

A

x

B}绝对补：A对全集U的相对补集，记作：~A或对称差：A

B=(A

B)∪(B

A)=(A∪B)(A∩B)一、几种常见的运算集合运算的直观表示：文氏图画法：(1)用大矩形表示全集U；(2)用一些圆圈(矩形内)表示不同的集合及其关系；(3)用阴影线表示运算结果。二、文氏图如：A

BA

BA

BA

B三、集合算律：(1)幂等律

A∪A=A

A∩A=A(2)结合律(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∩C)A∩(B∪C)=(A∩B)∪(A∩C)(9)吸收律

A∪(A∩B)=A

(7)排中律

A∪=U(8)矛盾律

A∩=

A∩(A∪B)=A(5)同一律

A∪

=A

A∩U=A(6)零律

A∪U=U

A∩

=

(10)德.摩根律A

(B∪C)=(A

B)∩(A

C)A

(B∩C)=(A

B)∪(A

C)(11)互补律

A∪=U(排中律)=U(德·摩根律)=

(德·摩根律)(12)双重否定律A∩=

(矛盾律)∪∩∪∩常用运算性质(1)A∩B

A

A∩B

B(2)A

A∪B

B

A∪B(3)A

B

A(5)A∪B=B

A

B

A∩B=A

A

B=(证明包含关系的各种方法)(4)(补变交)∩(7)(A

B)

C=A

(B

C)(8)A

=A(9)A

A=(6)A

B

=B

A(10)A

B=A

C

B=C(消去律)例3.2化简((A∪B∪C)∩(A∪B))

((A∪(B

C))∩A)解题思想：解：因为A∪B

A∪B∪C

A

A∪(B

C)所以(A∪B∪C)∩(A∪B)=A∪B(A∪(B

C))∩A=A所以原式是：(A∪B)

A=B

A利用算律和运算性质四、应用§3.3集合中元素的计数容斥原理：对任意两个有限集A和B，有|A∪B|=|A|+|B|

|A∩B||•|：集合的基数(元素个数)一、集合计数的基本原理证明：A∪B=B∪(A

B)且B∩(A

B)=

又A=(A

B)∪(A∩B)且(A

B)∩(A∩B)=

从而|A∪B|=|B|+|A

B||A|=|A

B|+|A∩B|即|A∪B|=|B|+|A|

|A∩B||A∪B∪C|

|A|

|B|

|C|

|A∩B|

|A∩C|

|B∩C|

|A∩B∩C|推广∩∩∪∩∩例3.3某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有两人会打这三种球，而6个会打网球的人都会打另外一种球(指篮球和排球)，求不会打这三种球的人数？二、实例=|A|+|B|+|C||A∩B||A∩C||B∩C|+|A∩B∩C|先求：=12+6+1465+2|A∩B|=23|A∩B|解：用A、B、C分别表示会打排球、网球、篮球的学生集合，则有：|A|=12，|A∩C|=6，∩∩∪∪|B|=6，|U|=25|C|=14，|B∩C|=5，|A∩B∩C|=2∪∪|A∪B∪C|又因为6个会打网球的人都会打另外一种球，=6(52)=3∩∩∩∩∩∩∩∩∪∩∩∩∩∪∪∪∩∩∩∪∩∩∩∪∩∩∪∩∩∩∩∪例3.4一个班里有50个学生，在第一次考试中有26人得5分，在第二次考试中有21人得5分。如果两次考试中都没得5分的有17人，那么在两次考试都得5分的有多少人？解：设A、B、分别表示第一和第二次考试中得5分学生的集合，那么有又