离散数学第2章.ppt

离散数学 DiscreteMathematics 2020 3 24 1 离散数学 DiscreteMathematics 计算机科学与工程系TianjinUniversityofTechnologyDepartmentofComputerScience Engineering魏雪丽 离散数学 DiscreteMathematics 计算机科学与工程系TianjinUniversityofTechnologyDepartmentofComputerScience Engineering魏雪丽 2020 3 24 2 第二章集合Sets 本章首先采用朴素集合论的方法 介绍有关集合的一些基本知识 内容显得较为直观 学起来易于接受 但集合及其相关的概念是本门课程后面各章内容的基础 同学们务必熟练的掌握 第一节集合的概念和表示法 一集合的概念 二集合的表示法 三元素和集合之间的关系 四集合间的包含关系 五特殊集合 六小结 一 集合的基本概念 1 集合的定义 具有某种共同属性的事物的全体 称为 例如 集合 计算机网络是计算机之间以信息传输为主要目的而连接起来的计算机系统的集合 计算机内存的全体单元构成一集合 一 集合的基本概念 2 集合的元素 1 集合的元素表示的事物可以是具体的 注 也可 以是 抽象的 2 集合的元素是任意的 但必须是确定的 和可 以区分的 集合里含有的对象或客体 称为集合的 元素 一 集合的基本概念 3 集合的分类 1 有限集合 集合的元素个数是有限的 2 无限集合 集合的元素个数是无限的 二 集合的表示法 1 符号表示法 通常用大写字母A B C 代表集合 用小写字母a b c 代表元素 1 如果a是集合A的一个元素 则记为 a A 读做 a属于A 或 a在集合A中 2 如果a不是集合A的一个元素 则记为 读做 a不属于A 或 a不在集合A中 任一元素 对某一集合而言 或属于该集合 或不属于该集合 二者必居其一 且只居其一 注 二 集合的表示法 1 符号表示法 绝不容许界限不分明或含糊不清的情况存在 注 离散数学中 只讨论界限清楚 无二义性的描述 不清晰的对象构成的集合 属于模糊论的研究范畴 著名理发师问题就属于模糊论的研究范畴 二 集合的表示法 2 描述集合中元素的方法1 列举法a 全部列举法 以任意顺序写出集合的所有元素 隔开 元素间用逗号 并将其放在花括号内 例如 所有小于5的正整数 这个集合的元素为 1 2 3 4 再没有别的元素了 如果把这个集合命名为A A 1 2 3 4 就可记为 二 集合的表示法 2 描述集合中元素的方法1 列举法b 部分列举法 列举集合的部分元素 素 其他元素可从列举的元 用省略号代替 例如A表示 全体小写英文字母 的集合 A a b y z 则 归纳出来 列举法仅适用于描述元素个数有限的集合 注 或 元素具有明显排列规律的集合 二 集合的表示法 2 描述集合中元素的方法2 描述法 把集合元素的共同属性描述出来 集合中元素的属性 P x 表示任何谓词 则 A x P x 即用谓词概括 表示所有使谓词P x 成立的元素x所组成的集合 例 x x2 3x 2 0 x x 2n 1 n N 如果P a 为真 则a A 否则 谓词表示法 集合的元素 集合的元素必须满足的条件 二 集合的表示法 1 有些集合可以用两种方法表示 注 但是有些 集合不可以用列元素法表示 如实数集合 2 集合的元素是彼此不同的 如果同一个元 素在集合中多次出现 应该认为是一个元素 如 3 4 4 4 5 3 4 5 5 4 3 是同一个集合 3 集合的元素是无序的 4 集合的元素可以是一个集合 但不允许以 集合自身为其元素 如 S a b S a b S a S A 三 元素和集合之间的关系 元素和集合之间的关系 是隶属关系 即属于 或不属于 属于记作 不属于记作 例如 A 1 1 2 3 3 1 1 2 3 A A 3 A 2 3 A A 可以用一种树形图表示集合与元素的隶属关系 A 2 1 2 A B 四 集合间的包含关系 1 子集 如果集合A中每个元素 都是集合B中的元素 则称A是B的 或A包含于B 子集 或者B包含A 记作A B 如果A不是B的子集 或B A A B x x A x B 则在A中至少有一个元素 不属于B时 称B不包含A 记作 或B A 注 1 A A 2 A B B C 则A C B 四 集合间的包含关系 2 集合相等1 定义 两个集合相等 当且仅当 它们有相同的元素 若A和B相等 记作 A B x x A x 外延性原理 A B 两个集合不相等 记作A B 四 集合间的包含关系 2 集合相等2 判断 A与B互为 子集 定理若A和B相等 当且仅当 A B 且 B A 即 A 四 集合间的包含关系 3 真子集 如果集合A中每个元素 都属于集合B 但B中 不属于A 则称A是B的 记作A B 或B A A B x x A x B 至少有一个元素 真子集 x x B x A B A B 例A a b B a b 不是 的子集 真 四 集合间的包含关系 3 真子集 可以用文氏图了表示集合间的包含关系 文氏 Venn 图是一种利用平面上的点构成的图形来形象展示集合的一种方法 集合用矩形 园面 如果A B 或一封闭曲线来表示 则表示A的圆面 一般完全落在 表示B 的圆面内 A B B A A B 四 集合间的包含关系 4 隶属和包含关系的区别 例A a a B a B A B A B是A的元素 B的元素a 是A的元素 B是A的子集 隶属是 元素 和 集合 的关系 包含是 集合 和 集合 的关系 某些集合可以同时成立这两种关系 是个体与整体的关系 是部分与整体的关系 五 特殊集合 1 空集定义 不含任何元素的集合 空集 称为 记作 例两条平行线交点的集合 为 例 x x 0 x 0 x R 注 1 与 的区别 是集合 没有元素 有1个元素的集合 2 五 特殊集合 1 空集定理 空集 是任一集合A的子集 即 A 下列命题是否为真 练习 1 2 3 4 五 特殊集合 1 空集推理 空集 是唯一的 设 1 2是两个空集 则 1 2 且 2 1 得 1 2 所以空集是唯一的 证明 证明唯一性一般采用反证法 绝对唯一 证毕 五 特殊集合 1 空集 2 证明一个集合是空集 或证明集合的唯一性 常采用反证方法 即假设该集合不是空集 或不唯一 导致与已知条件的矛盾或导致唯一 注 1 任何非空集合A 至少有子集 两个 和A 只有子集 一个 五 特殊集合 2 全集定义 在一定范围内 如果所有集合都是某一集合的子集 则称此集合为 全集 记作 U 注 1 全集是相对的 不同的问题有不同的全集 即使是同一个问题也可以取不同的全集 2 一般地说 全集取得小一些 问题的描述和处理会简单些 3 全集U用一个矩形的内部表示 U 五 特殊集合 3 幂集定义 由集合A的所有子集为元素所组成的集合 称为A的 幂集 记作 注 1 幂集的元素都是 集合 或P A 或2A 2 任一集合的幂集 都非空 3 在A的所有子集中 A 和 又叫平凡子集 A a 五 特殊集合 3 幂集例 的幂集 A a 的幂集 a A a b 的幂集 b a b 有个元素 1 有个元素 2 有个元素 4 20 21 22 A 五 特殊集合 3 幂集一般地 集合A a1 a2 an 则 有个元素 2n 它的m 0 m n 元子集有个 不同的子集共有 1 1 n 2n个 A x 理发师问题 在一个很僻静的孤岛上 住着一些人家 岛上只有一位理发师 该理发师专给那些并且只给那些自己不刮脸的人刮脸 那么 谁给这位理发师刮脸 解 设 不给自己刮脸的人 x是 b是这位理发师 1 若b A 则b是不给自己刮脸的人 而由题意 b只给集合A中的人刮脸 b要给b刮脸 即bA 理发师问题 在一个很僻静的孤岛上 住着一些人家 岛上只有一位理发师 该理发师专给那些并且只给那些自己不刮脸的人刮脸 那么 谁给这位理发师刮脸 解 则b是要给自己刮脸的人 而由题意 理发师只给自己不刮脸的人刮脸 b是不给自己刮脸的人 即b A 无论1 和2 都有 b A 同时成立 这种情况称为罗索悖论 是模糊论的范畴 第二节集合的运算 一集合的交 二集合的并 三集合的补 四集合的对称差 五集合恒等式 六小结 一 集合的交 1 定义2 文氏图 任意两个集合A和B 由A和B的 所有共同元素 组成的集合 称为A和B的 交集 记为 A B A B x x A x B 即 Intersection A B A B 一 集合的交 如果两个集合没有任何共同的元素 Intersection 例如 A a b c e f B b e f r s C a t u v 则 A B b e f A C a B C 则称它们是 不相交 集合 E A B 一 集合的交 三个或更多的集合的交集运算 Intersection A B C x x A x B x C 一 集合的交 3 性质 A A 1 幂等律 Intersection A A 2 零律 A E 3 同一律 A A B 4 交换律 B A A B C 5 结合律 A B C B 一 集合的交 3 性质 Intersection 若A B 6 则A C B C 反之 不然 证 A B x x A x 分析 若x A C 即 x A x C A B x A x B 则 x B x C x B C 反之 取C A a B b 则 A C B C 证毕 一 集合的交 3 性质 Intersection A B 7 A A B B 集合越交 越小 注 集合运算的规律和命题演算的某些规律是一致的 所以命题演算的方法是证明集合恒等式的基本方法 二 集合的并 1 定义2 文氏图 任意两个集合A和B 由属于A 或属于B 组成的集合 称为A和B的 并集 记为 A B A B x x A x B 即 Union 的元素 A B 二 集合的并 三个或更多的集合的并集运算 Union E A B A B C x x A C x B x C 二 集合的并 3 性质 A A 1 幂等律 Union A A U 2 零律 U A 3 同一律 A A B 4 交换律 B A A B C 5 结合律 A B C 二 集合的并 3 性质 Union 若A B 6 则A C B D 反之 不然 若x A C 即 x A x C C D 1 若x A 则x B x B D 2 若x C 则x D x B D 始终有x B D 反之 取C D E A a B b 则 A C E B D E 证 证毕 二 集合的并 3 性质 Union A B 7 A 集合越并 越大 A B B x B x B x A 二 集合的并 4 和 的关系 Union 定理 对任意集合A B和C有 1 A B C A B A C 2 A B C A B A C 即 对 可以分配 对 可以分配 1 A B C x x A x C x x A x C A B A C x x A x B x A x C x 分配律 分配律 证 x B x A 二 集合的并 4 和 的关系 Union 定理 对任意集合A B有 1 A A B A 2 A A B A 证一 1 A A B x x A x x A A 吸收律 吸收律 命题逻辑中的吸收律 二 集合的并 4 和 的关系吸收律 Union 定理 对任意集合A B有 A B A B B 或 A B A 当且仅当 A B B B A B B B B 由性质7 B A B A B B 反之 由性质7 A A B A B B A B 证 证毕 三 集合的补 1 定义2 文氏图 任意两个集合A和B 由属于A 但不属于B 组成的集合 称为B对于A的 补集 记为 A B A B x x A x B 即 RelativeComplement 所有元素 或相对 的 补 或A和B的差 x x A x B B A 三 集合的补 3 绝对补集 全集U和集合A的差集 称为A的 绝对补 记为 U A A 即 RelativeComplement 或A的余集 或A的补集 x x U x A A 或 A U A x A x A AbsoluteComplement 三 集合的补 4 性质 RelativeComplement A 1 双重否定律 A U 2 3 U A A 4 排中律 U A A 5 矛盾律 三 集合的补 4 性质 RelativeComplement 1 A B 6 德摩根律 A B 2 A B A B A B x x U x A B x x U x A x x U x A x B x x U x A x B x U A B x B 证 1 A B 三 集合的补 5 定理 RelativeComplement 2 利用 3 的结论 A A B A A B A A 3 的结论 德摩根律 A A B A B 1 A B A B 2 A B A A B 分配律 三 集合的补 5 定理 RelativeComplement 4 A B C A B A C 三 集合的补 5 定理 RelativeComplement 4 a A B B A b A B B A A B 证 a 若x A 则必有x B 因此x B 必有x A 即x B x A B A A B 由上述证明可知 A B A B A B A B B A 四 集合的对称差 1 定义 SymmetricDifference 设A B是两个集合 其元素 但 集合A和B的对称差 环和 是 集合 记作A B 或属于A 或属于B 不能既属于A 又属于B 即 A B A B B A 例如A a b c B b d 则A B a c d x x A x B x B x A 四 集合的对称差 2 文氏图 SymmetricDifference 四 集合的对称差 3 性质 SymmetricDifference 1 交换律 2 同一律 3 零律 A B 4 A B B A A A A A B A A B 四 集合的对称差 3 性质 SymmetricDifference A B C A B C 5 结合律 定义2 2 6A B两集合的环积记为AB 是集合 定理2 2 12 1 AB 2 AB BA 3 AA U 定理2 2 13 定理2 2 14 例1已知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 例2已知A B A C 是否必须B C 解 否 例 设A 1 2 B 1 C 2 例3已知A B A C 是否必须B C 解 例 设A 1 B 1 2 C 1 3 否 2 5集合的笛卡尔积 1 序偶 有序2元组 两个具有固定次序的客体组成一个序偶 有序2元组 记作 其中x是它的第一元素 y是它的第二元素 一 有序n元组 例 平面直角坐标系中的一个点的坐标就构成为一个有序序偶 我们可用表示 注 序偶是讲究次序的 例和表示平面上两个不同的点 这与集合不同 1 3 和 3 1 是两个相等的集合 2 定义 两个序偶相等 当且仅当x u且y v 一 有序n元组 3 有序 元组 是一个序偶 其第一元素本身也是一个序偶 表示为 z 或 4 有序n元组 有序n元组也是一个序偶 其第一元素是一个n 1元组 xn 通常简记为 其中xi称作它的第i坐标 i 1