合的基本概念和运算.ppt

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