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

1、华中师范大学计算机科学系,离散数学 第三章 集合的基本概念和运算,第三章 集合的基本概念和运算,3.1 集合的基本概念 3.2 集合的基本运算 3.3 集合中元素的计数 3.4 笛卡尔乘积,3.1 集合的基本概念,集合是不能精确定义的基本的数学概念，直观地讲，集合是由某些可以相互区别的事物汇集在一起所组成的整体。对于给定的集合和事物，应该可以断定这个特定的事物是否属于这个集合。如果属于，就称它为这个集合的元素。 集合通常用大写的英文字母来表示。 集合有两种表示方法：枚举法和谓词表示法。前一种方法是将集合中的所有元素罗列出来，元素之间用逗号隔开，并把它们用花括号括起来。例如 ， ， ，都是合法的

2、表示。 谓词表示法是用谓词来概括集合中元素的属性，例如 ， ， 集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素。集合的元素也是无序的，元素的排列顺序对集合没有影响。,3.1 集合的基本概念,定义3.1.1 设A，B为集合，如果B中的每个元素都是A中的元素，则称B为A的子集合，简称子集。这时也称B被A包含，或A包含B。记作BA。包含的符号化表示为 定义3.1.2设A，B为集合，如果BA且AB，则称A与B相等，记作A=B。相等的符号化表示为 由以上定义可知，两个集合相等的充分必要条件是它们具有相同的元素。如 ， 则A=B。,3.1 集合的基本概念,定义3.1.3设A，B为

3、集合，如果BA且BA，则称B是A的真子集，记作BA。真子集的符号化表示为 BABABA 如果B不是A的真子集，则记作 。例如0, 1是0, 1, 2的真子集，但0, 3和0, 1, 2都不是0, 1, 2的真子集。 定义3.1.4 不含任何元素的集合叫做空集，记作，空集可以符号化表示为=x | xx 定理3.1.1 空集是一切集合的子集。 证明：任何集合，由子集定义有 右边的蕴涵式中因前件 为假，所以整个蕴涵式对一切x为真，因此 为真。,3.1 集合的基本概念,推论 空集是唯一的。 一般地，称集合A的子集和A为A的平凡子集。 含有n个元素的集合简称n元集，它的含有m个(mn)元素的子集称作它的

4、m元子集。任给一个n元集，如何求出它的全部子集呢？ 例3.1.4 A= a, b, c，求A的全部子集。 解： 将A的子集从小到大分类： 0元子集，即空集, ； 1元子集，即单元集，a，b，c； 2元子集，a, b，b, c，a, c； 3元子集，a, b, c。 一般地，对n元集A，它的m(0mn)元子集有 个，不同的子集总数有,3.1 集合的基本概念,定义3.1.5 设A为集合，把A的全体子集构成的集合叫做A的幂集，记作(A)。幂集的符号化表示为 (A) = x | xA 对于例3.1.4中的集合A有(A) = , a, b, c, a, b, a, c, b, c, a, b, c。 定

5、义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，可以

6、通过集合的并，交，相对补-，绝对补和对称差 等运算产生新的集合。 定义3.2.1设A，B为集合，A与B的并集AB，交集AB，B对A的相对补集A-B分别定义如下： 显然AB由A或B中的元素构成， AB由A和B中的公共元素构成， A-B由属于A但不属于B的元素构成。 把以上定义加以推广，可以得到n个集合的并集和交集，即,3.2.1 集合的运算,定义3.2.2 设U为全集， AU，则称A对U的相对补集为A的绝对补集，记作A。 定义3.2.3 设A，B为集合，则A与B的对称差为 A与B的对称差还有一个等价的定义，即 。 例3.2.1 A=0, 1, 2，B=2, 3，计算 或 集合之间的相互关系和有关

7、运算可用文氏图给出形象的描述。,3.2 集合的基本运算,3.2.1 集合的运算 3.2.2 集合运算算律,3.2.2 集合运算算律,任何代数运算都遵从一定的算律，集合运算也不例外。下面给出集合运算的主要算律，其中A，B，C表示任意的集合。 幂等律 结合律 交换律 分配律 同一律 零 律 排中律 矛盾律 吸收律 双重否定律 德摩根律,3.2.2 集合运算算律续,除了以上算律，还有一些关于集合运算性质的重要结论，在此一并给出。 建立了相对补运算和交运算之间的联系，可以利用它将相对补转变成交。 给出了 的三种等价的定义，为证明两个集合之间包含关系提供了新方法，同时也可以用于集合公式的化简。,第三章

