离散数学 第三章集合

《离散数学 第三章集合》由会员分享，可在线阅读，更多相关《离散数学 第三章集合（148页珍藏版）》请在金锄头文库上搜索。

1、 2020年2月28日 裘国永 离散数学第三章集合 本章内容及教学要点 3 1集合的概念与表示法教学内容 集合 子集 包含 空集 幂集 全集 3 2集合的运算与性质教学内容 并 交 补 对称差 文氏图 3 3集合的划分与覆盖教学内容 划分 覆盖 3 6基本计数原理原理教学内容 加法原理 乘法原理 容斥原理 抽屉原理 集合论是现代数学的基础 是数学中不可或缺的基本描述工具 可以这样讲 现代数学与离散数学的 大厦 建立在集合论的基础之上 集合论的研究起源于对数学的基础研究 对数学的对象 性质及其发生 发展的一般规律进行的科学研究 德国数学家康托尔从1874年始 发表了一系列集合论方面的著作 从而创

2、立了集合论 在自然科学中 除了研究处于孤立的个体之外 更重要的是将一些相关的个体放在一起进行研究 这就直观地产生了引入集合这一概念的要求 集合是最简单的数学对象 随着计算机时代的到来 集合的元素已由传统的 数集 和 点集 拓展成包含文字 符号 图形 图表和声音等多媒体信息 构成了各种数据类型的集合 从而集合论在编译原理 开关理论 信息检索 形式语言 数据库和知识库 CAD CAM CAI及AI等各个领域得到了广泛的应用 但数学家们不久就在康托尔的理论 我们称之为朴素 古典 集合论 中发现了逻辑矛盾 即所谓的 悖论 Paradox 导致了数学发展史上的第三次危机 另两次分别是无理数的引入和无穷小

3、量的引入 其中最著名的就是1901年罗素发现的 罗素悖论 S x x S 罗素悖论 的通俗表示是所谓的 理发师悖论 小镇里的理发师放出豪言 我帮且只帮镇里所有不自己刮脸的人刮脸 哪么他是否应当给自己刮脸 如果他给自己刮脸 那么按照他的豪言他不应该为自己刮脸 但如果他不给自己刮脸 同样按照他的豪言他又应该为自己刮脸 正是寻求解决第三次数学危机的各种努力 给数学基础问题的研究带来了全新的转机 一部分数学家开始把精力集中于解决具有 能行性 的问题上 20世纪30年代中后期 图灵对计算的本质进行了研究 从而实现了对计算本质的真正认识 图灵提出了 图灵机 这一计算模型用来解决 能行计算 问题 而数字电子

4、计算机正是这种模型的具体实现 3 1集合的概念与表示法 这一节的主要内容 集合的元素 基数 有限集与无限集 集合的表示法 子集 平凡子集 不相交集合 空集 幂集 全集 一个集合是作为整体识别的 确定的 互相区别的一些事物的全体 严格地讲 这只是一种描述 不能算是集合的定义 类似于几何中的点 线 面等概念 在朴素集合论中 集合也是一种不加定义而直接引入的最基本的原始概念 一给出定义就要引入悖论 Paradox 而集合论中的其他概念 则都是从它出发给予了严格的定义 构成集合的每个事物称为这个集合的元素或成员 Member Element 集合一般用大写字母表示 元素用小写字母表示 但这也不是绝对的

5、 因为一个集合可以是另外一个集合的元素 给定一个集合A和一个a 可以判定a是否在集合A中 如果a在A中 我们称a属于A 记为a A 否则 称a不属于A 记为a A 例如 某大学计算机系的全体学生 所有自然数等都是集合 集合元素的特征 确定性 互异性 无序性 确定性 一旦给定了集合A 对于任意a 可准确地判定a是否在A中 互异性 集合中的元素之间是彼此不同的 即集合 a b b c 与集合 a b c 是一样的 无序性 集合中的元素之间没有次序关系 即集合 a b c 与集合 c b a 是一样的 若集合A中只有有限个元素时 称A为有限集合 Finiteset 集合中元素的个数称为集合的基数 势

6、 Cardinality 记为 A 否则 称A为无限集合 Infiniteset 下面将本书中常用的集合列举如下 N 表示全体自然数组成的集合 Z 表示全体整数组成的集合 Q 表示全体有理数组成的集合 R 表示全体实数组成的集合 Zm 表示模m同余关系所有剩余类组成的集合 集合表示法1 列举法列举法就是将集合的元素全部写在花括号内 元素之间用逗号分开 例如 A a b c N 0 1 2 列举法一般用于有限集合和有规律的无限集合 2 谓词表示法 属性描述法 谓词表示法是用谓词来概括集合中元素的属性 通常用 x P x 来表示具有性质P的一些对象组成的集合 例如 x 1 x 6 x为整数 为由1

7、 2 3 4 5 6组成的集合 集合的包含与相等外延性原理 两个集合A和B是相等的 当且仅当它们有相同的元素 记为A B 例如 若A 2 3 B 小于4的素数 则A B 定义3 1 1设A和B为两个集合 若对于任意a A必有a B 则称A是B的子集 Subset 也称A包含于B或B包含A 记作A B 如果B不包含A 记作AB B包含A的符号化表示为 A B x x A x B 例如 若A 1 2 3 4 B 1 2 C 2 3 则B A且C A 但CB 定理3 1 1集合A和B相等当且仅当这两个集合互为子集 即 A B A B B A 证明 若A B 则A和B具有相同的元素 于是 x x A

