离散数学 1_2(集合)[2014_9_17].ppt

* * * * * * * * * * * * * * * * * * * * * 主讲教师：常亮 E-mail: changl@guet.edu.cn QQ：737059669 办公室电话: 2291071 手机: 辅导教师：周小川 答疑时间： 答疑地点： 离散数学 内容回顾 集合、元素、属于(?) 集合的表示 枚举法 描述法 A = {x | P(x)} 文氏图法 集合的基数 |A| 集合包含 B?A iff 对于任一元素x：如果x?B则必然有x?A 集合相等 B=A iff B?A并且A?B 集合真包含 B?A iff B?A并且B?A 空集 ? vs. {?} 幂集 P(A) = 2A = {x | x ?A} 问：如果|A|=n，则|P(A)|= ? 练习 P(?) = ? P(P(?)) = ? P(P(P(?))) = ? …… 1.3 集合的运算 设U为全集，A、B是U的子集。 并： A∪B = {x | x?A 或者 x?B} 交： A∩B = {x | x?A 并且 x?B} 若 A∩B = ? ，则称A与B不相交 集合运算 差： A?B = {x | x?A 并且 x?B} 补： ?A = U?A = {x | x?U 并且 x?A} 性质： A?B = A∩ ?B 集合运算 对称差： A?B = (A?B)∪(B?A) = {x | x?A且x?B，或者x?B且x?A} 性质： A?B = (A?B)∪(B?A) 集合运算 例1.7：已知全集U和集合A、B为 U:全体英文小写字母 A={a, b, c, d} B={a, d, e, f} 求集合A和B的并集、交集、差集、补集和对称差集 解： A ? B = B ? A = {a，b，c，d，e，f} A ? B = B ? A = {a，d} A– B = {b，c }，B – A = {e，f } ?A ={e，f，g，h，i，j，k，l，m，n，o，p，q，r，s，t，v，w，x，z } ?B ={b，c，g，h，i，j，k，l，m，n，o，p，q，r，s，t，v，w，x，y } A ? B = B ? A = {b，c，e，f } 习题 求下列集合A和B的并集、交集、差集、补集和对称差集 。 ① A = N，B = Z，全集U = Z ②A = {1，3，5，8}，B = {2，3，4，5}，全集U = {x| x为自然数，且x ? 10} 集合运算的性质 ①幂等律：A∪A = A A∩A = A ②交换律：A∪B = B∪A　 A∩B = B∩A A?B = B?A ③结合律：(A∪B)∪C = A∪(B∪C) (A∩B)∩C = A∩(B∩C) (A?B)?C = A?(B?C) 集合运算的性质 ④分配律：A∪(B∩C) = (A∪B)∩(A∪C) A∩(B∪C) = (A∩B)∪(A∩C) ⑤吸收律：A∪(A ∩ B) = A 　A∩(A∪B) = A ⑥零律：A∪U = U A∩? = ? ⑦同一律：A∪? = A A∩U = A 集合运算的性质 ⑧排中律：A ∪ ?A = U ⑨矛盾律：A ∩ ?A = ? ⑩双重否定律： ?（ ? A） = A 集合运算的性质 ?补交转换律 A– B = A??B ?德?摩根律： ?(A∪B) = ?A ∩ ?B ?(A∩B) = ?A∪?B A?(B∪C) = (A?B)∩(A?C) A?(B∩C) = (A?B)∪(A?C) ?(余补集) ?? = U ?U = ? 上述性质都可用文氏图得到方便分析和直观理解。 证明集合运算的性质 如何证明这些基本性质的正确性？ 以对集合运算的定义为基础。 以已经得到证明的性质为基础， 利用集合演算。 要求：熟练掌握集合运算的基本定律，能够用来证明集合之间的相等关系。 证明集合运算的性质 例1.8. 对于集合A和B，证明A?B = (A–B) ? (B–A) 证明 对于任意x?A?B，根据对称差的定义知：x? A且x? B，