集合的基本概念和运算.ppt

华中师范大学计算机科学系 离散数学第三章集合的基本概念和运算 第三章集合的基本概念和运算 3 1集合的基本概念3 2集合的基本运算3 3集合中元素的计数3 4笛卡尔乘积 3 1集合的基本概念 集合是不能精确定义的基本的数学概念 直观地讲 集合是由某些可以相互区别的事物汇集在一起所组成的整体 对于给定的集合和事物 应该可以断定这个特定的事物是否属于这个集合 如果属于 就称它为这个集合的元素 集合通常用大写的英文字母来表示 集合有两种表示方法 枚举法和谓词表示法 前一种方法是将集合中的所有元素罗列出来 元素之间用逗号隔开 并把它们用花括号括起来 例如 都是合法的表示 谓词表示法是用谓词来概括集合中元素的属性 例如 集合的元素是彼此不同的 如果同一个元素在集合中多次出现应该认为是一个元素 集合的元素也是无序的 元素的排列顺序对集合没有影响 3 1集合的基本概念 定义3 1 1设A B为集合 如果B中的每个元素都是A中的元素 则称B为A的子集合 简称子集 这时也称B被A包含 或A包含B 记作B A 包含的符号化表示为定义3 1 2设A B为集合 如果B A且A B 则称A与B相等 记作A B 相等的符号化表示为由以上定义可知 两个集合相等的充分必要条件是它们具有相同的元素 如 则A B 3 1集合的基本概念 定义3 1 3设A B为集合 如果B A且B A 则称B是A的真子集 记作B A 真子集的符号化表示为B A B A B A如果B不是A的真子集 则记作 例如 0 1 是 0 1 2 的真子集 但 0 3 和 0 1 2 都不是 0 1 2 的真子集 定义3 1 4不含任何元素的集合叫做空集 记作 空集可以符号化表示为 x x x 定理3 1 1空集是一切集合的子集 证明 任何集合 由子集定义有右边的蕴涵式中因前件为假 所以整个蕴涵式对一切x为真 因此为真 3 1集合的基本概念 推论空集是唯一的 一般地 称集合A的子集 和A为A的平凡子集 含有n个元素的集合简称n元集 它的含有m个 m n 元素的子集称作它的m元子集 任给一个n元集 如何求出它的全部子集呢 例3 1 4A a b c 求A的全部子集 解 将A的子集从小到大分类 0元子集 即空集 1元子集 即单元集 a b c 2元子集 a b b c a c 3元子集 a b c 一般地 对n元集A 它的m 0 m n 元子集有个 不同的子集总数有 3 1集合的基本概念 定义3 1 5设A为集合 把A的全体子集构成的集合叫做A的幂集 记作 A 幂集的符号化表示为 A x x A 对于例3 1 4中的集合A有 A a b c a b a c b c a b c 定义3 1 6在一个具体的问题中 如果所涉及的集合都是某个集合的子集 则称这个集合为全集 记作U 全集是有相对性的 不同的问题有不同的全集 即使是同一个问题也可以取不同的全集 例如在研究平面上直线的相互关系时 可以把整个平面 平面上所有点的集合 取作全集 也可以把整个空间 空间上所有点的集合 取作全集 一般地 全集取得小一些 问题的描述和处理会简单些 第三章集合的基本概念和运算 3 1集合的基本概念3 2集合的基本运算3 3集合中元素的计数3 4笛卡尔乘积 3 2集合的基本运算 3 2 1集合的运算3 2 2集合运算算律 3 2 1集合的运算 给定集合A和B 可以通过集合的并 交 相对补 绝对补 和对称差等运算产生新的集合 定义3 2 1设A B为集合 A与B的并集A B 交集A B B对A的相对补集A B分别定义如下 显然A B由A或B中的元素构成 A B由A和B中的公共元素构成 A B由属于A但不属于B的元素构成 把以上定义加以推广 可以得到n个集合的并集和交集 即 3 2 1集合的运算 定义3 2 2设U为全集 A U 则称A对U的相对补集为A的绝对补集 记作 A 定义3 2 3设A B为集合 则A与B的对称差为A与B的对称差还有一个等价的定义 即 例3 2 1A 0 1 2 B 2 3 计算或集合之间的相互关系和有关运算可用文氏图给出形象的描述 3 2集合的基本运算 3 2 1集合的运算3 2 2集合运算算律 3 2 2集合运算算律 任何代数运算都遵从一定的算律 集合运算也不例外 下面给出集合运算的主要算律 其中A B C表示任意的集合 幂等律结合律交换律分配律同一律零律排中律矛盾律吸收律双重否定律德 摩根律 3 2 2集合运算算律续 除了以上算律 还有一些关于集合运算性质的重要结论 在此一并给出 建立了相对补运算和交运算之间的联系 可以利用它将相对补转变成交 给出了的三种等价的定义 为证明两个集合之间包含关系提供了新方法 同时也可以用于集合公式的化简 第三章集合的基本概念和运算 3 1集合的基本概念3 2集合的基本运算3 3集合中元素的计数3 4笛卡尔乘积 3 3集合中元素的计数 3 3 1容斥原理3 3 2容斥原理实例 3 3 1容斥原理 集合A含有n个元素 可以说集合A的基数是n 记作cardA n 所谓基数就是表示集合中所含元素多少的量 如果集合A的基数是n 也可以记为 A n 显然空集的基数是0 即 0 定义3 3 1设为集合 若存在自然数n 0也是自然数 使得 A cardA n 则称A为有穷集 否则就称A为无穷集 例3 3 1有100名程序员 其中47名熟悉C语言 35名熟悉C 语言 23名熟悉这两种语言 问有多少人对这两种语言都不熟悉 解 设A B分别表示熟悉C和C 语言的程序员的集合 则该问题可以用图3 3 1的文氏图表示 将熟悉两种语言的对应人数23填入A B的区域内 不难得到A B和B A的人数分别为 A B A A B 47 23 24 B A B A B 35 23 12从而得到 A B 24 23 12 59 故 A B 100 59 41 即两种语言都不熟悉的有41人 3 3 1容斥原理 设S是有穷集 P1和P2分别表示两种性质 对于S中的任何一个元素x 只能处于以下四种情况之一 1 只具有性质P1 2 只具有性质P2 3 具有P1和P2两种性质 4 两种性质都没有 令A1和A2分别表示S中具有性质P1和P2的元素的集合 为了使表达式简洁 对任何集合B 用代替 B 由文氏图不难得到以下公式这就是容斥原理的一种简单形式 如果涉及到三条性质 容斥原理的公式则变成 3 3 1容斥原理 定理3 3 1S中不具有性质P1 P2 Pm的元素数是定理3 3 1证明略 推论在S中至少具有一条性质的元素数是 3 3集合中元素的计数 3 3 1容斥原理3 3 2容斥原理实例 3 3 2容斥原理实例 例3 3 4某班学生150人 数学考试成绩90分以上的有80人 语文考试成绩90分以上的有75人 两门课程均在90分以上的有50人 问 1 只有一门课程成绩90分以上的学生有多少人 2 两门课程成绩均不在90分以上的学生有多少人 解 全集为该班学生组成的集合 设由题意可知 1 即需求 因为所以 即 3 3 2容斥原理实例续 2 即需求 第三章集合的基本概念和运算 3 1集合的基本概念3 2集合的基本运算3 3集合中元素的计数3 4笛卡尔乘积 3 4笛卡尔乘积 3 4 1有序对3 4 2笛卡尔积3 4 3n阶笛卡尔积 3 4 1有序对 定义3 4 1由两元素x和y 允许x y 按一定的顺序排列成的二元组叫做一个有序对 也称序偶 记作 其中x是它的第一元素 y是它的第二元素 一般地 有序对具有以下特点 1 当x y时 x y y x 2 两个有序对相等 即 x y u v 的充分必要条件是x u且y v 这两个特点是集合 x y 所不具备的 原因在于有序对中强调x和y的顺序性 而集合 x y 中的x和y是无序的 3 4 1有序对 例3 4 1证明 x y u v 的充分必要条件是x u且y v 证明 充分性显然成立 必要性若 x y u v 则 x x x y x y u v u u v 1 若 x u 则因为u u x 所以u x 2 若 x u v 则因为u u v x 所以有x u u x 故总有 x u 及x u成立 由 x x y u u v x u 得 x y u v 再由 x y u v 和x u可得y v 定义3 4 2一个有序n元组 n 3 是一个有序对 其中第一个元素是第一个有序n 1元组 一个有序n元组记作 x1 x2 xn 即 3 4笛卡尔乘积 3 4 1有序对3 4 2笛卡尔积3 4 3n阶笛卡尔积 3 4 2笛卡尔积 定义3 4 3设A B为集合 用A中元素为第一元素 B中元素为第二元素构成有序对 所有这样的有序对组成的集合叫做A和B的笛卡尔积 记作A B 符号化表示为从笛卡尔积的定义和逻辑演算的知识可以看出 若则有和 若 则有或 由排列组合知识不难证明 如果A中有m个元素 B中有n个元素 则A B和B A都有mn个元素 例如 则有 3 4 2笛卡尔积 笛卡尔积运算具有以下性质 1 若A B中有一个空集 则它们的笛卡尔积是空集 即 2 若A B且A B都不是空集时 有即笛卡尔积运算不满足交换律