集合的基本概念和运算(课堂PPT).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。记作BA。包含的符号化表示为 定义定义3.1.2设A，B为集合，如果BA且AB，则称A与B相等，记作A=B。相等的符号化表示为 由以上定义可知，两个集合相等的充分必要条件是它们具有相同的元素。如 ，则A=B。3.1 集合的基本概念集合的基本概念 定义定义3.1.3设A，B为集合，如果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)元素的子集称作它的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。定义定义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的并集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，计算 或 集合之间的相互关系和有关运算可用文氏图给出形象的描述。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，记作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+语言，23名熟悉这两种语言。问有多少人对这两种语言都不熟悉？解：设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；（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分以上的有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.3 n阶笛卡尔积 3.4.1 有序对有序对 定义定义3.4.1 由两元素x和y（允许x=y）按一定的顺序排列成的二元组叫做一个有序对（也称序偶），记作,其中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。（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,B,C都不是空集时有 即笛卡尔积运算不满足结合律。（4）笛卡尔积运算对或运算满足分配律，即3.4 笛卡尔乘积笛卡尔乘积 3.4.1 有序对 3.4.2 笛卡尔积 3.4.3 n阶笛卡尔积 3.4.3 n阶笛卡尔积阶笛卡尔积 定义定义3.4.4 设A1,A2,An是集合（n2），它们的n阶笛卡尔积记作A1A2An，其中 当A1=A2=An=A时，可将它们的n阶笛卡尔积简记为 。例如A=0,1，则 定理定理3.4.1 设 是有限集，则