离散数学集合

1、第3章 集合1 集合的概念及其表示2 集合的运算3 集合定律4包含容斥原理5多重序元和笛卡尔乘积1 集合的概念及其表示1、集合、集合 2、集合的元素、集合的元素3、有限集和无限集、有限集和无限集 4、集合的表示方法、集合的表示方法5、集合相等、集合相等 6、子集和包含、子集和包含7、真子集和真包含、真子集和真包含 8、空集、空集9、全集、全集 10、幂集、幂集1、集合具有某种特殊性质的客体的聚合具有某种特殊性质的客体的聚合集合是一种集合是一种不可精确定义不可精确定义的数学基本概的数学基本概念，只能给予一种念，只能给予一种描述描述。用大写的英文字母表示集合用大写的英文字母表示集合集合举例(1)全

2、体中国公民的集合。(2)平面上点的集合。(3)宇宙中全部星球的集合。2、集合的元素属于集合的任何客体属于集合的任何客体集合的元素集合的元素集合的成员集合的成员用小写字母表示用小写字母表示元素元素a属于集合属于集合AaAaAa属于属于A元素元素a不属于集合不属于集合Aa a A Aa不属于不属于A3、有限集和无限集一个集合的元素个数是有限的一个集合的元素个数是有限的有限集有限集一个集合的元素个数是无限的一个集合的元素个数是无限的无限集无限集有限集和无限集举例全体计算机全体计算机20072007级学生的集合级学生的集合自然数集合自然数集合有限集有限集无限集无限集4、集合的表示方法、集合的表示方法（

3、1）列举法列举法：（2）描述法描述法：列出集合中的元素列出集合中的元素元素之间用元素之间用逗号逗号分开分开用用花括号花括号括起来括起来用集合中元素所满足的性质表示集合用集合中元素所满足的性质表示集合谓词法谓词法构造法构造法集合的表示方法集合的表示方法列举法：A=2,4,6,8,10描述法：BC=x| =x| 整数集合整数集合x是大于等于2且小于等于10的偶数x I x10常用的集合符号常用的集合符号I:整数集合；整数集合；N：自然数集合；：自然数集合；R：实数集合；：实数集合；I+:正整数集合；正整数集合；5、集合相等、集合相等公理：公理：集合集合A集合集合B集合集合A和和B相等相等A和和B具

4、有具有相同的元素相同的元素A=B集合相等的解释集合相等的解释集合集合A A的的每一个每一个元素都是集合元素都是集合B B的一个元素；的一个元素；集合集合B B的的每一个每一个元素都是集合元素都是集合A A的一个元素；的一个元素；A=B ( x)( )x Ax B)( x)( )x Bx A)A=B ( x)(x Ax B)例：一个集合可以做为例：一个集合可以做为另一个集合的元素另一个集合的元素S=a, 1,2, p, qS中共4个元素，分别为：a1,2pq1,2 Sq S1 S 2 Sq S集合的特点集合的特点（1）元素的确定性元素的确定性（2） 互异性互异性（3） 无序性无序性集合中的元素是

5、确定的集合中的元素是确定的aA或或a A二者必居其一二者必居其一集合中的每个元素均不相同集合中的每个元素均不相同集合中元素没有先后顺序集合中元素没有先后顺序集合的举例特点集合的举例特点无序性：a,b,ca,b,c= b,c,a互异性：a,b,a,c,a6、子集和包含、子集和包含集合集合A集合集合BA A的的每一个每一个元素都是元素都是B B的元素的元素A为为B的子集的子集A BA包含于包含于BB包含包含AB AA B ( x)( )x Ax B子集举例子集举例已知：已知：A=aA=a，B=a,bB=a,b，C=a,b,cC=a,b,c则：则：A A B B B B C CA A C C证明集合

