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

第三章 集合与关系 3-9 集合的划分和覆盖 授课人：李朔 Email:chn.nj.ls@ 一、集合的覆盖和划分 在集合的讨论中，常须把一个集合分成若干子集加以讨论，这就是集的划分问题。如一个班男、女生。一个学院不同专业。 P128 定义3-9.1 若把一个集合A分成若干个称为分块的非空子集，使得A中每个元素至少属于一个分块，那么这些分块的全体构成的集合称为A的一个覆盖。 上述定义与下面定义是等价。 令A为给定非空集合，S ={S1, S2, ?, Sm},其中Si?A且Si?? ? (i=1, 2, ?, m) 且 则称S是集合A的一个覆盖。 *如果A中每个元素属于且仅属于一个分块，那么这些分块的全体构成的集叫做A的一个划分（或分划）。即：若有Si ?Sj =? (i?j)，则称S为A的一个划分。 一、集合的覆盖和划分 例 设 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的划分？哪些集合既不是覆盖，也不是划分？ 一、集合的覆盖和划分 例 设 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的覆盖，也不是划分。 一、集合的覆盖和划分 例 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的最大划分（每个元素构成一个单元素分块）。 *划分必是覆盖，覆盖未必是划分 一、集合的覆盖和划分 例3 设A=?1,2,3?，试确定A的所有划分。 一、集合的覆盖和划分 例：4个元素的集合A共有多少个不同的划分。 解：A的最大(所有元素），最小划分（各元素单列）都各有一个 把4个元素分成1，3两部分，有4种可能； 把4个元素分成2，2两部分，有3种可能； 把4个元素分成1，1，2三部分，有6种可能。 故总共有1＋1＋3＋6＋4＝15种。 二、交叉划分 P129 定义3-9.2 若{A1, A2, ?, Ar}与{B1, B2, ?, Bs}是同一集合A的两种划分，则其中所有Ai?Bj ??所组成的集，称为原来两种划分的交叉划分。 例 P129 所有生物 定理3-9.1 设{A1, A2, ?, Ar}与{B1, B2, ?, Bs}是同一集合X上的两种划分，则其交叉划分也是原集合的一种划分。 三、划分的加细 定义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必是原划分的加细。 本课小结 覆盖 划分 交叉划分 划分的加细 作业 P130 （2） * * 解：有一个划分块的划分是：??1,2,3?? 有两个划分块的划分是：??1?,?2,3??