8、集合的基本概念和运算,3.1 集合的基本概念 3.2 集合的基本运算 3.3 集合中元素的计数 3.4 笛卡尔乘积,3.3 集合中元素的计数,3.3.1 容斥原理 3.3.2 容斥原理实例,3.3.1 容斥原理,集合A含有n个元素，可以说集合A的基数是n，记作card A=n。所谓基数就是表示集合中所含元素多少的量。如果集合A的基数是n，也可以记为|A|=n。显然空集的基数是0，即|=0 。 定义3.3.1 设为集合，若存在自然数n（0也是自然数），使得|A|=card A=n ，则称A为有穷集，否则就称A为无穷集。 例3.3.1 有100名程序员，其中47名熟悉C语言，35名熟悉C+语言，2

9、3名熟悉这两种语言。问有多少人对这两种语言都不熟悉？ 解：设A，B分别表示熟悉C和C+语言的程序员的集合，则该问题可以用图3.3.1的文氏图表示。将熟悉两种语言的对应人数23填入AB的区域内，不难得到A-B和B-A的人数分别为 | A-B| = |A|-| AB|=47-23=24 | B-A| = |B|-| AB|=35-23=12 从而得到| AB|=24+23+12=59, 故，| (AB)|=100-59=41， 即两种语言都不熟悉的有41人。,3.3.1 容斥原理,设S是有穷集，P1和P2分别表示两种性质，对于S中的任何一个元素x，只能处于以下四种情况之一： （1）只具有性质P1

10、； （2）只具有性质P2 ； （3）具有P1和P2两种性质； （4）两种性质都没有。 令A1和A2分别表示S中具有性质P1和P2的元素的集合。为了使表达式简洁，对任何集合B，用 代替B。由文氏图不难得到以下公式 这就是容斥原理的一种简单形式。 如果涉及到三条性质，容斥原理的公式则变成,3.3.1 容斥原理,定理 3.3.1 S中不具有性质P1, P2, , Pm的元素数是 定理3.3.1证明略。 推论 在S中至少具有一条性质的元素数是,3.3 集合中元素的计数,3.3.1 容斥原理 3.3.2 容斥原理实例,3.3.2 容斥原理实例,例3.3.4 某班学生150人。数学考试成绩90分以上的有8

11、0人，语文考试成绩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.3 n阶笛卡尔积,3.4.1 有序对,定义3.4.1 由两元素x和y（允许x=y）按一定的

12、顺序排列成的二元组叫做一个有序对（也称序偶），记作,其中x是它的第一元素，y是它的第二元素。 一般地，有序对具有以下特点： （1）当 xy 时x, yy, 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,则 xx, x, y=x,y =u,v=u, u, v （1）若x=u，则因为uu=x，所以u = x。

13、 （2）若x=u, v，则因为uu, 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元组（n3）是一个有序对，其中第一个元素是第一个有序n-1元组，一个有序n元组记作x1,x2,xn，即,3.4 笛卡尔乘积,3.4.1 有序对 3.4.2 笛卡尔积 3.4.3 n阶笛卡尔积,3.4.2 笛卡尔积,定义3.4.3 设A，B为集合，用A中元素为第一元素，B中元素为第二元素构成有序对，所有这样的有序对组成的集合叫做A和B的笛卡尔积，记作AB。符号化表示为 从笛卡尔积的定义和逻辑演算的知识可以看出，若 则有 和 。若 ，则有 或 。 由排列组合知识不难证明，如果A中有m个元素，B中有n个元素，则AB和BA都有mn个元素。例如 ， ，则有,3.4.2 笛卡尔积,笛卡尔积运算具有以下性质： （1）若A，B中有一个空集，则它们的笛卡尔积是空集，即 （2）若AB且A，B都不是空集时，有 即笛卡尔积运算不满足交换律。 （3）当A ,