离散数学课件次序关系

1、1离散数学离散数学2学习内容学习内容3次序关系次序关系n偏序关系偏序关系n拟序关系拟序关系n全序关系全序关系n良序关系良序关系4偏序关系：r是是a上的关系，如果它是自反、反对称和传递的，上的关系，如果它是自反、反对称和传递的，则称则称r 是是。并称。并称是偏序集。是偏序集。例 试判断下列关系是否为偏序关系(1)集合a的幂集p(a)上的包含关系“ ”；(2)实数集合r上的小于或等于关系“ ”是是5 ：是偏序集，是偏序集，如果对如果对x,ya，必有，必有xy,或或yx, 则称则称x与与y是可比较的。是可比较的。上例中上例中1,2,4或或1,2,6间是可比较的，而间是可比较的，而4与与6间是不可比较

2、的间是不可比较的【注意【注意】若若“”是集合是集合a a上的一个偏序关系，这意味着对于上的一个偏序关系，这意味着对于任意任意x,yax,ya，当，当xyxy时，时，xyxy和和yxyx至多一个成立。至多一个成立。 6例7.3.5 考虑任务集t，它包含了拍摄一张室内开启闪光灯的照片必须按顺序完成的任务。1. 打开镜头盖2. 照相机调焦3. 开启闪光灯4. 按下快门按钮在t上定义关系r如下：, i jrijij如果或者任务 必须在任务 之前完成试判断r是否是t上的偏序关系并画出它的关系图。解：(1)列出r中的元素 (2) 判断是否满足属性 (3) 画出关系图7偏序关系的关系图特点：(1) 每个结点

3、都有环(2) 两个不同结点之间要么有且仅有一条边相连，要么没有边相连哈斯图哈斯图(hasse图图)：不能直观地反映出元素之间的次序，所以不能直观地反映出元素之间的次序，所以下面介绍另外一种图下面介绍另外一种图-哈斯哈斯图图(hasse图图)。通过这个图，就能够。通过这个图，就能够清晰地反映出元素间的层次。下面介绍清晰地反映出元素间的层次。下面介绍hasse图。图。8例例 a=1,2,4,6, 表示整除关系，则表示整除关系，则是个偏序。是个偏序。2。1。64。关系图哈斯图画法：9例7.3.7 a=2,3,6,12,24,36, 是是a上上整除关系。画出关系整除关系。画出关系图及哈斯图。图及哈斯图

4、。10课堂小测验：课堂小测验：(1) d=1,2,3,5,6,10,15,30, 是是d上上整除关系，整除关系， 求求hasse图图，（2）a=a,b,c ，求，求的的hasse图图30。3。2。5。0。5。6。a,b,c。b。a。c。a,c。b,c。a,b。11偏序集中的特殊元素一.极小元与极大元(1(1）如果存在一个元素如果存在一个元素bb且在且在b中找不到元素中找不到元素b有有b b且且b b 则称则称b是是b的的极小元极小元 .）（在（在b b中没有比中没有比b b更小的元素了，更小的元素了，b b就是就是极小元）极小元）（2）如果存在一个元素如果存在一个元素bb且中找不到元素且中找不

5、到元素b有有b b且且 b b ，则称，则称b是是b的的极大元极大元 .( (在在b b中没有比中没有比b b更大的元素了，更大的元素了，b b就是就是极大元极大元) )12举例举例给定给定,hasse图如图所示：图如图所示： 从从hasse图找图找极极(大大)元：元：(上)。12。24。36。子集b极小元极大元2,31,2,36,12,24c2, 32, 312, 3624124,3613例：例：是偏序集，是偏序集， ，设设是偏序集，是偏序集，b是是a的非空有限子集，的非空有限子集，则则b一定存在极大（小）元。一定存在极大（小）元。则则 中极大元：，中极大元：， 极小元：，极小元：，14二二

6、. .最小元与最大元最小元与最大元 （1）如果存在一个元素）如果存在一个元素bb对每一个对每一个bb 均有均有b b 则则称称b是是b的的最小元最小元 ( (最小元最小元 是是b b中元素，该元素中元素，该元素比比b b中所有元素都小中所有元素都小) ) （2）如果存在一个元素如果存在一个元素bb对每一个对每一个bb 均有均有b b 则称则称b是是b的的最大元最大元 (最大元最大元b b是是b b中元素，该元素中元素，该元素比比b b中中所有元素都大所有元素都大) )举例举例，给定，给定的的hasse图如图所示：图如图所示：从从hasse图找图找最小最小(大大)元：子集中如果只有唯一的极元：子

7、集中如果只有唯一的极小小(大大)元，则这个元，则这个极小极小(大大)元，就是元，就是最小最小(大大)元。否则元。否则就没有最小就没有最小(大大)元。元。下面介绍下面介绍最小(大)元的唯一定理。12。24。36。子集b最小元最大元2,31,2,36,12,24c无无1无6241无15定理定理2：是偏序集，是偏序集，b是是a的非空子集，如果的非空子集，如果b有有最小元最小元(最大元最大元)，则最小元，则最小元(最大元最大元)是唯一的。是唯一的。证明证明：假设：假设b有两个最小元有两个最小元x、y,则则 因为因为x是是最小元，最小元，yb，根据，根据最小元定义，有最小元定义，有xy;类似地，因为类似

8、地，因为y是是最小元，最小元，xb，根据，根据最小元定义，有最小元定义，有yx。因为。因为有反对称性，所以有有反对称性，所以有x=y。 同理可证同理可证最大元的唯一性。最大元的唯一性。小结小结：(a,)是偏序集，是偏序集，b是是a的非空子集，则的非空子集，则 b的的极小极小(大大)元总是存在的，就是子集中处在最下元总是存在的，就是子集中处在最下(上上)层的元素是极小层的元素是极小(大大)元。元。 如果有唯一的极小如果有唯一的极小(大大)元，则这个极小元，则这个极小(大大)元就是最元就是最小小(大大)元。否则就没有最小元。否则就没有最小(大大)元。元。163.3.上界与下界上界与下界 (uppe

9、r bound and lower bound)(1)设设是偏序集，是偏序集，b a，若存在，若存在aa，使得，使得 对对 bb，ba,称称a为为b的上界。的上界。（上界（上界a a是是a a中元素，该元素中元素，该元素比比b b中所有元素都大中所有元素都大) )(2)(2) 设设是偏序集，是偏序集，b a，若存在，若存在aa，使得，使得 对对 bb，ab,称称a为为b的下界。的下界。（下下界界a a是是a a中元素，该元素中元素，该元素比比b b中所有元素都中所有元素都小小) )举例举例，给定，给定的的hasse图如图所示：图如图所示： 从从hasse图找图找上上(下下)界：界：注意注意是在

