左孝凌离散数学课件3.1集合的概念和表示法3.2集合的运算

1、2022-4-172022-4-1712022-4-1712022-4-172022-4-1722022-4-172 集合论是从集合出发，来定义数及其运算，进而集合论是从集合出发，来定义数及其运算，进而发展到整个数学。发展到整个数学。 按现代数学的观点，数学各分支的研究对象或者按现代数学的观点，数学各分支的研究对象或者本身都是带有某种特定结构的集合，如群、环、拓扑本身都是带有某种特定结构的集合，如群、环、拓扑空间等，或者是可以通过集合来定义的。从这个意义空间等，或者是可以通过集合来定义的。从这个意义上说，集合论可以看做是整个现代数学的基础。它的上说，集合论可以看做是整个现代数学的基础。它的基本

2、概念已经渗透到数学的所有领域，如古典分析、基本概念已经渗透到数学的所有领域，如古典分析、泛函、概率、函数论等。泛函、概率、函数论等。2022-4-172022-4-1732022-4-173 1 1 集合的概念和表示法集合的概念和表示法 2 2 集合的运算集合的运算3 34 4序偶与笛卡尔集序偶与笛卡尔集 5 5关系及其表示关系及其表示6 6 关系的性质关系的性质7 7 复合关系和逆关系复合关系和逆关系8 8 关系的闭包运算关系的闭包运算9 9 1010等价关系与划分等价关系与划分11 11 相容关系与覆盖相容关系与覆盖12 12 偏序关系偏序关系2022-4-172022-4-1742022

3、-4-174一、基本概念一、基本概念二、集合的表示方式二、集合的表示方式三、集合间的关系三、集合间的关系四、几类特殊的集合四、几类特殊的集合 3.1 集合概念及其表示法2022-4-172022-4-175一、基本概念一、基本概念 集合集合由某些特殊对象汇集在一起构成的整体。由某些特殊对象汇集在一起构成的整体。研究对象的全体研究对象的全体用大写字母表示。如用大写字母表示。如N:N:自然数集，自然数集，I I：整数集，：整数集，Q Q：有理数集，：有理数集，R R：实数集。：实数集。元素：元素：组成集合的单个体称为集合的元素组成集合的单个体称为集合的元素通常用小写字母表示。例如，集合通常用小写字

4、母表示。例如，集合A A中的某个元素中的某个元素a a二者关系二者关系若个体若个体a a是集合是集合A A的元素，称的元素，称a a属于属于A A, ,记作记作“aAaA”否则称否则称a a不属于集合不属于集合A A，记作，记作 有限集：有限集：集合中的元素个数是有限的。集合中的元素个数是有限的。无限集：无限集：集合中的元素个数是无限的。集合中的元素个数是无限的。Aa3.1 集合概念及其表示法2022-4-172022-4-1762022-4-176二、集合的表示方二、集合的表示方法法列举法列举法将构成集合的元素列出来，元素之间用逗号隔开，并用将构成集合的元素列出来，元素之间用逗号隔开，并用花

5、括号括起来。花括号括起来。例如：例如：A=a,b,c,d,B=4,5,6,7,8 A=a,b,c,d,B=4,5,6,7,8 叙述法叙述法：P(x)P(x)表示谓词，描述元素的共同特征。表示谓词，描述元素的共同特征。A=xP(x)A=xP(x)表示集合表示集合当且仅当个体当且仅当个体a a使使P(a)P(a)成立时，成立时，aAaA，否则，否则 。B=xxNB=xxN且且4x8C=24x8C=2x xiZiZ+ +,即即C=2C=20 0,2,21 1,2,22 2,2,23 3, , D=2xxZD=2xxZ+ +且且x50,x50,即即D=0,2,4,6,D=0,2,4,6,98,100,

6、98,100 3.1 集合概念及其表示法Aa 集合中的元素彼此不集合中的元素彼此不同，且无顺序要求同，且无顺序要求集合中的元素也可以集合中的元素也可以是集合是集合本法可能会出现悖论。本法可能会出现悖论。著名的著名的“理发师悖论理发师悖论”：“我要给所有不给自己我要给所有不给自己刮脸的人刮脸，而不给刮脸的人刮脸，而不给给自己刮脸的人刮脸给自己刮脸的人刮脸”2022-4-172022-4-1772022-4-177练习练习用列举法表示下列集合用列举法表示下列集合（1）A=a|aPP且且a20a20（2）B=a|a|4且且a为奇数为奇数2. 用描述法表示下列集合用描述法表示下列集合 (1) A=0,

