离散数学第2版作者王元元离散第1讲课件.ppt

-*- ξ第一讲 集合的概念、表示与基本运算 关于并、交、差、补运算的几个定理 定理6： A – (B∪C) = (A – B)∩(A – C) A – (B∩C) = (A – B)∪(A – C) (A∪B)ˉ = Aˉ∩Bˉ (A∩B)ˉ = Aˉ∪Bˉ A – B = A∩Bˉ 证明 A – (B∩C) = (A – B)∪(A – C) 对任意x，x? A – (B∩C) ? x? A 且x? B∩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) -*- ξ第一讲 集合的概念、表示与基本运算 关于并、交、差、补运算的几个定理 定理7： A ? B，A – B = ?，A∪B =B，A∩B = A四命题等价 定理8：对任意集合A、B，若它们满足 1) A∪B = U 2) A∩B = ? 那么B = Aˉ 证明：B = B∪? = B∪(A∩Aˉ) = (B∪A) ∩ (B∪Aˉ) = U ∩ (B∪Aˉ) = (A∪Aˉ) ∩ (B∪Aˉ) = (A∩B ) ∪ Aˉ = ? ∪ Aˉ = Aˉ -*- ξ第一讲 集合的概念、表示与基本运算 集合幂运算 定义9：我们把集合A的所有子集组成的集合称为A的幂集（power set），记成ρ(A)，即 ρ(A) = {x | x?A} 举例： A={2, 4}, B={{4, 5}, 6, 7}, C= ? ρ(A), ρ(B), ρ(C) -*- ξ第一讲 集合的概念、表示与基本运算 幂集的性质 定理9：设A、B为任意集合，A?B当且仅当ρ(A) ?ρ(B) 证明： 先证必要性。假设A?B，X是ρ(A) 中任一元素，则根据ρ(A) 定义，X ? A。由于A?B，所以X ? B，从而X ? ρ(B)。即ρ(A) ?ρ(B)。 再证充分性。假设ρ(A) ?ρ(B)，x是集合A中任一元素，则{x} ? A，根据ρ(A) 定义，{x} ? ρ(A) 。因为ρ(A) ?ρ(B)，所以{x} ? ρ(B)，从而{x} ?B，进一步x ?B。即A?B。 -*- ξ第一讲 集合的概念、表示与基本运算 集合恒等式的证明方法 集合恒等式的证明大体上可以分为以下几种情况： 根据外延公理利用自然语言叙述或等价式推演 利用已经得到证明的恒等式进行代换 利用前面的性质把恒等式的左边和右边都化成只含∪、∩、ˉ三种运算的式子，看右边是否等于左边 最后还可以利用文氏图进行验证 -*- ξ第一讲 集合的概念、表示与基本运算 本讲小结 主要内容 集合和元素的概念 集合的表示方法 外延公理、子集合 集合的并、交、差、补运算及相关性质 集合幂运算 作业 P15. 13、14(4) 用3种方法 、 16 ξ第一讲 集合的概念、表示与基本运算 计算机专业基础课程 指挥自动化学院 计算机理论教研室 王 元 元 PowerPoint Template_Sub 1.1 集合的概念与表示 1.2 集合运算 1.3 集合的归纳定义 PowerPoint Template_Sub 集合论是一门研究数学基础的学科，产生于16世纪末 德国数学家康托（Georg Cantor, 1845~1918）通过集合的直观定义开创了朴素集合论，被公认为集合理论的创始人 1902年英国数学家罗素（Russell, 1872~1970 ）证明朴素集合论导致悖论，随后为弥补这一缺陷出现了各种公理化集合论体系 集合不仅可以表示数及其运算，更可以用于非数值信息及离散结构的表示和处理。集合论的原理和方法作为数学基本技术广泛地应用于计算机科学的基础研究和实际应用中 集合的概念、表示与基本运算 Page 1 to 7 《离散数学》第1讲 -*- ξ第一讲 集合的概念、表示与基本运算 内容提要 基础知识 集合