等价关系和偏序关系（讲授）.pptVIP

【例12】设偏序集A, ? 的哈斯图如右，试写出集合A上的偏序关系? 。 解:(1)由平面上的结点知A={a,b,c,d,e,f,g,h}; (2)有直接连线的两个结点是盖住关系，即 R1={a,c,b,c,a,d,b,d,c,e,d,e,f,g} ? ? ; (3)有自上到下间接连线的两个结点是可比关系，即 R2={a,e,b,e} ? ? ; (4)偏序关系是省略了环的图，即 IA={a,a,b,b,c,c,d,d,e,e,f,f,g,g,h,h}? ? ; 所以，?=R1∪R2∪IA ={a,c,b,c,a,d,b,d,c,e,d,e,f,g, a,e,b,e, a,a,b,b, c,c,d,d,e,e,f,f,g,g,h,h} 四、偏序关系的特殊元和界 特殊元定义：设A, ? 为偏序集，B?A∧?y∈B, (1) ?x(x∈B→y?x)为真，则称y是B的最小元; (2) ?x(x∈B→x?y)为真，则称y是B的最大元; (3) ?? x(x∈B∧x?y)为真，则称y是B的极小元; (4) ?? x(x∈B∧y?x)为真，则称y是B的极大元; * 本节介绍两种重要的关系----等价关系和偏序关系。重点介绍等价关系中的等价类、商集、划分的概念;偏序关系中的可比和盖住概念,哈斯图绘制及偏序关系中的特殊元的定义。 等价关系 偏序关系 一、等价关系 定义：集合A(≠? )上的关系R，若有性质: (1) ?x(x∈A→x,x∈R) (2) ?x?y( x,y∈A∧x,y∈R→y,x∈R) (3) ?x?y?z(x,y,z∈A∧x,y∈R∧y,z∈R→x,z∈R) 则同时满足性质(1)(2)的关系为相容关系; 同时满足性质(1)(2)(3)的关系为等价关系； 若R为等价关系，x,y∈R ，则称x和y等价，记为x～y。 【例1】设 A={1,2,…,8}，试说明A上的关系R为等价关系。 其中R={x,y| x,y∈A∧x ≡ y(mod 3)} 解：R={1,1,1,4,1,7,2,2,2,5,2,8,3,3,3,6,4,1, 4,4,4,7,5,2,5,5,5,8,6,3,6,6,7,1,7,4,7,7,8,2, 8,5,8,8}，显然，该关系是自反的、对称的、传递的，即该关系是等价关系。此时有1 4 7 ，2 5 8 ，3 6 。 特点: (1) 等价关系中，集合A中的元素间的等价具有自反、对称和传递性; (2) 等价关系R把集合A中的元素分成了若干个子集，在每个子集上是 全域关系。 关系图 ～ ～ ～ ～ ～ 【思考】下列关系是否为等价关系？ （1）在一群人所组成的集合上定义的“同姓”关系。 （2）在一群人所组成的集合上定义的“朋友”关系。 （3）整数集上的“小于”关系。 （4）整数集上的“等于”关系。 （5）直线间的“平行”关系。 （6）幂集上的“?”关系。 √ √ × × × × 等价类：A (≠? )上的等价关系R，引入符号[x]R， 定义: [x]R ={y︱x,y∈A∧x,y ∈R}， 则称[x]R为x关于R的等价类，简记为[x] 。 如例1中的等价关系R={x,y| x,y∈A∧x ≡ y(mod 3)}，则 关于集合A={1,2,…,8}上各元素的等价类有结果： [1]R= . [2]R= . [3]R= . 结论：即等价的元素关于R的等价类相等。 {1,4,7}= [4]R = [7]R {2,5,8}= [5]R = [8]R {3,6}= [6]R 【例2】 已知A={1,2,3}上的EA和IA，试求A上的元素关于 EA和IA的等价类。 解：对于全关系EA : [1]=[2]=[3]={1,2,3} 对于恒等关系IA : [1]={1} ,[2]={2}, [3]={3} 结