6、相等的充分必要条件证明集合相等的充分必要条件定理：定理：集合集合A A和和B B相等的充分必要条件是：相等的充分必要条件是：A A和和B B互为子集互为子集即：即： A=B A A B B B B A A（1 1）必要性证明）必要性证明已知已知: : A=B 证明证明: : A BB A A=B由公由公理理A和和B有相同的元素有相同的元素即：即： ( x)(x Ax B) ( x)(x Bx A)A BB AA=B A BB A（2 2）充分性证明）充分性证明已知已知: : A BB A证明证明: :A=B反证反证法法假设假设ABA和和B的元素不完全相同的元素不完全相同( x)( x Ax B

7、)与已知与已知A B相矛盾相矛盾( x)( x Bx A)与已知与已知B A相矛盾相矛盾A=B7 7、真子集和真包含、真子集和真包含集合集合A集合集合BA A的的每一个每一个元素都是元素都是B B的元素的元素A为为B的真子集的真子集A BA真包含于真包含于BB真包含真包含AA B A BABx Ax BB B中至少有一个元素不属于中至少有一个元素不属于A AA B （ x)( )( y)( )y By A8 8、空集、空集不包含任何元素的集合是空集不包含任何元素的集合是空集 例：例： 定理：对于任意集合定理：对于任意集合A A，均有，均有 A A证明方法证明方法1 1：反证法反证法假设假设 A

8、为假为假( x)( x x A)不包含任何元素不包含任何元素这与这与的定义相矛盾的定义相矛盾假设错误假设错误 A证明方法证明方法2 2：注意：对于任意的非空集合注意：对于任意的非空集合A A至少有两个子集至少有两个子集A A和和。设设x是是A中的任意元素中的任意元素x 假单条件命题单条件命题: x x A真善意的推善意的推定定任意任意性性（ x)(x x A)真 A AA A9 9、全集、全集在一定范围内在一定范围内, ,若所有集合均为某一集若所有集合均为某一集合的子集合的子集, ,则该集合称为则该集合称为全集全集E求子集举例求子集举例A=1A=1，2 2，33，求，求A A的所有子集。的所有

9、子集。解：解：1231，21，32，31，2，323=8个子集个子集集合的元素个数1010、幂集、幂集给定集合给定集合A,A,由集合由集合A A的所有子集为元素的所有子集为元素组成的集合组成的集合, ,称为集合称为集合A A的的幂集幂集(A)=(A)x| x A幂集举例幂集举例A=1A=1，2 2，33，求，求A A的幂集的幂集解：解：(A)=, 1, 2, 3, 1(A)=, 1, 2, 3, 1，2, 12, 1，3, 23, 2，3, 13, 1，2 2，33定理定理如果有限集合如果有限集合A有有n个元素，则它的幂个元素，则它的幂集集(A)(A)有有2 2n n个元素。个元素。定理证明定

10、理证明集合集合A中有中有n个元素个元素从从n个元素中选取个元素中选取1个元素的方案共有：个元素的方案共有：Cn1从从n个元素中选取个元素中选取2个不同元素的方案共有：个不同元素的方案共有：Cn2从从n个元素中选取个元素中选取i个不同元素的方案共有：个不同元素的方案共有：Cni从从n个元素中选取个元素中选取n个不同元素的方案共有：个不同元素的方案共有：CnnA的不同子集的数目：的不同子集的数目：Cn0 +Cn1 +Cn2 +Cn3 + Cnn(x+y)(x+y)n n = =定理证明定理证明( (续续) )即即:(A)有有2n个元素个元素xn+Cn1xn-1y+Cn2xn-2y2+Cnnynx=

11、y=1(1+1)(1+1)n n = =1+ Cn1+ Cn2+ Cnn=2=2n n 2 集合的运算1、交运算（、交运算（ ）2、并运算（、并运算（ ）3、差分运算（）、差分运算（）4、对称差分运算（、对称差分运算（ ）1 1、交运算（、交运算（ ）集合集合A集合集合B所有所有共同元素共同元素组成的集合组成的集合A和和B的交集的交集ABAB = x|xAxBABAB的文氏图表示的文氏图表示AB交运算的性质交运算的性质(1)等幂律等幂律: AA= A(2)零律零律:A= (3)同一律同一律: AE= A(4)交换律交换律:AB= BA(5)结合律结合律: (AB)C=A(BC)AB AAB B

