《离散数学》集合的基本概念和运算

1、第第3 3章章 集合的概念集合的概念 集合的概念2 集合是数学中最重要的概念，集合理论是数学中最重要的理论。 十九世纪七十年代，威尔斯特拉斯、戴德金、康托尔等人深入研究实数理论，建立起极限论的基本定理，不仅为微积分建立起严格的理论基础，也导致了集合论的诞生。 集合论分朴素集合论和公理化集合论。 集合论被广泛应用在计算机科学中，如数据结构、操作系统、数据库、知识库、编译原理、形式语言、程序设计、人工智能、信息检索、CAD 等。3一、什么是集合？-只能给予直观的描述。所谓集合（Set），就是把人们直观的或想象中的某些确定的能够区分的对象汇合在一起组成的一个整体。-组成集合的各个对象，称为这个集合的

2、元素（Element）或成员（Member）。通常，用大写字母A，B，C，表示集合，用小写字母a，b，c，表示元素。集合与元素之间的关系“属于”关系- a a A aA a B B3.1 3.1 集集合合的的基基本本概概念念4二、集合的表示二、集合的表示列举法列举法-将集合中的元素一一列举出来，或者列出足够多的元素以反映集合中成员的特征，并用花括号将元素括起来，其表示形如：A=a1，a2，an A=a1，a2，a3, -列举法必须把元素的全体尽列出来，不能遗漏任何一个，并且集合中的元素没有顺序之分且不重复。3.1 3.1 集集合合的的基基本本概概念念5谓词表示法-用一个谓词来描述集合中元素具有

