离散数学课件：3-8 集合的划分和覆盖.ppt

八、集合的划分和覆盖八、集合的划分和覆盖 设设X为非空集，为非空集，S={S1, S2, …, Sm}, Si  X，， Si (i=1, 2, …, m)且且S1∪∪S2∪∪…∪∪Sm=X，称，称S是是X的的覆盖覆盖(covering). 若再加若再加Si∩Sj=(i≠j, i,j=1,2,…,m)，，则称则称S是是X的的划分划分(partition), m称为称为S的秩的秩.(一一) 集合的划分和覆盖的定义集合的划分和覆盖的定义(a)集合的覆盖集合的覆盖(b)集合的划分集合的划分例例例例3.8.13.8.1设设X={1,2,3,4,5}，则，则C={{1,2},{3},{4,5}}B={{1,2},{2,3},{4,5}}A={{1,2,3},{4}}U={{1,2,3,4,5}}V={{1},{2},{3},{4},{5}}U称为称为X的的最小划分最小划分，，V称为称为X的的最大划分最大划分.划分划分划分划分划分划分非覆盖非覆盖覆盖覆盖集合的划分和覆盖的定义集合的划分和覆盖的定义八、集合的划分和覆盖八、集合的划分和覆盖(二二) 交叉划分交叉划分 若若{A1, A2, …, Ar}与与{B1, B2, …, Bs}是同一集是同一集合合X的两种划分，则其中所有的两种划分，则其中所有Ai∩Bj组成的集合，组成的集合，称为是原来两种划分的称为是原来两种划分的交叉划分交叉划分.例例例例3.8.23.8.2 给定一个玩具积木的集合给定一个玩具积木的集合按颜色得划分：按颜色得划分： 按形状得划分：按形状得划分： 同时考虑颜色和形状，得交叉划分：同时考虑颜色和形状，得交叉划分： { }, { }x2x1x6x5x3x8x4x7x2x1x6x5x3x8x4x7X={ }{ }, { }x2x1x6x5x3x8x4x7x2x1x6x5x3x8x4x7{ }, { }, { }, { }八、集合的划分和覆盖八、集合的划分和覆盖交叉划分交叉划分 设设{A1, A2, …, Ar}与与{B1, B2, …, Bs}是同一集是同一集合合X的两种划分，则其交叉划分亦是原集合的一种划的两种划分，则其交叉划分亦是原集合的一种划分分.证：证：设设{A1, A2, …, Ar}与与{B1, B2, …, Bs}的交叉划的交叉划分为分为 T={Ai∩Bj |1  i  r, 1  j  s}.(1)=X.八、集合的划分和覆盖八、集合的划分和覆盖交叉划分交叉划分 设设{A1, A2, …, Ar}与与{B1, B2, …, Bs}是同一集是同一集合合X的两种划分，则其交叉划分亦是原集合的一种划的两种划分，则其交叉划分亦是原集合的一种划分分.证：证：(2)任取任取Ai∩Bj , Ah∩Bk T ，，所以，所以，T是是X的一个划分的一个划分.(Ai∩Bj) ∩(Ah∩Bk)=, i   h i=h, j k , 八、集合的划分和覆盖八、集合的划分和覆盖(三三) 划分的加细划分的加细 设设{A1, A2, …, Ar}与与{B1, B2, …, Bs}是同一集是同一集合合X的两种划分，若对于每个的两种划分，若对于每个Aj均有均有Bk，使，使Aj   Bk ,则则{A1, A2, …, Ar}称为是称为是{B1, B2, …, Bs}的的加细加细. 性质：性质：任何两种划分的交叉划分都是原划分的一任何两种划分的交叉划分都是原划分的一种加细种加细.证：证： 设设{A1, A2, …, Ar}与与{B1, B2, …, Bs}的交叉划的交叉划分为分为 T={Ai∩Bj |1  i  r, 1  j  s}.则对则对T中任意元素中任意元素Ai∩Bj ，，均有均有Ai∩Bj   Ai , Ai∩Bj   Bj ,故故T是原划分的加细是原划分的加细.八、集合的划分和覆盖八、集合的划分和覆盖例例例例3.8.23.8.2 给定一个玩具积木的集合给定一个玩具积木的集合按颜色得划分：按颜色得划分： 按形状得划分：按形状得划分： 同时考虑颜色和形状，得交叉划分：同时考虑颜色和形状，得交叉划分： { }, { }x2x1x6x5x3x8x4x7x2x1x6x5x3x8x4x7X={ }{ }, { }x2x1x6x5x3x8x4x7x2x1x6x5x3x8x4x7{ }, { }, { }, { }划分的加细划分的加细从这个例子可以看到：从这个例子可以看到：&交叉划分也是原集合的一种划分；交叉划分也是原集合的一种划分；&交叉划分是原来各划分的加细交叉划分是原来各划分的加细. HW: 3-9习题习题 (1);(5)八、集合的划分和覆盖八、集合的划分和覆盖。