离散数学课件资料1.ppt_图文

第三章

集合的基本概念和运算

§3.1 集合的基本概念

§3.2 集合的基本运算
§3.3 集合中元素的计数

2019/4/25

离散数学

1

§3.1 集合的基本概念
一、集合
集 合:一些可确定的可分辨的事物构成的整体。
用大写字母A, B, C, …标记。 集合的元素:一个集合的每一个特定的事物。用小 写字母a, b, c, …标记。 如:(1) 26个英文字母的集合; (2) 坐标平面上所有点的集合。

规定:集合的元素之间彼此相异,无次序关系。
2019/4/25 离散数学 2

二、常用的集合
常用的集合记号:
N: 自然数集合(包括0 )

Z: 整数集合
Q: 有理数集合 R: 实数集合 C: 复数集合 ?: 空集(不含任何元素) E: 全集
2019/4/25 离散数学 3

三、集合的表示方法
列出集合的所有元素,元素之间用逗号 1、列举法: 隔开。如A = { a, b, c } 用谓词概括该集合中元素的属性。 2、描述法: 即:A = { x | P (x) } 如:A = { x | x?Z ? 3 < x ? 6 } 元素与集合之间的关系(?属于): 若A={a,{a},b,{a,b}},则a?A ,{a} ?A
2019/4/25 离散数学 4

四、集合之间的关系
1、子 集:集合B中的每个元素都是集合A中的元素,
则B是A的子集,记作B ? A。符号化为

B ? A ? ? x(x?B ? x?A)
显然:A ? A,? ? A 2、相等集:如果A ? B且B ? A,则A与B相等。记作 A = B。符号化为A = B ? A ? B ? B ? A 3、真子集:如果B ? A且A ? B,则B是A的真子集。 记作B ? A。
2019/4/25 离散数学 5

四、集合之间的关系(续)
4、幂 集:集合A的全体子集构成的集合,记作P (A)。
符号化为P (A) = { x | x ? A} n 元集A的幂集P (A)含有2n个元素。 例1:A = {a, b, c},求A的幂集P (A)。 解:0元子集:?,

1元子集:{a}, {b}, {c},

2元子集:{a, b}, {a, c}, {b, c},3元子集:{a, b, c}
P(A) = {?, {a}, {b}, {c}, {a, b}, {a, c}, {b, c},{a, b, c}}

2019/4/25

离散数学

6

四、集合之间的关系(续)
例2:计算以下幂集。
(1) P(?);

(2) P({?,{?}});
(3) P({1, {2, 3}})。 解:(1) P (?) = {?}

(2) P ({?, {?}}) = {?, {?}, {{?}}, {?, {?}}} (3) P ({1, {2, 3}}) = {?, {1}, {{2, 3}}, {1, {2, 3}}}

2019/4/25

离散数学

7

§3.2 集合的基本运算
一、几种常见的运算
1、并:A∪B = { x | x?A ? x?B }
2、交:A∩B = { x | x?A ? x?B }, 若A∩B = ?,则称A与B不交。 3、相对补:A ? B = { x | x?A ? x?B }(B对A的)

4、绝对补:A对全集E的相对补集,记作:~ A ~ A = E ? A = { x | x? E ? x? A } 5、对称差:A ? B = (A?B)∪(B?A) = (A∪B) ? (A∩B)
2019/4/25 离散数学 8

二、文氏图
如:
A∪B
E

A∩B
E

A? B
E

~A
E

A? B
E

2019/4/25

离散数学

9

三、集合算律
(1) 幂等律: A∪A = A
A∩A = A

(2) 结合律: (A∪B)∪C = A∪(B∪C)
(A∩B)∩C = A∩(B∩C) (3) 交换律: A∪B = B∪A

A∩B = B∩A
(4) 分配律: A∪(B∩C) = (A∪B)∩(A∪C) A∩(B∪C) = (A∩B)∪(A∩C)
2019/4/25 离散数学 10

三、集合算律(续)
(5) 同一律: A∪? = A
A∩E = A

(6) 零

律: A∪E = E
A∩? = ?

(7) 排中律: A∪~ A = E

(8) 矛盾律: A∩~ A = ?
(9) 吸收律: A∪(A∩B) = A A∩(A∪B) = A
2019/4/25 离散数学 11

三、集合算律(续)
(10) 德·摩根律: A ? (B∪C) = (A ? B)∩(A ? C)
A ? (B∩C) = (A ? B)∪(A ? C) ~ (B∪C) = ~ B∩~ C ~ (B∩C) = ~ B∪~ C ~?=E ~E=? (11) 双重否定律: ~ (~ A) = A
2019/4/25 离散数学 12

四、集合算律(续)
以上恒等式的证明主要通过命题演算等值式。
证明的基本思想是:欲证P=Q,即证: P? Q ?Q?P 即证x?P ? x?Q和 x?Q ? x?P 成立, 即证x?P ? x?Q

2019/4/25

离散数学

13