12、证明：证明：AB=BAAB=BA设设x是交集是交集ABAB中的任意元素中的任意元素x x ABABx x AxAx B Bx x BxBx A Ax x BABA AB=BA AB=BA集合不相交集合不相交集合集合A集合集合B没有共同的元素没有共同的元素A和和B不相交不相交AB交运算举例交运算举例A=1,2,5,B=2,4,C=1,4A=1,2,5,B=2,4,C=1,4则：则： AB=AB= 22AC=AC= 11BC=BC= 44ABC=ABC=2 2、并运算（、并运算（ ）集合集合A集合集合B所有元素所有元素组成的集合组成的集合A和和B的并集的并集A BAB =x|xAxB并运算的性质并

13、运算的性质(1)等幂律等幂律:AA=A(2)零律零律:AE=E(3)同一律同一律:A=A(4)交换律交换律:AB=BA(5)结合律结合律:(AB)C=A(BC)A ABB AB并运算举例并运算举例A=1,2,5,B=2,4,C=1,4A=1,2,5,B=2,4,C=1,4则：则： A AB=B= 1,2,4,51,2,4,5A AC=C= 1 ,2,4,51 ,2,4,5BC=BC= 1,2,41,2,4ABC=ABC= 1,2,4,51,2,4,5定理：分配率定理：分配率集合集合A集合集合B集合集合C对对 、 对对满足分配率满足分配率A(BC)= (AB)(AC)A(BC)= (AB)(AC

14、)定理：吸收律定理：吸收律设设A、B为任意的两个集合，则：为任意的两个集合，则：A(AB)= AA(AB)=A吸收律的证明吸收律的证明A(AB)=A（1 1）A A(AB)(AB)同一律同一律=(AE)(AB)分配率分配率=A(EB)零律零律=AE同一律同一律=A吸收律的证明吸收律的证明A(AB)=A(方法方法1)（1）A(AB)同一律同一律=(A)(AB)分配率分配率=A(B)零律零律=A同一律同一律=AA(AB)吸收律的证明吸收律的证明A(AB)=A (方法方法2)等幂律等幂律=(AA)(AB)分配率分配率A(AB)吸收律吸收律(1)=A定理定理A A B BABB且且ABA定理证明：必要

15、性定理证明：必要性(只证明只证明ABB)已知：已知：A B证明：证明：ABBAB BB ABAB B对任意的对任意的xABxA xB(已知已知A B)xB xB等幂律等幂律xBAB B B AB由由运算的性质运算的性质B AB综上：综上： ABB定理证明：充分性定理证明：充分性已知：已知： ABB证明：证明：A B对任意的对任意的xAxAB(已知已知ABB )xBA B综上：综上： 定理得证定理得证3 3、差运算（、差运算（- - ）集合集合A集合集合B属于属于A而不属于而不属于B的一切元素组成的集合的一切元素组成的集合A和和B的差集的差集A-BA-B =x|xAx BB对对A的的相相对补集对

16、补集绝对补集（补集）绝对补集（补集）全集全集E集合集合AA对对E的补集的补集EAA的绝对补集的绝对补集补集补集A=x|xEx AE-A =x|x A差运算举例差运算举例A=0,1,2,B=1,2,3A=0,1,2,B=1,2,3则：则：A-BA-BE=1,2,3,4,A=1,2=0=0B-AB-A=33则：则：A=A= 3,43,4差运算举例差运算举例设：设：Ax|x是素数是素数则：则：A-B1,2,3,5,7,11,13,17B=x|x是奇数是奇数=1,3,5,7,9,11,13,15,17=2除除2之外的素数之外的素数均为奇数均为奇数补运算的性质补运算的性质(1)(A)= A(2)E=(3

17、)AA= E(4)AA= 定理：德定理：德.摩根定律摩根定律设任意两个集合设任意两个集合A和和B,则：则：(1)(AB)=ABAB(2)(AB)=证明：证明：(AB)=AB对任意的对任意的x (AB)，有：，有： x (AB)x AB(x AB)(x Ax B)(x A) ( x B) x Ax B x Ax B x AB 定理定理设任意两个集合设任意两个集合A和和B,则：则：(1)A-B= AB(2)A-B= A-(AB)利用文氏图证明利用文氏图证明A-B=ABABAB定理定理: : 对满足分配率对满足分配率设任意三个集合设任意三个集合A、B、C,则：则：A(B-C)= (AB)-(AC)定