3、的共同性质。表示形式如A=x|P(x)意义是：集合A 由且仅由满足性质P 的那些对象所组成，也就是说aA 当且仅当a 满足性质P。3. 3.1 1 集集合合的的基基本本概概念念6练习练习用列举法表示下列集合用列举法表示下列集合（1）A=a|aP且且a2020（2）B=a|a|4且且a为奇为奇数数2. 用描述法表示下列集合用描述法表示下列集合 (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且且x1001002n|nN且且n10n10 3.1 3.1 集集合合的的基基本本概概念念7集合与元素集合与元素

4、元素与集合的关系：隶属关系 属于，不属于 实例 A= x | xRx2-1=0 , A=-1,1 1A, 2A注意：对于任何集合A和元素x(可以是集合)， xA和 xA 两者成立其一，且仅成立其一. 8隶属关系的层次结构隶属关系的层次结构例例 3.1A= a, b,c, d, d b,c Ab Ad Ad Ad A 9 包含（子集）包含（子集） A B x (x A x B) 不包含不包含 A B x (x A x B) 相等相等 A = B A B B A 不相等不相等 A B 真包含真包含 A B A B A B 不真包含不真包含 A B 思考：思考： 和和 的定义的定义 注意注意 和和

5、是不同层次的问题是不同层次的问题一、集合之间的关系一、集合之间的关系 例例1 A=a, b, c, d, B=a, e, x, y, z, C=a, x 则则 C B，C A，B A， A B3.1 3.1 集集合合的的基基本本概概念念10集合的包含关系具有如下几条性质： 对任意集合A，A； 自反性：AA反对称性：若AB且BA，则AB传递性：若AB且BC，则A C若|A|n，则A有2n个子集3.1 3.1 集集合合的的基基本本概概念念11空集与全集空集与全集空集 不含任何元素的集合实例 x | x2+1=0 xR 就是空集定理 空集是任何集合的子集 A x (xxA) T 推论 空集是惟一的.

6、证 假设存在1和2，则12 且12，因此 1=2全集 在一个具体问题中，如果所涉及的集合都是某个 集合的子集，则称这个集合为全集，记作E 全集具有相对性 在给定问题中，全集包含任何集合，即A (AE )12三、幂集（三、幂集（PowerSetPowerSet）定义定义1.2.2 1.2.2 给定集合给定集合A A，以，以A A的所有子集为元素的所有子集为元素的集合称为的集合称为A A的幂集，记作的幂集，记作P(A)P(A)。例例3 A=3 A=，B=，a，a P（A） P（B），a，a，a，a，a，a，a，a3.1 3.1 集集合合的的基基本本概概念念13集合的基数 设A 为任一集合，用|A|

7、(或#A)表示A中不同元素的个数，称为集合A的基数，有：若|A|=0，则称A 为空集合（Empty Set），记为；若|A|为某自然数，则称A 为有限集合（Finite Set）；若|A|为无穷，则称A 为无限集合（Infinite Set）3.1 3.1 集集合合的的基基本本概概念念14:a1,a2 ,an:a1, a2,a1, a3 :a1, a2 , , an证明证明 设设A= a1, a2 , , an,从从n个元素中选个元素中选取取m个元素的方法有个元素的方法有 种，所以种，所以A的子集的子集个数为个数为mnC0nC1nC2nCnnC注：注：设设A是有限集，则是有限集，则 .( )2

8、AP A 0121|( )|22AnnnnnnnnP ACCCCC3.1 3.1 集集合合的的基基本本概概念念15 练习练习1 1 设设A=a,b,c,a,a,bA=a,b,c,a,a,b，试指出下试指出下列论断是否正确？列论断是否正确？ (1) (1)a a A ( ) (8)bA ( ) (8)b A ( )A ( ) (2)a (2)a A ( ) (9)a,bA ( ) (9)a,b A ( )A ( ) (3)a (3)a A ( ) (10)a,bA ( ) (10)a,b A ( )A ( ) (4) (4) A ( ) (11)cA ( ) (11)c A ( )A ( ) (

9、5) (5) A ( ) (12)cA ( ) (12)c A ( )A ( ) (6)b (6)b A ( ) (13)cA ( ) (13)c A ( )A ( ) (7)b (7)b A ( ) (14)a,b,cA ( ) (14)a,b,c A ( )A ( ) 3.1 3.1 集集合合的的基基本本概概念念16 练习练习2 2 列出集合列出集合A=1,2A=1,2的全部子集。的全部子集。 解解 因为因为是任何集合的子集，所以是任何集合的子集，所以是是A A的子集。由的子集。由A A中任意一个元素所组成的中任意一个元素所组成的集合是集合是A A的子集，所以的子集，所以11和和22是是A

10、 A的子的子集。由集。由A A中任意两个元素所组成的集合是中任意两个元素所组成的集合是A A的子集，所以的子集，所以1,21,2是是A A的子集。因为的子集。因为A A中中只有两个元素，故只有两个元素，故A A再没有其他的子集。再没有其他的子集。 由上可知，由上可知，A A有四个子集：有四个子集：，11，22，1,21,2。 典典型型习习题题17练习练习3 3 设有集合设有集合A,B,CA,B,C和和D, D, 下述论断是否下述论断是否正确？说明理由。正确？说明理由。（1 1）若）若A A B,BB,B C,C,则则A A C C 解解 正确。因为正确。因为B B C C，所以集合，所以集合B

11、 B的每一的每一个元素也是集合个元素也是集合C C的元素，由的元素，由A A B B知知A A是是B B的的一个元素，因此一个元素，因此A A也是也是C C的一个元素，故的一个元素，故A A C C。 （2 2）若若A A B,BB,B C,C,则则A A C C 解解 错误。举反例如下：设错误。举反例如下：设A=aA=a，B=a,bB=a,b，C=a,b,cC=a,b,c，显然，显然A A B B，B B C C，但，但A A不是不是C C的子集。因为的子集。因为a a A A，但，但a a C C。 典典型型习习题题18例例1.3.1 设设A=a,b,c, B=c,d,f , C=b,e则

12、则 AB定义定义3.7 A、B是任意集合，由属于是任意集合，由属于A或属于或属于B的的所有元素组成的集合称为所有元素组成的集合称为A与与B的并集，记的并集，记作作 。即。即BAfdcbaBA,ecbaCA,fedcbCB,显然：显然： BABBAA,BuAuuBA或|BA3.23.2集集合合的的基基本本运运算算19例例1.3.2 设设A=a,b,c,d, B=d,f,a, C=e,f,g则则 显然：显然： AB定义定义3.7 设有设有A、B是是任意两个集合，属于任意两个集合，属于A同同时又属于时又属于B的所有元素组成的集合称为的所有元素组成的集合称为A与与B的交的交集，记作集，记作 。即。即B

13、AadBA,CAfCBBBAABABABuAuuBA且|3.23.2集集合合的的基基本本运运算算20定义3.7 设A、B是任意两个集合，所有属于A而不属于B的元素组成的集合，称为B对A的相对补集，记作A-B。即例例1.3.3 设设A=a,b,c,d, B=d,f,a, C=e,f,g 则则B-A= f , C-A= e ,f , g =C BAAB|ABx xAxB且ABAB重要性质：重要性质：3.23.2集集合合的的基基本本运运算算21A A定义定义3.8 E为全集，为全集，A为为E的子集，的子集，E-A称为称为A的的绝对补集，记作绝对补集，记作 。即。即 A AEAxExA且3.23.2集

14、集合合的的基基本本运运算算22例如例如 设设U=1，2，3，4，10， A=2，4，6，8，10 则则又例如又例如 设设U=I（I是整数集），是整数集）， 则则1,3,5,7,9AUA0,|iIiiA且|0AUAi iIi且3.23.2集集合合的的基基本本运运算算23定义定义1.4.1 A、B为任意两个集合，所有属于为任意两个集合，所有属于A而而不属于不属于B或属于或属于B而不属于而不属于A的元素组成的集合，的元素组成的集合，称为称为A与与B的的，记作，记作 。即。即BA()()ABA BB AABBAABBA3.23.2集集合合的的基基本本运运算算24关于运算的说明关于运算的说明运算顺序：

15、和幂集优先，其他由括号确定并和交运算可以推广到有穷个集合上，即 A1A2An= x | xA1xA2xAn A1A2An= x | xA1xA2xAn某些重要结果 ABA AB AB=（后面证明） AB= AB=A25只有一、二年级的学生才爱好体育运动只有一、二年级的学生才爱好体育运动 F:一年级大学生的集合一年级大学生的集合 S：二年级大学生的集合：二年级大学生的集合 R：计算机系学生的集合：计算机系学生的集合 M：数学系学生的集合：数学系学生的集合 T：选修离散数学的学生的集合：选修离散数学的学生的集合 L：爱好文学学生的集合：爱好文学学生的集合 P：爱好体育运动学生的集合：爱好体育运动学

16、生的集合T (M R) SR S T(M F) T=M L PP F SS (M R) P除去数学和计算机系二年级学生外都不除去数学和计算机系二年级学生外都不选修离散数学选修离散数学例例所有计算机系二年级学生都选修离散数学所有计算机系二年级学生都选修离散数学数学系一年级的学生都没有选修离散数学数学系一年级的学生都没有选修离散数学数学系学生或爱好文学或爱好体育运动数学系学生或爱好文学或爱好体育运动26例例分别对条件分别对条件(1)到到(5)，确定，确定 X 集合与下述那些集合相等。集合与下述那些集合相等。 S1 = 1, 2, , 8, 9 , S2= 2, 4, 6, 8 , S3= 1, 3

17、, 5, 7, 9 , S4 = 3, 4, 5 , S5= 3, 5 若若 X S5=, 则则 X 若若 X S4, X S2=, 则则 X 若若 X S1，X S3, 则则 X 若若 X S3=, 则则 X 若若 X S3，X S1, 则则 X= S2= S5= S1, S2, S4= S3, S5与与 S1, . , S5 都不等都不等3.23.2集集合合的的基基本本运运算算27对于全集合对于全集合E E的任意子集的任意子集A、B、C，有：，有： ABBA交换律交换律ABBACBACBA)()(结合律结合律CBACBA)()(分配律分配律)()()(CABACBA)()()(CABACB

18、A恒等律恒等律AAAEA3.23.2集集合合的的基基本本运运算算28互补律互补律UAA AA否定律否定律AA )(幂等律幂等律AAAAAA零一律零一律UUAA吸收律吸收律ABAA)(ABAA)(德德 摩根律摩根律BABA)(BABA)(对偶原理：把一个等式中的对偶原理：把一个等式中的中的中的，E和和的分别代以的分别代以，和和E后得到后得到另一等式另一等式3.23.2集集合合的的基基本本运运算算29()()()()()()()()()iff,ABCABCABCABACABABABABABABABABABAC thenBC()()ABABBA AA= A =A A E=A BB AA3.23.2集

19、集合合的的基基本本运运算算30三、集合包含的证明方法集合包含的证明方法证明证明 X Y-命题演算法命题演算法-包含传递法包含传递法-等价条件法等价条件法-反证法反证法-并交运算法并交运算法3.23.2集集合合的的基基本本运运算算313.1.命题演算法命题演算法证证 X Y任取任取 x ， x X x Y证明：证明：A B P(A) P(B) 任取任取x x P(A) x A x B x P(B) 任取任取x x A x A x P(A) x P(B) x B x B 323.2.包含传递法包含传递法证证 X Y找到集合找到集合T 满足满足 X T 且且 T Y，从而有，从而有X Y。例例4 A

20、 B A B证证 A B A A A B 所以所以 A B A B333.3.利用包含的等价条件利用包含的等价条件证证 X Y A-BABABBABA例例5 A C B C A B C 证证 A C A C=C B C B C=C (A B) C=A (B C)=A C=C (A B) C=C A B C 命题得证命题得证343.4.反证法反证法证证 X Y欲证欲证X Y, 假设命题不成立，必存在假设命题不成立，必存在 x 使得使得 x X 且且 x Y. 然后推出矛盾然后推出矛盾. 例例6 证明证明 A C B C A B C证证 假设假设 A B C 不成立，不成立， 则则 x (x A

21、B x C) 因此因此 x A 或或 x B，且，且 x C 若若 x A, 则与则与 A C 矛盾；矛盾； 若若 x B, 则与则与 B C 矛盾矛盾. 353.5.3.5.利用已知包含式并交运算利用已知包含式并交运算由已知包含式通过运算产生新的包含式由已知包含式通过运算产生新的包含式 X X Y Y X X Z Z Y Y Z, XZ, X Z Z Y Y Z Z 例例7 7 证明证明 A A C C B B C C A A C C B B C C A A B B证证 A A C C B B C C， A A C C B B C C 上式两边求并，得上式两边求并，得 (A(A C)C) (

22、 (A A C) C) ( (B B C)C) ( (B B C)C) (A (A C)C) ( (A AC) C) ( (B B C)C) ( (B BC)C) A A (C(CC) C) B B ( (C CC) C) A A E E B B E E A A B B36四、集合相等的证明方法集合相等的证明方法证明证明 X=Y-命题演算法命题演算法-等式代入法等式代入法-反证法反证法-运算法运算法37 例例8 证明证明 A (A B)=A （吸收律）（吸收律） 证证 任取任取x, x A (A B) x A x A B x A (x A x B) x A 4.1 4.1 命题演算法证明命题演

23、算法证明X=YX=Y任取任取 x ， x X x Y x Y x X 或者或者 x X x Y 384.2.4.2.等式替换证明等式替换证明X=YX=Y例例9 证明证明A (A B)=A （吸收律）（吸收律）证证 (假设交换律、分配律、同一律、零律成立假设交换律、分配律、同一律、零律成立) A (A B) =(A E) (A B) 同一律同一律 =A (E B) 分配律分配律 =A (B E) 交换律交换律 =A E 零律零律 =A 同一律同一律不断进行代入化简，最终得到两边相等不断进行代入化简，最终得到两边相等3.23.2集集合合的的基基本本运运算算394.3.4.3.反证法证明反证法证明X

24、=YX=Y例例10 证明以下等价条件证明以下等价条件 A B A B=B A B=A A B= (1) (2) (3) (4) 证明顺序：证明顺序： (1) (2), (2) (3), (3) (4), (4) (1) 假设假设 X=Y 不成立，则存在不成立，则存在 x 使得使得 x X且且x Y，或者或者存在存在 x 使得使得 x Y且且x X，然后推出矛盾，然后推出矛盾. 40(1) (2)显然显然B A B，下面证明，下面证明A B B. 任取任取x， x A B x A x B x B x B x B因此有因此有A B B. 综合上述（综合上述（2）得证）得证. (2) (3) A=A

25、 (A B) A=A B （将（将A B用用B代入代入) 3.23.2集集合合的的基基本本运运算算41(3) (4)假设假设A B, 即即 x A B，那么，那么x A且且x B. 而而 x B x A B. 从而与从而与A B=A矛盾矛盾.(4) (1) 假设假设A B不成立，那么不成立，那么 x (x A x B) x A B A B与条件（与条件（4）矛盾）矛盾. 424.4.4.4.集合运算法证明集合运算法证明X=YX=Y例例11 证明证明A C=B C A C=B C A=B证证 由由 A C=B C 和和 A C=B C 得到得到 (A C)-(A C)=(B C)-(B C) 从

26、而有从而有 A C=B C A=B（消去律）（消去律） 因此因此 A C=B C (A C) C =(B C) C A (C C) =B (C C) A=B A=B由已知等式通过运算产生新的等式由已知等式通过运算产生新的等式 X=Y X Z=Y Z, X Z=Y Z，X-Z=Y-Z3.23.2集集合合的的基基本本运运算算43集合集合 A 的的基数基数：集合：集合A中的元素数，记作中的元素数，记作 cardA有穷集有穷集 A： cardA=|A|=n，n为自然数为自然数.有穷集的实例：有穷集的实例： A= a,b,c, cardA=|A|=3； B= x | x2+1=0, x R, cardB

27、=|B|=0 无穷集的实例：无穷集的实例： N, Z, Q, R, C 等等 集合的基数与有穷集合集合的基数与有穷集合3.33.3集集合合的的计计数数44包含排斥原理包含排斥原理定理定理 设设 S 为有穷集，为有穷集，P1, P2, , Pm 是是 m 种性质，种性质，Ai 是是 S 中具有性质中具有性质 Pi 的元素构成的子集，的元素构成的子集，i=1, 2, , m.则则 S 中不具有性质中不具有性质 P1, P2, , Pm 的元素数为的元素数为|.|)1(.|.|2111121mmmkjikjimimjijiimAAAAAAAAASAAA 3.33.3集集合合的的计计数数45|.|)

