离散数学(3.9划分与覆盖)

1离散数学(DiscreteMathematics)第三章集合与关系（SetsandRelations)

3.6关系的闭包运算(ClosureOperations)3.7集合的划分与覆盖(Partition&CoverofSets)3.8等价关系(EquivalentRelations)3.9相容关系(Compatibility

Relations)3.10序关系(OrderedRelations)3.1集合及其运算(Sets&Operationswithsets)

3.2序偶与笛卡尔积(OrderedPairs&CartesianProduct)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集合的划分与覆盖（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，15}{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，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，有多少种不同的方法划分成为两块？

解A有个不同的子集，且这个不同的子集中，两两互补，除和U互补，但不能构成A的分划外，其余的每对集合均构成将A分成两块的一个划分，因此A

有种方法分成两块。

3.7.3全集的划分(ThePartitionoftheUniversalSetU)设A,B,C是全集U的子集,则及都是A的划分.一般地,设是全集U的m个子集,则