7、2,4,200 (2) B=2,4,8,1024 2,3,5,7,11,13,17,19 - -3,- -1,1,3 2x|xZ+且且x100 x1002n|nNN且且n10n10 2022-4-172022-4-1782022-4-178例如例如 设设 A=a, b, c, d, B=a, e, x, y, z, C=a, x则则 集合的包含集合的包含设设A A、B B是任意两个集合是任意两个集合，如果，如果A A的每一个元素都是的每一个元素都是B B的成员，则称的成员，则称A A是是B B的子集，记作的子集，记作 或或 ，读作，读作“A A包含在包含在B B内内”或或“B B包含包含A A

8、”。如果如果A A不是不是B B的子集，则记作的子集，则记作 。 （判断子集的方法）（判断子集的方法）性质性质对任意集合对任意集合A， ；对任意集合对任意集合A， ；对任意集合对任意集合A、B、C，若，若 则则3.1 集合概念及其表示法三、集合间的关系：三、集合间的关系：集合的包含和相等是集合间的两个基本关系集合的包含和相等是集合间的两个基本关系BABABC ACABBAAB )(BxAxxBAAAABACB CA2022-4-172022-4-1792022-4-179例如例如 设设A=x | xN 且且 x能整除能整除24， B=1, 2, 3, 4, 6, 8, 12, 24 则则 A=

9、B又例如又例如 （1）a, b, c =b, c, a （2）a, b, c, c =a, b, c （3）a, b, c a, b, c （4） 两集合相等两集合相等设设A、B是任何两个是任何两个集合，若集合，若 且且 ，即，即A A、B B有相同的成有相同的成员，则称集合员，则称集合A与与B相等，记作相等，记作A=B。（外延性原理）。（外延性原理）BA AB 3.1 集合概念及其表示法三、集合间的关系：三、集合间的关系：集合的包含和相等是集合间的两个基本关系集合的包含和相等是集合间的两个基本关系2022-4-172022-4-1710真子集真子集设集合设集合A、B，若，若 , 且且ABB，

10、则称，则称A A是是B B的真子集，记的真子集，记作作 ，若，若A A不是不是B B的真子集，则记作的真子集，则记作若若 ，则对，则对 ，如果，如果 则必有则必有 , ,且且 使得使得 且且3.1 集合概念及其表示法三、集合间的关系：三、集合间的关系：集合的包含和相等是集合间的两个基本关系集合的包含和相等是集合间的两个基本关系BABABABAxAxBx0 xBx 0Ax 0例如例如 设设A=0A=0，11，B=0B=0，1 1，22，C=0C=0 则则 但但BABC BBB 2022-4-172022-4-1711空集：空集：不含任何元素的集合，称为不含任何元素的集合，称为空集空集，记作，记作

11、。例如例如 A=x | xR 且且 x2+8=0 = 定理定理1 1：空集是任何集合的子集即：空集是任何集合的子集即推论：推论：空集是唯一的。空集是唯一的。对于每一个非空集合对于每一个非空集合A，至少有两个不同的子集，至少有两个不同的子集，A和和，称为，称为A的的平凡子集平凡子集。3.1 集合概念及其表示法四、几类特殊的集合四、几类特殊的集合A2022-4-172022-4-1712全集：在一定范围内，如果所有集合均为某一集合的子集，全集：在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集，记作则称该集合为全集，记作E E或或U U对于任一对于任一xA,因因 ,则则 xE,即即 恒

12、真。恒真。全集相当于论域，即全集相当于论域，即 ， 为任何谓词为任何谓词幂集：给定集合幂集：给定集合A A，由集合，由集合A A的所有子集为元素组成的集合，的所有子集为元素组成的集合，称为集合称为集合A A的幂集，记为的幂集，记为P (A)P (A)=x|x A注意注意: x P (A) x A 例如例如: A=a,b的的0元子集元子集： ，1元子集元子集： a,b， 2元子集：元子集：为为a,b 所以：所以： P (A)=,a,b,a,b，共，共22=4个子集。个子集。如果有限集合如果有限集合A有有n个元素，则幂集个元素，则幂集P (A)有有2n个元素。个元素。3.1 集合概念及其表示法四、

13、几类特殊的集合四、几类特殊的集合EA)(Exx)()(|xpxpxE)(xp判断：任何集合的判断：任何集合的幂集一定不是空集。幂集一定不是空集。（空集呢？）（空集呢？）2022-4-172022-4-17132022-4-1713例例1.1. 设设 , 求求A和和B的幂集的幂集解解 对于集合对于集合A，它只有一个子集，它只有一个子集 ， 即 对于集合对于集合B，有，有 1个元素的子集：个元素的子集： ，a，a 2个元素的子集：个元素的子集： , , 3个元素的子集：个元素的子集： 0个元素的子集：个元素的子集： 因此因此 A aaB, A2 aa, a, a, , ,2Baaaa aa,aaa

14、a2022-4-172022-4-17142022-4-1714(1)(2)(3)(4)( )( )( )( )( )( )( )( )YYYYYYNN令令则则例例2.2.设设 , B, B是是A A的幂集的幂集，判断下的幂集的幂集，判断下列论断是否正确，并将列论断是否正确，并将“Y”或或“N”填入相应填入相应论断后面的括号中。论断后面的括号中。 AB B B B,B B B B,2AC,2CB2022-4-172022-4-17152022-4-1715答案：答案：( )ABD答案：答案：( )A BC练习练习 B. C. D. 1 试判断下列各式是否正确，并将正确的题试判断下列各式是否正确

15、，并将正确的题号填入括号内。号填入括号内。 SS SS2 2 设设 , 试判断下列各式是否正试判断下列各式是否正确，并将正确的题号填入括号内。确，并将正确的题号填入括号内。 B. C. D. aa , 4, 3,aS aaa, aaa, aa SSSS 2022-4-172022-4-17162022-4-1716 3.2 集合的运算 文氏图文氏图例如例如 UAABBA2022-4-172022-4-17172022-4-1717一、交运算一、交运算 例如例如 设设A=a,b,c,d, B=d,f,a, C=e,f,g则 交运算性质交运算性质: :定义定义1 1：设有集合设有集合A、B，属于，

16、属于A同时又属于同时又属于B的所有元素组成的所有元素组成的集合称为的集合称为A与与B的交集，记作的交集，记作 。即。即BAadBA,CAfCBBBAABAABBABuAuuBA且|a) A A = A （幂等律）（幂等律）b) A = （零律）（零律）c) A E = A （同一律）（同一律）d) A B = B A （交换律）（交换律）e) (A B) C = A (B C) （结合律）（结合律）f) 3.2 集合的运算2022-4-172022-4-17182022-4-1718 3. 2集合的运算二、并运算二、并运算 例如例如 设设A=a,b,c, B=c,d,f, C=b,e则 AB定

