离散数学3.9划分与覆盖资料.ppt

《离散数学3.9划分与覆盖资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1离散数学(DiscreteMathematics)第三章集合与关系（SetsandRelations)3.6关系的闭包运算(ClosureOperations)3.7集合的划分与覆盖(Partition&CoverofSets)3.8等价关系(EquivalentRelations)3.9相容关系(CompatibilityRelations)3.10序关系(OrderedRelations)3.1集合及其运算(Sets&Operationswithsets)3.2序偶与笛卡尔积(OrderedPairs&Carte

2、sianProduct)3.3关系(Relations)3.4关系的性质(ThePropetiesofRelations)3.5复合关系与逆关系(CompoundRelations&InverseRelations)3.7集合的划分与覆盖(Partition&CoverofSets)3.7.1集合的划分(PartitionofSets)3.7.2集合的覆盖(CoverofSets)3.7.3全集的划分(ThePartitionoftheUniversalSetU)第三章集合与关系(Sets&Relations)3.7集

3、合的划分与覆盖（1），当i≠j时(2)例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集合的划分(PartitionofSets)定义3.7.1设有非空集合A，S={A1,A2,…,Am}，其中，且（i=1，2，…，m），若例2设A={2，3，4，8，9，10，15}定义A的如下子集：试问是否A的一个划分。解根据题意{2，4，8，10}{3，9，1

4、5}{10，15}不是A的划分，可成为A的一个划分。3.7.2集合的覆盖(CoverofSets)定义3.7.2设有非空集合A，,其中且（i=1，2，…，m），若，则称S是集合A的一个覆盖。例如例2中是A的划分，也是A的覆盖。是A的覆盖，但不是A的划分。例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，

5、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,e，f}}（）11说明:(1)若S是A的划分,则S也一定是A的覆盖.(2)任意给定集合A的划分或覆盖不是唯一的.(3)给定了集合A的划分或覆盖,则A便唯一确定.(4)覆盖中各子集可重叠,划分则不然.(5)以非空集A为元素的集合S={A}称为A的最小划分.(6)称为A的最大划分.例4n个元素的集合A，有多少种不同的方法划

6、分成为两块？解A有个不同的子集，且这个不同的子集中，两两互补，除和U互补，但不能构成A的分划外，其余的每对集合均构成将A分成两块的一个划分，因此A有种方法分成两块。3.7.3全集的划分(ThePartitionoftheUniversalSetU)设A,B,C是全集U的子集,则及都是A的划分.一般地,设是全集U的m个子集,则为U的一个划分.其中第三章集合与关系(Sets&Relations)小结:本节介绍了集合的划分与覆盖的概念及全集的划分。重点掌握集合的划分与覆盖的概念。作业：P130（1），（2）