《03离散数学课件资料》由会员分享，可在线阅读，更多相关《03离散数学课件资料（22页珍藏版）》请在金锄头文库上搜索。
1、 第三章第三章 集合的基本概念和运算集合的基本概念和运算3.13.1 集合的基本概念集合的基本概念3.23.2 集合的基本运算集合的基本运算3.33.3 集合中元素的计数集合中元素的计数2018/8/111离散数学一、集合一、集合集集 合：合：一些可确定的可分辨的事物构成的整体。一些可确定的可分辨的事物构成的整体。用大写字母用大写字母A A, , B B, , C C, , 标记。标记。3.1 3.1 集合的基本概念集合的基本概念集合的元素：集合的元素：一个集合的每一个特定的事物。用小一个集合的每一个特定的事物。用小写字母写字母a a, , b b, , c c, , 标记。标记。如如: :(
2、1) 26(1) 26个英文字母的集合；个英文字母的集合；(2) (2) 坐标平面上所有点的集合。坐标平面上所有点的集合。规定：集合的元素之间彼此相异，无次序关系。规定：集合的元素之间彼此相异，无次序关系。2018/8/112离散数学二、常用的集合二、常用的集合常用的集合记号：常用的集合记号：N N: : 自然数集合自然数集合( (包括包括0 0 ) )Z Z: : 整数集合整数集合Q Q: : 有理数集合有理数集合R R: : 实数集合实数集合C C: : 复数集合复数集合: : 空集空集( (不含任何元素不含任何元素) )E E: : 全集全集2018/8/113离散数学三、集合的表示方法
3、三、集合的表示方法列出集合的所有元素，元素之间用逗号列出集合的所有元素，元素之间用逗号隔开。如隔开。如A A = = a a, , b b, , c c 用谓词概括该集合中元素的属性。用谓词概括该集合中元素的属性。即：即：A A = = x x | | P P ( (x x) ) 如：如：A A = = x x | | x x Z Z 3 3 x x 6 6 1 1、列举法：列举法：2 2、描述法：描述法：元素与集合之间的关系元素与集合之间的关系( ( 属于属于):):若若A A=a a, ,a a, ,b b, ,a a, ,b b,则则a a A A , ,a a A A 2018/8/1
4、14离散数学3 3、真子集真子集：如果如果B B A A且且A A B B，则则B B是是A A的真的真子集。子集。记作记作B B A A。四、集合之间的关系四、集合之间的关系1 1、子子 集：集：集合集合B B中的每个元素都是集合中的每个元素都是集合A A中的元素，中的元素，则则B B是是A A的子集，记作的子集，记作B B A A。符号化为符号化为B B A A x x( (x x B B x x A A) )2 2、相等集：相等集：如果如果A A B B且且B B A A，则则A A与与B B相等相等。记作。记作A A = = B B。符号化为符号化为A A = = B B A A B
5、B B B A A显然：显然：A A A A， A A2018/8/115离散数学解：解：0 0元子集：元子集：，四、集合之间的关系（续）四、集合之间的关系（续）4 4、幂幂 集：集：集合集合A A的全体子集构成的集合，记作的全体子集构成的集合，记作P P ( (A A) )。符号化为符号化为P P ( (A A) = ) = x x | | x x A A 例例1 1：A A = = a a, , b b, , c c ，求，求A A的幂集的幂集P P ( (A A) )。n n 元集元集A A的幂集的幂集P P ( (A A) )含有含有2 2n n个元素。个元素。1 1元子集：元子集：
6、a a, , b b, , c c ，2 2元子集：元子集： a a, , b b, , a a, , c c, , b b, , c c ，P P( (A A) = ) = , , a a, , b b, , c c, , a a, , b b, , a a, , c c, , b b, , c c,a a, , b b, , c c3 3元子集元子集： a a, , b b, , c c 2018/8/116离散数学四、集合之间的关系（续）四、集合之间的关系（续）例例2 2：计算以下幂集。：计算以下幂集。(1) (1) P P( () )；(2) (2) P P( (, ,) )；(3)
7、(3) P P( (1, 2, 31, 2, 3) )。解：解：(1) (1) P P ( () = ) = (2) (2) P P ( (, , ) = ) = , , , , , , , , (3) (3) P P ( (1, 2, 31, 2, 3) = ) = , , 1 1, , 2, 32, 3, , 1, 2, 31, 2, 3 2018/8/117离散数学1 1、并：、并：A AB B = = x x | | x x A A x x B B 一、几种常见的运算一、几种常见的运算3.2 3.2 集合的基本运算集合的基本运算2 2、交：交：A A B B = = x x | | x
8、 x A A x x B B ，若若A A B B = = ，则称则称A A与与B B不交。不交。3 3、相对补：、相对补：A A B B = = x x | | x x A A x x B B （B B对对A A的）的）4 4、绝对补：、绝对补：A A对全集对全集E E的相对补集，记作：的相对补集，记作： A A A = E A = E A A = = x x | | x x E E x x A A 5 5、对称差：、对称差：A A B B = ( = (A A B B) )( (B B A A) = () = (A AB B) ) ( (A A B B) )2018/8/118离散数学二、
9、文氏图二、文氏图E EA AB B 如如：E EE E E E E EA A B B A A B B A AA A B B 2018/8/119离散数学三、集合算律三、集合算律(1) (1) 幂等律：幂等律： A AA = AA = AA A A = AA = A(2) (2) 结合律：结合律：(3) (3) 交换交换律：律：(4) (4) 分配律：分配律：( (A AB B) )C = AC = A( (B BC C) )( (A A B B) ) C = AC = A ( (B B C C) )A AB = BB = BA AA A B = BB = B A AA A( (B B C C)
10、 ) = = ( (A AB B) ) ( (A AC C) ) A A ( (B BC C) ) = = ( (A A B B) )( (A A C C) ) 2018/8/1110离散数学三、集合算律（续）三、集合算律（续）(5) (5) 同一律同一律： A A = A = AA A E = AE = A(6) (6) 零零 律：律：(7) (7) 排中排中律：律：(8) (8) 矛盾律：矛盾律：A AE = EE = EA A = = A A A = EA = EA A A = A = A A( (A A B B) ) = A= AA A ( (A AB B) ) = A= A(9) (
11、9) 吸收律：吸收律：2018/8/1111离散数学三、集合算律（续）三、集合算律（续）(10) (10) 德德 摩根律摩根律： A A ( (B BC C) ) = = ( (A A B B) ) ( (A A C C) )A A ( (B B C C) ) = = ( (A A B B) )( (A A C C) ) ( (B BC C) ) = = B B C C ( (B B C C) ) = = B B C C = E = E E = E = ( ( A A) ) = A= A(11) (11) 双重否定律双重否定律：2018/8/1112离散数学四、集合算律（续）四、集合算律（续）
12、以上恒等式的证明主要通过命题演算等值式。以上恒等式的证明主要通过命题演算等值式。P P QQ Q Q P P即证即证x x P P x x QQ和和x x QQ x x P P 成立，成立，即证即证x x P P x x QQ证明的基本思想是：欲证证明的基本思想是：欲证P P= =QQ，即证：，即证：2018/8/1113离散数学四、集合算律（续）四、集合算律（续）例例3 3：证明：证明A A (B (BC) = (A C) = (A B) B) (A (A C)C) x x A A x x B BC C x x A A ( (x x B BC)C)证明：证明：x x A A (B (BC)C) x x A A ( (x x B B x x C)C) x x A A ( (x x B B ) ) (x x C)C) x x A A ( (x x B B x x C)C) ( (x x A A x x B)B) ( (x x A A x x C C) ) ( (x x A A B)B) ( (x x A A C)C)故：故：A A (B (BC) = (A C) = (A B) B) (A (A C)C) x x ( ( A A B)B) ( (A A
