离散第1讲集合的概念、交并补差幂集.ppt

计算机专业基础课程 授课人 梁妍 离散数学的特点与学习要求 特点离散性抽象性逻辑性有难度要求预习复习独立完成作业 PowerPointTemplate Sub 集合的概念与表示 集合运算 集合的归纳定义 PowerPointTemplate Sub 集合论是一门研究数学基础的学科 产生于16世纪末德国数学家康托 GeorgCantor 1845 1918 通过集合的直观定义开创了朴素集合论 被公认为集合理论的创始人1902年英国数学家罗素 Russell 1872 1970 证明朴素集合论导致悖论 随后为弥补这一缺陷出现了各种公理化集合论体系集合不仅可以表示数及其运算 更可以用于非数值信息及离散结构的表示和处理 集合论的原理和方法作为数学基本技术广泛地应用于计算机科学的基础研究和实际应用中 集合的概念 表示与基本运算 Page1to7 离散数学 第1讲 6 第一讲集合的概念 表示与基本运算 内容提要 基础知识集合 元素的概念怎样表示一个集合 列举 描述 空集 全集 有限集 无限集外延性公理集合相等 子集 若干定理集合的基本运算并 交 差 补幂集运算 7 第一讲集合的概念 表示与基本运算 何为集合 何为元素 集合 sets 指确定的 互相区别的 作整体识别的一些事物 对象 的全体 简称集 集合中的对象称为集合的元素 members 或称为元 成员 当某一个对象a是集合A的成员时 就说 a属于A 记成a A 当a不是集合A的成员时 就说 a不属于A 记成a A 对于任何对象a和任何集合A a要么属于A 要么不属于A 二者必居其一 8 第一讲集合的概念 表示与基本运算 集合举例 师范大学全体学生师范大学所有班级全体正整数1 2 3 4 偶质数的全体09计算机1班和他们本学期选修的所有课程所有长得像张三的人中国所有著名导演方程x2 2x 1 0的根方程x2 x 1 0的根 9 第一讲集合的概念 表示与基本运算 集合与元素 集合中的元素可以是任何具体或抽象的个体 也可以是集合A 1 2 1 2 集合与其成员是两个截然不同的概念1 1 a a 通常用大写字母A B C表示集合 用小写字母a b c表示集合的元素 并非绝对 10 第一讲集合的概念 表示与基本运算 集合的表示方法 列举法 枚举法 a b c 秦始皇 汉武帝 1 2 3 4 2 4 6 8 1 2 4 7 11 描述法A x P x A中的元素均满足性质P 而A以外的元素一个也不满足性质P x A P x x x是整数且x 0 x x2 2x 1 0 x x出生于大连 x x是0到1区间的实数 11 第一讲集合的概念 表示与基本运算 集合的表示方法 归纳法 以后介绍 文氏图 常用于表示集合之间的关系 12 第一讲集合的概念 表示与基本运算 常用集合及其表示 0 1 x x 0或x 1 自然数集合 或非负整数的集合 N 0 1 2 3 整数集合I 2 1 0 1 2 正整数集合I 1 2 3 x x I且x 0 13 第一讲集合的概念 表示与基本运算 常用集合及其表示 偶数集合E 4 2 0 2 4 x x是偶数 x x I且2 x 前n个自然数的集合Nn 0 1 2 n 1 x x N且x n 14 第一讲集合的概念 表示与基本运算 常用集合及其表示 P 全体素数的集合Q 全体有理数的集合Q 全体正有理数的集合R 全体实数的集合R 全体正实数的集合C 全体复数的集合 15 第一讲集合的概念 表示与基本运算 空集 有限集和无限集 定义1 1 没有任何元素的集合称为空集 记为 由全体对象组成的集合称为全集 记为U 定义1 2 只含有限多个元素的集合称为有限集 不是有限集的集合称为无限集 空集是有限集有限集合A中元素的个数称为A的基数 cardinality 记为 A 空集的基数是0 即 0 16 第一讲集合的概念 表示与基本运算 空集 有限集和无限集举例 x x 0或x 1 自然数集合N正整数集合A 1 2 1 2 师范大学全体学生方程x2 x 1 0的根 17 第一讲集合的概念 表示与基本运算 外延性公理 extensionalityaxiom 外延性公理 两个集合相等当且仅当这两个集合具有完全相同的成员 即对任意的集合A和B A B当且仅当对任意元素x x属于A则一定有x属于B 反之 x属于B也一定有x属于A 也就是说 集合A中的所有元素均是集合B中的元素 反之 B中的所有元素均是A中的元素例1 4 0 1 1 0 0 1 0 x x x2 2x 1 0 外延性公理事实上刻画了集合元素的无序性 相异性及集合表示形式的不唯一性 18 第一讲集合的概念 表示与基本运算 子集合 subsets 定义1 3 设A B为集合 若A中每一个元素都同时是B的元素 则称A是B的子集 即对于任意元素x 当x属于A时一定有x属于B 表示为A B 读成A包含于B 或B包含A 任意集合A均是自己的子集 即 A A若要说明A不是B的子集 只须在A中找到某一个元素x 使得x B即可定义1 4 设A B为集合 当A B且A B时 称A为B的真子集 记成A B 读做A真包含于B 或B真包含A 19 第一讲集合的概念 表示与基本运算 包含关系vs 隶属关系 包含 集合与集合之间的关系 1 2 1 2 3 4 1 2 1 2 3 4 a a 隶属 元素与集合之间的关系1 1 2 3 4 5 1 2 3 4 a a 20 第一讲集合的概念 表示与基本运算 关于子集的若干定理 定理1 1 对任何集合A B A B当且仅当A B且B A 对任何集合A A A定理1 3 对于任何集合A B C 若A B B C 则A C 证明 设x为A中任一元素 因为A B 所以x B 又因为B C 所以x C这就是说 A中所有元素均属于C 所以有A C 21 第一讲集合的概念 表示与基本运算 关于子集的若干定理 定理1 2 1 4 对任意集合A A U A定理1 5 空集是唯一的证明 假设 1 2都是空集 根据定理3 应该有 1 2且 2 1 从而由定理1知 1 2 22 第一讲集合的概念 表示与基本运算 关于子集的若干定理 定理1 6 设A为一个有限集 且 A n 则A的子集个数为2n证明 集合A的子集最多有n个元素 最少有0个元素 0个元素的子集共有C n 0 个 1个元素的子集共有C n 1 个 n个元素的子集共有C n n 个 因此 集合A共有子集C n 0 C n 1 C n n 2n个 23 第一讲集合的概念 表示与基本运算 集合的运算 集合运算 以集合作为运算对象 运算结果仍为集合的运算算术运算 3 5 84 6 24集合运算 1 2 2 3 2 1 2 2 3 1 2 3 有哪些集合运算交 并 差 补求幂运算广义并 交求笛卡尔积运算 24 第一讲集合的概念 表示与基本运算 集合的并运算union 定义1 5 1 设A B为任意集合 则由A B的所有元素合在一起所组成的集合称为A与B的并集 记成A B 即 A B x x A或x B x A B x A或x B例1 6U 0 1 2 9 A 2 4 B 4 5 6 7 C 0 8 9 D 1 2 3 A B A C C D B D 25 第一讲集合的概念 表示与基本运算 集合的交运算intersection 定义1 5 2 设A B为任意集合 则由A B的公共元素所组成的集合称为A与B的交集 记成A B 即 A B x x A并且x B x A B x A并且x B例1 6U 0 1 2 9 A 2 4 B 4 5 6 7 C 0 8 9 D 1 2 3 A B A C C D B D 26 第一讲集合的概念 表示与基本运算 集合的差运算difference 定义1 5 3 设A B为任意集合 则由在A中而不在B中的元素所组成的集合称为A对B的差 记成A B 即 A B x x A且x B x A B x A并且x B例1 6U 0 1 2 9 A 2 4 B 4 5 6 7 C 0 8 9 D 1 2 3 A B A C C D B D 27 第一讲集合的概念 表示与基本运算 集合的补运算complement 定义1 5 4 设U为全集 A为任意集合 则所有在全集U中但不属于A的元素所组成的集合称为A的补集 记成A 即 A x x U且x A x A x A例1 6U 0 1 2 9 A 2 4 B 4 5 6 7 C 0 8 9 D 1 2 3 A B C D 28 第一讲集合的概念 表示与基本运算 文氏图表示的集合并 交 差 补运算 A A B A B A B A B C 29 第一讲集合的概念 表示与基本运算 关于并 交 差 补运算的一些直观结论 A A A A A A U UA A A A A U AA A A A A U A A U A U U A AA A A A UA A B B A B A B A A B BA B A若A B 则A B B A B A A B 若A B 则A B A 30 第一讲集合的概念 表示与基本运算 关于交换律和结合律 交换律2 3 3 2 a b b aA B B A A B B A一般而言 A B B A结合律2 3 5 2 3 5 a b c a b cA B C A B CA B C A B C一般而言 A B C A B C 31 第一讲集合的概念 表示与基本运算 关于分配律和吸收率 分配律a b c a b a cA B C A B A C A B C A B A C A B C A B A C 一般而言 A B C A B A C 吸收律A A B AA A B A 32 第一讲集合的概念 表示与基本运算 关于并 交 差 补运算的几个定理 定理1 6 A B C A B A C A B C A B A C 定理1 8 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 33 第一讲集合的概念 表示与基本运算 关于并 交 差 补运算的几个定理 定理1 10 A B A B A B B A B A四命题等价定理1 11 对任意集合A B 若它们满足1 A B U2 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 第二种证法 相互包含 34 第一讲集合的概念 表示与基本运算 集合幂运算 定义1 6 我们把集合A的所有子集组成的集合称为A的幂集 powerset 记成 A 即 A x x A 例 A 2 4 B 4 5 6 7 C A B C 35 第一讲集合的概念 表示与基本运算 幂集的性质 定理1 12 设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