北大集合论与图论ppt课件.ppt

2020 4 14 集合论与图论 第3讲 1 第3讲集合的概念与运算北京大学 1 集合的概念2 集合之间的关系3 集合的运算4 文氏图 容斥原理 2020 4 14 集合论与图论 第3讲 2 集合论 settheory 十九世纪数学最伟大成就之一集合论体系朴素 naive 集合论公理 axiomatic 集合论创始人康托 Cantor GeorgFerdinandPhilipCantor1845 1918德国数学家 集合论创始人 2020 4 14 集合论与图论 第3讲 3 什么是集合 set 集合 不能精确定义 一些对象的整体就构成集合 这些对象称为元素 element 或成员 member 用大写英文字母A B C 表示集合用小写英文字母a b c 表示元素a A 表示a是A的元素 读作 a属于A a A 表示a不是A的元素 读作 a不属于A 2020 4 14 集合论与图论 第3讲 4 集合的表示 列举法描述法特征函数法 2020 4 14 集合论与图论 第3讲 5 列举法 roster 列出集合中的全体元素 元素之间用逗号分开 然后用花括号括起来 例如A a b c d x y z B 0 1 2 3 4 5 6 7 8 9 集合中的元素不规定顺序C 2 1 1 2 集合中的元素各不相同 多重集除外 C 2 1 1 2 2 1 2020 4 14 集合论与图论 第3讲 6 多重集 multipleset 多重集 允许元素多次重复出现的集合元素的重复度 元素的出现次数 0 例如 设A a a b b c 是多重集元素a b的重复度是2元素c的重复度是1元素d的重复度是0 2020 4 14 集合论与图论 第3讲 7 描述法 definingpredicate 用谓词P x 表示x具有性质P 用 x P x 表示具有性质P的集合 例如P1 x x是英文字母A x P1 x x x是英文字母 a b c d x y z P2 x x是十进制数字B x P2 x x x是十进制数字 0 1 2 3 4 5 6 7 8 9 2020 4 14 集合论与图论 第3讲 8 描述法 续 两种表示法可以互相转化 例如E 2 4 6 8 x x 0且x是偶数 x x 2 k 1 k为非负整数 2 k 1 k为非负整数 有些书在描述法中用 代替 例如 2 k 1 k为非负整数 2020 4 14 集合论与图论 第3讲 9 特征函数法 characteristicfunction 集合A的特征函数是 A x 1 若x A A x 0 若x A对多重集 A x x在A中的重复度 2020 4 14 集合论与图论 第3讲 10 常用的数集合 N 自然数 naturalnumbers 集合N 0 1 2 3 Z 整数 integers 集合Z 0 1 2 2 1 0 1 2 Q 有理数 rationalnumbers 集合R 实数 realnumbers 集合C 复数 complexnumbers 集合 2020 4 14 集合论与图论 第3讲 11 集合之间的关系 子集 相等 真子集空集 全集幂集 n元集 有限集集族 2020 4 14 集合论与图论 第3讲 12 子集 subset B包含于A A包含B B A x x B x A B不是A的子集 B A x x B x A x x B x A x x B x A x x B x A x x B x A 2020 4 14 集合论与图论 第3讲 13 相等 equal 相等 A B A B B A x x A x B A B A B B A 定义 x x A x B x x B x A 定义 x x A x B x B x A 量词分配 x x A x B 等值式 2020 4 14 集合论与图论 第3讲 14 包含 的性质 A A证明 A A x x A x A 1若A B 且A B 则B A证明 A B A B A B B A 定义 A B B A 德 摩根律 A B 已知 B A 即B A 析取三段论 2020 4 14 集合论与图论 第3讲 15 包含 的性质 续 若A B 且B C 则A C证明 A B x x A x B x x A x B A B x C B C x x A x C 即A C 2020 4 14 集合论与图论 第3讲 16 真子集 propersubset 真子集 B真包含A A B A B A BA B A B A B 定义 A B A B 德 摩根律 x x A x B A B 定义 2020 4 14 集合论与图论 第3讲 17 真包含 的性质 A A证明 A A A A A A 1 0 0 若A B 则B A证明 反证 设B A 则A B A B A B A B 化简 B A B A B A B A所以A B B A A B 定义 但是A B A B A B A B 化简 矛盾 2020 4 14 集合论与图论 第3讲 18 真包含 的性质 续 若A B 且B C 则A C证明 A B A B A B A B 化简 同理B C B C 所以A C 假设A C 则B C B A 又A B 故A B 此与A B矛盾 所以A C 所以 A C 2020 4 14 集合论与图论 第3讲 19 空集 emptyset 空集 没有任何元素的集合是空集 记作 例如 x R x2 1 0 定理1 对任意集合A A证明 A x x x A x 0 x A 1 推论 空集是唯一的 证明 设 1与 2都是空集 则 1 2 2 1 1 2 2020 4 14 集合论与图论 第3讲 20 全集 全集 如果限定所讨论的集合都是某个集合的子集 则称这个集合是全集 记作E全集是相对的 视情况而定 因此不唯一 例如 讨论 a b 区间里的实数性质时 可以选E a b E a b E a b E a b E a E 等 2020 4 14 集合论与图论 第3讲 21 幂集 powerset 幂集 A的全体子集组成的集合 称为A的幂集 记作P A P A x x A 注意 x P A x A例子 A a b P A a b a b 2020 4 14 集合论与图论 第3讲 22 n元集 n set n元集 含有n个元素的集合称为n元集0元集 1元集 或单元集 如 a b A 表示集合A中的元素个数 A是n元集 A n有限集 fimiteset A 是有限数 A 也叫有穷集 2020 4 14 集合论与图论 第3讲 23 幂集 续 定理 A n P A 2n 证明 每个子集对应一种染色 一共有2n种不同染色 A a1 a1 a2 a3 an a1 a3 2020 4 14 集合论与图论 第3讲 24 集族 setfamily 集族 由集合构成的集合 幂集都是集族 指标集 indexset 设A是集族 若A A S 则S称为A的指标集 S中的元素与A中的集合是一一对应的 也记作A A S A S例1 A1 A2 的指标集是 1 2 2020 4 14 集合论与图论 第3讲 25 集族 举例 例2 An x N x n A0 0 A1 1 An n N 0 1 2 An n N 的指标集是N例3 设R x R x 0 Aa 0 a Aa a R 的指标集是R 0 a 2020 4 14 集合论与图论 第3讲 26 集合之间的运算 并集 交集相对补集 对称差 绝对补广义并集 广义交集 2020 4 14 集合论与图论 第3讲 27 并集 union 并集 A B x x A x B x A B x A x B 初级并 2020 4 14 集合论与图论 第3讲 28 并集 举例 例1 设An x R n 1 x n n 1 2 10 则例2 设An x R 0 x 1 n n 1 2 则 2020 4 14 集合论与图论 第3讲 29 交集 intersection 交集 A B x x A x B x A B x A x B 初级交 2020 4 14 集合论与图论 第3讲 30 交集 举例 例1 设An x R n 1 x n n 1 2 10 则例2 设An x R 0 x 1 n n 1 2 则 2020 4 14 集合论与图论 第3讲 31 不相交 disjoint 不相交 A B 互不相交 设A1 A2 是可数多个集合 若对于任意的i j 都有Ai Aj 则说它们互不相交例 设An x R n 1 x n n 1 2 10 则A1 A2 是不相交的 2020 4 14 集合论与图论 第3讲 32 相对补集 setdifference 相对补集 属于A而不属于B的全体元素 称为B对A的相对补集 记作A BA B x x A x B A B A B 2020 4 14 集合论与图论 第3讲 33 对称差 symmetricdifference 对称差 属于A而不属于B 或属于B而不属于A的全体元素 称为A与B的对称差 记作A BA B x x A x B x A x B A B A B B A A B A B A B A B 2020 4 14 集合论与图论 第3讲 34 绝对补 complement 绝对补 A E A E是全集 A E A x x E x A A x E x A A A 2020 4 14 集合论与图论 第3讲 35 相对补 对称差 补 举例 例 设A x R 0 x 2 B x R 1 x 3 则A B x R 0 x 1 0 1 B A x R 2 x 3 2 3 A B x R 0 x 1 2 x 3 0 1 2 3 2020 4 14 集合论与图论 第3讲 36 广义并集 bigunion 广义并 设A是集族 A中所有集合的元素的全体 称为A的广义并 记作 A A x z x z z A 当A是以S为指标集的集族时 A A S A S例 设A a b c d d e f 则 A a b c d e f 2020 4 14 集合论与图论 第3讲 37 广义交集 bigintersection 广义交 设A是集族 A中所有集合的公共元素的全体 称为A的广义交 记作 A A x z z A x z 当A是以S为指标集的集族时 A A S A S例 设A 1 2 3 1 a b 1 6 7 则 A 1 2020 4 14 集合论与图论 第3讲 38 广义交 广义并 举例 设A1 a b c d A2 a b A3 a A4 A5 a a A6 则 A1 a b c d A1 a b c d A2 a b A2 a b A3 a A3 a A4 A4 A5 a A5 a A6 A6 E 2020 4 14 集合论与图论 第3讲 39 文氏图 Venndiagram 文氏图 平面上的n个圆 或椭圆 使得任何可能的相交部分 都是非空的和连通的JohnVenn 1834 1923例 2020 4 14 集合论与图论 第3讲 40 文氏图 应用 文氏图可表示集合运算 结果用阴影表示 A B A B A B A B A A A A A A A B B B B B A B 2020 4 14 集合论与图论 第3讲 41 容斥原理 principleofinclusion exclusion 容斥原理 或包含排斥原理 2020 4 14 集合论与图论 第3讲 42 容斥原理 证明 n 2时的情况 A B A B A B 归纳证明 以n 3为例 A B C A B C A B C A B C A B A B C A C B C A B A B C A C B C A C B C A B C A B A C B C A B C A B B C A 2020 4 14 集合论与图论 第3讲 43 容斥原理 举例 例1 在1到10000之间既不是某个整数的平方 也不是某个整数的立方的数有多少 解 设E x N 1 x 10000 E 10000A x E x k2 k Z A 100B x E x k3 k Z B 21则 A B E A B E A B A B 10000 100 21 4 9883注意A B x E x k6 k Z A B 4 2020 4 14 集合论与图论 第3讲 44 容斥原理 举例 续 例2 在24名科技人员中 会说英 日 德 法语的人数分别为13 5 10 和9 其中同时会说英语 德语 或同时会说英语 法语 或同时会说德语 法语两种语言的人数均为4 会说日语的人既不会说法语也不会说德语 试求只会说一种语言的人数各为多少 又同时会说英 德 法语的人数有多少 解 设E x x是24名科技人员之一 E 24A x E x会说英语 B x E x会说日语 C x E x会说德语 D x E x会说法语 2020 4 14 集合论与图论 第3讲 45 容斥原理 举例 续 解 续 设所求人数分别为x1 x2 x3 x4 x 如图 A x E x会说英语 A 13B x E x会说日语 B 5C x E x会