集合的基本概念和运算.

华中师范大学计算机科学系离散数学第三章集合的基本概念和运算第三章集合的基本概念和运算3.1集合的基本概念3.2集合的基本运算3.3集合中元素的计数3.4笛卡尔乘积3.1集合的基本概念集合是不能精确定义的基本的数学概念，直观地讲，集合是由某些可以相互区别的事物汇集在一起所组成的整体。对于给定的集合和事物，应该可以断定这个特定的事物是否属于这个集合。如果属于，就称它为这个集合的元素。集合通常用大写的英文字母来表示。集合有两种表示方法：枚举法和谓词表示法。前一种方法是将集合中的所有元素罗列出来，元素之间用逗号隔开，并把它们用花括号括起来。例如，，，都是合法的表示。谓词表示法是用谓词来概括集合中元素的属性，例如，，集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素。集合的元素也是无序的，元素的排列顺序对集合没有影响。},,{cbaA...},3,2,1{B}{冬秋，夏，春，C}|{是学生xxD}|{是整数xxE}01|{2xRxxF3.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。)()(AxBxxABABBAAB}3|{的素数是小于等于xxA}32|{xxxB3.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为真，因此为真。ABAxØxxAØØxAØ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)元子集有个，不同的子集总数有mnCnnnnnnCCCC2...210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个集合的并集和交集，即}|{BxAxxBA}|{BxAxxBA}|{BxAxxBA}...|{...2121nnAxAxAxxAAA}...|{...2121nnAxAxAxxAAA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}，计算或集合之间的相互关系和有关运算可用文氏图给出形象的描述。}|{~AxUxxAUA)()(ABBABA)()(ABBABABA}3,1,0{}3{}1,0{BA}3,1,0{}2{}3,2,1,0{BA3.2集合的基本运算3.2.1集合的运算3.2.2集合运算算律3.2.2集合运算算律任何代数运算都遵从一定的算律，集合运算也不例外。下面给出集合运算的主要算律，其中A，B，C表示任意的集合。幂等律结合律交换律分配律同一律零律排中律矛盾律吸收律双重否定律德·摩根律AAAAAACBACBACBACBAABBAABBACABACBACABACBAAØAAUAUUAØØAUAA~ØAA~,ABAAABAAAA~~CABACBACABACBACBCB~~~CBCB~~~UØ~ØU~3.2.2集合运算算律续除了以上算律，还有一些关于集合运算性质的重要结论，在此一并给出。建立了相对补运算和交运算之间的联系，可以利用它将相对补转变成交。给出了的三种等价的定义，为证明两个集合之间包含关系提供了新方法，同时也可以用于集合公式的化简。BBAABABABBAAABABABA~ØBAABABABBAABBACBACBAAOAOAACBCABABABA~ØBAABABABBABA第三章集合的基本概念和运算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。由文氏图不难得到以下公式这就是容斥原理的一种简单形式。如果涉及到三条性质，容斥原理的公式则变成B212121AAAASAA321323121321321AAAAAAAAAAAASAAA3.3.1容斥原理定理3.3.1S中不具有性质P1,P2,…,Pm的元素数是定理3.3.1证明略。推论在S中至少具有一条性质的元素数是mmmkjikjimjijimiimAAAAAAAAASAAA...1......2111121mmmkjikjimjijimiimAAAAAAAAAAAA...1......21111121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）即需求。因为所以，，即分以上的数学成绩在90|xxA分以上的语文成绩在90|xxB80A75B50BA150UBABABABBBABBABAABABABABABABABABABABABA5550507580BABABABABABABA3.3.2容斥原理实例续（2）即需求BA45507580150BABAUBAUBABA第三章集合的基本概念和运算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,其中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}中的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﹥，即nnnxxxxxxx,...,,,...,,,121213.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个元素。例