计算机中的集合运算.ppt

计算机中的集合 第一节集合的基本概念1 1个体与集合之间的关系1 2集合的表示法1 3集合与集合之间的关系1 4幂集第二节集合的基本运算2 1集合的补运算2 2集合的交运算和并运算2 3集合的宏运算 1 1个体与集合之间的关系什么是集合 关于集合的各种不同说法如下 1 莫斯科大学的那汤松教授说 凡具有某种特殊性质的对象的汇集称之为集 2 复旦大学的陈建功教授说 凡可供吾人思维的 不论它有形或无形 都叫做物 具有某种条件的物 称它们的全部谓之一集 3 南开大学的杨宗磐教授说 集就是 乌合之众 不考虑怎样 乌合 起来的 众可以具体 可以抽象 4 集合论之父G Cantor 1845 1918 说 集是由总括某些个体成一个整体而成的 对于每个个体 只设其为可思考对象 辨别它的异同 个体之间并不需要有任何关系 综上所述集合的概念有三要素1 个体 元素 2 个体的可辨认性3 集合 动词 通常用小写拉丁字母表示集合中的个体 a b c d 通常用大写拉丁字母表示集合的名称 A B C D 个体与集合之间的关系称为属于关系 对于某个个体a和某个集合A而言 a只有两种可能1 a属于A 记为a A 称a是A中的元素 2 a不属于A 记为a A 称a不是A中的元素 判断个体a属于A还是不属于A 必须使用个体的可辨认性 而且个体的可辨认性是无二义性的 即或者a属于A或者a不属于A 二者居其一且只居其一 关于个体的辨认有赖于各方面的公认的知识 集合 名词 1 2集合的表示法 文字表示法用文字表示集合的元素 两端加上花括号 在座的同学 高等数学中的积分公式 元素列举法将集合中的元素逐一列出 两端加上花括号 1 2 3 4 5 风 马 牛 2 4 6 8 10 谓词表示法 x p x p表示x所满足的性质 x x2 1 y y是开区间 a b 上的连续函数 使x2 1的实数 1 1 x x2 1 集合的特殊情况 不含任何元素的集合称为空集 记为 或 只含一个元素的集合称为单元素集 记为 a 含讨论问题所需全部元素的集合称为全集 记为X 常用集合的字母表示 自然数集 整数集 有理数集 实数集 复数集分别用大写字母N Z Q R C表示 有时还用Q 表示正有理数集 用R 表示负实数集 等等 1 3集合与集合之间的关系 定义1设A B是两个集合1 若对于A中的每个元素x 都有x属于B 则称A包含在B中 记为A B 同时称A是B的子集 2 若A中的每个元素都属于B 且B中的每个元素都属于A 则称A等于B 记为A B 子集的两种特殊情况 平凡子集 1 空集是任一集合的子集 2 每个集合是它自己的子集 集合与集合之间的关系称为包含关系 真子集 对于两个集合A与B 如果AB 并且AB 就说集合A是集合B的真子集 记作AB 或BA 空集是任何非空集合的真子集 全集 如果集体S含有所要研究各个集合的全部元素 这个集合就可以看作一个全集 全集通常用表示I表示 补集 一般地 设S中一个集合 A是S的一个子集 即AS 由S中所有不属于A的元素组成的集合 叫做S中子集A的补集 或余集 记作A即A x xS 且xA 1 4幂集 定义2设A是集合 A的所有子集组成的集合称为A的幂集 记为2A 2A x x A 定理1设集合A是有限集合 A n 则 2A 2 A 定理2设A B是两个集合 那么A B当且仅当2A 2B 第二节集合的基本运算 2 1集合的补运算 一元运算 定义1设X是集合 A是X的子集 A x x X x A 称A 是A关于X的补集 称 为补运算 定理1设X是集合 A B是X的子集 则1 A A 2 若A B 则B A 3 若A B 则A B 4 X X 2 2集合的交运算和并运算 定义2设A B是两个集合1 A B x x A x B 称A B为A与B的交集 称 为集合交运算 2 A B x x A x B 称A B为A与B的并集 称 为集合并运算 定理2设X是全集 A B C是X的三个子集合 则1 A A A A A A2 A A A A X3 A X A A X X4 A A A5 A B B A A B B A6 A B C A B C A B C A B C 7 A B C A B A C A B C A B A C 定理3设A B C为三个集合 则1 A A B A B A 2 若A C且B C 则A B C 3 若C A且C B 则C A B 定理4设A B为两个集合 则下面三式等价 1 A B2 A B B3 A B A定理5设A B为两个集合 则1 A B A B 2 A B A B 2 3集合的宏运算 定义3设A B是两个集合 A B x x A x B 称A B为A和B的差集 称 为集合差运算 由差运算 交运算 补运算的定义知A B A B 由于差运算可以由并 交 补运算线性表出 因此称差运算为宏运算 定理6设X是全集 A B C是X的三个子集合 则1 A B A 2 A A 3 X A A A X 4 A A A 5 A B C A B A C 6 A B C A B A C 7 A B C A B C 8 A B C A B A C 9 A B C A B A C 例 如图 I为全集 集合M N满足 MN 那么图中红色阴影部分用集合表示 可表示为 例 如果集合M满足M 7 13 20 且M中至多含有一个奇数 那么符合上述条件的集合M共有 个 6个 分析 集合M满足两个条件 是集合 7 13 20 的真子集 其中至多含有一个奇数 即M的元素中或者没有奇数或者仅有一个奇数 还要注意空集是符合条件的 由上得M可能是 20 7 13 7 20 13 20 再见