苏XI友无密码课件第3章集合的基本概念和运算.ppt

Chap 3集合的基本概念和运算 集合论是研究集合一般性质的数学分支 它作为一门独立学科诞生于19世纪 创始人为乔治 康托 GeorgeCantor 1845 1918 康托建立的集合论一般称为古典 或朴素 集合论 集合论是全部现代数学的理论基础 已深入到现代科学的各个方面 集合的概念已成为表达各种严谨科学概念的必不可少的数学语言 集合论的语言适应于描述和研究离散对象及其关系 所以它是计算机科学和技术的基础理论和表达工具 集合论在程序语言 数据结构 开关理论 形式语言 关系数据库 编译原理 操作系统 人工智能 信息检索等领域都有着重要应用 本课程主要介绍集合论的基础知识 属于古典集合论的范畴 2020 2 13 北京林业大学信息学院苏喜友 1 1集合的基本概念 集合是人们直观上或思想上能够明确区分的一些对象所构成的一个整体 集合是在一定范围内所讨论的对象组成的整体 集合是把一些事物汇集到一起组成的一个整体 Cantor称集合是 一些确定的 不同的东西的总体 这些东西 人们能够意识到 并且能判断一个给定的东西是否属于这个总体 2020 2 13 北京林业大学信息学院苏喜友 2 集合中的事物 对象 客体称为集合的成员或元素 集合用大写英文字母表示 元素用小写英文字母表示 集合与元素之间的关系是属于或不属于的关系 如 一元素a 要么a S 要么a S 1集合的基本概念 2020 2 13 北京林业大学信息学院苏喜友 3 如果集合S中包含的元素个数是有限的 则称S为有限 有穷 集合 否则 称为无限 无穷 集合 称只有一个元素的集合为单元集 称两个元素的集合为二元集 一般地称有n个元素的集合为n元集 1集合的基本概念 2020 2 13 北京林业大学信息学院苏喜友 4 关于集合的定义需要注意 Note1集合的元素是彼此不同的 如 1 1 2 1 2 Note2集合的元素是无序的 如 1 2 3 3 1 2 Note3集合的元素可以是任何类型的事物 尤其可以是集合 如 A a a b c 1集合的基本概念 2020 2 13 北京林业大学信息学院苏喜友 5 集合的描述或表示通常有下述三种方法 1 列举法 枚举法 列举集合中的所有元素来表示某个集合 例如 A a b c d N 0 1 2 3 2 谓词法 隐式法 叙述法 抽象法 用集合元素所具有的共同性质来描述这个集合 可以用非形式化的自然语言描述 也可以用形式化的谓词表示 1集合的基本概念 2020 2 13 北京林业大学信息学院苏喜友 6 例如 Z x x是整数 且x 0 R x x是实数 B x x R x2 1 0 S x P x 其中 x具有性质P 3 归纳法 由归纳法定义集合中的元素 例如 设a0 1 a1 1 ai 1 ai ai 1 i 1 则S a0 a1 a2 a3 再例如 命题公式的集合和谓词公式的集合都是由归纳法定义的 1集合的基本概念 2020 2 13 北京林业大学信息学院苏喜友 7 一般说来 任意的集合都可以用谓词法表示 例如 A a e i o u A x x是英文中的元音字母 B 2 3 5 7 B x x是素数且x 10 C 2 3 5 C x x 2 x 3 x 5 由此可见 谓词法是表示集合的基本方法 1集合的基本概念 2020 2 13 北京林业大学信息学院苏喜友 8 1集合的基本概念 Def 1子集 Subset 设A和B是两个集合 如果A的每个元素都是B的元素 则称A是B的子集 也称A包含于B或B包含A 记为A B或B A 用谓词形式表示为 A B x x A x B 由定义 任意一个集合都是其自身的子集 即A A 2020 2 13 北京林业大学信息学院苏喜友 9 1集合的基本概念 Def 2相等设A B是集合 如果A B且B A 则称A和B相等 记为A B 若A和B不相等 记为A B 用谓词形式表示 A B A B B A x x A x B x x B x A x x A x B 2020 2 13 北京林业大学信息学院苏喜友 10 1集合的基本概念 Def 3真子集 RealSubset 设A B为集合 如果A B且A B 则称A是B的真子集 也称A真包含于B 或B真包含A 记为A B 用谓词形式表示 A B A B A B x x A x B x x B x A 2020 2 13 北京林业大学信息学院苏喜友 11 1集合的基本概念 Def 4全集由全体客体组成的集合称为全集 记为E或U 全集具有相对性 不同的问题有不同的全集 既使同一个问题 也可以有不同的全集 一般说来 全集取得小一些 问题的描述和处理会简单些 Def 5空集不包含任何元素的集合称为空集或零集 记为 用谓词形式表示 x P x P x 其中 P x 为任意的谓词 2020 2 13 北京林业大学信息学院苏喜友 12 1集合的基本概念 Theorem1设A为一集合 则有 A A A A E 证明 A x x x A 1 A A A E类似可证 Th 2空集是唯一的 证明 设空集不唯一 不妨设 和 都是空集 由Th 1 得 由集合相等的定义 得 2020 2 13 北京林业大学信息学院苏喜友 13 1集合的基本概念 Def 6幂集 Powerset 设A为集合 A的所有子集组成的集合称为A的幂集 记为P A 或2A 即P A x x A 例如 A a b c 则P A a b c a b a c b c a b c Def 7基数 CardinalNumber 集合中不同元素的数目称为集合的基数或势 若基数是有限数 则称该集合为有限 有穷 集 否则称为无限 无穷 集 有限集的基数记为 A 如上例 A 3 P A 8 2020 2 13 北京林业大学信息学院苏喜友 14 1集合的基本概念 Th 3 幂集的基数 设A为有限集 则P A 的基数为 P A 2 A 证明 设 A n 即A中有n个不同元素 从A中n个元素任意取i个元素组成A的子集 共有个 故A的所有子集的个数为 即 2020 2 13 北京林业大学信息学院苏喜友 15 1集合的基本概念 Exp 1判断下列命题是否为真 1 2 3 a a 4 a a 5 a a 6 a a 7 a b a b c a b 8 a b a b c a b 1 1 1 0 0 1 1 1 2020 2 13 北京林业大学信息学院苏喜友 16 1集合的基本概念 Exp 2求下列集合的幂集 1 2 3 a a 解 1 P 2 P 3 P a a a a a a 2020 2 13 北京林业大学信息学院苏喜友 17 2集合的运算 Def 1集合的运算 1 并集合A与B的并记为A B A B x x A x B 2 交集合A与B的交记为A B A B x x A x B 3 相对补 集 集合A与B的相对补记为A B A B x x A x B 也称A B为A与B的差 集 B相对于A的补 集 2020 2 13 北京林业大学信息学院苏喜友 18 2集合的运算 4 绝对补 集 设E为全集 A E A的绝对补记为 A 或A A E A x x E x A 5 对称差 集 集合A与B的对称差记为A B A B A B B A x x A x B x B x A 也称A B为A与B的环和 2020 2 13 北京林业大学信息学院苏喜友 19 2集合的运算 上述定义可以用文氏 JohnVenn 图描述如下 A B A B A B A A B A B A A B A B A B 由文氏图立得 A B A B A B A B A B E E E E E 2020 2 13 北京林业大学信息学院苏喜友 20 2集合的运算 集合运算中 优先于 和 后几种运算平级 有括号先进行括号里的运算 无括号按从左到右次序运算 Th 1设E是全集 A B C是E的任意子集 则下述等式成立 1 交换律A B B A A B B A A B B A 2 结合律 A B C A B C A B C A B C A B C A B C 2020 2 13 北京林业大学信息学院苏喜友 21 2集合的运算 3 分配律A B C A B A C A B C A B A C 4 同一律A A A E A A A A A 5 零律A A E E A A A E A A 6 补余律A A E 排中律A A 矛盾律 7 双否律 A A 2020 2 13 北京林业大学信息学院苏喜友 22 2集合的运算 8 幂等律A A A A A A 9 吸收律A A B A A A B A 10 德 摩根律A B C A B A C A B C A B A C B C B C B C B C E E 2020 2 13 北京林业大学信息学院苏喜友 23 2集合的运算 以上恒等式的证明主要用到命题演算的等值式 基本思想是 欲证P Q 即证P Q Q P 也就是要证对任意的x有x P x Q x Q x P即x P x Q 一般 要证明两个集合相等 可以按照上述思路根据定义来证 也可以根据已知的集合恒等式证明 2020 2 13 北京林业大学信息学院苏喜友 24 2集合的运算 1 利用集合相等定义证明 Exp 1A B B A 证明 对任意的x x A B x A x B x B x A x B A 所以 x x A B x B A 即A B B A 2020 2 13 北京林业大学信息学院苏喜友 25 2集合的运算 Exp 2证明 A B A B 证 对任意x x A B x A x B x A x B x A B 故A B A B 2020 2 13 北京林业大学信息学院苏喜友 26 2集合的运算 Exp 3证明A B C A B A C 证 对任意的x x A B C x A x B C x A x B C x A x B x C x A x B x C x A x B x C x A 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 故A B C A B A C 2020 2 13 北京林业大学信息学院苏喜友 27 2集合的运算 2 利用集合恒等式证明 Exp 4证明 A B A B A 证 A B A B A B B A E A 2020 2 13 北京林业大学信息学院苏喜友 28 2集合的运算 Exp 5已知A B A C 证明B C 证 因为A B A C 所以A A B A A C A A B A A C B C 故B C 2020 2 13 北京林业大学信息学院苏喜友 29 2集合的运算 Exp 6证明 A B A B A 证 A B A A B A A A B A B A B A B A 此外 还有利用文氏图 用集合成员表和利用规定原理证明两集合相等等方法 但都不很常用 2020 2 13 北京林业大学信息学院苏喜友 30 2集合的运算 Exp 7证明A C B C A C B C A B 证 因为A C B CA C B C所以 A C A C B C B C A C A C B C B C A C C B C C A E B E故A B 证明中利用了P1 Q1 P2 Q2 P1 P2 Q1 Q2 同时也有P1 Q1 P2 Q2 P1 P2 Q1 Q2 2020 2 13 北京林业大学信息学院苏喜友 31 2集合的运算 Th 2设A和B是任意集合 则以下四个命题等价 1 A B 2 A B B 3 A B A 4 A B 证 1 2 3 4 1 2020 2 13 北京林业大学信息学院苏喜友 32 2集合的运算 1 A B 2 A B B 对任意x x B 则x A x B 从而x A B 故B A B 对任意x x A B 则x A x B 由于A B 所以总有x B 故A B B 所以A B B 2020 2 13 北京林业大学信息学院苏喜友 33 2集合的运算 2 A B B 3 A B A 因为A B B 所以A B A A B A 3 A B A 4 A B A B A B A B B A B B A 4 A B 1 A B 任取x A 若x B 则x A B 与A B 矛盾 所以x B 故A B 2020 2 13 北京林业大学信息学院苏喜友 34 2集合的运算 Exp 8在什么条件下等式 A B A C 成立 解 A B A C A B C 由Th 2知 A B C 当且仅当A B C 故 A B A C 成立的充要条件是A B C 2020 2 13 北京林业大学信息学院苏喜友 35 2集合的运算 Exp 7证明 A C B C A C B C A B 证二 因为A C B C A C B C 所以 A C B C A C A C B C A C A B C A C A B C A C 上述等式两边分别取并 得 A B C A B C A C A C A B C C A C C A B E A E 即A B A 故A B 2020 2 13 北京林业大学信息学院苏喜友 36 3有穷集合的计数 Exp 1对24名会外语的科技人员进行掌握外语情况的调查 其统计结果如下 会英 日 德和法语的人分别为13 5 10和9人 其中同时会英语和日语的有2人 会英 德和法语中任两种语言的都是4人 已知会