18、理证明定理证明左式左式A(B-C)= ABC右式右式(AB)-(AC)(AB)(AC)(AB)(AC)=(ABA)(ABC)=(ABC)= ABC所以：所以： A(B-C)= (AB)-(AC)定理定理设任意两个集合设任意两个集合A、B,若若A B，则：，则：(1)B A(2)(B-A)A= B定理证明定理证明: (B-A)A=B(B-A)A=(BA)A=(AB)(AA)分配率分配率= (AB)E=B=AB A B4 4、对称差运算、对称差运算( ( ) )集合集合A集合集合B或属于或属于A,或属于或属于B,但不能既属于但不能既属于A又属于又属于B的元素组成的元素组成A和和B的对称差的对称差A

19、 BA B =x| xA xB(AB)(BA)ABBA对称差运算的性质对称差运算的性质(1)交换律交换律B AA B=(2)结合律结合律(A B) C= A (B C)(3)A = A(4)A A= (5)A B=(AB)(BA)=(AB)(BA)(AB)-(AB)证明：证明：A =AA (A)-(A)=A-=A3 集合定律1、等幂律、等幂律2、结合律、结合律3、交换律、交换律4、分配率、分配率5、同一律、同一律6、零律、零律7、补余律、补余律8、吸收律、吸收律9、德、德.摩根定律摩根定律10、双重否定定律、双重否定定律11、包含关系式、包含关系式12、蕴涵式、蕴涵式1、等幂律(、 )A AA

20、=AA=AA AA=A A=A 对应的命题公式：对应的命题公式：(P(PP PP)P)(P(PP PP)P)2、结合律 (、 )(A(AB)B)C=AC=A(BC)(BC)(A(AB)B)C=AC=A(BC)(BC)对应的命题公式：对应的命题公式：(PQ)R(PQ)RP(QR)P(QR)(PQ)R(PQ)RP P(QR)(QR)3、交换律(、 )A AB=BAB=BAAB=BAAB=BA对应的命题公式：对应的命题公式：PQPQQPQPPQPQQPQP4、分配率(对 、 对)A A(B(BC)=(AC)=(AB)(AC)B)(AC)A A(B(BC)=(AC)=(AB)(AC)B)(AC)对应的

21、命题公式：对应的命题公式：P(QR)P(QR)(P(PQ)(PR)Q)(PR)P(QR)P(QR)(P(PQ)(PR)Q)(PR)5、同一律A=AA=AAE=AAE=A对应的命题公式：对应的命题公式：PFPFP PPTPTP P6、零律AE=EAE=EA= A= 对应的命题公式：对应的命题公式：PTPTT TPFPFF F7、补余律AA=EAA=对应的命题公式：对应的命题公式：P PTP PF8、吸收律A (A B)=AA (A B)=A对应的命题公式：对应的命题公式：P(PQ)P P(PQ)P9、德.摩根定律(AB)=AB(AB)=A BE= =E对应的命题公式：对应的命题公式： (PQ)P

22、 Q (PQ)P Q T F F T10、双重否定定律(A)=A对应的命题公式：对应的命题公式：PP11、包含关系式AB AAB BA AB B AB A-B A12、蕴涵式(AB ) (AB)(A)(B)(A)(B)4包含容斥原理1、两个集合的包含排斥原理、两个集合的包含排斥原理2、三个集合的包含排斥原理、三个集合的包含排斥原理有限集合的计算不等式A为有限集合为有限集合:B为有限集合为有限集合:A集合元素个数为集合元素个数为|A|B集合元素个数为集合元素个数为|B|(1)|AB |A|+|B|(2)|AB |min(|A|,|B|)(3)|A- B|A|-|B|(4)|A B|A|+|B|-