10、是在a中找！中找！。12。24。36。子集b上界下界2,31,2,36,12,24c 16,12,24,361246,2,3,11无6,12,24,36174. 4. 最小上界最小上界( (上确界上确界) )和最大下界和最大下界( (下确界下确界) )(least upper bound and greatest lower bound)(least upper bound and greatest lower bound)1： a是是b的上界，并且对的上界，并且对b的所有上界的所有上界a,都有都有aa,则称则称a是是b的的最小上界最小上界( (上确界上确界) ) 。上确界上确界. .( (即

11、即a a是上界中最小的。如果是上界中最小的。如果b b有上确界，则是唯一的有上确界，则是唯一的) )2： a是是b的下界，并且对的下界，并且对b的所有下界的所有下界a,都有都有a a则称则称a是是b的的最大下界最大下界( (下确界下确界) ) 。下确界下确界. .( (即即a a是下界中最大的。如果是下界中最大的。如果b b有下确界，则是唯一的有下确界，则是唯一的) )18子集b上界下界2,31,2,36,12,24c 16,12,24,361241,2,3,61无6,12,24,36上确界上确界下确界下确界6624无1161。12。24。36。举例举例，给定（，给定（c,）的）的hasse图

12、如图所示图如图所示：19 求求(1)b=a,b，a,c，b,c，a，b，c,例：例：设设aa,b,c, 幂集是幂集是2a a,b,c ,a,b ,a,c,b,c ,a ,b ,， r是幂集上的包含关系。是幂集上的包含关系。 （2）b= a，c 的特殊元素。的特殊元素。20解答解答：设：设aa,b,c,幂集是幂集是2a a,b,c ,a,b，a,c,b,c，a，b， c， 其上的包含关系是一个偏序关系。其上的包含关系是一个偏序关系。（1）设）设 b=a,b，b,c， a,c, a，b，c,则它没有最大元素，但有极大元素：则它没有最大元素，但有极大元素： a,b，b,c， a,c, ；它；它的上界

13、与上确界是相同的即是的上界与上确界是相同的即是a,b,c。它的最小元素、极小元素、下界、下确界都相同是它的最小元素、极小元素、下界、下确界都相同是。（2）设）设b= a，c，则它的最大元素没有，极大元素是，则它的最大元素没有，极大元素是a，c。上界是上界是a,b,c ,a,b，a,c,b,c。上确界没有。上确界没有。最小元素没有，极小元素是最小元素没有，极小元素是a，c，下界、下确界都，下界、下确界都是是。a,b,c。b。a。c。a,c。b,c。a,b。211. 非空子集极小非空子集极小(极大极大)元总是存在的。但极大元、极小元并不元总是存在的。但极大元、极小元并不是唯一，且同一元素可以既是极

