离散数学3.9划分与覆盖名师优质课获奖市赛课一等奖课件.ppt

1离散数学离散数学(Discrete Mathematics)第1页第三章第三章 集合与关系集合与关系（Sets and Relations)Sets and Relations)3.6 3.6 关系闭包运算关系闭包运算(Closure Operations)(Closure Operations)3.7 3.7 集合划分与覆盖集合划分与覆盖(Partition&Cover of Sets)(Partition&Cover of Sets)3.8 3.8 等价关系等价关系(Equivalent Relations)(Equivalent Relations)3.9 3.9 相容关系相容关系(Compatibility(CompatibilityRelations)Relations)3.10 3.10 序关系序关系(Ordered Relations)(Ordered Relations)3.1 3.1 集合及其运算集合及其运算(Sets&Operations with sets)(Sets&Operations with sets)3.2 3.2 序偶与笛卡尔积序偶与笛卡尔积(Ordered Pairs&Cartesian Product)(Ordered Pairs&Cartesian Product)3.3 3.3 关系关系(Relations)(Relations)3.4 3.4 关系性质关系性质(The Propeties of Relations)(The Propeties of Relations)3.5 3.5 复合关系与逆关系复合关系与逆关系(Compound Relations&Inverse(Compound Relations&Inverse Relations)Relations)第2页3.7 3.7 集合划分与覆盖集合划分与覆盖(Partition&Cover of Sets)(Partition&Cover of Sets)3.7.1 3.7.1 集合划分集合划分 (Partition of Sets)(Partition of Sets)3.7.2 3.7.2 集合覆盖集合覆盖(Cover of Sets)(Cover of Sets)3.7.3 3.7.3 全集划分全集划分 (The Partition of the Universal(The Partition of the Universal Set U)Set U)第三章第三章 集合与关系集合与关系(Sets&Relations)第3页 3.7 3.7 集合划分与覆盖集合划分与覆盖（1），当，当ij时时 (2)例例 1 1 设设A=1，2，3，4 则则 S1=1，2，3，4,S2=2，3，1，4,S3=1，2，3，4 都是都是A划分划分.则称则称S是集合是集合A一个划分，每一个一个划分，每一个 称为这个划分一个分块。称为这个划分一个分块。3.7.1 3.7.1 集合划分集合划分 (Partition of Sets)(Partition of Sets)定义定义3.7.13.7.1 设有非空集合设有非空集合A，S=A1,A2,Am，其，其中中 ，且，且 （i=1，2，m），若），若 第4页例例 2 2 设设A=2A=2，3 3，4 4，8 8，9 9，1010，15 15 定义定义A A以下子集：以下子集：试问试问 是否是否A一个划分。一个划分。解解依据题意依据题意 2，4，8，10 3，9，1510，15 不是不是A划分，划分，可成为可成为A一个划分。一个划分。第5页3.7.2 3.7.2 集合覆盖集合覆盖(Cover of Sets)(Cover of Sets)定义定义3.7.23.7.2 设有非空集合设有非空集合A，,其中其中 且且 （i=1，2，m），若），若 ，则称则称S是集合是集合A一个覆盖。一个覆盖。比如比如 例例2中中 是是A划分，也是划分，也是A覆盖。覆盖。是是A覆盖，但不是覆盖，但不是A划分。划分。第6页例例3 设设A=a，b，c，d，e，f，指指出出以以下下哪哪些些是是A划划分分（在在对对应应括括号号内内填填入入“1”），哪哪些些是是A覆覆盖盖（在在对对应应括括号号内内填填入入“2”），哪哪些些既既不不是是划划分分，也不是覆盖（在对应括号内填入也不是覆盖（在对应括号内填入“0”）S1=a，b ，c，d ，a，e，f （）S2=c，e ，c，d，f ，b （）S3=a，b，c，d ，e，f （）S4=a，c，e ，b，c （）201,20S5=a,b,c,d,e,f,（）S6=a，b，c，d,d,e，f f （）11第7页说明说明:(1)若若S是是A划分划分,则则S也一定是也一定是A覆盖覆盖.(2)任意给定集合任意给定集合A划分或覆盖不是唯一划分或覆盖不是唯一.(3)给定了集合给定了集合A划分或覆盖划分或覆盖,则则A便唯一确定便唯一确定.(4)覆盖中各子集可重合覆盖中各子集可重合,划分则不然划分则不然.(5)以非空集以非空集A为元素集合为元素集合S=A称为称为A最小划分最小划分.(6)称为称为A最大划分最大划分.第8页例例4 n个元素集合个元素集合A，有多少种不一样方法划，有多少种不一样方法划分成为两块？分成为两块？解解 A有有 个不一样子集，且这个不一样子集，且这 个不一个不一样子集中，两两互补，除样子集中，两两互补，除 和和U互补，但互补，但不能组成不能组成A分划外，其余每对集合均组成分划外，其余每对集合均组成将将A分成两块一个划分，所以分成两块一个划分，所以A有有 种方法分成两块。种方法分成两块。第9页3.7.3 3.7.3 全集划分全集划分 (The Partition of the(The Partition of the Universal Set U)Universal Set U)设设A,B,C是全集是全集U子集子集,则则 及及都是都是A划分划分.普通地普通地,设设 是全集是全集Um个子集个子集,则则 为为U一个划分一个划分.第10页其中其中第11页第三章第三章 集合与关系集合与关系(Sets&Relations)小结小结:本节介绍了集合本节介绍了集合划分与覆盖概念及全划分与覆盖概念及全集划分。重点掌握集划分。重点掌握集合集合划分与覆盖概念。划分与覆盖概念。作业作业：P130（1），（2）第12页