1、集合集合集合间的关系集合间的关系集合的运算集合的运算幂集与编码幂集与编码集合恒等式的证明集合恒等式的证明11.1集集合合1.1.1 1.1.1 集合的概念集合的概念集合集合是具有某种特定性质的事物的全体。是具有某种特定性质的事物的全体。集合中的单个事物通常也称为集合中的单个事物通常也称为“个体个体”或或“元素元素”。通常用英文大写字母来表示集合，如通常用英文大写字母来表示集合，如A A、B B、C C等，用小写字母等，用小写字母来表示集合中的元素，如来表示集合中的元素，如a a、b b、c c等，但不是绝对的，因为等，但不是绝对的，因为一个集合也可以作为另一个集合的元素。如果元素一个集合也可以
2、作为另一个集合的元素。如果元素a a是集合是集合A A中的元素，用符号中的元素，用符号aAaA来表示，读作来表示，读作“元素元素a a属于集合属于集合A A”；反之，如果元素反之，如果元素a a不是集合不是集合A A中的元素，用符号中的元素，用符号a a A A来表来表示，读作示，读作“元素元素a a不属于集合不属于集合A A”。集合集合、元素元素和和属于属于是是集合论中的三个最基本的概念。集合论中的三个最基本的概念。2例例1.11.1判断下列各项是否是集合。判断下列各项是否是集合。（1 1）英文字母表中的英文字母表中的2626个字母；个字母；（2 2）所有的自然数；所有的自然数；（3 3）一
3、些自行车；一些自行车；（4 4）上海财经大学全体学生的集合。上海财经大学全体学生的集合。3 N N：全体自然数的集合；：全体自然数的集合；Q Q：全体有理数的集合；：全体有理数的集合；R R：全体实数的集合；：全体实数的集合；C C：全体复数的集合；：全体复数的集合；Z Z：全体整数的集合；：全体整数的集合；E E：全体偶数的集合；：全体偶数的集合；O O：全体奇数的集合；：全体奇数的集合；P P：全体素数的集合。：全体素数的集合。4互异性：互异性：互异性是指一个集合的各个元素是可以互相互异性是指一个集合的各个元素是可以互相区分开的，并且每个元素只能出现一次，如果某个区分开的，并且每个元素只能
4、出现一次，如果某个元素在集合中出现多次，也只能看作是一个元素。元素在集合中出现多次，也只能看作是一个元素。如：集合如：集合1,2,3,21,2,3,2就是集合就是集合1,2,31,2,3。无序性：无序性：无序性是指一个集合中所有元素之间的排列无序性是指一个集合中所有元素之间的排列次序是任意的，即集合的表示形式是不唯一的。如次序是任意的，即集合的表示形式是不唯一的。如集合集合1,2,31,2,3和集合和集合2,1,32,1,3是同一个集合。是同一个集合。确定性：确定性：任意一个元素是否属于某一个集合回答是确任意一个元素是否属于某一个集合回答是确定的。如给定元素定的。如给定元素a a和集合和集合A
5、 A，元素，元素a a和集合和集合A A之间的之间的关系是确定的，关系是确定的，aAaA和和a a A A二者必有一个成立。二者必有一个成立。5三大基本原理三大基本原理:1.1.外延公理外延公理:两个集合和相等的充要条件是他两个集合和相等的充要条件是他们有相同的元素。们有相同的元素。(互异性和无序性互异性和无序性)2.2.概括公理概括公理:纯粹性纯粹性凡该集合中的元素都具有某种性质凡该集合中的元素都具有某种性质.完备性完备性凡具有某种性质的元素都在该集合中凡具有某种性质的元素都在该集合中.63.3.正则公理正则公理:不存在集合不存在集合A,B,C,A,B,C,使得使得 C C B B A.(-
6、A.(-消除了悖论消除了悖论)悖论：悖论：所谓悖论是指：一个命题所谓悖论是指：一个命题Q Q，如果从，如果从Q Q为真，可为真，可以推导出以推导出Q Q为假；又从为假；又从Q Q为非真推导出为非真推导出Q Q为真，命题为真，命题Q Q是一个悖论。是一个悖论。7 “我正在说谎我正在说谎.”问问:这个人是在说谎还是在讲真话这个人是在说谎还是在讲真话?解解 如果他在说谎，这表明他的断言如果他在说谎，这表明他的断言“我正在说谎我正在说谎”是谎话，也就是说他在讲真话。即他说谎，推是谎话，也就是说他在讲真话。即他说谎，推出他是讲真话（即没有说谎）。出他是讲真话（即没有说谎）。另一方面，如果他讲真话，这表明
7、他的断言另一方面，如果他讲真话，这表明他的断言“我正我正在说谎在说谎”是真话，也就是说他正说谎话，即他讲是真话，也就是说他正说谎话，即他讲真话，推出他在说谎（即没有讲真话）。真话，推出他在说谎（即没有讲真话）。81）罗素将集合分成两素将集合分成两类：一：一类是集合是集合A本身是本身是A的的一个元素，即一个元素，即A A；另一；另一类是集合是集合A本身不是本身不是A的一个元素，即的一个元素，即A A；2）构造一个集合）构造一个集合S：S=A|A A，即，即，S是由是由满足条件足条件A A的那些的那些A组成的一个新的集合。成的一个新的集合。问：S是不是它自己的一个元素是不是它自己的一个元素?即即S
8、 S,还是是S S？9解解 我们作如下分析：我们作如下分析：如果如果S S S,S,因为集合因为集合S S由所有满足条件由所有满足条件A A A A的的集合组成集合组成,由于由于S S S,S,所以所以S S满足对于集合满足对于集合S S中元中元素的定义，即素的定义，即S S是集合是集合S S的元素，也就是说的元素，也就是说 S S S S。如果如果S S S,S,因为因为S S中任一元素中任一元素A A都有都有A A A,A,又又由于由于S S S,S,根据集合根据集合S S的规定，知的规定，知S S不是集合不是集合S S的元的元素素,也就是说也就是说S S S S。既不是既不是S S S
9、S，也不是，也不是S S S S。10罗素悖论的出现罗素悖论的出现,说明朴素集合论有问题说明朴素集合论有问题,从从而使数学的基础发生了动摇（第而使数学的基础发生了动摇（第3 3次数学危次数学危机）机）,引起了一些著名数学家的极大重视。引起了一些著名数学家的极大重视。经过长期的努力，作出如下经过长期的努力，作出如下约定约定：先有成员才形成集合，一个正在形成的集合先有成员才形成集合，一个正在形成的集合不能作为一个实体充当本集合的成员，否则不能作为一个实体充当本集合的成员，否则在概念上将产生循环，从而导致悖论。这正在概念上将产生循环，从而导致悖论。这正是正则公理的内容，从而消除悖论。是正则公理的内容
10、，从而消除悖论。111.1.列举法：所谓列举法就是将集合中的元素列举法：所谓列举法就是将集合中的元素用一对花括号括起来，这个集合可以是有限用一对花括号括起来，这个集合可以是有限集，也可以是无限集。集，也可以是无限集。例例1.4 1.4（1 1）A A=1=1，2 2，3 3，44（2 2）B B=a a，b b，c c，d d，x x，y y，z z（3 3）C C 桌子，椅子桌子，椅子（4 4）N N=0=0，2 2，4 4，6 6，8 8，1010，122.2.描述法：描述集合的方法是通过刻画集合中描述法：描述集合的方法是通过刻画集合中元素所具备的某种特性来表示集合。我们通元素所具备的某种
11、特性来表示集合。我们通常用符号常用符号P(x)P(x)来表示不同对象来表示不同对象x x所具有的性质所具有的性质P P，由，由P(x)P(x)所定义的集合常记为：所定义的集合常记为：x|x|P(x)P(x)例例1.51.5（1 1）A A=x x 00 xx2 2，x xR R （2 2）B B=x x x x2 2-1=0-1=0，x xR R （3 3）C C=(=(x x，y y)x x2 2+y y2 244，x x，y yR R （4 4）D D=x x x x是动物是动物 说明：描述法中说明：描述法中A A=x x 00 x x 22与与A A=y y 0 0 y y 22是表示同
12、一个集合。是表示同一个集合。133.3.文氏图文氏图用平面上封闭曲线包围点集的图形来表示集合用平面上封闭曲线包围点集的图形来表示集合（见图（见图1.11.1）。文氏图可以形象和直观地描述集）。文氏图可以形象和直观地描述集合之间的关系和集合之间的有关运算。合之间的关系和集合之间的有关运算。A图1.1 集合A144.Backus Naur Form(BNF)4.Backus Naur Form(BNF)常用于定义高级程序设计语言的语法集合。常用于定义高级程序设计语言的语法集合。例例1.61.6 在在PASCALPASCAL语言中，标识符集合定义如语言中，标识符集合定义如下：下：LetterLett
13、er:=:=LetterLetter LetterLetter or or DigitDigit LetterLetter or or Digit Digit:=:=LetterLetter|DigitDigit155.5.递规定义递规定义给定基础元素，通过计算规则定义集合的其他元素。给定基础元素，通过计算规则定义集合的其他元素。a a0 0=1=1，a a1 1=1=1，a ai+1i+1=2=2a ai i+a+ai i-1-1(i i1)1)，于是：于是：S S=a a0 0，a a1 1，a an n=a a k k|k k00 161.2.11.2.1包含包含关系关系定义定义1.11
14、.1 包含包含设设A A和和B B是两个集合是两个集合,若若A A中的每一个元素都是中的每一个元素都是B B的元的元素素,则称则称A A是是B B的的子集子集,记作记作A A B B或或B B A.A.若若A A B B且且A A B,B,则称则称A A是是B B的的真子集真子集,记作记作A A B.BB.B称为称为A A的的超集超集.此外，若存在元素此外，若存在元素a a A,A,但但a a B,B,则则A A不是不是B B的子的子集集.17例例1.8 1.8 N N I I Q Q R R与与N N I I Q Q R R同时成立。同时成立。例例1.9 1.9 11 1,21,2与与 1
15、1 1,21,2同同时成立。时成立。例例1.10 N1.10 N N N成立成立,但是但是 N N N N不成立。即一个不成立。即一个集合可以是自身的子集集合可以是自身的子集,但不可以是自身的但不可以是自身的真子集。真子集。18自反性自反性：A A A A反对称性反对称性：若：若A A B B且且B B A A，则，则A A=B B 传递性传递性：若：若A A B B且且B B C C，则，则A A C C19定义定义1.21.2 集合集合A A和和B B的元素全相同，则称的元素全相同，则称A A和和B B相等相等，A=BA=B；否则称；否则称A A和和B B不相等，不相等，A A B B。由
16、集合包含关系的定义，我们可以给出集合由集合包含关系的定义，我们可以给出集合相等关系的另一种定义形式：相等关系的另一种定义形式：定义定义1.31.3 设设A A和和B B是两个集合，如果是两个集合，如果A A B B且且B B A,A,则称则称A=B.A=B.20例例1.11 1.11 集合集合A=2,3A=2,3，B=B=x x|x x2 2-5-5x x+6=0+6=0，则有集合。则有集合。例例1.121.12集合集合A=A=，B=x|xB=x|x2 2+x+1=0,xR+x+1=0,xR，则有集合则有集合A=BA=B。21定理定理1.1 1.1 设设A A和和B B是两个集合，是两个集合，
17、A=BA=B的充的充要条件是：要条件是：A A B B且且B B A A，即两个，即两个集合相等的充要条件是它们互为子集。集合相等的充要条件是它们互为子集。22证明：证明：必要性必要性 A=BA=B A A B B并且并且B B A A。因为因为A=BA=B，由定义，由定义A A中的每个元素是在中的每个元素是在B B中，所以中，所以A A B B，同理，同理B B中的每个元素是在中的每个元素是在A A中，所以中，所以B B A A。充分性充分性 A A B B并且并且B B A A A=BA=B。反证法。如果反证法。如果A A B B，则，则A A中至少有一个元素不在中至少有一个元素不在B B
18、中，与中，与A A B B矛盾；或者矛盾；或者B B中至少有一个元素不在中至少有一个元素不在A A中，中，与与B B A A矛盾。所以矛盾。所以A A B B不可能成立。所以不可能成立。所以A=BA=B。23自反性自反性:A:A=A=A对称性对称性:若若A A=B,=B,则则B=AB=A传递性传递性:若若A A=B=B且且B=C,B=C,则则A A=C=C24定义定义1.41.4 集合集合A A中所包含的不同元素的个数，称为中所包含的不同元素的个数，称为集合集合A A的的基数基数，通常用，通常用|A A|或或Card Card(A)(A)表示。表示。例例1.13 1.13 计算下列集合的基数。
19、计算下列集合的基数。(1)(1)集合集合A=0,1,2A=0,1,2。(2)(2)空集空集。(3)(3)集合集合B=x|xB=x|x2 2-2x+1=0-2x+1=0。(4)(4)自然数集自然数集 N N。(5)(5)集合集合C=(x,y)|xC=(x,y)|x2 2+y+y2 244。(6)(6)集合集合D=D=,1,2,1,2,1,2,1,2。25定义定义1.51.5 设设A A是集合，如果是集合，如果A A中有有限个不同的元素，中有有限个不同的元素，则称则称A A为为有限集有限集，否则称，否则称A A为为无限集无限集。对有限集。对有限集A A，如果含有如果含有n n个不同的元素，简称个不
20、同的元素，简称A A为为n n元集元集，它的基，它的基数为数为m m（0 0 m m n n）的子集称为它的）的子集称为它的m m元子集元子集。26例例1.14 1.14 设集合设集合A A=a a,b b,c c，写出它的全部子集。，写出它的全部子集。解解 0 0元子集，有元子集，有C C3 30 01 1个：个：；1 1元子集，有元子集，有C C3 31 1 3 3个：个：a a,b b,c,c；2 2元子集，有元子集，有C C3 32 2 3 3个：个：a a,b b,a a,c c,b b,c c；3 3元子集，有元子集，有C C3 33 31 1个：个：a a,b b,c c。共有共
21、有C C3 30 0C C3 31 1C C3 32 2C C3 33 3 8 8个子集。个子集。27例例1.15 1.15 设集合设集合A=a,b,c,A=a,b,c,写出它的全部子写出它的全部子集。集。例例1.16 1.16 设集合设集合A=A=,a,b,c,a,b,c,写出它写出它的全部子集。的全部子集。28一般地，对于一般地，对于n n元子集，它的元子集，它的m m（0 0 m m n n）元）元子集有个，所以集合子集有个，所以集合A A的不同子集总数有的不同子集总数有C Cn n0 0C Cn n1 1 C Cn nn n 2 2n n个。个。定义定义1.61.6 对于每个非空集合对
22、于每个非空集合S S，至少有两个不，至少有两个不同的子集同的子集 和和S S，称，称和和S S是是S S的的平凡子集平凡子集。29定义定义1.71.7 不包含任何元素的集合称为不包含任何元素的集合称为空集空集，用符号，用符号 或或表示。表示。定理定理1.21.2 是一切集合的子集是一切集合的子集.证明证明 反证法。反证法。设存在某一集合设存在某一集合A A，使得，使得不是集合不是集合A A的子集，则存在的子集，则存在x x 且且x x A A。这与。这与的定义相矛盾。因此定理成立。的定义相矛盾。因此定理成立。定理定理1.31.3空集是唯一的空集是唯一的.证明证明 假设有假设有2 2个空集个空集
23、1 1和和2 2，由定理，由定理1.21.2得出得出1 1 2 2 ，且，且2 2 1 1 。再由集合相等的定义有。再由集合相等的定义有1 1=2 2 。故空集是唯一的。故空集是唯一的。例例1.17 1.17：A=xA=x x x2 2+x+2=0,x+x+2=0,x RR，这是空集。，这是空集。30定义定义1.81.8在一定范围内，如果所有集合均为某一集合在一定范围内，如果所有集合均为某一集合的子集，则称该集合为的子集，则称该集合为全集全集。记作。记作U U。例如全体自然数组成了全集。例如全体自然数组成了全集。全集的概念是相对的。不同的问题有不同的全集，全集的概念是相对的。不同的问题有不同的
24、全集，即使同一问题也可以取不同的全集，全集的选取要即使同一问题也可以取不同的全集，全集的选取要看具体研究的问题。如要研究看具体研究的问题。如要研究20072007年全国毕业大学年全国毕业大学生的就业情况，则将生的就业情况，则将20072007年毕业的所有的大学生全年毕业的所有的大学生全体作为全集；若只研究上海市体作为全集；若只研究上海市20072007年毕业的大学生年毕业的大学生就业情况时，只需将就业情况时，只需将20072007年上海市毕业的大学生全年上海市毕业的大学生全体作为全集。体作为全集。31定义定义1.9 1.9 设设 A A、B B 是两个集合是两个集合,由集合由集合 A A 和和
25、B B 中所有的元素组成的集合称为集合中所有的元素组成的集合称为集合A A 与与B B 的并集的并集,记作记作AB,AB,读作读作“A A 并并B”B”。即。即AB AB 是由属于是由属于A A或属于或属于B B的元素所组成的元素所组成,用符号表用符号表示为示为 AB=x|xA AB=x|xA 或或xBxB32例例1.18 1.18 设集合设集合A=1,2,3,A=1,2,3,集合集合B=a,bB=a,b，则，则ABAB1,2,3,a,b1,2,3,a,b。例例1.191.19设集合设集合A=1,2,3,A=1,2,3,集合集合B=a,b,1,2B=a,b,1,2，则，则ABAB1,2,3,a
26、,b1,2,3,a,b。例例1.20 1.20 设集合设集合A=1,2,3,A=1,2,3,集合集合B=x|xB=x|x2 2+x+2=0,+x+2=0,xR,xR,则则AB=1,2,3AB=1,2,3。33定义定义1.101.10 设设A A、B B是两个集合，由集合是两个集合，由集合A A和和B B中中公共元素组成的集合称为集合公共元素组成的集合称为集合A A与与B B的的交集交集，记作记作ABAB，即，即ABAB是由既属于是由既属于A A又属于又属于B B的元的元素组成，用符号表示为：素组成，用符号表示为：ABABx|xAx|xA且且xB xB 34例例1.21 1.21 设集合设集合A
27、=1,2,3,A=1,2,3,集合集合B=a,bB=a,b，则，则ABAB。例例1.221.22设集合设集合A=1,2,3,A=1,2,3,集合集合B=a,b,1,2B=a,b,1,2，则则ABAB1,21,2。例例1.23 1.23 设集合设集合A=1,2,3,A=1,2,3,集合集合B=x|xB=x|x2 2+x+2=0,xR,+x+2=0,xR,则则AB=AB=。35两个集合的并和交运算可以推广成两个集合的并和交运算可以推广成n n个集合的个集合的并和交，我们用公式表示如下：并和交，我们用公式表示如下：36定义定义1.111.11 设设A A、B B是两个集合，由在集合是两个集合，由在集
28、合A A中中且不在集合且不在集合B B中的所有元素组成的集合，称中的所有元素组成的集合，称为集合为集合B B对对A A的的相对补集相对补集，记作，记作A-BA-B，用符号，用符号表示为：表示为：A AB Bx|xAx|xA且且x x B B 37例例1.24 1.24 设集合设集合A=1,2,3,A=1,2,3,集合集合B=a,bB=a,b，则，则A-BA-B1,2,31,2,3。例例1.251.25设集合设集合A=1,2,3,A=1,2,3,集合集合B=a,b,1,2B=a,b,1,2，则则A-BA-B33。例例1.26 1.26 设集合设集合A=1,2,3,A=1,2,3,集合集合B=x|
29、xB=x|x2 2+x+2=0,xR,+x+2=0,xR,则则A-B=AA-B=A。38定义定义1.121.12 集合的绝对补，是对于全集而言的，设集合的绝对补，是对于全集而言的，设U U为全集，则集合为全集，则集合A A的绝对补集是由不在集合的绝对补集是由不在集合A A中的所中的所有的元素构成的集合，称为有的元素构成的集合，称为A A的的绝对补集绝对补集，记作或，记作或A A 表示，绝对补集也简称为表示，绝对补集也简称为补集补集，用符号表示为：，用符号表示为：A A=U-A=x|x=U-A=x|x U U且且 x x A A 例例1.271.27设集合设集合U=1,2,3,U=1,2,3,求
30、下列集合的补集。求下列集合的补集。（1 1）集合）集合A=1,2A=1,2 。（2 2）集合）集合A A 。39定义定义1.131.13 集合集合A A和和B B的的对称差对称差定义如下式所示：定义如下式所示：A A B=B=（A-B)(B-A)A-B)(B-A)或用符号表示为：或用符号表示为：A A B=x|xB=x|x A A且且x x B,B,或或x x B B且且x x AA例例1.281.28设集合设集合A=1,2,3,A=1,2,3,集合集合B=a,b,1,2B=a,b,1,2，则，则A A B=(A-B)(B-A)=3aB=(A-B)(B-A)=3a，b=ab=a，b b，334
31、0（1 1）双重否定律）双重否定律 (A(A)=A=A（2 2）交换律）交换律 AB=BA AB=BA AAB=BA AB=BA A B=BB=B A A（3 3）结合律）结合律 A(BC)=(AB)CA(BC)=(AB)C A(BC)=(AB)C A(BC)=(AB)C A A(B(B C)=(AC)=(A B)B)C C（4 4）分配律）分配律 A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(B A(BC)C)(A-B)(A-C)(A-B)(A-C)(AB)(AB)(AC)(AC)A(BA(BC)C)41（5 5）同一律）
32、同一律 AA=A AU=A=A AU=A A A=A A=A A=A=A（6 6）互补律）互补律 AAAA=U =U （7 7）矛盾律）矛盾律 AAAA=（8 8）幂等律）幂等律 AA=A AA=AAA=A AA=A（9 9）零一律）零一律 AU=U AAU=U A=A AA=A=A A A=A=（1010）吸收律）吸收律 A(AB)=A A(AB)=A A(AB)=A A(AB)=A42（1111）德摩根律）德摩根律 =U U=U U=(AB)(AB)=A=A BB (AB)(AB)=A=A B B A A(BC)=(A(BC)=(AB)(AB)(AC)C)A A(BC)=(A(BC)=(A
33、B)(AB)(AC)C)（1212）功能完备律）功能完备律 A AB=ABB=AB A A B=(AB)B=(AB)(AB)(AB)=(A =(AB)(BB)(BA)A)=(AB =(AB)(A)(A B)B)43有有了了集集合合的的运运算算定定律律，结结合合前前面面介介绍绍的的集集合合的的基基数数的的概概念念，可可以以求求出出任任意意一一个个有有限限集集合合中中元元素素的的个个数数，计计算算出出有有限限集集合合中中元元素素的的个个数数通通常常有有两两种种方方法法：文文氏氏图图法法和和排排斥斥原原理理。下下面面分分别别来来介介绍绍这这两两种种方方法法：文文氏氏图图法法与与排排斥原理法。斥原理法
34、。441.1.文氏图法文氏图法：每一条性质定义为一个集合，：每一条性质定义为一个集合，用一个圆来表示，如无特殊说明，任何两个用一个圆来表示，如无特殊说明，任何两个圆画成相交的，然后将已知集合的元素填入圆画成相交的，然后将已知集合的元素填入表示该集合的区域内。通常从表示该集合的区域内。通常从n n个集合的交个集合的交集填起，根据计算的结果逐步将数字填入其集填起，根据计算的结果逐步将数字填入其它各空白区域。如果交集的值是未知的，可它各空白区域。如果交集的值是未知的，可以设为以设为x x，根据题目的条件列出方程或方程，根据题目的条件列出方程或方程组，求出所需结果。组，求出所需结果。45例例1.29
35、1.29 对对2424名会外语的科技人员进行掌握外名会外语的科技人员进行掌握外语情况的调查。其统计结果如下：会英、日、语情况的调查。其统计结果如下：会英、日、德和法语的人分别为德和法语的人分别为1313，5 5，1010和和9 9人，其中人，其中同时会英语和日语的有同时会英语和日语的有2 2人，会英、德和法人，会英、德和法语中任两种语言的都是语中任两种语言的都是4 4人。已知会日语的人。已知会日语的人既不懂法语也不懂德语，分别求只会一种人既不懂法语也不懂德语，分别求只会一种语言语言(英、德、法、日英、德、法、日)的人数和会三种语言的人数和会三种语言的人数。的人数。46设设U U为全集为全集,A
36、,A1 1，A A2 2，A An n为为U U的有限子集的有限子集,则有如下则有如下3 3个公式。个公式。(1)(1)两个集合的排斥原理公式：两个集合的排斥原理公式：|A A1 1 A A2 2|=|=|A A1 1|+|+|A A2 2|-|-|A A1 1 A A2 2|(2)(2)三个集合的排斥原理公式：三个集合的排斥原理公式：|A A1 1A A2 2A A3 3|=|=|A A1 1|+|+|A A2 2|+|+|A A3 3|-|-|A A1 1A A2 2|-|-|A A1 1A A3 3|-|-|A A2 2A A3 3|+|+|A A1 1A A2 2A A3 3|(3)(
37、3)个集合的排斥原理公式个集合的排斥原理公式 4748例1.30 在20名青年有10名是公司职员，12名是学生，其中5名既是职员又是学生，问有几名既不是职员，又不是学生。49例1.30 在20名青年有10名是公司职员，12名是学生，其中5名既是职员又是学生，问有几名既不是职员，又不是学生。解 设集合A是职员集合，集合B是学生集合，根据题意有：A=10，B =12，AB=5AB=A+B-AB=10+12-5=17则(AB)=E-AB=20-17=3因此，有3名既不是职员又不是学生。50例1.31 某班有学生60人,其中38人学习pascal语言,有16人学习C语言,有21人学习Fortran语言
38、,有3人这三种语言都学习,有4人这三种语言都不学习,问仅学习两门语言的学生数是多少?51解解 设设A A是学习是学习pascalpascal语言的学生集合，语言的学生集合，B B是学习是学习C C语言的学生语言的学生集合，集合，C C是学习是学习FortranFortran语言的学生集合，根据题意有：语言的学生集合，根据题意有：|A|=38|A|=38，|B|=16|B|=16，|C|=21|C|=21，|ABC|=3|ABC|=3，|ABC|+4=60|ABC|+4=60，即即|ABC|=56|ABC|=56因为因为|ABC|=|A|+|B|+|C|-|AB|-|AC|-|ABC|=|A|+
39、|B|+|C|-|AB|-|AC|-|BC|+|ABC|BC|+|ABC|故故|AB|+|AC|+|BC|=38+16+21+3-56=22|AB|+|AC|+|BC|=38+16+21+3-56=22所求仅学生两门语言的学生人数应为所求仅学生两门语言的学生人数应为|(ABC|(ABC)(AB)(ABC)(AC)(ABC)|=|AB|+|AC|BC)|=|AB|+|AC|+|BC|-3|ABC|+|BC|-3|ABC|=22-3 =22-3 3 3 =13 =13即仅学习两门语言的学生数为即仅学习两门语言的学生数为1313人。人。52例例1.32 1.32 某市举行中学生数学、物理、化学某市举
40、行中学生数学、物理、化学三科竞赛，共有三科竞赛，共有100100人参加竞赛，结果数学人参加竞赛，结果数学优秀者为优秀者为4141人，物理优秀者为人，物理优秀者为4646人，化学优人，化学优秀者为秀者为3939人，三门课全优者为人，三门课全优者为8 8人，仅两门人，仅两门课为优者课为优者2626人，问没有得到优秀的人数是多人，问没有得到优秀的人数是多少？少？53解解 设设A A表示数学优秀者的集合，表示数学优秀者的集合，B B表示物理优秀者的集合，表示物理优秀者的集合，C C表表示化学优秀者的集合。由题意可得：示化学优秀者的集合。由题意可得：|A|=41|A|=41，|B|=46|B|=46，|
41、C|=39|C|=39，|ABC|=8|ABC|=8仅两门课为优秀的人数为：仅两门课为优秀的人数为：|(ABC|(ABC)(AB)(ABC)(AC)(ABC)|=|AB|+|AC BC)|=|AB|+|AC|+|BC|-3|ABC|+|BC|-3|ABC|即即 26=|AB|+|AC|+|BC|-3*826=|AB|+|AC|+|BC|-3*8因此因此|AB|+|AC|+|BC|=50|AB|+|AC|+|BC|=50因此一门课为优秀的人数为：因此一门课为优秀的人数为：|ABC|=|A|+|B|+|C|-|AB|-|AC|-|BC|ABC|=|A|+|B|+|C|-|AB|-|AC|-|BC|
42、+|ABC|+|ABC|=41+46+39-50+8 =41+46+39-50+8 =84 =84因此没有得到的优秀的人数为因此没有得到的优秀的人数为100-84=16100-84=16（人）（人）54解解:因为因为11112 2=121,=121,不超过不超过120120的合数的合数(除了除了1 1和它自身还能被其他数整除的和它自身还能被其他数整除的数数)至少有至少有2,3,52,3,5或或7 7这几个素因子之一这几个素因子之一,首先考虑不能被首先考虑不能被2,3,5,72,3,5,7整除的整除的整数整数,设设 S=x|xZ,1x120 S=x|xZ,1x120 A A1 1=x|xS,x=
43、x|xS,x是是2 2的倍数的倍数 A A2 2=x|xS,x=x|xS,x是是3 3的倍数的倍数 A A3 3=x|xS,x=x|xS,x是是5 5的倍数的倍数 A A4 4=x|xS,x=x|xS,x是是7 7的倍数的倍数 则上述集合的基数分别为则上述集合的基数分别为|S|=120,|A|S|=120,|A1 1|=60,|A|=60,|A2 2|=40,|A|=40,|A3 3|=24,|A|=24,|A4 4|=17|A|=17|A1 1AA2 2|=20,|A|=20,|A1 1AA3 3|=12,|=12,|A|A1 1 A A4 4|=8,|A|=8,|A2 2AA3 3|=8,
44、|A|=8,|A2 2AA4 4|=5,|A|=5,|A3 3AA4 4|=3|=3|A|A1 1AA2 2AA3 3|=4,|A|=4,|A1 1AA2 2AA4 4|=2,|A|=2,|A1 1AA3 3AA4 4|=1,|A|=1,|A2 2AA3 3AA4 4|=1,|=1,|A|A1 1AA2 2AA3 3AA4 4|=0|=0 根据包含排斥原理根据包含排斥原理,不能被不能被2,3,5,72,3,5,7整除的整数有整除的整数有|A|A1 1AA2 2AA3 3AA4 4|=120-(60+40+24+17)+(20+12+8+8+5+3)-|=120-(60+40+24+17)+(2
45、0+12+8+8+5+3)-(4+2+1+1)+0=27(4+2+1+1)+0=27 因为因为2 2、3 3、5 5、7 7不满足上述条件不满足上述条件,但是它们都是素数。另外但是它们都是素数。另外,1,1满足上述条满足上述条件件,但是但是1 1不不 是素数是素数,因此因此,不超过不超过120120的素数有的素数有27+4-1=3027+4-1=30个。个。551.4.1 1.4.1 幂集幂集定义定义1.141.14 给定集合给定集合A A，由集合，由集合A A的所有子集的所有子集为元素组成的集合，称为集合为元素组成的集合，称为集合A A的的幂集幂集，记为记为P(A)P(A)或或2 2A A，
46、即，即P(A)=2P(A)=2A A=X|X=X|X AA。56例例1.34 1.34 设集合设集合 A A aa，b b，cc，则，则P(A)P(A)，aa，bb，cc，aa，bb，a a，c c，bb，cc，aa，b b，c c 例例1.351.35计算下列集合的幂集。计算下列集合的幂集。(1)A=(1)A=。(2)B=P(2)B=P()。(3)C=(3)C=,P(,P()。57定理定理1.41.4 如果有限集合如果有限集合A A中有中有n n个元素，则其个元素，则其幂集幂集P(A)P(A)有有2 2n n个元素。个元素。证明证明 由由A A的的k k个元素组成的子集的个数为个元素组成的子
47、集的个数为C Cn nk k，当当k k从从0 0取到取到n n时就构成了集合时就构成了集合A A的所有的子集，的所有的子集，因此集合因此集合A A的子集的个数为：的子集的个数为：C Cn n0 0+C+Cn n1 1+C+Cn nn n=2 2n n 因此因此P(A)P(A)的元素个数是的元素个数是2 2n n 。58（1 1）当）当A A B B当且仅当当且仅当P(A)P(A)P(B)P(B)（2 2）P(A)P(B)P(A)P(B)P(A B)P(A B)（3 3）P(AB)=P(A)P(B)P(AB)=P(A)P(B)（4 4）P(AP(A)(P(A)(P(A)59证明证明:(1):(
48、1)必要性必要性:对对 x x P(A)P(A)x x A A x x B B x x P(B)P(B)因此因此P(A)P(A)P(B)P(B)充分性充分性:对对 x x A A x x P(A)P(A)x x P(B)P(B)x x B B 因此因此A A B B60(2)(2)对对 x x P(A)P(B)P(A)P(B)x x P(A)P(A)x x P(B)P(B)x x A A x x B B x x A B A B x x P(A B)P(A B)P(A)P(B)P(A)P(B)P(A P(A B)B)例:P(A)P(B)P(AB)A=1,B=2,AB=1,2P(A)P(B)=,1
49、,2P(AB)=,1,2,1,261(3)(3)对对 x x P(AP(AB)B)x x A A且且x x B B x x P(A)P(A)且且x x P(B)P(B)x x P(A)P(A)P(P(B)B)(4)(4)显然成立，不用证明。显然成立，不用证明。62现在引进一种编码，用来唯一地表示有限集幂集的元现在引进一种编码，用来唯一地表示有限集幂集的元素。设集合素。设集合A A中有中有n n个元素，确定下标为个元素，确定下标为n n位的二进制位的二进制数，每一位对应集合数，每一位对应集合A A中的一个元素。如果元素在某中的一个元素。如果元素在某个子集中出现，则相应的二进制位为个子集中出现，则
50、相应的二进制位为1 1，否则为，否则为0 0。以集合以集合A=a,b,cA=a,b,c为例：为例：是二进制数且 将P（A）中的各个元素详细描述如下：=A000，a=A100，b=A010，c=A001，a,b=A110，a,c=A101，b,c=A011，a,b,c=A11163设设Ai1i2in是集合是集合A A的子集，的子集，i1i2in是是Ai1i2in的的 二进制编码表示，则二进制编码表示，则 Ai1i2in 补集的二进制补集的二进制编码表示只需将每个编码表示只需将每个1 1换成换成0 0，0 0换成换成1 1即可。即可。如如A A001001的补集为的补集为A A110110。64两