28、1(.|.|21111121mmmkjikjimimjijiimAAAAAAAAAAAA S S中至少具有一条性质的元素数为中至少具有一条性质的元素数为证明证明 |.|.|.|212121mmmAAASAAASAAA 将定理将定理 1 1 代入即可代入即可推论推论3.33.3集集合合的的计计数数46解：解：S = x | x Z, 1 x 1000 , 如下定义如下定义 S 的的 3 个子集个子集 A, B, C： A= x | x S, 5 | x ， B= x | x S, 6 | x ， C= x | x S, 8 | x 例例1 求求1到到1000之间（包含之间（包含1和和1000在内

29、）既不能在内）既不能被被 5 和和6 整除，也不能被整除，也不能被 8 整除的数有多少个？整除的数有多少个？应用应用3.33.3集集合合的的计计数数47对上述子集计数：对上述子集计数： |S|=1000, |A|= 1000/5 =200, |B|= 1000/6 =166， |C|= 1000/8 =125, |A B|= 1000/30 =33, |B C| = 1000/40 =25, |B C|= 1000/24 =41, |A B C| = 1000/5,6,8的最小公倍数的最小公倍数 1000/120 =8, 代入公式代入公式 N = 1000 (200+166+125)+(33+25+41) 8=600例例1（续）（续）3.33.3集集合合的的计计数数48文氏图法文氏图法 求求1到到1000之间（包含之间（包含1和和1000在内）既不能被在内）既不能被 5 和和6 整整除，也不能被除，也不能被 8 整除的数有多少个？整除的数有多少个？ |A B