14、大元又是极小元。如果有是唯一，且同一元素可以既是极大元又是极小元。如果有唯一的极小唯一的极小(大大)元，则这个极小元，则这个极小(大大)元就是最小元就是最小(大大)元。否元。否则就没有最小则就没有最小(大大)元。元。极大元、极小元必须是子集极大元、极小元必须是子集b b中的元素中的元素。3.最大元（最小元）本身应属于子集最大元（最小元）本身应属于子集b，且与，且与b中任一元素都中任一元素都有关系。最大元（最小元）可能存在也可能不存在，如果存有关系。最大元（最小元）可能存在也可能不存在，如果存在是唯一的。在是唯一的。：224. 子集b的上/下界和最小上/最大下界必须在集合a中寻找；5. 子集b的

15、上/下界不一定存在，如果存在，可以不唯一的；6. 子集b的上界/下界、最小上/最大下界不一定存在，如果存在，则最小上界与最大下界是唯一的；7. 子集b有最小上/最大下界，一定有上(下)界；反之不然。8. b的最小元一定是b的下界，同时也是b的最大下界。同样，b的最大元一定是b的上界，同时也是b的最小上界。9. 但反过来不一定正确，b的下界不一定是b的最小元，因为它可能不是b中的元素。同样的，b的上界也不一定是b的最大元。23课堂小练习课堂小练习 设集合a=a,b,c,d,e,f,g,h，对应哈斯图见右图。令b1=a,b，b2=c,d,e。求出b1，b2的极大元、极小元、最大元、最小元、上界、下

16、界、上确界、下确界。abcdefhg极大元极小元最大元最小元上界下界上确界下确界b1b2a,bd,ea,bc无无无cc,d,e,f,g,hh无c,a,bcch无b1b224次序关系次序关系n偏序关系偏序关系n拟序关系拟序关系n全序关系全序关系n良序关系良序关系25实数集实数集r上的上的“”关系不是偏序关系。关系不是偏序关系。a上的真包含关系上的真包含关系“ ”也不是偏序关系。也不是偏序关系。：r是a上的关系，如果它是反自反的、传递的则称r 是。并称是拟序集。定理定理1：集合集合a上的关系上的关系r是拟序的，则必是反对称的。是拟序的，则必是反对称的。 定理定理2 :设设r是集合是集合a上的关系，

17、则上的关系，则 (1)如果如果r是一个拟序关系，则是一个拟序关系，则 r(r)=r i是一个偏序关系是一个偏序关系 (2)如果如果r是一个偏序关系，则是一个偏序关系，则 r i是一个拟序关系是一个拟序关系证明：假设a不是反对称的，则必存在x，y a，且，且xy，满足满足 r并且并且 r。因为。因为r是拟序关系，所以是拟序关系，所以r具有传递性，从而有具有传递性，从而有 r。这与。这与r是反自反的矛盾。是反自反的矛盾。26次序关系次序关系n偏序关系偏序关系n拟序关系拟序关系n全序关系全序关系n良序关系良序关系并不是所有的元素都可以比较并不是所有的元素都可以比较所有的元素都可以比较所有的元素都可以

18、比较27全序(线序、链)1.定义定义：是偏序集，如果对任何是偏序集，如果对任何x,ya，如果，如果x与与y都都是可比较的（即是可比较的（即都有都有xy，或，或yx）则称）则称是全序关系是全序关系(线线序、链序、链)。例例1 . b=1,2,4,8, “ ”表示整除关系，表示整除关系，则则“” 是全序关系，有向图：是全序关系，有向图： 例例2.2.正整数集正整数集n n上的小于或等于关系上的小于或等于关系“”也是也是n n上的一个全上的一个全序；而序；而n n上的整除关系就仅是一个偏序而不是全序上的整除关系就仅是一个偏序而不是全序; ; 。 1 1）：中每两个元素均能比较大小，：中每两个元素均能比较大小，即任何两个元素都能排序；而偏序则是部分有序。即任何两个元素都能排序；而偏序则是部分有序。 （2 2）：全序一定是偏序但偏序不一定是全序。：全序一定是偏序但偏序不一定是全序。 2。1。8428例例1(续续) b=1,2,4,8,表示整除关系表示整除关系。关系图哈斯图2。1。8429例：判断下列关系是否为全序关系，如果是，请画出哈斯图1. 设集合a=a，b，c，其上的关系“”=,；2. 实数集合r上定义的小于等于关系“”；3. 实数集合r上定义的小于关系“”4. 集合a的幂集p(a)上定义的包含关系“ ” 解