8、x B x x B x A 都为真 即A B且B A 反之 若A B且B A 假设A B 则A与B元素不完全相同 不妨设有某个元素x A但x B 这与A B矛盾 所以A B 定理3 1 2设A B和C是三个集合 则 1 A A 2 A B B C A C 证明 1 由定义显然成立 2 A B B C x x A x B x x B x C x x A x B x B x C x x A x C A C 定义3 1 2设A和B是两个集合 若A B且B中至少有一个元素b使得b A 则称A是B的真子集 Propersubset 也称A真包含于B或B真包含A 记作A B 否则 记作A B B真包含A的

9、符号化表示 A B x x A x B x x B x A 若两个集合A和B没有公共元素 我们说A和B是不相交的 Disjoint 例如 若A a b c d B b c 则B是A的真子集 但A不是A的真子集 注 与 表示元素和集合的关系 而 与 表示集合和集合的关系 例如 若A 0 1 B 0 1 0 1 则A B且A B 定理3 1 3设A B和C是三个集合 则 1 A A 2 A B B A 3 A B B C A C 证明 仅证 2 和 3 2 A B x x A x B x x B x A x x A x B x x B x A x x A x B x x B x A x x A x

10、 B x x A x B x x A x B x x A x B x x A x B x x B x A B A 3 A B B C x x A x B x x B x A x x B x C x x C x B x x A x B x B x C x x B x A x x C x B x x A x C x x C x A A C 定义3 1 3没有任何元素的集合称为空集 EmptySet 记作 以集合为元素的集合称为集族 例如 x x x x R 是空集 x x是某大学的学生社团 是集族 定理3 1 4空集是任何集合的子集 对于任一集合A 我们称空集 和其自身A为A的平凡子集 Trivi

11、alSubset 特别要注意 与 的区别 是不含任何元素的集合 是任意集合的子集 而 是含有一个元素 的集合 定义3 1 4一个集合A的所有子集组成的集合称为A的幂集 PowerSet 记作P A 或2A 例3 1 1求幂集P P P P 1 2 3 解 P P P P 1 2 3 1 2 3 1 2 3 定理3 1 5若 A n 则 P A 2n 证明 因为A的m个元素的子集的个数为C n m 所以 P A C n 0 C n 1 C n n 2n 定理3 1 6设A和B是两个集合 则 1 B P A B A 2 A B P A P B 3 P A P B A B 4 P A P B A B

12、 5 P A P B P A B 6 P A P B P A B 定义3 1 5所要讨论的集合都是某个集合的子集 称这个集合为全集 Universalset 记作U或E 全集是一个相对的概念 由于所研究的问题不同 所取的全集也不同 例如 在研究整数问题时 可把整数集Z取作全集 在研究平面几何问题时 可把整个坐标平面取作全集 3 2集合的运算与性质 这一节的主要内容 集合的并 交 差 补 对称差 基本集合恒等式 幂等律 交换律 结合律 分配律 同一律 零律 互补律 吸收律 德 摩根律 双否律 集合的交 并 补定义3 2 1设A和B为两个集合 A和B的交集A B Intersection 并集A

13、B Union 分别定义如下 A B x x A x B A B x x A x B 例如 若A 1 2 3 B 1 4 则A B 1 A B 1 2 3 4 集合的交与并可以推广到n个集合的情况 即A1 A2 An x x A1 x A2 x An A1 A2 An x x A1 x A2 x An 例3 2 1设A B和C为任意集合 且A B 则A C B C 证明 对任意的x A C 则有x A且x C 而A B 由x A得x B 则x B且x C 从而x B C 所以 A C B C 例3 2 2设A和B为两个集合 则A B A B B A B A 证明 对任意的x A B 则x A或

14、x B 又A B 所以x B 于是A B B 又显然有B A B 故A B B 反之 若A B B 因A A B 所以A B 同理可证A B A B A 定义3 2 2设A和B为两个集合 所有属于A而不属于B的元素组成的集合称为B对于A的补集 Complement 或相对补 记作A B x x A x B A B也称为A和B的差集 Difference 例如 若A 1 2 3 B 1 4 则A B 2 3 B A 4 定义3 2 3设U为全集 集合A关于U的补集U A称为集合A的绝对补或余集 Relativecomplement 记为 或Ac 即 x x U且x A 例3 2 3设A和B为两个

15、集合 则A B A 证明 因为x A B x A x B x A x x A 所以A B A 定理3 2 1对于任意3个集合A B和C 其交 并 补满足下面10个定律 1 幂等律A A A A A A 2 结合律 A B C A B C A B C A B C 3 交换律A B B A A B B A 4 分配律A B C A B A C A B C A B A C 5 同一律A A A U A 6 零律A U U A 7 互补律A U A 8 吸收律A A B A A A B A 9 德 摩根律 A B C A B A C A B C A B A C 10 双重否定律 A以上等式的证明主要用

16、到命题演算的等价式 即欲证集合A B 只需证明x A x B 定理3 2 2对任意集合A和B B A B U且A B 证明 如B 则A B A U A B A 反之 若A B U且A B 则B B U B A B A B B A B A B U 例3 2 4证明A B C A B A C 证明 因为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 所以A B C A B A C 例3 2 5证明 证明 因为x x A B x A x B x x x 所以 集合的对称差定义3 2 4集合A和B的对称差 SymmetricDifference 定义为A B A B B A 例如 若A 0 0 则P A A P A A A P A 0 0 0 0 定理3 2 3设A B和C为三个集合 则 1 A B B A 2 A B C A B C 3 A B C A B A C 4 A A A U A A A U 5 A B A B A B 证明 仅证 5 A B A B B A A B A B A A B A B A