四、集合算律(续)
例3:证明A ? (B∪C) = (A ? B)∩(A ? C) 证明: x ? A ? (B∪C) ? x ? A ? x ? B∪C ? x ? A ? ? (x ? B∪C) ? x? A ? ?(x ? B ? x ? C) ? x? A ? (?(x? B )? ?(x? C)) ? x ? A ? (x ? B ? x ? C) ? (x?A ? x ? B)? (x?A ? x?C) ? (x?A ? B)∩(x?A ? C) ? x? ( A ? B)∩(A ? C) 故:A ? (B∪C) = (A ? B)∩(A ? C)
2019/4/25 离散数学 14

四、常用运算性质
(1) A∩B ? A (2) A ? A∪B
(3) A ? B ? A (4) A ? B = A∩~ B (5) A∪B = B ? A ? B ? A∩B = A ? A ? B = ? (6) A ? B = B ? A (7) (A ? B) ? C = A ? (B ? C)
2019/4/25 离散数学 15

A∩B ? B B ? A∪B

四、常用运算性质(续)
(8) A ? ? = A (9) A ? A = ?
(10) A ? B = A ? C ? B = C 证明两个集合相等,除了采用命题演算等值式外,

还可以采用集合运算性质。集合运算性质也可用于证
明两个集合之间的包含关系。

2019/4/25

离散数学

16

四、常用运算性质(续)
例4:证明(A? B)∪B = A∪B 证明: (A? B)∪B = (A∩~ B)∪B = (A∪B)∩ (~ B∪B) = (A∪B)∩E = A∪B

2019/4/25

离散数学

17

四、常用运算性质(续)
例3:化简((A∪B∪C)∩(A∪B)) ? ((A∪(B ? C))∩A) 解: ∵ A∪B ? A∪B∪C 和 A ? A∪(B ? C) ∴ (A∪B∪C)∩(A∪B) = A∪B ∴ (A∪(B ? C))∩A = A

原式 = (A∪B) ? A = (A∪B)∩~ A = B ? A

2019/4/25

离散数学

18

§3.3 集合中元素的计数
一、理论
基数:集合中元素的个数,用|A|表示。 容斥原理:对任意两个有限集A和B,有

|A∪B| = |A| + |B| ? |A∩B|
推广1:| A∪B∪C | = |A| + |B| + |C| ? |A∩B| ? |A∩C| ?|B∩C| + |A∩B∩C|

∩ C | = |E| ? |A∪B∪C| 推广2: | A∩ B
2019/4/25 离散数学 19

二、应用
例4:某班有25个学生,其中14人会打篮球,12人会
打排球,6人会打篮球和排球,5人会打篮球和网球,

2人会打这三种球,而6个会打网球的人都会打另外
一种球(指篮球或排球),求不会打这三种球的人数? 解:分别用A,B,C表示会打篮球、排球、网球的学

生集合。依题意有:|A| = 14,|B| = 12,|C| = 6,
|A∩B| = 6,|A∩C| = 5,|A∩B∩C| = 2, 且有C ? A∪B,求| A∩ B ∩ C |
2019/4/25 离散数学 20

二、应用(续)
于是 C = C∩(A∪B) = (C∩A)∪(C∩B) |C| = |A∩C| + |B∩C| ? |A∩B∩C| 6 = 5+ |B∩C| ? 2 得 |B∩C| = 3
? |B∩C| + |A∩B∩C| = 14 + 12 + 6 ? 6 ? 5 ? 3 + 2 = 20 | A∩ B ∩ C | = |E| ? |A∪B∪C| =25 ? 20 = 5
2019/4/25 离散数学 21

从而|A∪B∪C| = |A| + |B| + |C| ? |A∩B| ? |A∩C|

二、应用(续)
例5:一个班有50个学生,第一次考试有26人得5分,
第二次考试有21人得5分。如果两次考试都没得5分

的有17人,那么在两次考试都得5分的有多少人? 解:分别用A,B表示第一次考试得5分和第二次考试
得5分的学生集合。 依题意有:|A| = 26,|B| = 21,| A∩ B | = 17 则|A∩B| = |A| + |B| ? |A∪B| = |A| + |B| ?(|E| ? | A∩ B |) = 26 + 21 ? 50 + 17 = 14
2019/4/25 离散数学 22


相关文档

离散数学课件资料.ppt
02离散数学课件资料-PPT精选文档
最新-六年级上册数学课件-5.1 圆的认识|人教新课件(2014秋) (共20张PPT)-PPT文档资料
最新-六年级上册数学课件-1.2《圆的认识(二)》|北师大版(2014秋) (共31张PPT)-PPT文档资料
最新-六年级上册数学课件-1.2 因数与倍数_沪教版 (共19张PPT)-PPT文档资料
最新-六年级上册数学课件-3.1《倒数的认识》 |苏教版(2018秋) (共21张PPT)-PPT文档资料
最新-六年级上册数学课件-3.2 比的基本性质 第1课时_沪教版 (共13张PPT)-PPT文档资料
最新-六年级上册数学课件-1.1《分数乘整数》 |人教新课标(2018秋) (共21张PPT)-PPT文档资料
最新-六年级上册数学课件-1.3欣赏与设计∣北师大版(2018秋) (共14张PPT)-PPT文档资料
最新-六年级上册数学课件-3.1《倒数的认识》 |苏教版(2018秋) (共19张PPT)-PPT文档资料
学霸百科
6030274文学网 60302741php网站 60302742jsp网站 60302743小说站 60302744算命网 60302745占卜网 60302746星座网
电脑版 |