离散数学3.12序关系课件

1、1,离散数学(Discrete Mathematics),张捷,第三章 集合与关系 （Sets and Relations),3.6 关系的闭包运算(Closure Operations) 3.7 集合的划分与覆盖(Partition & Cover of Sets) 3.8 等价关系(Equivalent Relations) 3.9 相容关系(CompatibilityRelations) 3.10 序关系(Ordered Relations),3.1 集合及其运算(Sets & Operations with sets) 3.2 序偶与笛卡尔积(Ordered Pairs & Carte

2、sian Product) 3.3 关系 (Relations) 3.4 关系的性质(The Propeties of Relations) 3.5 复合关系与逆关系(Compound Relations & Inverse Relations),3.10 序关系(Ordered Relations) 3.10.1 偏序关系的定义(Partially Ordered Relations) 3.10.2 偏序关系的哈斯图(The Hasse Diagram of Posets ) 3.10.3 偏序集中特殊位置的元素 3.10.4 几种特殊的偏序集,第三章 集合与关系(Sets & Relati

3、ons),3.10 偏序关系 3.10.1 偏序关系的定义(Partially Ordered Relations) 定义3.10.1 集合A上的关系,如果它是自反的,反对称的 且可传递的,则称是A上的偏序关系.记作“”,序偶 称为偏序集(partially ordered set or poset for short ).,例1 实数集R上的“”关系显然是一个偏序关系。,证明 对于任意 ，有 ，所以“ ”是自反的。,对任意 ，若 且 ，则 所以“ ” 是反对称的。,例2 全集合U的幂集2U上的“ ”关系也是一个偏序关系。,对任意 ，若 ， ，则 所以“ ”是可传递的。,例3 设A=1,2,3

4、,4,6,8,12，定义A上的整除关系 如下： 则是A上的偏序关系。,例4 自然数集上的整除关系是偏序关系。,3.10.2 偏序关系的哈斯图(The Hasse Diagram of Posets ),ac,cb，则称元素b盖住元素a，并且记,称 为偏序集 中的盖住关系。显然 。,定义3.10.2 在偏序集中 ，若元素 ，ab，ab，且在集A中不存在任何其它元素c，使得,3.10.2 偏序关系的哈斯图(The Hasse Diagram of Posets ),例5 设U=a,b,c，则“ ”关系是2U上的偏序关系，,偏序关系“ ”的哈斯图如下：,例6 设A=2,3,6,12,24,36，A上

5、的整除关系是一偏序关系，其哈斯图如下：,3.10.3 偏序集中特殊位置的元素,既然偏序集的元素之间 具有分明的层次关系， 则其中必有一些处于特殊位置的元素。,定义3-10.3（极大元，极小元，最大元，最小元）,设,是一个偏序集，且B,A，如果存在元素bB,使得,B满足x,b且x,（2）不存在x,b，则称b为B的极小元；,a,b,c a,b,c,a,例7. 设Aa,b,c，对于偏序集,，,例8 在例6中取B=6，12，C=2，3，6，则,A B C,24，36 12 6,2，3 6 2，3,无 12 6,无 6 无,最大（小）元和极大（小）元的性质：,（1）最大（小）元必是极大（小）元，反之不然

6、。,（2）最大（小）元不一定存在，若存在，则是唯一的。,（3）极大（小）元不唯一，当BA时，偏序集 的,极大元即是其哈斯图中最顶层元素，其极小元是哈斯图中最底层元素，不同的极大（小）元之间不可比，它们处在哈斯图中的同一个层次。,证：,定义3.10.4（上界，下界，上确界，下确界),则称a为B的最小上界（上确界），记作LUB(B)；,则称a为B的最大下界（下确界），记作GLB(B)。,a,b,c a,b,c,a,例9. 设Aa,b,c，对于偏序集,，,a,b,c,a,b,c,a,b,c,a,a,b,a,b,a,b,c,a,b,a,例10 在例6中取B=12,24,36，C=2，3，6，则,A B

7、 C,无 无 6,12,24,36,无 12,6,3,2 无,无 无 6,无 12 无,A=2,3,6,12,24,36,通过以上例子可以看出界有以下性质：,（1）一个集合可能没有上界或下界，若有，则不一定唯一，并且它们可能在B中，也可能在B外； （2）一个集合若有上下确界，必定是唯一的，并且若是B的最大（小）元素，则它必是B的上（下）确界。,3.10.4 两种特殊的偏序集 1.全序 设“”是集合A上的一个偏序关系，对于任意a,bA，当ab时，ab和ba至多一个成立，这意味着允许ab和ba可以都不成立。,例如 在例3的整除关系中，34，43均不成立。,在例4的包含关系中,定义3.10.5 设是

8、集合A上的一个偏序，若对于任意元素a,bA，必有ab或ba，则称它为A上的一个全序。,例如 实数集R上的数之间的小于或等于关系“”就是R上的一个全序，,正整数集N上的小于或等于关系“”也是N上的一个全序。,N上的整除关系就仅是一个偏序而不是全序。,例11 设A=1,2,8,24,48，则A上的整除关系是A上的偏序，并且也是一个全序.,3.10.4 两种特殊的偏序集 2.良序 定义3.10.6 设“”是集合A上的一个偏序关系，若A的任意子集B均有最小元素,则称为A上的一个良序。 称为良序集。,例如 (1)正整数集N上的小于等于关系“”是良序关系。,(2)In =1,2,n上的小于等于关系“”是良

