集合划分覆盖等价及序关系课件.ppt

《集合划分覆盖等价及序关系课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3-9集合的划分和覆盖定义3-9.1[覆盖cover]：若把一个集合A分成若干个叫做分块的非空子集，使得A中每个元素至少属于一个分块，这些分块的全体叫做A的一个覆盖。即：设A为非空集合，S={S1,S2,…,Sm}，其中SiA，Si≠(i=1,2,…,m)且S1S2…Sm＝A，则集合S称作集合A的覆盖。例:判断以下集合是否为集合A的覆盖？其中A={a,b,c,d,e,f}（1）S1={,{a,b},{c,d},{f}}（2）S2={{a,b},{c,d},{f,g}}（3）S3={{a,b},{c,d},{f}}（4）S4={{a,b},{c,d,e},{e,f}}不

2、是不是不是是定义3-9.2[划分partition]：给定集合A的一个覆盖S，若A中的每个元素属于且仅属于S的一个分块，则S称作是A的一个划分。即：若S是集合A的覆盖，且满足Si∩Sj=，（这里i≠j），则称S是A的划分。是例:判断以下集合是否为集合A的划分？其中A={a,b,c,d,e,f}（1）S1={,{a,b,c,d},{f}}（2）S4={{a,b},{c,d,e},{e,f}}（3）S5={{a,b},{c,d},{e,f}}（4）S6={{a},{b},{c},{d},{e},{f}}（5）S7={{a,b,c,d,e,f}}我们看到对于一个给定集合,划分不唯一

3、不是不是是是最大划分最小划分定义3-9.3[交叉划分]：若{A1,A2,…,Ar}与{B1,B2,…,Bs}是同一集合A的两种划分，则其中所有Ai∩Bj组成的非空集合，称为原来两种划分的交叉划分。定义3-9.4[加细]：给定X集合的任意两个划分{A1,A2,…,Ar}和{B1,B2,…,Bs}，若对于每一个Aj，均有Bk使AjBk，则称{A1,A2,…,Ar}为{B1,B2,…,Bs}的加细。定理3-9.1:设{A1,A2,…,Ar}与{B1,B2,…,Bs}是同一集合X的两种划分，则其交叉划分仍是原集合的一种划分。证明见书129页。定理3-9.2:任何两种划分的交叉划分，都是

4、原来各划分的一种加细。证明见书130页。3-10等价关系与等价类3-10.1等价关系定义3-10.1[等价关系EquivalenceRelations]：设A，RAA，若R是自反的、对称的和传递的，则称R为A上的等价关系。例如平面上三角形集合中，三角形的全等关系、相似关系是等价关系。一个班级中，同学之间的同姓关系也是等价关系例1:见书131页例题2（验证一个等价关系）3-10.2等价类定义3-10.2[等价类Equivalenceclasses]：设R是非空集合A上的等价关系，对任意的aA，定义[a]R={xA

5、aRx}，称为a关于R的等价类，简称a的等价类，在不混淆

6、的情况下记为[a]。显然[a]R非空，因为a[a]R定理3-10.1设R是非空集合A上的等价关系，对于任意a,bA，有aRbiff[a]R=[b]R。证明：假设[a]R=[b]R，因为a[a]R，故a[b]R，即aRb。若aRb，设c[a]RaRccRacRbc[b]R，即[a]R[b]R同理，若c[b]RbRccRbcRac[a]R，即[a]R[b]R由此证得若aRb，则[a]R=[b]R定义3-10.3[商集]：设R是非空集合A上的等价关系，关于R的全体不同的等价类为元素的集合{[a]R

7、aA}称为A关于R的商集，记为A/R。例2：仍以书

8、131页例题2为例（给出一个集合和等价关系，求商集）。定理3-10.2：非空集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R。定理的证明见书133页上，在此省略。定理3-10.3：集合A的一个划分确定A的元素间的一个等价关系。定理的证明见书133页下，在此省略。例：包含三个元素的集合，可以有多少种不同的划分，就有多少种等价关系。5种。看P134例题4定理3-10.4：设R1和R2为非空集合A上的等价关系，则R1=R2当且仅当A/R1=A/R2。定理的证明见书134页中，在此省略。本次课小结及要求小结：1.集合的划分和覆盖的概念2.等价关系的概念及等价关系与划分一一对

9、应要求：1.掌握集合的划分和覆盖的概念2.掌握等价关系的概念，会判断一个关系是否是等价关系，记住几个实例。3.掌握等价关系与划分一一对应，给定划分会求等价关系；给定等价关系会求划分。作业（3-10）P134(3)(7)(5)选作3-11相容关系定义3-11.1[相容关系]：给定集合A上的关系r，若r是自反的，对称的，则称r是相容关系。我们可以知道，相容关系的关系矩阵的对角线元素都为1，且是对称矩阵，为此，可以将矩阵用梯形表示。关系图上，每个结点都有自回路，且相关结点间的有向边成对