(精品)第2-1章 集合及其运算.ppt

《(精品)第2-1章 集合及其运算.ppt》由会员分享，可在线阅读，更多相关《(精品)第2-1章 集合及其运算.ppt（96页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2篇集合与关系篇集合与关系第第2-1章章集合及其运算集合及其运算第第2-2章章二元关系二元关系第第2-3章章函数函数第第2-1章章集合及其运算集合及其运算2-1-1集合的概念集合的概念及其表示及其表示2-1-2集合的基本运算集合的基本运算2-1-3集合中元素的计数集合中元素的计数2-1-1集合的概念及其表示集合的概念及其表示一集合的概念一集合的概念一些事物汇集到一起组成一个整体就叫一些事物汇集到一起组成一个整体就叫集合集合，而这些事物就是这个集合的而这些事物就是这个集合的元素元素或或成员成员。例如：例如：方程方程x210的实数解集合；的实数解集合；26个英文字母的集合；个英文字母的集合；坐

2、标平面上所有点的集合；坐标平面上所有点的集合；集合通常用大写英文字母来表示，集合通常用大写英文字母来表示，元素用小写字母表示元素用小写字母表示实数集合实数集合R，复数集合复数集合C等。等。自然数集合自然数集合N，整数集合整数集合Z，有理数集合有理数集合Q，集合的表示方法有两种：列举法和谓词法。集合的表示方法有两种：列举法和谓词法。例如例如:A=a，b，c，zZ=0，1，2，列举法列举法（穷举法）（穷举法）x|xRx210谓词法谓词法(叙述法叙述法)描述集合中元素的属性描述集合中元素的属性x|P(x)使使P(x)成立的所有元素的集合成立的所有元素的集合例如：方程例如：方程x210的实数解。的实数

3、解。集合的元素是彼此不同的（无重复性）集合的元素是彼此不同的（无重复性）集合的元素是无序的。集合的元素是无序的。1，2，33，1，21，1，2，2，31，2，3|A|表示表示A中元素个数中元素个数树形图来表示隶属关系，树形图来表示隶属关系，该图分层构成，每个层该图分层构成，每个层上的结点都表示一个集上的结点都表示一个集合，它的儿子就是它的合，它的儿子就是它的元素。元素。元素和集合之间的关系元素和集合之间的关系隶属关系隶属关系属于属于或或不属于不属于，属于记作，属于记作，不属于记作，不属于记作 例如例如:Aa，b，c，d，daA，b，cA，dA，dA，b A，d A规定：对任何集合规定：对任何集