17、义定义2 2 设有集合设有集合A、B，属于，属于A或属于或属于B的所有元素组成的集合称的所有元素组成的集合称为为A与与B的并集，记作的并集，记作 。即。即BAfdcbaBA,ecbaCA,fedcbCB,BuAuuBA或|BA2022-4-172022-4-17192022-4-1719 3. 2集合的运算二、并运算二、并运算 a) A A = A （幂等律）（幂等律）b) A = A （同一律）（同一律）c) A E = E （零律）（零律）d) A B = B A （交换律）（交换律）e) (A B) C = A (B C) （结合律）（结合律）f)并运算的性质并运算的性质BABBAA,2

18、022-4-172022-4-17202022-4-1720 3. 2集合的运算二、并运算二、并运算 1) 设设A B,C D,则则A C B D2) A B,则则A C B C3)分配律分配律4)吸收律吸收律5)当且仅当当且仅当A B = B A B = A A B并运算的其他性质并运算的其他性质)()()(CABACBA)()()(CABACBAABAA)(ABAA)(2022-4-172022-4-17212022-4-1721定义定义3 3 设有集合设有集合A、B，所有属于，所有属于B而不属于而不属于A的的元素组成的集合，称为元素组成的集合，称为A相对于相对于B的补集的补集，记作，记作

19、B-A。即即例如例如 设设A=a,b,c,d, B=d,f,a, C=e,f,g 则则B-A= f , C-A= e ,f , g =C BAABAuBuuAB但| 3. 2集合的运算三、相对补运算三、相对补运算( (差差) ) 2022-4-172022-4-17222022-4-1722A AAA定义定义4 4 集合集合A相对于全集合相对于全集合U的补集称为的补集称为A的绝对的绝对补集，简称为补集，简称为A的补集，记作的补集，记作 。即。即AAuuAuUuuAUA|但 3. 2集合的运算四、绝对补运算四、绝对补运算 2022-4-172022-4-17232022-4-1723例如例如 设

20、设U=1，2，3，4，10， A=2，4，6，8，10 则则又例如又例如 设设U=I（I是整数集），是整数集）， 则则9 , 7 , 5 , 3 , 1AUA0,|iIiiA且0|iIiiAUA且2022-4-172022-4-17242022-4-1724定义定义5 5：设有集合设有集合A、B，所有属于，所有属于A而不属于而不属于B或属于或属于B而不属于而不属于A的元素组成的集合，称为的元素组成的集合，称为A与与B的的，记作，记作 。即。即ABBABA)()()()(ABxBAxxBxAxxBAABBA 3. 2集合的运算五、对称差运算五、对称差运算 2022-4-172022-4-1725

21、2022-4-1725 六、集合运算的十条定律六、集合运算的十条定律对于全集合对于全集合U的任意子集的任意子集A、B、C，有：，有： ABBA交换律交换律ABBACBACBA)()(结合律结合律CBACBA)()(分配律分配律)()()(CABACBA)()()(CABACBA同一律同一律AAAUA 3. 2集合的运算2022-4-172022-4-17262022-4-1726互补律互补律UAA AA对合律对合律AA )(幂等律幂等律AAAAAA零一律零一律UUAA吸收律吸收律ABAA)(ABAA)(德德摩根律摩根律BABA)(BABA)( 六、集合运算的十条定律六、集合运算的十条定律 3.

22、 2集合的运算2022-4-172022-4-17272022-4-1727交换律交换律ABBA零一律零一律 AAAA结合律结合律)()(CBACBA)()(ABBABA 六、集合运算的十条定律六、集合运算的十条定律 3. 2集合的运算2022-4-172022-4-17282022-4-1728D 若若 ，则，则 A=B 练习练习1 设设A、B、C是任意集合，判断下述论断是否是任意集合，判断下述论断是否正确，并将正确的题号填入括号内。正确，并将正确的题号填入括号内。 A 若若 ，则，则 B=CB 若若 ，则，则 B=C C 若若A-B=A-C，则，则 B=C ( )D CABACABABA

23、反例反例 设设A= a , b , c , B= b , d , C= c , d 则则 但但,dcbaCABACB 2022-4-172022-4-17292022-4-1729CBA)(2 设设U=1，2，3，4，5，A=2，4，B=4，3，5，C=2，5，3，确定下列，确定下列集合的元素，将其填入相应的花括号内。集合的元素，将其填入相应的花括号内。 (1) (2) (3) (4) (5)21, 42, 3, 4, 54BA)(CBACABCA)(CBA)(2022-4-172022-4-17302022-4-17303 设设U表示刘平拥有的所有书的集合，其中表示刘平拥有的所有书的集合，其

24、中A是离散数学参是离散数学参考书的集合，考书的集合，B是操作系统参考书的集合，是操作系统参考书的集合，C是今年出版的是今年出版的新书的集合，新书的集合，D是从图书馆借来的书的集合。现知道如下情是从图书馆借来的书的集合。现知道如下情形：形：（1）所有离散数学参考书都是今年出版的新书。（）所有离散数学参考书都是今年出版的新书。（ ） （2）所有操作系统参考书都是从图书馆借来的。（）所有操作系统参考书都是从图书馆借来的。（ ） （3）今年出版的新书不是从图书馆借来的。（）今年出版的新书不是从图书馆借来的。（ ） （4）没有一本操作系统的参考书是今年出版的。（）没有一本操作系统的参考书是今年出版的。（

25、 ） 3157试用集合的方法分别表示上述四种情形，可供选择的答案试用集合的方法分别表示上述四种情形，可供选择的答案如下，请从下述答案中挑选出相应表达式的编号填入每一如下，请从下述答案中挑选出相应表达式的编号填入每一种情形后面的括号中。种情形后面的括号中。 2. 3. 4. 5. 6. 7.DB BC CADADC CB CB2022-4-172022-4-17312022-4-17314 判断下列论断是否正确，对正确的论断在相应题后的括判断下列论断是否正确，对正确的论断在相应题后的括号中标入号中标入“Y”，对错误的论断在相应题后的括号中标入，对错误的论断在相应题后的括号中标入“N”。1） 若若

26、 ，则，则 （ ） 2） 若若 ，则，则 （ ） 3） 若若 ，则，则 （ ） 4） 若若 ，则，则 （ ） 5） 若若 ，则，则 ( )6） 若若 ，则，则 ( )7） 若若 ，则，则 ( )8） 若若 ，则，则 ( )YYYYNNNNAaAaBAaBAaBAaBaBAaBaBABBABAABAAaAaBAaBAa32根据定义，利用逻辑等价式和逻辑推理规则利用集合恒等式和已知的集合结论七、集合恒等式的几种证明方法七、集合恒等式的几种证明方法 3. 2集合的运算33 题型题型: A=B. 证明证明： x, xA (?) xB A=B 证毕. 或证明或证明： x, xA (?) xB. 则， A B另，x, xB (?) xA.则， B A A=B证毕.题型题型: A B. 证明证明: x, x A (?) x B A B证毕证毕. 3. 2集合的运算34例1：分配律(证明)A(BC)=(AB)(AC)证明: x, xA(BC) xA x(BC) (定义) xA (xB xC) (定义) (xAxB)(xAxC) (命题逻辑分配律) (xAB)(xAC) (定义) x(AB)(AC) (定义) A(BC)=(AB)(AC)成立 3. 2集合的运算35例2：零律(证明)