《离散数学-3-9集合的划分和覆盖.ppt》由会员分享，可在线阅读，更多相关《离散数学-3-9集合的划分和覆盖.ppt（11页珍藏版）》请在三一办公上搜索。
1、1,第三章 集合与关系,3-9 集合的划分和覆盖 授课人：李朔Email:,2,一、集合的覆盖和划分,在集合的讨论中，常须把一个集合分成若干子集加以讨论，这就是集的划分问题。如一个班男、女生。一个学院不同专业。P128 定义3-9.1 若把一个集合A分成若干个称为分块的非空子集，使得A中每个元素至少属于一个分块，那么这些分块的全体构成的集合称为A的一个覆盖。上述定义与下面定义是等价。令A为给定非空集合，S=S1,S2,Sm,其中SiA且Si(i=1,2,m)且 则称S是集合A的一个覆盖。*如果A中每个元素属于且仅属于一个分块，那么这些分块的全体构成的集叫做A的一个划分（或分划）。即：若有Si
2、Sj=(ij)，则称S为A的一个划分。,3,一、集合的覆盖和划分,例 设 A=a,b,c，以下是A的子集构成的集合：S=a,b,b,c Q=a,a,b,a,c D=a,b,c G=a,b,c E=a,b,c F=a,a,c 试确定哪些集合是A的覆盖？哪些集合是A的划分？哪些集合既不是覆盖，也不是划分？,4,一、集合的覆盖和划分,例 设 A=a,b,c，以下是A的子集构成的集合：S=a,b,b,c Q=a,a,b,a,c D=a,b,c G=a,b,c E=a,b,c F=a,a,c 试确定哪些集合是A的覆盖？哪些集合是A的划分？哪些集合既不是覆盖，也不是划分？解：S和Q是A的覆盖，但不是划分；
3、D、G和E是A的覆盖，也是划分；F不是A的覆盖，也不是划分。,5,一、集合的覆盖和划分,例 A=a,b,c则 S=a,b,b,c、Q=a,a,b,a,c都为A的覆盖，而D=a,b,c、G=a,b,c、E=a,b,c为A的划分。而且称G为A的最小划分（由集合的全部元素组成），而E为A的最大划分（每个元素构成一个单元素分块）。*划分必是覆盖，覆盖未必是划分,6,一、集合的覆盖和划分,例3 设A=1,2,3，试确定A的所有划分。,解：有一个划分块的划分是：1,2,3 有两个划分块的划分是：1,2,3 2,1,3 3,1,2 有三个划分块的划分是：1,2,3上图是A的所有划分的示意图。(a)表示有一个
4、划分块的划分1,2,3。(b)、(c)和(d)表示有两个划分块的划分1,2,3、2,1,3和3,1,2。(e)表示有三个划分块的划分1,2,3。*给定一个集合A，它的划分和覆盖都不是唯一的。,7,一、集合的覆盖和划分,例：4个元素的集合A共有多少个不同的划分。解：A的最大(所有元素），最小划分（各元素单列）都各有一个 把4个元素分成1，3两部分，有4种可能；把4个元素分成2，2两部分，有3种可能；把4个元素分成1，1，2三部分，有6种可能。故总共有1136415种。,8,二、交叉划分,P129 定义3-9.2 若A1,A2,Ar与B1,B2,Bs是同一集合A的两种划分，则其中所有AiBj 所组
5、成的集，称为原来两种划分的交叉划分。例 P129 所有生物定理3-9.1 设A1,A2,Ar与B1,B2,Bs是同一集合X上的两种划分，则其交叉划分也是原集合的一种划分。,9,三、划分的加细,定义3-9.3 对集合X上的任两种划分A1,A2,Ar与B1,B2,Bs，若对于每一个Aj均有Bk，使得Aj Bk，则A1,A2,Ar称为B1,B2,Bs的加细。定理3.9.2 任何两种划分的交叉划分，都是原划分的一种加细。证明：设A1,A2,Ar和B1,B2,Bs的交叉划分为T，对T中的任意元素Aj Bj，必有Aj Bj Aj,Aj Bj Bj故T必是原划分的加细。,10,本课小结,覆盖划分交叉划分划分的加细,11,作业,P130（2）,