9、序关系。,(3)整数集Z和实数集R上的小于等于关系“”不是良序关系 (因为Z或R本身无最小元) 。,定理3.10.1 每一个良序集一定是全序集.,注意: 定理3.10.1的逆不成立 。,例如: 整数集Z和实数集R上的小于等于关系“”是全序关系,但不是良序关系 。,证: 设 为良序集,则对任意的a ,bA,a,b构成A的子集,因此它必有最小元素,最小元素非a则b,故一定有ab或ba.所以 是一个全序集.,但是,对于有限的全序集,定理3.10.1的逆也成立.即有,定理3.10.2 每一个有限的全序集一定是良序集.,综合练习 1.对下述论断判断正确与否，在相应括号中键入“Y”或“N”。（1）设A=2

10、,3,6,12,24,36，A上的整除关系是一偏序关系， 用“”表示。,(b)“”=2,2,2,6,3,3, 3,6,6,6,6,12,12,12, 12,24,24,24,36,36 （ ）,N,Y,（2）集合A=3,9,27,54上的整除关系是A上的全序 （ ）,Y,（a）该偏序关系的哈斯图是 （ ）,解 满足上述条件的最小基数的关系 2 =2,3，2,4，4,3,一般说，给定1和12，不能唯一的确定2 。 例如2=2,3，2,4，4,3，0,0，3,3也可以.,2给定1=0,1,1,2,3,4, 12 =1,3，1,4，3,3, 求满足上述条件的一个基数最小的关系 2. 一般地说,若给定

11、1和12 ，2 能被唯一地确定吗? 基数最小的2能被唯一确定吗 ？,给定1和12，也不能唯一的确定出最小基数的2。,则2=2,3，2,4，4,3或 2=2,3，2,4，3,3都可以。,例如1=0,1，1,2，3,3，3,4， 12=1,3，1,4，3,3，,4,3,3下列关系哪一个是自反的、对称的、反对称的或可传递的？ 1当且仅当n1n28(n1,n2N)时,有n1n2 2当且仅当r1 | r2| (r1,r2R)时,有r1r2,解1不是自反的，如4N，但44=168。,是对称的，因为 对于任意的 n1, n2N，若有 n1n2 8，则 n2n1 = n1n2 8。,不是可传递的，例如，328

12、。,不是反对称的，例，238，328，但32.,2是自反的，因为对任意的rR，有r |r|。,不是对称的，如-1|3|，但3|-1|。,不是可传递的，100|-101|， -101|2|，但100|2|,不是反对称的，如-3|2|，2|-3|，但-32。,4.设1和2是集合A上的任意两个关系,判断下列 命题是否正确,并说明理由. 1若1和2是自反的，则12也是自反的； 2若1和2是非自反的，则12也是非自反的；,证明 1正确。,2否。,所以对任意的a A , 有 a12a ， 因此12也是自反的。,例如，设集合A=a,b. 1=a ,b, b ,a ,2 =a, b ,b,a,显然1和2都是非

13、自反的，但12自反。,3若1和2是对称的，则12也是对称的； 4若1和2是反对称的，则12也是反对称的； 5若1和2是可传递的，则12也是可传递的；,例如 ，设集合A=1,2,3， 1=1,2，2, 1 ,2=1,3，3,1， 显然 1和2都是对称的，,例如设 A =1,2,3,1=1,2,3，3, 2 =2,3,3，1显然1和2都是反对称的，,例如设 A =1,2,3,1=1,2,2,3,1,3, 2 =2，3，3，1，2，1， 显然1和2都可传递的.,但12=2,3不是对称的。,但12=1,3,2,1,1,1 不是可传递的。,但12 =1, 3，3,1不是反对称的。,证明3否 .,4 否

14、.,5否 .,5 .有人说，集合A上的关系 ，如果是对称的且可 传递，则它也是自反的。其理由是，从,对称性,传递性,例 设 A1,2，3 1,2,2,1,1,1,2,2,6 设1是集合A上的一个关系，2=a,b| 存在 c， 使a,c1且c,b1，试证明： 若 1是一个等价关系，则2也是一个等价关系。,证明 因为1是自反的，所以对于任意的 a A, 有a, a1,，由a,a1 ,a,a 1,由1的对称性,又有b, c1 ,且c, a1 ,因而有b, a2 ,故2 是对称的。,对于任意的a, bA,若a, b2 ,则必有元素cA，使得a, c1, 且c, b1 ,因此有 a,a2 ,2 是自反的。,对于任意的a, b, cA , 若a, b2 , b, c 2,则必有元素 d , e A , 使得 a, d1 d, b1 b, e1 e, c 1,由1的可传递性，又有a, b1, b, c 1, 于是有a, c2,故2 是可传递的。,由上证得2 是一个等价关系。,证法二,设a, b