23、2|AB|=1、两个集合的包含排斥原理|AB |= A为有限集合为有限集合:B为有限集合为有限集合:A集合元素个数为集合元素个数为|A|B集合元素个数为集合元素个数为|B|A|+|B|-|AB|包含排斥原理证明 AB = 时时|AB |= |A|+|B| AB 时时|A|AB|AB|B|AB| |AB|A|B|AB|AB|2 |AB|AB |AB|AB| |AB|式式式式和式和式左右相减得左右相减得:|A|B| - |AB | |AB|AB |=|A|+|B|-|AB|AB |=|A|+|B|-|AB|两个集合的包含排斥原理举例某班有某班有50名学生，第一次考试中名学生，第一次考试中26人人成

24、绩为优，第二次考试中成绩为优，第二次考试中21人成绩为优，人成绩为优，已知两次考试中都不为优的共已知两次考试中都不为优的共17人。问两人。问两次考试中都为优的有多少人？次考试中都为优的有多少人？ 利用包含排斥原理进行问题求解A: 第一次考试中成绩为优的学生集合；第一次考试中成绩为优的学生集合；B:第二次考试中成绩为优的学生集合；第二次考试中成绩为优的学生集合；|A|=26|B|=21设设:两次考试中都为优的有两次考试中都为优的有x人人|AB|x；|A-B|26-x； |B-A|21-x；|E|=50|(AB) |=17(26-x)x(21-x)17= 50 x=142、三个集合的包含排斥原理|

25、AB C |= A为有限集合为有限集合:B为有限集合为有限集合:A集合元素个数为集合元素个数为|A|B集合元素个数为集合元素个数为|B|A|+|B|+|C| C为有限集合为有限集合: C集合元素个数为集合元素个数为|C|-|AB|-|AC|-|BC|+| ABC|三个集合的包含排斥原理举例据调查，学生阅读杂志的据调查，学生阅读杂志的 情况如下：情况如下：60读甲类杂志；读甲类杂志；50读乙类杂志；读乙类杂志；50读丙类杂志；读丙类杂志；30读读甲与乙甲与乙类杂志；类杂志；30读读乙与丙乙与丙类杂类杂志；志； 30读读甲与丙甲与丙类杂志；类杂志；10读读3类杂志。问：类杂志。问：（1）确实阅读两

26、类杂志的学生的百分比？）确实阅读两类杂志的学生的百分比？（2）不读任何杂志的学生的百分比？）不读任何杂志的学生的百分比？利用包含排斥原理进行问题求解A:读甲类杂志读甲类杂志的学生集合；的学生集合；|A|=60%;B:读乙类杂志读乙类杂志的学生集合；的学生集合；|B|=50%;C:读丙类杂志读丙类杂志的学生集合；的学生集合；|C|=50%;| AB |=30%;| BC |=30%;| AC |=30%| AB C |=10%确实阅读两类杂志确实阅读两类杂志的学生的百分比的学生的百分比不读任何杂志的学不读任何杂志的学生的百分比生的百分比5多重序元和笛卡尔乘积多重序元和笛卡尔乘积一、多重序元一、多

27、重序元二、笛卡尔乘积二、笛卡尔乘积一、多重序元一、多重序元1、序偶、序偶2、三重序元、三重序元3、n重序元重序元1、序偶、序偶两个具有两个具有固定次序固定次序的客体组成的序列的客体组成的序列序偶的第一个元素序偶的第一个元素序偶的第二个元素序偶的第二个元素两个序偶相等的定义两个序偶相等的定义序偶序偶序偶序偶x=uy=v2、三重序元、三重序元三重序元是一个序偶三重序元是一个序偶第一个元素本身也是个序偶第一个元素本身也是个序偶3、n重序元重序元n重序元是一个序偶重序元是一个序偶第一个元素是第一个元素是(n-1)重序元重序元n重序元的第重序元的第i个坐标个坐标两个两个n重序元相等的定义重序元相等的定义