离散数学-3-9集合的划分和覆盖

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第三章 集合与关系,3-9 集合的划分和覆盖,授课人：李朔,Email:,1,一、集合的覆盖和划分,在,集合,的讨论中，常须把一个集合分成若干子集加以讨论，这就是集的划分问题。如一个班男、女生。一个学院不同专业。,P128,定义3-9.1,若把一个集合,A,分成若干个称为分块的非空子集，使得,A,中每个元素至少属于一个分块，那么这些分块的全体构成的集合称为,A,的一个,覆盖,。,上述定义与下面定义是等价。,令,A,为给定非空集合，,S=S,1,S,2,S,m,其中,S,i,A,且,S,i,(i=1,2,m),且,则称,S,是集合,A,的一个,覆盖,。,*如果,A,中每个元素属于且仅属于一个分块，那么这些分块的全体构成的集叫做,A,的一个,划分（或分划）,。即：若有,S,i,S,j,=,(i,j)，,则称,S,为,A,的一个划分。,2,一、集合的覆盖和划分,例 设,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,的划分？哪些集合既不是覆盖，也不是划分？,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,的划分,？哪些集合,既不是覆盖，也不是划分,？,解：,S,和,Q,是,A,的覆盖，但不是划分；,D,、,G,和,E,是,A,的覆盖，也是划分；,F,不是,A,的覆盖，也不是划分。,4,一、集合的覆盖和划分,例,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,的,最大划分（每个元素构成一个单元素分块）,。,*划分必是覆盖，覆盖未必是划分,5,一、集合的覆盖和划分,例3 设,A,=,1,2,3,，,试确定,A,的所有划分。,解：,有一个划分块的划分是：,1,2,3,有两个划分块的划分是：,1,2,3,2,1,3,3,1,2,有三个划分块的划分是：,1,2,3,上图是,A,的所有划分的示意图。(,a),表示有一个划分块的划分,1,2,3,。(,b)、(c),和(,d),表示有两个划分块的划分,1,2,3,、,2,1,3,和,3,1,2,。(,e),表示有三个划分块的划分,1,2,3,。,*给定一个集合,A，,它的划分和覆盖都不是唯一的。,6,一、集合的覆盖和划分,例,：4个元素的集合,A,共有多少个不同的划分。,解：,A,的最大(所有元素），最小划分（各元素单列）都各有一个,把4个元素分成1，3两部分，有4种可能；,把4个元素分成2，2两部分，有3种可能；,把4个元素分成1，1，2三部分，有6种可能。,故总共有1136415种。,7,二、交叉划分,P129,定义3-9.2,若,A,1,A,2,A,r,与,B,1,B,2,B,s,是同一集合,A,的两种划分，则其中所有,A,i,B,j,所组成的集，称为原来两种划分的,交叉划分,。,例,P129,所有生物,定理3-9.1,设,A,1,A,2,A,r,与,B,1,B,2,B,s,是同一集合,X,上的两种划分，则其,交叉划分也是原集合的一种划分,。,8,三、划分的加细,定义3-9.3,对集合,X,上的任两种划分,A,1,A,2,A,r,与,B,1,B,2,B,s,，,若对于每一个,A,j,均有,B,k,，,使得,A,j,B,k,，,则,A,1,A,2,A,r,称为,B,1,B,2,B,s,的加细,。,定理3.9.2,任何两种划分的交叉划分，,都是原划分的一种加细。,证明：,设,A,1,A,2,A,r,和,B,1,B,2,B,s,的交叉划分为,T，,对,T,中的任意元素,A,j,B,j,，,必有,A,j,B,j,A,j,A,j,B,j,B,j,故,T,必是原划分的加细。,9,本课小结,覆盖,划分,交叉划分,划分的加细,10,作业,P130（2）,11,