《左孝凌离散数学课件3.1集合的概念和表示法-3.2集合的运算.ppt》由会员分享，可在线阅读，更多相关《左孝凌离散数学课件3.1集合的概念和表示法-3.2集合的运算.ppt（42页珍藏版）》请在金锄头文库上搜索。
1、2024/8/131离散数学离散数学(Discrete Mathematics)2024/8/1312024/8/1322024/8/132第二篇第二篇 集集 合合 论论 集合论是从集合出发，来定义数及其运算，集合论是从集合出发，来定义数及其运算，进而发展到整个数学。进而发展到整个数学。 按现代数学的观点，数学各分支的研究对象按现代数学的观点，数学各分支的研究对象或者本身都是带有某种特定结构的集合，如群、环、或者本身都是带有某种特定结构的集合，如群、环、拓扑空间等，或者是可以通过集合来定义的。从这个拓扑空间等，或者是可以通过集合来定义的。从这个意义上说，集合论可以看做是整个现代数学的基础。意义
2、上说，集合论可以看做是整个现代数学的基础。它的基本概念已经渗透到数学的所有领域，如古典分它的基本概念已经渗透到数学的所有领域，如古典分析、泛函、概率、函数论等。析、泛函、概率、函数论等。2024/8/1332024/8/133 1 1 集合的概念和表示集合的概念和表示法法 2 2 集合的运算集合的运算3 34 4序偶与笛卡尔集序偶与笛卡尔集 5 5关系及其表示关系及其表示6 6 关系的性质关系的性质7 7 复合关系和逆关系复合关系和逆关系8 8 关系的闭包运算关系的闭包运算9 9 1010等价关系与划分等价关系与划分11 11 相容关系与覆盖相容关系与覆盖12 12 偏序关系偏序关系第三章第三
3、章 集合与关系集合与关系2024/8/1342024/8/134一、基本概念一、基本概念二、集合的表示方式二、集合的表示方式三、集合间的关系三、集合间的关系四、几类特殊的集合四、几类特殊的集合 3.1集合概念及其表示法2024/8/1352024/8/135一、基本概念一、基本概念 1.1.集合集合由某些特殊对象汇集在一起构成的整体。由某些特殊对象汇集在一起构成的整体。研究对象的全体研究对象的全体用大写字母表示。如用大写字母表示。如N:N:自然数集，自然数集，I I：整数集，：整数集，Q Q：有理数集，：有理数集，R R：实数集。：实数集。2.2.元素：元素：组成集合的单个体称为集合的元素组成
4、集合的单个体称为集合的元素通常用小写字母表示。例如，集合通常用小写字母表示。例如，集合A A中的某个元素中的某个元素a a3.3.二者关系二者关系若个体若个体a a是集合是集合A A的元素，称的元素，称a a属于属于A A, ,记作记作“aAaA”否则称否则称a a不属于集合不属于集合A A，记作，记作 4.4.有限集：有限集：集合中的元素个数是有限的。集合中的元素个数是有限的。5.5.无限集：无限集：集合中的元素个数是无限的。集合中的元素个数是无限的。3.1集合概念及其表示法2024/8/1362024/8/136二、集合的表示方二、集合的表示方法法1.1.列举法列举法将将构构成成集集合合的
5、的元元素素列列出出来来，元元素素之之间间用用逗逗号号隔隔开开，并并用用花括号括起来。花括号括起来。例如：例如：A=a,b,c,d,B=4,5,6,7,8 A=a,b,c,d,B=4,5,6,7,8 2.2.叙述法叙述法：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+
6、+且且x50,x50,即即D=0,2,4,6,D=0,2,4,6,98,100,98,100 3.1集合概念及其表示法集合中的元素彼此不集合中的元素彼此不同，且无顺序要求同，且无顺序要求集合中的元素也可以集合中的元素也可以是集合是集合本法可能会出现悖论。本法可能会出现悖论。著名的著名的“理发师悖论理发师悖论”：“我要给所有不给自我要给所有不给自己刮脸的人刮脸，而不己刮脸的人刮脸，而不给给自己刮脸的人刮脸给给自己刮脸的人刮脸”2024/8/13 72024/8/137练习练习1.用列举法表示下列集合用列举法表示下列集合（1）A=a|aPP且且a20a20（2）B=a|a|4且且a为奇数为奇数2.
7、 用描述法表示下列集合用描述法表示下列集合 (1) A=0,2,4,200 (2) B=2,4,8,1024 2,3,5,7,11,13,17,19 - -3,- -1,1,3 2x|xZ+且且x100x1002n|nNN且且n10n10 2024/8/1382024/8/138例如例如 设设 A=a, b, c, d, B=a, e, x, y, z, C=a, x则则 1.1.集合的包含集合的包含设设A、B是任意两个集合是任意两个集合，如果，如果A的每一个元素都是的每一个元素都是B的成员，则称的成员，则称A是是B的子集，记作的子集，记作 或或 ，读作，读作“A A包含在包含在B B内内”或
8、或“B B包含包含A A”。如果如果A不是不是B的子集，则记作的子集，则记作 。 （判断子集的方法）（判断子集的方法）性质性质对任意集合对任意集合A， ；对任意集合对任意集合A， ；对任意集合对任意集合A、B、C，若，若 则则3.1集合概念及其表示法三、集合间的关系：三、集合间的关系：集合的包含和相等是集合间的两个基本关系集合的包含和相等是集合间的两个基本关系2024/8/1392024/8/139例如例如 设设A=x | xN 且且 x能整除能整除24， B=1, 2, 3, 4, 6, 8, 12, 24 则则 A=B又例如又例如（1）a, b, c =b, c, a （2）a, b, c
9、, c =a, b, c （3）a, b, c a, b, c （4） 2.2.两集合相等两集合相等设设A、B是任何两个是任何两个集合，若集合，若 且且 ，即，即A A、B B有相同有相同的成员，则称集合的成员，则称集合A与与B相等，记作相等，记作A=B。（外延性原理）。（外延性原理）3.1集合概念及其表示法三、集合间的关系：三、集合间的关系：集合的包含和相等是集合间的两个基本关系集合的包含和相等是集合间的两个基本关系2024/8/13103.3.真子集真子集设集合设集合A、B，若，若 , 且且ABB，则称，则称A A是是B B的真子集，记作的真子集，记作 ，若，若A A不是不是B B的真子集
10、，则记作的真子集，则记作若若 ，则对，则对 ，如果，如果 则必有则必有 , ,且且 使得使得 且且3.1集合概念及其表示法三、集合间的关系：三、集合间的关系：集合的包含和相等是集合间的两个基本关系集合的包含和相等是集合间的两个基本关系例如例如 设设A=0A=0，11，B=0B=0，1 1，22，C=0C=0 则则 但但2024/8/13111.1.空集：空集：不含任何元素的集合，称为不含任何元素的集合，称为空集空集，记作，记作。例如例如 A=x | xR 且且 x2+8=0 = 定理定理1 1：空集是任何集合的子集即：空集是任何集合的子集即推论：推论：空集是唯一的。空集是唯一的。对于每一个非空
11、集合对于每一个非空集合A，至少有两个不同的子集，至少有两个不同的子集，A和和，称为，称为A的的平凡子集平凡子集。3.1集合概念及其表示法四、几类特殊的集合四、几类特殊的集合2024/8/13122.2.全集：在一定范围内，如果所有集合均为某一集合的子集，全集：在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集，记作则称该集合为全集，记作E E或或U U对于任一对于任一xA,因因 ,则则 xE,即即 恒真。恒真。全集相当于论域，即全集相当于论域，即 ， 为任何谓词为任何谓词3.3.幂集：给定集合幂集：给定集合A A，由集合，由集合A A的所有子集为元素组成的集合，的所有子集为元素组成
12、的集合，称为集合称为集合A A的幂集，记为的幂集，记为P P (A)P P (A)=x|x A注意注意: x P (A) x A 例如例如: A=a,b的的0元子集元子集： ，1元子集元子集： a,b， 2元子集：元子集：为为a,b 所以：所以： P P (A)=,a,b,a,b，共，共22=4个子集。个子集。如果有限集合如果有限集合A有有n个元素，则幂集个元素，则幂集P P (A)有有2n个元素。个元素。3.1集合概念及其表示法四、几类特殊的集合四、几类特殊的集合判断：任何集合的判断：任何集合的幂集一定不是空集。幂集一定不是空集。（空集呢？）（空集呢？）2024/8/13132024/8/1
13、313例例1.1. 设设 , 求求A和和B的幂集的幂集解解对于集合对于集合A，它只有一个子集，它只有一个子集 ， 即对于集合对于集合B，有，有 1个元素的子集：个元素的子集： ，a，a2个元素的子集：个元素的子集： , , 3个元素的子集：个元素的子集： 0个元素的子集：个元素的子集： 因此因此 2024/8/13142024/8/1314(1)(2)(3)(4)( )( )( )( )( )( )( )( )YYYYYYNN令令则则例例2.2.设设 , B, B是是A A的幂集的幂集，判断下的幂集的幂集，判断下列论断是否正确，并将列论断是否正确，并将“Y”或或“N”填入相填入相应论断后面的括
14、号中。应论断后面的括号中。2024/8/13152024/8/1315答案：答案：( )ABD答案：答案：( )A BC练习练习A.B.C. D. 1 试判断下列各式是否正确，并将正确的题试判断下列各式是否正确，并将正确的题号填入括号内。号填入括号内。 2 2 设设 , 试判断下列各式是否正确，试判断下列各式是否正确，并将正确的题号填入括号内。并将正确的题号填入括号内。 A.B.C. D. 2024/8/13162024/8/1316 3.2集合的运算 文氏文氏图例如例如 UAAB2024/8/13172024/8/1317一、交运算一、交运算 例如例如 设设A=a,b,c,d, B=d,f,
15、a, C=e,f,g则交运算性质交运算性质: :定定义义1 1：设设有有集集合合A、B，属属于于A同同时时又又属属于于B的的所所有有元元素素组组成成的集合称为的集合称为A与与B的交集，记作的交集，记作 。即。即ABa) A A = A （幂等律）（幂等律）b) A = （零律）（零律）c) A E = A （同一律）（同一律）d) A B = B A （交换律）（交换律）e) (A B) C = A (B C) （结合律）（结合律）f) 3.2集合的运算2024/8/13182024/8/1318 3.2集合的运算二、并运算二、并运算 例如例如 设设A=a,b,c, B=c,d,f, C=b,
16、e则AB定定义义2 2设设有有集集合合A、B，属属于于A或或属属于于B的的所所有有元元素素组组成成的的集集合合称称为为A与与B的并集，记作的并集，记作 。即。即2024/8/13192024/8/1319 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)并运算的性质并运算的性质2024/8/13202024/8/1320 3.2集合的运算二、并运算二、并运算 1) 设设A B,
17、C D,则则A C B D2) A B,则则A C B C3)分配律分配律4)吸收律吸收律5)当且仅当当且仅当A B = B A B = A A B并运算的其他性质并运算的其他性质2024/8/13212024/8/1321定定义义3 3 设设有有集集合合A、B，所所有有属属于于B而而不不属属于于A的的元元素素组组成成的的集集合合，称称为为A相相对对于于B的的补补集集，记记作作B-A。即即例如例如 设设A=a,b,c,d, B=d,f,a, C=e,f,g 则则B-A= f , C-A= e ,f , g =C BA 3.2集合的运算三、相对补运算三、相对补运算( (差差) ) 2024/8/
18、13222024/8/1322A AA定义定义4 4 集合集合A相对于全集合相对于全集合U的补集称为的补集称为A的绝对的绝对补集，简称为补集，简称为A的补集，记作的补集，记作 。即。即 3.2集合的运算四、绝对补运算四、绝对补运算 2024/8/13232024/8/1323例如例如 设设U=1，2，3，4，10， A=2，4，6，8，10 则则又例如又例如设设U=I（I是整数集），是整数集）， 则则2024/8/13 242024/8/1324定义定义5 5：设有集合设有集合A、B，所有属于，所有属于A而不属于而不属于B或属于或属于B而不属于而不属于A的元素组成的集合，称为的元素组成的集合，
19、称为A与与B的的对称差对称差，记作，记作 。即。即AB 3.2集合的运算五、对称差运算五、对称差运算 2024/8/13252024/8/1325 六、集合运算的十条定律六、集合运算的十条定律对于全集合对于全集合U的任意子集的任意子集A、B、C，有：，有： 交换律交换律结合律结合律分配律分配律同一律同一律 3.2集合的运算2024/8/13262024/8/1326互补律互补律对合律对合律幂等律幂等律零一律零一律吸收律吸收律德德摩根律摩根律 六、集合运算的十条定律六、集合运算的十条定律 3.2集合的运算2024/8/13272024/8/1327对称差运算的性质：对称差运算的性质：交换律交换律
20、零一律零一律结合律结合律 六、集合运算的十条定律六、集合运算的十条定律 3.2集合的运算2024/8/13282024/8/1328D 若若 ，则，则 A=B 练习练习1 设设A、B、C是任意集合，判断下述论断是否是任意集合，判断下述论断是否正确，并将正确的题号填入括号内。正确，并将正确的题号填入括号内。 A 若若 ，则，则 B=CB 若若 ，则，则 B=C C 若若A-B=A-C，则，则 B=C ()D 反例反例 设设A= a , b , c , B= b , d , C= c , d 则则 但但2024/8/13292024/8/13292 设设U=1，2，3，4，5，A=2，4，B=4，
21、3，5，C=2，5，3，确定下列集合，确定下列集合的元素，将其填入相应的花括号内。的元素，将其填入相应的花括号内。 (1) (2) (3) (4) (5)21, 42, 3, 4, 542024/8/13302024/8/13303 设设U表表示示刘刘平平拥拥有有的的所所有有书书的的集集合合，其其中中A是是离离散散数数学学参参考考书书的的集集合合，B是是操操作作系系统统参参考考书书的的集集合合，C是是今今年年出出版版的的新新书书的的集集合合，D是是从从图图书书馆馆借借来来的的书书的的集集合合。现现知知道道如如下下情情形：形：（1）所有离散数学参考书都是今年出版的新书。（）所有离散数学参考书都是
22、今年出版的新书。（ ） （2）所有操作系统参考书都是从图书馆借来的。（）所有操作系统参考书都是从图书馆借来的。（ ） （3）今年出版的新书不是从图书馆借来的。（）今年出版的新书不是从图书馆借来的。（ ） （4）没有一本操作系统的参考书是今年出版的。（）没有一本操作系统的参考书是今年出版的。（ ） 3157试试用用集集合合的的方方法法分分别别表表示示上上述述四四种种情情形形，可可供供选选择择的的答答案案如如下下，请请从从下下述述答答案案中中挑挑选选出出相相应应表表达达式式的的编编号号填填入入每每一一种情形后面的括号中。种情形后面的括号中。1. 2. 3. 4. 5. 6. 7.2024/8/13
23、312024/8/13314 判判断断下下列列论论断断是是否否正正确确，对对正正确确的的论论断断在在相相应应题题后后的的括括号号中中标标入入“Y”，对对错错误误的的论论断断在在相相应应题题后后的的括括号号中中标标入入“N”。1） 若若 ，则，则 （ ） 2） 若若 ，则，则 （ ） 3） 若若 ，则，则 （ ） 4） 若若 ，则，则 （ ） 5） 若若 ，则，则 ( )6） 若若 ，则，则 ( )7） 若若 ，则，则 ( )8） 若若 ，则，则 ( )YYYYNNNN逻逻辑演算法辑演算法: : 根据定义，利用逻辑等价式和逻辑推理规则集合演算法集合演算法: : 利用集合恒等式和已知的集合结论七、
24、集合恒等式的几种证明方法七、集合恒等式的几种证明方法 3.2集合的运算逻逻辑演算法辑演算法( (根据定义根据定义) ) 题型题型: 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集合的运算例1：分配律(证明)A(BC)=(AB)(AC)证明: x, xA(BC) xA x(BC) (定义) xA (xB xC) (定义) (xAxB)(xAxC) (命题逻辑分配律) (xAB)(
25、xAC) (定义) x(AB)(AC) (定义) A(BC)=(AB)(AC)成立逻辑演算法逻辑演算法( (根据定义根据定义) ) 3.2集合的运算例2：零律(证明) A = 证明: x, xA xA x (定义) xA F (定义) F (命题逻辑零律) A = 成立逻辑演算法逻辑演算法( (根据定义根据定义) ) 3.2集合的运算例3.排中律(证明)AA = E证明: x, xAA xA xA (定义) xA xA (定义) xA (xA) (定义) T (命题逻辑排中律) AA = E 成立逻辑演算法逻辑演算法( (根据定义根据定义) ) 3.2集合的运算2024/8/13372024/
26、8/1337即即 且且 ，因此因此 ，故故 。反之反之 若若 ，则则 且且 ，即即 且且 ，因此因此 。由上证得，由上证得，例例 4 4 证明证明证明证明 若若 则则 且且 ，故故 。逻辑演算法逻辑演算法( (根据定义根据定义) )集合演算法（格式）集合演算法（格式）题型:A=B.题型:AB.证明:A证明:A=(?)(?)=BBA=B.#AB.# 3.2集合的运算例1：吸收律(一式证明)A(AB)=A证明: A(AB) = (AE)(AB) (同一律) = A(EB) (逆用分配律) = AE (零律) = A (同一律) A(AB)=A集合演算法集合演算法 3.2集合的运算例2：吸收律(二式
27、证明)A(AB) = A证明: A(AB) = (AA)(AB) (分配律) = A(AB) (幂等律) = A (吸收律第一式) A(AB) = A集合演算法集合演算法 3.2集合的运算集合演算法（格式）续集合演算法（格式）续题型题型: A B 证明: AB (或AB) =(?) = A (或B) AB. # 说明说明: 化化 成成=题型题型: A=B证明证明: ( ) A B ( ) A B A = B. #说明说明: 把把=分成分成 与与 A B=AA BA B=BA B2024/8/13422024/8/1342 小小结结：本本节节介介绍绍了了集集合合的的基基本本概概念念、集集合合的的运运算算和和运运算算定定律及律及幂集的概念。重点掌握集合的基数及幂集的概念。幂集的概念。重点掌握集合的基数及幂集的概念。作业：作业：P86 P86 （4 4）a a，c c（6 6），（），（9 9） 3.2集合的运算
