《集合划分覆盖等价及序关系ppt课件.ppt》由会员分享，可在线阅读，更多相关《集合划分覆盖等价及序关系ppt课件.ppt（48页珍藏版）》请在三一办公上搜索。
1、3-9 集合的划分和覆盖,定义3-9.1覆盖cover：若把一个集合A分成若干个叫做分块的非空子集，使得A中每个元素至少属于一个分块，这些分块的全体叫做A的一个覆盖。即：设A为非空集合，S=S1,S2 ,Sm，其中Si A，Si(i=1,2, ,m) 且S1S2 SmA，则集合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 ,不是,不是,不是,是,定义3-9.2划分partition ：给定集合A的一个覆
2、盖S，若A中的每个元素属于且仅属于S的一个分块，则S称作是A的一个划分。即：若S是集合A的覆盖，且满足SiSj=， （这里ij），则称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-9.3交叉划分：若A1,A2, ,Ar与B1,B2, ,Bs是同一集合A的两种划分，则其
3、中所有AiBj组成的非空集合，称为原来两种划分的交叉划分。定义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: 任何两种划分的交叉划分，都是原来各划分的一种加细。证明见书130页。,3-10 等价关系与等价类,3-10.1 等价关系定义3-10.1等价关系Equivalence Relations：设A ，R A
4、 A，若R是自反的、对称的和传递的，则称R为A上的等价关系。例如平面上三角形集合中，三角形的全等关系、相似关系是等价关系。一个班级中，同学之间的同姓关系也是等价关系例1:见书131页例题2（验证一个等价关系）,3-10.2 等价类,定义3-10.2等价类Equivalence classes：设R是非空集合A上的等价关系，对任意的aA，定义 aR = xA | aRx，称为a关于R的等价类，简称a的等价类，在不混淆的情况下记为a。显然aR非空，因为a aR,定理3-10.1 设R是非空集合A上的等价关系，对于任意a, bA，有aRb iff aR =bR。证明：假设aR =bR，因为a aR
5、，故a bR ，即aRb。若aRb，设caR aRc cRa cRb cbR ，即aR bR同理，若cbR bRc cRb cRa caR ，即aR bR由此证得若aRb，则aR =bR,定义3-10.3商集：设R是非空集合A上的等价关系，关于R的全体不同的等价类为元素的集合 aR| aA称为A关于R的商集，记为A/R。例2：仍以书131页例题2为例（给出一个集合和等价关系，求商集）。,定理3-10.2：非空集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R。定理的证明见书133页上，在此省略。,定理3-10.3：集合A的一个划分确定A的元素间的一个等价关系。定理的证明见书133页
6、下，在此省略。例：包含三个元素的集合，可以有多少种不同的划分，就有多少种等价关系。5种。看P134 例题4,定理3-10.4：设R1和R2为非空集合A上的等价关系，则R1=R2当且仅当A/R1=A/R2。定理的证明见书134页中，在此省略。,本次课小结及要求,小结： 1. 集合的划分和覆盖的概念 2. 等价关系的概念及等价关系与划分一一对应要求： 1. 掌握集合的划分和覆盖的概念 2. 掌握等价关系的概念，会判断一个关系是否是等价关系，记住几个实例。 3. 掌握等价关系与划分一一对应，给定划分会求等价关系；给定等价关系会求划分。,作业（3-10）,P134 (3) (7) (5) 选作,3-1
7、1 相容关系,定义3-11.1相容关系：给定集合A上的关系r，若r是自反的，对称的，则称r是相容关系。我们可以知道，相容关系的关系矩阵的对角线元素都为1，且是对称矩阵，为此，可以将矩阵用梯形表示。关系图上，每个结点都有自回路，且相关结点间的有向边成对出现，可以把图形简化为：不画自回路，并用单线（无向边）代替双向有向边。,例1：设X=216，2234，379，648，545，R是X中的二元关系。R=|xX，yX，x和y有相同的数字，试说明R是一个相容关系，并写出R的关系矩阵，画出关系图。解：令X中的元素分别为x1x5，则R=,关系矩阵如下： 1 1 0 1 0 1 1 1 1 1MR= 0 1
8、1 0 0 1 1 0 1 1 0 1 0 1 1转化后如下：X2 1 X3 0 1X4 1 1 0X5 0 1 0 1 x1 x2 x3 x4,x5,x4,x1,x2,x3,定义3-11.2相容类: 设r是集合A上的相容关系，若CA ，如果对于C中任意两个元素a1，a2有a1 r a2，称C是由相容关系r产生的相容类。上例中的相容类有：x1,x2,x1,x4,x2,x4,x2,x4,x5,x2,x3等。,定义3-11.3 最大相容类：设r是集合A上的相容关系，不能真包含在任何其它相容类中的相容类，称作最大相容类。记作Cr。在相容关系图中，最大完全多边形的顶点集合，就是最大相容类。此外，一个孤
9、立结点，以及不是完全多边形的两个结点的连线，也是最大相容类。例2：见P137 例1。,定理3-11.1：设r是有限集合A上的相容关系，C是一个相容类，那么必存在一个最大相容类Cr，使得CCr。定义3-11.4A的完全覆盖：在集合A上给定相容关系r，其最大相容类的集合称作A的完全覆盖，记作Cr(A).例1中X的完全覆盖是 x1,x2,x4,x2,x4,x5, x2,x3,已知集合的覆盖，求相容关系,定理3-11.2：给定集合A的覆盖A1，A2，An，由它确定的关系R=A1A1 A2 A2 An An 是相容关系。定理3-11.3：集合A上的相容关系r与完全覆盖Cr(A)存在一一对应。,作业（3-
10、11）,P139 (2),3-12 序关系,在这一节中，我们将介绍以下一些序关系：偏序关系全序关系良序关系拟序关系*,3-12 序关系,在一个集合上，我们常常要考虑使得元素具有一定的次序的关系，其中很重要的一类关系称作偏序关系。下面给出一些偏序关系的例子：实数集上的小于等于（或大于等于）关系。幂集合中的集合之间的包含关系。整数集合上的整除关系。一个单位里，部门之间的责任关系。若将命题演算中所有合式公式都以主析取（或主合取）范式表示，那么可建立全体合式公式上的蕴含关系。,3-12.1 偏序关系,定义3-12.1偏序关系 (partial order) : 设A ，R A A，若R是自反的、反对称
11、的和传递的，则称R是A上的偏序关系。常将偏序关系R记为“”，并将 xRy记为xy。序偶称为偏序集(partially ordered set, poset) 。,例1:验证实数集R上的小于等于关系“” 是偏序关系。（见书140页例题1）。证明：1. 对于任何实数aR,有aa成立，故“”是自反的。2. 对于任何实数a,bR，如果ab，ba，则必有a=b，故“”是反对称的。3. 如果ab，bc 那么必有ac，故“”是传递的。因此“” 是一个偏序关系。,定义3-12.2盖住:设是偏序集，若有x, yA，x y ，且x y，且不存在其它元素z， zA，使得x z z y，则称元素y盖住元素x。并且记盖
12、住集为：COVA=|x,yA ;y盖住x。例2：求盖住集。P140 例2COVA=, , 。例3： P140 例3COVA=, 。,3-12.2 哈斯图,根据上述定义，可以简化偏序关系的关系图得到哈斯图(Hasse diagram)，具体画法如下：用小圆圈代表元素； 若x y，x y，将代表y的小圆圈放在代表x的小圆圈之上，如果 COVA，则在y与x之间用直线连接。,例3的哈斯图,1,2,3,6,12,4,注意到：哈斯图中的边不再需要用有向边。因为若u，v两点间有边，且u在v的下层，则表示u v，所以边的方向一定是从下层结点指向上层结点的。,由关系图改画为哈斯图的方法,首先去掉自环，然后去掉封
13、闭边，再按照有向边的方向，将结点位置进行重新排列，即有向边起始的结点放下层，终点的结点放上层；最后把有向边改为无向边。,例5：验证定义在P(a,b)上的包含关系是偏序关系，并画出哈斯图。证明：因为P(a,b)有元素为a，b，a，b，；又知a a，b ， b a，b ， a，b ， a ， b ，a，ba ，b ，a a ， b b， ；可看出此包含关系具有自反，反对称和传递性，所以是偏序关系。哈斯图如下：,定义3-12.3链chain，反链：设是一个偏序集合，在A的一个子集中，如果每两个元素都是有关系的，则称这个子集为链。在A的一个子集中，如果每两个元素都是无关的，则称这个子集为反链。我们约定
14、， 若A的子集中只有单个元素，则这个子集既是链又是反链。特别地，当A本身是链，称是全序集，而关系“”称为全序关系。,定义3-12.4全序关系linear order： 在偏序集中，如果A是一个链，则称为全序集合或称线序集合，在这种情况下，二元关系“”称为全序关系或线序关系。全序集linearly ordered sets 就是对任意x，yA，或者有xy或者有yx成立。例如，定义在自然数集合N上的“小于等于”关系“”是偏序关系，且对任意i，jN，必有 ij 或 ji 成立，故也是全序关系。,3-12.3 极大(小)元，最大(小)元,定义3-12.5最大(小)元、极大(小)元： 设为偏序集，BA，
15、则：1. 若存在yB，使得x (xB y x)为真，则称y为B的最小元(least element)。2. 若存在yB，使得x (xB x y)为真，则称y为B的最大元(greatest element)。3. 若存在yB，使得x (xB x y x = y)为真，则称y为B的极小元(minimal element)。4. 若存在yB，使得x (xB y x x = y)为真，则称y为B的极大元(maximal element)。,考虑偏序集, 哈斯图为P143图3-12.7所示。A）若B=a，则a是B的极、最大元， 是B的极、最小元。B）若B=a， b，则B没有最大元和最小元。 a， b是B
16、的极大元，也是极小元。 C）若B=，a，b，则a，b是B的极、最大元， 是B的极、最小元。D）若B=a， b， ，则a，b是B的极大元， 是B的极、最小元。,定理3-12.1：设为偏序集，BA，若B有最小（大）元，则该最小（大）元是唯一的。证明：假定a，b两者都是B的最大元素，则ab，ba，从的反对称性，得到a=b。同理可证最小元唯一。,定义3-12.6上下（确）界：设为偏序集，BA，则：1.若yA满足x (xB x y)，称y为B的上界(upper bound)。2.若yA满足x (xB y x)，称y为B的下界(lower bound)。3.记B = y | yA且y是B的上界，若B有最小
17、元，则称该最小元为B的上确界(least upper bound，或join)，记为LUB(B)或B。4.记B = y | yA且y是B的下界，若B有最大元，则称该最大元为B的下确界(greatest lower bound，或meet)，记为GLB(B)或B。,定义3-12.7良序集：若偏序集A的每一个非空子集存在最小元，则称A为良序集。定理3-12.2: 每一个良序集必是全序集，每一个有限的全序集必是良序集。如：I表示全体整数的集合，则就不是良序集。因为取一子集I=,-3,-2,-1,其上就没有最小元。拟序关系是一种反自反的、可传递的二元关系。,偏序集 全序集 良序集 （链） （有最小元的
18、全序集）,作业：(3-12),P145 （1） （6） （7）,本次课小结及要求,小结： 1. 偏序关系及偏序集的概念 2. 偏序集的哈斯图,极大极小元、最大最小元、上下（确）界要求： 1. 掌握偏序关系及偏序集的概念 2. 会判断一个关系是否是偏序关系，记住几个实例。 3. 会画偏序集的哈斯图，能确定极大极小元、最大最小元、上下（确）界。,第三章 小结,主要知识点：集合和元素的概念，集合与元素之间的关系（属于和不属于），集合及元素的表示。子集的概念，集合间相等、包含、真包含，集合的幂集的概念。集合的基本运算，如并、交，补（绝对补）、差（相对补）、对称差的概念及性质。,(4) 序偶（二元组）、
19、n元组，笛卡尔积（直积）的概念及性质。(5) 二元关系、n元关系的概念，表示方法（集合表达式、关系矩阵和关系图），关系的定义域和值域的概念。(6) 二元关系的性质：自反性、反自反性、对称性、反对称性和传递性；掌握利用关系的不同表示获得关系所具有性质的方法。,(7) 特殊的二元关系：空关系、恒等关系、全域关系、等价关系、序关系（偏序关系、全序关系、良序关系、拟序关系）(8) 等价类、商集的概念。(9) 等价关系对应一个划分，相容关系对应一个覆盖。(10) 关系的运算及其性质。关系的基本运算就是集合的基本运算，即并、交、补、差、对称差；关系的复合（合成）运算及逆运算、闭包运算（自反闭包、对称闭包、传递闭包）。闭包的有关性质。,偏序关系是一种具备自反性、反对称性和传递性的二元关系，而（A，）称为偏序集。偏序关系的关系图用哈斯图表示，哈斯图中一定没有三角形那样的子图。一般地，哈斯图中没有水平方向的边。重点掌握利用哈斯图判断成员关系的方法，如：最大元、最小元、极大元、极小元、上界、下界、最小上界（上确界）、最大下界（下确界）的概念及判定。,(14) 全序关系要求偏序集中的任意两个元素都要可以比较；良序关系要求偏序集的任意一个子集均有最小元。拟序关系是一种反自反的、反对称的和可传递的二元关系。,
