离散数学课件--第六章-集合代数

1希帕索斯悖论与第一次数学危机毕达哥拉斯：欧多克索斯：2贝克莱悖论与第二次数学危机牛顿、莱布尼兹：贝克莱：3第6章集合代数4本章说明本章的主要内容–集合的基本概念—集合、相等、(真)包含、子集、空集、全集、幂集–集合运算—交、并、(相对和绝对)补、对称差、广义交、广义并–文氏图—有穷集计数问题–集合恒等式本章与后续各章的关系–是集合论后面各章的基础–是典型的布尔代数系统56.1集合的基本概念集合(Set)是不能精确定义的基本概念。–所谓集合，是指我们无意中或思想中将一些确定的、彼此完全不同的客体的总和而考虑为一个整体。这些客体叫做该集合的元素。(康托)–直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员。例如：–方程x2－1＝0的实数解集合：–26个英文字母的集合；–坐标平面上所有点的集合；–……集合通常用大写的英文字母来标记。6常见的数的集合N—自然数集合Z—整数集合Q—有理数集合R—实数集合C—复数集合7集合的表示方法表示一个集合的方法主要有两种：列元素法和谓词表示法。列元素法(roster)是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。–A＝{a，b，c，…，z}–Z＝{0，±1，±2，…}–C＝{桌子,灯泡,老虎,自然数}谓词表示法(definingpredicate)是用谓词来概括集合中元素的属性。–B＝{x|x∈R∧x2－1＝0}许多集合可以用两种方法来表示，如B也可以写成{-1，1}。但是有些集合不可以用列元素法表示，如实数集合。8集合的元素集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素。例如：{1，1，2，2，3}＝{1，2，3}集合的元素是无序的。例如：{1，2，3}＝{3，1，2}在本书所采用的体系中规定：集合的元素都是集合。9元素和集合之间的关系元素和集合之间的关系是隶属关系，即属于或不属于，属于记作∈，不属于记作。例如：A＝{a，{b，c}，d，{{d}}}a∈A，{b，c}∈A，d∈A，{{d}}∈A，bA，{d}A。b和{d}是A的元素的元素。可以用一种树形图表示集合与元素的隶属关系。说明隶属关系可以看作是处在不同层次上的集合之间的关系。规定：对任何集合A都有AA。Aa{b,c}d{{d}}bc{d}d10子集（subset）定义6.1设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。这时也称B被A包含，或A包含B，记作BA。包含的符号化表示为BAx(x∈B→x∈A)如果B不被A包含，则记作BA。例如：NZQRC，但ZN。显然对任何集合A都有AA。11隶属和包含的说明隶属关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。例如A＝{a，{a}}和{a}既有{a}∈A，又有{a}A。前者把它们看成是不同层次上的两个集合，后者把它们看成是同一层次上的两个集合。12集合相等(equal)定义6.2设A，B为集合，如果AB且BA，则称A与B相等，记作A＝B。相等的符号化表示为：A＝BAB∧BA如果A与B不相等，则记作A≠B。13真子集定义6.3设A，B为集合，如果BA且B≠A，则称B是A的真子集，记作BA。真子集的符号化表示为BABA∧B≠A如果B不是A的真子集，则记作BA。例如：NN14空集(emptyset)定义6.4不含任何元素的集合叫做空集，记作。空集的符号化表示为：＝{x|x≠x}。例如:{x|x∈R∧x2+1=0}是方程x2+1=0的实数解集，因为该方程无实数解，所以是空集。15空集的性质推论空集是唯一的。证明：假设存在空集1和2，由定理6.1有12，21。根据集合相等的定义，有1＝2。定理6.1空集是一切集合的子集。证明：任给集合A，由子集定义有Ax(x∈→x∈A)右边的蕴涵式因前件假而为真命题，所以A也为真。16n元集含有n个元素的集合简称n元集，它的含有m(m≤n)个元素的子集叫做它的m元子集。例6.1A＝{1,2,3}，将A的子集分类：0元子集（空集）1元子集（单元集）{1}，{2}，{3}2元子集{1,2}，{1,3}，{2,3}3元子集{1,2,3}17幂集(powerset)一般地说，对于n元集A，它的0元子集有个，1元子集有个，…，m元子集有个，…，n元子集有个。子集总数为nnn2n1n0n2CCCC0nC1nCmnCnnC定义6.5设A为集合，把A的全部子集构成的集合叫做A的幂集，记作P(A)(或PA，2A)。P(A)＝{x|xA}若A是n元集，则P(A)有2n个元素。18全集定义6.6在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作E。说明全集是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。例如，在研究平面上直线的相互关系时，可以把整个平面(平面上所有点的集合)取作全集，也可以把整个空间(空间上所有点的集合)取作全集。一般地说，全集取得小一些，问题的描述和处理会简单些。196.2集合的运算定义6.7设A，B为集合，A与B的并集A∪B，交集A∩B，B对A的相对补集A－B分别定义如下：A∪B＝{x|x∈A∨x∈B}(unionset)A∩B＝{x|x∈A∧x∈B}(intersectionset)A－B＝{x|x∈A∧xB}(differenceset)举例设A＝{a，b，c}，B＝{a}，C＝{b，d}则有A∪B＝{a，b，c}，A∩B＝{a}，A－B＝{b，c}，B－A＝，B∩C＝说明如果两个集合的交集为，则称这两个集合是不相交的。例如B和C是不相交的。20n个集合的并和交两个集合的并和交运算可以推广成n个集合的并和交：A1∪A2∪…∪An＝{x|x∈A1∨x∈A2∨…∨x∈An}A1∩A2∩…∩An＝{x|x∈A1∧x∈A2∧…∧x∈An}上述的并和交可以简记为：n1iiA＝A1∩A2∩…∩Ann1iiA＝A1∪A2∪…∪An两个集合的并和交运算可以推广到无穷多个集合的情况：1iiA＝A1∩A2∩…1iiA＝A1∪A2∪…21对称差集定义6.8设A，B为集合，A与B的对称差集AB定义为：AB＝(A－B)∪(B－A)对称差运算的另一种定义是AB＝(A∪B)－(A∩B)例如:A＝{a，b，c}，B＝{b，d}，则AB＝{a，c，d}22绝对补集定义6.9～A＝E－A＝{x|x∈E∧xA}因为E是全集，x∈E是真命题，所以～A可以定义为：A＝{x|xA}例如:E＝{a，b，c，d}，A＝{a，b，c}～A＝{d}23文氏图(VennDiagram)集合之间的关系和运算可以用文氏图给予形象的描述。文氏图的构造方法如下：–画一个大矩形表示全集E(有时为简单起见可将全集省略)。–在矩形内画一些圆(或任何其它的适当的闭曲线)，用圆的内部表示集合。–不同的圆代表不同的集合。如果没有关于集合不交的说明，任何两个圆彼此相交。–图中阴影的区域表示新组成的集合。–可以用实心点代表集合中的元素。24文氏图的实例25有穷集的计数问题使用文氏图可以很方便地解决有穷集的计数问题。首先根据已知条件把对应的文氏图画出来。–一般地说，每一条性质决定一个集合。–有多少条性质，就有多少个集合。–如果没有特殊说明，任何两个集合都画成相交的然后将已知集合的元素数填入表示该集合的区域内。–通常从n个集合的交集填起，–根据计算的结果将数字逐步填入所有的空白区域。–如果交集的数字是未知的，可以设为x。根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。26例6.2例6.2对24名会外语的科技人员进行掌握外语情况的调查。其统计结果如下：会英、日、德和法语的人分别为13，5，10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数。解：令A，B，C，D分别表示会英、法、德、日语的人的集合。根据题意画出文氏图。设同时会三种语言的有x人，只会英、法或德语一种语言的分别为y1，y2和y3人。将x和y1，y2，y3填入图中相应的区域，然后依次填入其它区域的人数。27例6.24-x4-x4-xxy2y1y325-2英13法9德10日5y1+2(4-x)+x+2＝13y2+2(4-x)+x＝9y3+2(4-x)+x＝10y1+y2+y3+3(4-x)+x＝24-528包含排斥原理定理6.2设S为有穷集，P1,P2,…,Pm是m个性质。S中的任何元素x或者具有性质Pi，或者不具有性质Pi(i=1,2,…m),两种情况必居其一。令Ai表示S中具有性质Pk的元素构成的子集，则S中不具有性质P1,P2,…,Pm的元素为|AAA|1)(|AAA||AA||A||S||AAA|m21mkjmkji1ijmji1im1iim2129推论S中至少具有一条性质的元素数为mkji1m211mkjimji1jim1iim21|AAA|1)(|AAA||AA||A||AAA|30例6.3例6.3求1到1000之间(包含1和1000在内)既不能被5和6，也不能被8整除的数有多少个。解答S＝{x|x∈Z∧1≤x≤1000}A＝{x|x∈S∧x可被5整除}B＝{x|x∈S∧x可被6整除}C＝{x|x∈S∧x可被8整除}|T|表示有穷集T中的元素数x表示小于等于x的最大整数lcm(x1,x2,…,xn)表示x1,x2,…,xn的最小公倍数31例6.3|A|＝1000/5＝200|B|＝1000/6＝166|C|＝1000/8＝125|A∩B|＝1000/lcm(5,6)＝33|A∩C|＝1000/lcm(5,8)＝25|B∩C|＝1000/lcm(6,8)＝41|A∩B∩C|＝1000/lcm(5,6,8)＝8将这些数字依次填入文氏图，得到32例6.3根据包含排斥原理，所求不能被5，6和8整除的数应为由文氏图也可得知，不能被5，6和8整除的数有1000－(200+100＋33＋67)＝600个。6008-41)25(33125)166(200-1000|CBA||)CB||CA||BA(||)C||B||A(||S||CBA|33广义并和广义交定义6.10设A为集合，A的元素的元素构成的集合称为A的广义并，记为∪A。符号化表示为∪A＝{x|z(z∈A∧x∈z)}定义6.11设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记为∩A。符号化表示为∩A＝{x|z(z∈A→x∈z)}34例6.4例6.4设A＝{{a,b,c},{a,c,d},{a,e,f}}B＝{{a}}C＝{a,{c,d}}则∪A＝{a,b,c,d,e,f}∪B＝{a}∪C＝a∪{c,d}∪＝∩A＝{a}∩B＝{a}∩C＝a∩{c,d}35广义并与广义交的说明若A＝{A1,A2,…,An}，则∪A＝A1∪A2∪…∪An若A＝{A1,A2,…,An}，则∩A＝A1∩A2∩…∩An在后面的叙述中，若只说并或交，则这都是指集合的初级并或初级交；如果在并或交前边冠以“广义”两个字，则指集合的广义并或广义交。为了使得集合表达式更为简洁，我们对集合运算的优先顺序做如下规定：–称广义并、广义交、幂集、绝对补运算为一类运算–并、交、相对补、对称差运算为二类运算。–一类运算优先于二类运算–一类运算之间由右向左顺序进行–二类运算之间由括号决定先后顺序。36例6.5例6.5设A＝{{a},{a,b}}计算∪∪A，∩∩A，∩