离散数学 第1章_集合_meng.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 集合运算 例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，u，v，w，x，y，z } ?B ={b，c，g，h，i，j，k，l，m，n，o，p，q，r，s，t，u，v，w，x，y，z } A ? B = B ? A = {b，c，e，f } 1.3.2集合运算的性质根据集合运算的定义，可以得到集合运算的许多性质，这些性质又称为集合运算的基本恒等式。对于集合A 、B和C，以及全集U，可以列写出如下一些主要性质： ①幂等律：A∪A = AA∩A = A ②交换律：A∪B = B∪AA∩B = B∩AA?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) = AA∩(A∪B) = A ⑥零律：A∪U = UA∩? = ? ⑦同一律：A∪? = AA∩U = A ⑧排中律：A ∪ ?A = U ⑨矛盾律：A ∩ ?A = ? 集合运算的基本定律 ⑩双重否定律：A = A ?补交转换律 A– B = A??B ?德?摩根律： ?(A∪B) = ?A ∩ ?B(A∩B) = ?A∪?BA?(B∪C) = (A?B)∩(A?C)A?(B∩C) = (A?B)∪(A?C) ?(余补集)= UU = ? 上述性质都可用文氏图得到方便分析和直观理解。利用上述性质，可以推演出各种新的集合等式或包含式。 集合运算的基本定律 如何证明这些基本定律的正确性？ 以对集合运算的定义为基础。 以已经得到证明的基本定律为基础，利用集合演算。 例：证明A∪(B∩C) = (A∪B)∩(A∪C) 提示：以集合运算的定义为基础来证明 例：证明A ∩(A∪B) = A 提示：基于已证明基本定律为基础来证明 要求：熟练掌握集合运算的基本定律，能够用来证明集合之间的相等关系。 集合运算的基本定律 例1.8:对于集合A和B，证明A?B = (A–B) ? (B–A) 证明对于任意x?A?B，根据对称差的定义知：x? A且x? B，或者x? B且x?A；又根据差集的定义知：x? A–B，或者x? B –A；再根据并集的定义知：x?(A–B)? (B–A)。由此，A?B ? (A–B) ? (B–A)。 对于任意x?(A–B) ? (B–A)，根据并集的定义知：x? A–B，或者x? B –A；又根据差集的定义知：x? A且x? B，或者x? B且x?A；再根据对称差的定义知：x? A?B 。由此， (A–B) ? (B–A) ? A?B。 综上述，A?B = (A–B) ? (B–A)。 证毕。 集合运算的基本定律 例1.9:对于集合A、B和C，证明：如果A ? B = A ? C， 则B = C 证明 对于任意x?B，分两种情形讨论。 情形一：x?A。由x?A及交集的定义，x?A?B。从而，由对称差的定义知x?A?B，那么由已知条件得到x?A?C。假定x?C，那么由差集的定义知：x?A–C；进而，由A?C = (A–C)?(C–A)知：x?A?C。矛盾。所以有x?C。故B ?C 情形二：x?A。由x?B及差集的定义，x?B–A。由A?B = (A–B)?(B–A)知：x?A?B，那么由已知条件得到x?A?C。再由A?C = (A–C)?(C–A)知：x?A–C或x?C–A。由于x?A，于是x?A–C。由此，x?C–A。进而x?C。故B ?C 同理，可证得C ?B。 综上知，如果A ? B = A ? C，则B = C。证毕。 集合运算的基本定律 例1.10:已知A?B = A?C，A?B = A?C，求证B = C 证明 B = B?(A?B)（吸收律） = B?(A?C)（已知条件） = (B?A)?( B?C)（分配律） = (A?B)?( B?C)（交换律） = (A?C)?( B?C)（已知条件） = (A?B) ? C（分配律） = (A?C) ? C = C（已知条件、吸收律） 证毕。 集合运算的基本定律