4、合A都有都有A A。规定集合的元素都是集合。规定集合的元素都是集合。定义定义1.2包含关系包含关系设设A，B为集合，如果为集合，如果A中的每个元素都是中的每个元素都是B中中的元素，则称的元素，则称A是是B的子集合，或的子集合，或A包含于包含于B，或或B包含包含A，记作记作AB，或，或BA。如果如果A不被不被B包含，则记作包含，则记作AB。例如例如NZQRC，但，但ZN。对任何集合对任何集合A都有都有AA。AB x(x(xAxB)集合集合间的包含的包含关关系系“”的性的性质1、自反性、自反性2、传递性、传递性(AB)(BC)(AC)二集合之间的关系二集合之间的关系定义定义1.1相等关系相等关系当

5、且仅当两个集合所有元素都相同，记做当且仅当两个集合所有元素都相同，记做A=B；不相等记做不相等记做AB例如：例如：1，2，4=1，4，2=1，2，2，41，2，41，2，4A=B(AB)(BA)由包含关系，可见由包含关系，可见定理定理1.1外延性原理外延性原理证明集合相等的方法：互为子集证明集合相等的方法：互为子集定义定义1.3真包含真包含设设A，B为集合，如果为集合，如果A中每个元素都属于中每个元素都属于B，而，而B中至少有一个元素不属于中至少有一个元素不属于A，则称则称A是是B的真子集。的真子集。记作记作A B。A B x(x(xAxB)x(x(xB x A)A B(AB)(AB)例如例如

6、NZQRC，但，但NN。三特殊的集合三特殊的集合定义定义1.4空集空集不含任何元素的集合叫做不含任何元素的集合叫做空集空集，记作，记作。例如：方程例如：方程x2+10的实根的集合。的实根的集合。定理定理1.2对任一集合对任一集合A，定义定义1.5全集全集在一定范围内，如果所有集合均为某一集合的在一定范围内，如果所有集合均为某一集合的子集，则称该集合为子集，则称该集合为全集全集，记做，记做E。定义定义1.6幂集幂集给定集合给定集合A，由集合由集合A的所有子集为元素组成的所有子集为元素组成的集合，称为集合的集合，称为集合A的的幂集幂集，记做，记做P(A)(或或2A)。P(A)=X|XAA例例1.5

7、A=0，1，2，求，求P(A)定理定理1.3设设A=a1，a2，an，则，则|P(A)|=2n四集合的数码表示四集合的数码表示计算机中表示集合计算机中表示集合及其幂集（数码表示法）及其幂集（数码表示法）设集合设集合A2=x1，x2对集合中元素标定次序，对集合中元素标定次序，x1是第一个元素，是第一个元素，x2是第二个元素是第二个元素P(A2)=，x1，x2，x1，x2S00S10S01S11P(A2)=Si|i J,J=00,01,10,11将将J中二进制转成十进制数中二进制转成十进制数J=0,1,2,3P(A2)=Si|i J,J=i|i 是两位二进制数且是两位二进制数且i=0,1,2,3扩

8、展到扩展到n个元素情况个元素情况P(An)=Si|i J,J=i|i是是n位二进制数位二进制数 且且 0i2n-1例例：A6=x1，x2，x3，x4，x5，x6写出写出S7和和S12代表的两个子集代表的两个子集7=00011112=001100S7=x4，x5，x6S12=x3，x42-1-2集合的基本运算集合的基本运算（5种）种）并并、交、交、相对补、相对补、绝对补、绝对补、对称差、对称差 一、并运算一、并运算定义定义2.1设设A、B是任意两个集合，所有属于是任意两个集合，所有属于A或者或者属于属于B的元素组成的集合，称为的元素组成的集合，称为A与与B的并集的并集。记做记做 A AB BAB

9、=x|(xA)(xB)例例2.2设设AB，CD D，则则 AC BD二、交运算二、交运算定义定义2.2设设A、B是任意两个集合，由是任意两个集合，由A和和B的公共的公共元素组成的集合，称为元素组成的集合，称为A与与B的交集的交集。记做记做 A AB BAB=x|(xA)(xB)例例2.5设设A是能被是能被5整除的整数集合，整除的整数集合，B是能被是能被8整整除的整数集合。除的整数集合。AB是能被是能被40整除的整数集合。整除的整数集合。定理定理2.1设设A、B、C为任意三个集合，则为任意三个集合，则(1)幂等律幂等律AA=AAA=A(2)交换律交换律AB=BAAB=BA(3)结合律结合律(AB

10、)C=A(BC)(4)同一律同一律A=AAE=A(5)零律零律AE E=EA=(6)AAB，BAB(AB)C=A(BC)(7)AB=BAB(6)ABA，ABB(7)AB=AAB三、交运算和并运算之间的联系三、交运算和并运算之间的联系定理定理2.3分配律分配律(1)交运算对并运算的分配律交运算对并运算的分配律(2)并运算对交运算的分配律并运算对交运算的分配律A(B C)=(AB)(AC)A(BC)=(A B)(A C)定理定理2.4吸收律吸收律(1)A(A B)=A(2)A(AB)=A四、集合的补运算四、集合的补运算定义定义2.3设设A、B是任意两个集合，由属于是任意两个集合，由属于A而不而不属

11、于属于B的一切元素构成的集合，称为的一切元素构成的集合，称为A与与B的差运算的差运算（又称（又称B对对A补运算）。补运算）。记做记做 A-BA-BA-B=x|(xA)(x B)若若A=E，对任意集合对任意集合B关于关于E的补集的补集EB，称为称为B的绝对补集，的绝对补集，B例例6设设A=1，2，3，4，5，B=1，2，4，7AB=3，5例例7设设A是素数集合，是素数集合，B是奇数集合，是奇数集合，AB=2定理定理2.5设设A、B、C为任意三个集合，则为任意三个集合，则(9)若若AB，当且仅当当且仅当五、集合的对称差运算五、集合的对称差运算定义定义2.4设设A、B是任意两个集合，由是任意两个集合

12、，由“属于属于A而不而不属于属于B”或或“属于属于B而不属于而不属于A”的一切元素构成的的一切元素构成的集合，称为集合，称为A与与B的对称差。的对称差。记做记做A BA B=(AB)(BA)=x|(xA)(xB)A B=(A B)(AB)例例6设设A=1，2，3，4，5，B=1，2，4，5，7A B=3，7定理定理2.6设设A、B、C为任意三个集合，则为任意三个集合，则(1)A B=B A(2)A =A(3)A A=文氏图表示集合关系及运算文氏图表示集合关系及运算例例证明(AB)BAB证证:(AB)B(AB)B(AB)(BB)(AB)EAB化简(ABC)(AB)(A(BC)A)解：(ABC)(

13、AB)(A(BC)A)BA(AB)A2-1-3集合中元素的计数集合中元素的计数一、两个基本原理一、两个基本原理加法原理加法原理：若一个事件以：若一个事件以m种方式出现种方式出现(这些方式这些方式构成集合构成集合A)，另一个事件以另一个事件以n种事件出现种事件出现(这些方这些方式构成集合式构成集合B)，这两个事件完成一件即能达到目这两个事件完成一件即能达到目的，则达到目的的方式数为的，则达到目的的方式数为m+n。例例3.1假设从城市假设从城市A到城市到城市B有铁路两条，公路三有铁路两条，公路三条，航线一条，则从城市条，航线一条，则从城市A到城市到城市B有有条。条。乘法原理乘法原理：若一个事件以：

14、若一个事件以m种方式出现种方式出现(这些方式这些方式构成集合构成集合A)，另一个事件以另一个事件以n种事件出现种事件出现(这些方这些方式构成集合式构成集合B)，这两个事件同时完成才能达到目这两个事件同时完成才能达到目的，则达到目的的方式数为的，则达到目的的方式数为mn。例例3.2一位学生想从图书馆借一位学生想从图书馆借离散数学离散数学和和C语言语言各一本，书架上有各一本，书架上有3种不同作者的离散种不同作者的离散数学书，有数学书，有2种不同作者的种不同作者的C语言书，那么这位学语言书，那么这位学生共有生共有种不同的选法。种不同的选法。二、排列、组合二、排列、组合从从n个元素的集合中每次取个元素

15、的集合中每次取m个的排列和组合的个的排列和组合的计算公式分别为计算公式分别为排列和组合的最基本恒等式有：排列和组合的最基本恒等式有：例例3.3将英文单词将英文单词“Computer”的字母全部取出进的字母全部取出进行全排列，其中行全排列，其中C不在第一位，不在第一位，r不在末位，问共有不在末位，问共有多少种不同的排法？多少种不同的排法？解：解：“Computer”的字母的全排列数有的字母的全排列数有其中其中C排在第一位的排法有排在第一位的排法有7！种；！种；r排在末位的排法有排在末位的排法有7！种。！种。设为集合设为集合E设为集合设为集合A设为集合设为集合B|E|=8!，|A|=7!，|B|=

16、7!AB=|A|+|B|AB|AB|=6!AB=7!+7!6!EAB=8!7!7!+6!=30960ABEABEEAB例例3.4将将1，2，3三个数字排成三个数字排成2行行3列的矩阵，列的矩阵，要求同行和同列上都没有相同的数字，问这样的要求同行和同列上都没有相同的数字，问这样的数字矩阵有多少？数字矩阵有多少？解：先排矩阵的第一行共有解：先排矩阵的第一行共有种排法种排法如果不管题目要求，第二行也有如果不管题目要求，第二行也有种排法种排法可知，由这可知，由这3个数字排成同行没有相同数字的矩阵个数字排成同行没有相同数字的矩阵共有共有36种种(乘法原理乘法原理)。题目要求同列也没有相同数字题目要求同列

17、也没有相同数字设同列中有相同数字的矩阵分为几种情况：设同列中有相同数字的矩阵分为几种情况：有一列数字相同其他两列数字不同；有一列数字相同其他两列数字不同；有两列数字相同有两列数字相同(三列数字相同三列数字相同)；同行同列上都没有相同数字的矩阵有同行同列上都没有相同数字的矩阵有36-18-6=12种种一般地，从一般地，从n个元素的集合中抽群个元素的集合中抽群m个元素，允许个元素，允许重复的排列数为：重复的排列数为：nm。可以设想有可以设想有m个位子，每个位子都可以放个位子，每个位子都可以放n个元素个元素中的任一个，允许重复，中的任一个，允许重复，例例3.5求电子计算机中的求电子计算机中的6位二进

18、制数。位二进制数。例例3.6考试时有考试时有25个正确或错误的问题，学生也个正确或错误的问题，学生也可能不作答，问有多少种不同的考试结果。可能不作答，问有多少种不同的考试结果。重复组合数问题重复组合数问题从从1，2，3种每次取出两个（允许重复抽取）的种每次取出两个（允许重复抽取）的组合按自然数顺序写出来（枚举）：组合按自然数顺序写出来（枚举）：11，12，13，22，23，33现将各种组合分别加上现将各种组合分别加上01，就得到，就得到12，13，14，23，24，34组合组合(2)恰好是从恰好是从1，2，3，4中任取两个不重复中任取两个不重复元素的组合元素的组合(自然数顺序自然数顺序)情况情

19、况组合组合(1)组合组合(2)组合组合(1)组合组合(2)+0101一一对应的关系一一对应的关系所以，从三个互异元素中任取两个的重复组合数所以，从三个互异元素中任取两个的重复组合数可转化为从四个互异元素中任取两个不重复可转化为从四个互异元素中任取两个不重复的元素的组合数的元素的组合数来计算。来计算。推广到一般情况，从推广到一般情况，从n个互异元素中任取个互异元素中任取m个个的重复组合数的重复组合数可转换为从可转换为从n+m-1个互异个互异元素中任取元素中任取m个不重复元素的组合数。个不重复元素的组合数。考虑从考虑从1，2，3，n任取任取m个允许重复的元素个允许重复的元素每一组合，将其元素分别加

20、上每一组合，将其元素分别加上0，1，2，m-1，即变成从即变成从1，2，3，n，n+1，n+m-1任取任取m个不重复元素的组合。个不重复元素的组合。例例3.7求成自然序的四位数码的个数求成自然序的四位数码的个数解：四位数码是从解：四位数码是从0,1,2,3,4,5,6,7,8,9中选四个中选四个数字组成，数字可以重复，属于重复组合数问题。数字组成，数字可以重复，属于重复组合数问题。相当于从十个互异元素中选四个允许重复的组合。相当于从十个互异元素中选四个允许重复的组合。环状排列问题环状排列问题例例3.88位朋友围圆桌而坐，若座位不编号有多少位朋友围圆桌而坐，若座位不编号有多少种坐法？座位编号又有

21、多少种坐法种坐法？座位编号又有多少种坐法？1876543212345678218765432345678187654321812345678种12345681876543278!/8=7!座位不编号座位不编号3218765434567812若座位编号，属于若座位编号，属于全排列全排列问题问题8!=40320例例3.95颗红珠，颗红珠，3颗白珠，穿在一个项链上，有颗白珠，穿在一个项链上，有多少种方法？多少种方法？分析：环状排列问题，分析：环状排列问题，解：若解：若8颗珠子互异，则有颗珠子互异，则有7！种串法！种串法但但5颗红珠相同；颗红珠相同；3颗白珠也相同颗白珠也相同三、容斥原理三、容斥原理集

22、合的基数集合的基数设集合设集合A=a1,a2,an，含有含有n个元素，称集合个元素，称集合基数为基数为n,记做记做CardA=n,也可记作也可记作|A|=n。称称A为有穷集，否则称为无穷集为有穷集，否则称为无穷集空集的基数为空集的基数为0定理定理3.1容斥原理容斥原理设设A，B为有限集合，则为有限集合，则|AB|=|A|+|B|AB|定理定理3.2设设A，B为有限集合，则为有限集合，则|A B|=|A|+|B|2|AB|例例3.10假设假设10名青年中有名青年中有5名是工人，名是工人，7名是学生名是学生其中既是工人又是学生的有其中既是工人又是学生的有3名，问既不是工人又名，问既不是工人又不是学

23、生的有几名？不是学生的有几名？EABA=工人工人B=学生学生|AB|=3|A|=5|B|=7要求的部分为要求的部分为EAB|AB|=|A|+|B|AB|=5+7-3=9|EAB|=109=1定理定理3.3（容斥原理）（容斥原理）设设A为有穷集为有穷集,P1，P2，Pm是是m个不同的性质，个不同的性质，令令A Ai表示表示A A中具有性质中具有性质P Pi的元素构成的子集，的元素构成的子集，i=1,2=1,2，m，A Ai A Aj(ij)表示表示A A中同时具有性质中同时具有性质P Pi和和P Pj的元素组成的子集，的元素组成的子集，A Ai A Aj A Ak(ij k)表示表示A A中中同

24、时具有性质同时具有性质P Pi、P Pj和和P Pk的元素组成的子集，的元素组成的子集，A中至少具有一条性质的元素数为中至少具有一条性质的元素数为A A中不具有性质中不具有性质P P1 1，P P2 2，P Pm m的元素数为的元素数为例例3.11求不超过求不超过1000的自然数中能被的自然数中能被2或或3或或5整除的数的个数？整除的数的个数？解：设解：设A=1,2，,1000，研究对象的集合研究对象的集合(全集全集)在在A上定义性质上定义性质P1,P2,P3，分别表示能被分别表示能被2、3、5整除，设整除，设A1，A2，A3分别表示具有性质分别表示具有性质P1,P2,P3的集合。的集合。所求

25、部分为所求部分为|A1A2A3|A1|=500|A2|=333|A3|=200|A1A2A3|=|A1|+|A2|+|A3|A1A2|A1A3|A2A3|+|A1A2A3|A1A2|=166|A1A3|=100|A2A3|=66|A1A2A3|=33|A1A2A3|=500+333+20016610066+33=734错位排列错位排列的计数问题。的计数问题。有有n个人在参加晚会时寄存了自己的帽子，可是保个人在参加晚会时寄存了自己的帽子，可是保管人忘记放寄存号，当每个人领取帽子时，他只能管人忘记放寄存号，当每个人领取帽子时，他只能随机选择一顶帽子交给寄存人。问在随机选择一顶帽子交给寄存人。问在n

26、!种领取帽子种领取帽子的方式中，有多少种方式使得每个人都没有领到自的方式中，有多少种方式使得每个人都没有领到自己的帽子？如果将这些人与他们的帽子分别标号为己的帽子？如果将这些人与他们的帽子分别标号为1，2，n。设。设j领到的帽子标号为领到的帽子标号为ij，j=1,2,，n，那么这些人领到的帽子可以用排列那么这些人领到的帽子可以用排列i1i2in来表示，其中每个人都没有领到自己的来表示，其中每个人都没有领到自己的帽子的排列帽子的排列i1i2in满足满足ijj,j=1,2,，n。称这种排列为错位排列，错位排列数记做称这种排列为错位排列，错位排列数记做Dn，证明：证明：证明：设证明：设S为为1,2,

27、，的排列的集合，的排列的集合，Pi是是i处在处在排列中的第排列中的第i位性质，位性质，Ai是是S中具有性质中具有性质Pi的排列的排列的集合，的集合，i=1,2,，n。错位排列数错位排列数Dn就是就是S中不中不具有以上任何一条性质的排列数。具有以上任何一条性质的排列数。隶属关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。例如Aa，a和a既有aA，又有aA。前者把它们看成是不同层次上的两个集合，后者把它们看成是同一层次上的两个集合，都是正确的。定义定义6.2设A，B为集合，如果AB且BA，则称A与B相等相等，记作AB。如果A与B不相等，则记作AB。ABABBA相等的符号化

28、表示为定义定义6.3设A，B为集合，如果BA且BA，则称B是A的真子集真子集，记作BA。如果B不是A的真子集，则记作BA。真子集的符号化表示为BABABA例如NZQRC，但NN。定义定义6.4不含任何元素的集合叫做不含任何元素的集合叫做空集空集，记作，记作。空集可以符号化表示为x|xx。例如x|xRx2+1=0是方程x2+1=0的实数解集，因为该方程无实数解，所以是空集。定理定理6.1空集是一切集合的子集。空集是一切集合的子集。证证：任何集合A，由子集定义有Ax(xxA)右边的蕴涵式因前件假而为真命题，所以A也为真。推论推论空集是唯一的。空集是唯一的。证证：假设存在空集1和2，由定理6.1有1

29、2，21。根据集合相等的定义，有12。含有n个元素的集合简称n元集元集，它的含有m(mn)个元素的子集叫做它的m元子集元子集。任给一个n元集，怎样求出它的全部子集呢？例例6.1A1,2,3，将A的子集分类：解:0元子集，也就是空集，只有一个：；1元子集，即单元集单元集：1，2，3；2元子集：1,2，1,3，2,3；3元子集：1,2,3。一般地说，对于n元集A，它的0元子集有个，1元子集有个，m元子集有个，n元子集有个。子集总数为+2n个。定义定义6.5设A为集合，把A的全部子集构成的集合叫做A的幂集幂集，记作P(A)(或PA，2A)。幂集的符号化表示为P(A)x|xA例6.1中的集合A有P(A

30、)，1，2，3，1，2，1，3，2，3，1，2，3若A是n元集，则P(A)有2n个元素定义定义6.6在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集全集，记作E。全集是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。例如在研究平面上直线的相互关系时，可以把整个平面(平面上所有点的集合)取作全集，也可以把整个空间(空间上所有点的集合)取作全集。一般地说，全集取得小一些，问题的描述和处理会简单些。6.2集合的运算集合的运算一集合的基本运算集合的基本运算有并，交，相对补和对称差。定义定义6.7设A，B为集合，A与B的并集并集AB，交集交集AB，B对A的

31、相对补集相对补集AB分别定义如下：ABx|xAxBABx|xAxBABx|xAxBA或B中的元素构成A和B中的公共元素构成属于A但不属于B的元素构成a，b，cab，c例如Aa，b，c，Ba，Cb，dABABABBABC如果两个集合的交集为，则称这两个集合是不相交不相交的。两个集合的并和交运算可以推广成n个集合的并和交：A1A2Anx|xA1xA2xAnA1A2Anx|xA1xA2xAnA1A2AnA1A2AnABA并和交运算还可以推广到无穷多个集合的情况：A1A2A1A2定义定义6.8设A，B为集合，A与B的对称差集对称差集AB定义为：AB(AB)(BA)例如Aa，b，c，Bb，dABa，c，

32、d。对称差运算的另一种定义是AB(AB)(AB)在给定全集E以后，AE，A的绝对补集绝对补集A定义如下：定义定义6.9AEAx|xExA因为E是全集，xE是真命题，所以A可以定义为Ax|xA例如Ea，b，c，d，Aa，b，cAd。集合之间的关系和运算可以用文氏图文氏图(VennDiagram)给予形象的描述。文氏图的构造方法如下：首先画一个大矩形表示全集E(有时为简单起见可将全集省略)，其次在矩形内画一些圆(或任何其它的适当的闭曲线)，用圆的内部表示集合。不同的圆代表不同的集合。如果没有关于集合不交的说明，任何两个圆彼此相交。图中阴影的区域表示新组成的集合图6.2就是一些文氏图的实例。三广义交

33、和广义并三广义交和广义并以上定义的并和交运算称为初级并和初级交。下面考虑推广的并和交运算，即广义并和广义交。定义定义6.10设A为集合，A的元素的元素构成的集合称为A的广义并广义并，记为A。符号化表示为Ax|z(zAxz)。例例6.4设Aa,b,c,a,c,d,a,e,fBaCa,c,d则ABC a,b,c,d,e,faac,d根据广义并定义不难证明，若AA1,A2,An，则AA1A2An。类似地可以定义集合的广义交。定义定义6.11设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交广义交，记为A。符号化表示为Ax|z(zAxz)Aa，Ba，Cac，d 和广义并类似，若AA1,A2

34、,An，则AA1A2An为了使得集合表达式更为简洁，我们对集合运算的集合运算的优先顺序优先顺序做如下规定：称广义并，广义交，幂集，绝对补运算为一类运算一类运算，并，交，相对补，对称差运算为二类运算二类运算。一类运算优先于二类运算。一类运算之间由右向左顺序进行。二类运算之间由括号决定先后顺序。下面的集合公式：AB，P(A)，P(A)B，(AB)都是合理的公式。例例6.5设Aa,a,b计算A，A和A(AA)。解解:Aa,bAaAabAaAabAaA(AA)(ab)(ab)a)(ab)(ba)b使用文氏图可以很方便地解决有穷集合的计数问题有穷集合的计数问题。首先根据已知条件把对应的文氏图画出来。一般

35、地说，每一条性质决定一个集合。有多少条性质，就有多少个集合。如果没有特殊说明，任何两个集合都画成相交的，然后将已知集合的元素数填入表示该集合的区域内。通常从通常从n n个集合的交集填起个集合的交集填起，根据计算的结果将数字逐步填入所有的空白区域。如果交集的数字是未知的，可以设为x。根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。6.3有穷集的计数有穷集的计数例例6.2对24名会外语的科技人员进行掌握外语情况的调查。其统计结果如下：会英、日、德和法语的人分别为13，5，10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德

36、语，分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数。解解令A，B，C，D分别表示会英、法、德、日语的人的集合。根据题意画出文氏图如图6.3所示。设同时会三种语言的有x人，只会英、法或德语一种语言的分别为y1，y2和y3人。将x和y1，y2，y3填入图中相应的区域，然后依次填入其它区域的人数。A，B，C，D分别表示会英、法、德、日语的人的集合根据已知条件列出方程组如下：解得x1，y14，y22，y33。英英13法法9德德10日日5例例6.2求1到1000之间（包含1和1000在内）既不能被5和6，也不能被8整除的数有多少个。解：设 Sx|xZ1x1000 Ax|xZx可被5整除 B

37、x|xZx可被6整除 Cx|xZx可被8整除 用|T|表示有穷集，表示小于等于x的最大整数，lcm(x1,x2,xn)表示x1,x2,xn的最小公倍数，则有|A|=200|B|=166|AB|=33|C|=125|AC|=25|BC|=41|ABC|=8将这些数字依次填入文史图，得到图6.4，由图可知，不能被5，6，8整除的数有1000（2001003367）600ABC150100672517338定理6.2（包容排斥原理）设S为有穷集，P1，P2，Pm是m个性质，S中任何元素x或者具有性质Pi （i=1,2,，m）,两种情况必居一种。令Ai表示S中具有性质Pi的元素构成的子集，则S中不具

38、有性质P1，P2，Pm的元素数为=1000-(200+166+125)+(33+25+41)-8=600推论推论S中至少具有一条性质的元素数为中至少具有一条性质的元素数为例例6.7 错位排列错位排列的计数问题。的计数问题。有有n个人在参加晚会时寄存了自己的帽子，可是保个人在参加晚会时寄存了自己的帽子，可是保管人忘记放寄存号，当每个人领取帽子时，他只能管人忘记放寄存号，当每个人领取帽子时，他只能随机选择一顶帽子交给寄存人。问在随机选择一顶帽子交给寄存人。问在n!种领取帽子种领取帽子的方式中，有多少种方式使得每个人都没有领到自的方式中，有多少种方式使得每个人都没有领到自己的帽子？如果将这些人与他们

39、的帽子分别标号为己的帽子？如果将这些人与他们的帽子分别标号为1，2，n。设。设j领到的帽子标号为领到的帽子标号为ij，j=1,2,，n，那么这些人领到的帽子可以用排列那么这些人领到的帽子可以用排列i1i2in来表示，其中每个人都没有领到自己的来表示，其中每个人都没有领到自己的帽子的排列帽子的排列i1i2in满足满足ijj,j=1,2,，n。称这种排列为错位排列，错位排列数记做称这种排列为错位排列，错位排列数记做Dn，证明：证明：证明：设证明：设S为为1,2,，的排列的集合，的排列的集合，Pi是是i处在处在排列中的第排列中的第i位性质，位性质，Ai是是S中具有性质中具有性质Pi的排列的排列的集合

40、，的集合，i=1,2,，n。错位排列数错位排列数Dn就是就是S中不中不具有以上任何一条性质的排列数。具有以上任何一条性质的排列数。6.4集合恒等式集合恒等式一基本集合恒等式一基本集合恒等式下面的恒等式给出了集合运算的主要算律，其中A，B，C代表任意集合。幂等律幂等律AAA(6.1)AAA(6.2)结合律结合律(AB)CA(BC)(6.3)(AB)CA(BC)(6.4)交换律交换律ABBA(6.5)ABBA(6.6)分配律分配律A(BC)(AB)(AC)(6.7)A(BC)(AB)(AC)(6.8)同一律同一律AA(6.9)AEA(6.10)零律零律AEE(6.11)A(6.12)排中律排中律A

41、AE(6.13)矛盾律矛盾律AA(6.14)吸收律吸收律A(AB)A(6.15)A(AB)A(6.16)德摩根律德摩根律A(BC)(AB)(AC)(6.17)A(BC)(AB)(AC)(6.18)(BC)=BC(6.19)(BC)=BC(6.20)E(6.21)E(6.22)双重否定律双重否定律(A)A(6.23)例6.6证明式(6.17)A(BC)(AB)(AC)集合证明中经常大量用到命题逻辑的等值式，在叙述中采用半形式化的方法，其中表示当且仅当证明：对任意的xxA(BC)xA(xBxC)xAx(BC)xAxBxC(xAxB)(xAxC)x(AB)x(AC)以上证明的基本思想是：设，为集合公

42、式，欲证，即证PQQP为真。也就是要证对于任意的x有xPxQ和xQxP成立对于某些恒等式可以将这两个方向的推理合到一起，就是xPxQ不难看出，集合运算的规律和命题演算的某些规律是一致的。所以命题演算的方法是证明集合恒等式的基本方法。例6.8假设已知等式6.16.14，试证等式6.15即A（AB）A证明：A（AB）（AE）（AB）A（EB）AEA证明集合恒等式的另一种方法是利用已知的恒等式来代入。二证明技巧二证明技巧证明技巧一证明技巧一除了以上算律以外，还有一些关于集合运算性质的重要结果。ABA，ABB(6.24)AAB，BAB(6.25)ABA(6.26)ABAB(6.27)例例6.9证明等式

43、6.27，即ABAB。证证:对于任意的x，xABxAxBxAxBxAB所以ABAB。把相对补运算转换成交运算，这在证明有关相对补的恒等式中是很有用的。A-B=ABAB=BAB=A。证明：过程如下A-B=ABAB=BAB=AA-B=。假设ABABxAxBxA-B与A-B=矛盾显然BAB反之，任取x，xABxAxBxBxB（AB）xB因此ABB。显然ABA，任取x，xAAB=BAB=AxABxBxAxBxABAAB因此假设存在xA-B，xAxBxABxB假设A-BAB=AA-B=xAxBxB出现矛盾例例6.10证明(AB)BAB证证:(AB)B(AB)B(AB)(BB)(AB)EAB例6.12化简

44、(ABC)(AB)(A(BC)A)解：(ABC)(AB)(A(BC)A)(AB)ABA例6.13已知ABAC，证明BC证明：已知ABAC，所以有主要内容主要内容1.集合，相等，（真）包含，子集，空集，全集，幂集2.交，并，（相对和绝对）补，对称差，广义交，广义并3.文氏图，有穷集计数问题4.集合恒等式（等幂律，交换律，结合律，分配律，德摩根律，吸收律，零律，同一律，排中律，矛盾律，余补律，双重否定律，补交转换律等）学习要求学习要求1.熟练掌握集合的子集、相等、空集、全集、幂集等概2.念及其符号化表示2.熟练掌握集合的交、并、（相对和绝对）补、对称差、广义交、广义并的定义及其性质3.掌握集合的文

45、氏图的画法及利用文氏图解决有限集的计数问题的方法4.牢记基本的集合恒等式（等幂律、交换律、结合律、分配律、德摩根律、收律、零律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律）5.准确地用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式1.证明A-B=AAB=。xABxAxBxA-BxB（因为A-B=A）xAxBxB出现矛盾证明：必要性。A-B=AAB=假设AB充分性。AB=A-B=AA-B=(A-B)（AB）（AB）A（BB）AEAA-B=AA=B=A=BA=B3.设A,B为集合，试确定下列各式成立的充分必要条件：（1）A-B=B（2）A-B=B-A（3）AB=AB（4）A

46、B=AB=(A-B)B=ABBBBB=AB=AA(AB)=AAB=4.判断下列命题是否为真。（1）为真为假（2）为真为假（3）;为假为真（4）;为真为假（5）xx,x-x;为真为假（6）xx,x-x.为真为假5.设F表示一年级大学生的集合，S表示二年级大学生的集合，M表示数学专业学生的集合，R表示计算机专业学生的集合，T表示听离散数学课学生的集合，G表示星期一晚上参加音乐会的学生的集合，H表示星期一晚上很迟才睡觉的学生的集合。问下列各句子所对应的集合表达式分别是什么？请从备选的答案中挑出来。(1)所有计算机专业二年级的学生在学离散数学课。(2)这些且只有这些学离散数学课的学生或者星期一晚上去听音乐会的学生在星期一晚上很迟才睡觉。(3)听离散数学课的学生都没参加星期一晚上的音乐会。SRTH=GTTG=(4)这个音乐会只有大学一、二年级的学生参加。(5)除去数学专业和计算机专业以外的二年级学生都去参加了音乐会。GFSS-(RM)G备选答案：TGHGHTSRTHGTTGFSGGFSS-(RM)GGS-(RM)