离散数学243(偏序关系)[20141015].ppt

主讲教师：常亮主讲教师：常亮 E-mail: E-mail: QQQQ：737059669737059669 办公室电话办公室电话: 2291071 : 2291071 手机手机:辅导教师：周小川辅导教师：周小川 答疑时间：星期四答疑时间：星期四 上午上午 10:20-11:5010:20-11:50 答疑地点：答疑地点：5 5教教5 5楼楼 软件工程教研室软件工程教研室 离散数学离散数学 回顾回顾 oo 关系可能具有的性质：关系可能具有的性质： n n 自反自反 n n 反自反反自反 n n 对称对称 n n 反对称反对称 n n 传递传递 oo 特殊关系：具有上述某些性质的关系特殊关系：具有上述某些性质的关系 n n 等价关系：自反、对称、传递等价关系：自反、对称、传递 n n 偏序关系偏序关系：自反、：自反、反对称反对称、传递、传递 2.4.3 2.4.3 偏序关系偏序关系 定义定义2.282.28 oo 设设R R为非空集合为非空集合A A上的关系（即上的关系（即A A 并且并且R R A A A A）。）。 如果如果R R是是自反的自反的、反对称的反对称的和和传递的传递的， 则称则称R R为为A A上的上的偏序关系偏序关系。 oo 一般用符号一般用符号“ “ ” ”来表示偏序关系。来表示偏序关系。 oo 设设 R R 是一个偏序关系。如果是一个偏序关系。如果 R R, , 则记为则记为x x y y。 oo 如果集合如果集合AA上存在偏序关系，则称上存在偏序关系，则称AA为为偏序集偏序集，记为，记为 。 oo 例：集合例：集合A=2,4,6,8A=2,4,6,8上的小于等于关系上的小于等于关系 = , , , , , , = , , , , , , , , , , , , 。 “偏序” 例例2.662.66 判断下列关系是否为偏序关系判断下列关系是否为偏序关系 集合集合AA的幂集合的幂集合P P( (AA) )中元素之间的包含关系中元素之间的包含关系“ “ ” ”； 实数集合实数集合RR上的小于等于关系上的小于等于关系“ “ ” ”； 实数集合实数集合RR上的大于等于关系上的大于等于关系“ “ ” ”； 自然数集合自然数集合NN上的模上的模n n同余关系；同余关系； 人群中的人群中的“ “父子父子” ”关系。关系。 例例2.672.67 判断集合判断集合AA=2, 3, 4, 5, 6, 8=2, 3, 4, 5, 6, 8上的整除关系是否为偏序关系？上的整除关系是否为偏序关系？ 并用关系矩阵和关系图表示。并用关系矩阵和关系图表示。 解解: : 集合集合 A A 上的整除关系为上的整除关系为 R R =, =, , 该关系具有自反性、反对称性和传递性。所以，它是偏序关系。该关系具有自反性、反对称性和传递性。所以，它是偏序关系。 该关系的关系矩阵和关系图表示如下：该关系的关系矩阵和关系图表示如下： 6 2 5 3 4 8 R 可比、盖住可比、盖住 定定义义义义2.29 2.29 设设设设R R为为为为非空集合非空集合A A上的偏序关系，上的偏序关系，对对对对于任意元素于任意元素x x, , y y A A， 如果如果 R R或或 R R，则则则则称称x x与与y y是可比的是可比的。 如果如果 R R且且 R R，则则则则称称x x与与y y是不可比的是不可比的。 若若x x y y且且x x y y，则则则则称称x x排在排在y y的的前面前面，记记记记作作x x y y，读读读读作作“ “x x小于小于y y” ”。 若若x x y y且不存在元素且不存在元素z z A A使得使得x x z z且且z z y y，则则则则称称y y盖住盖住x x。 设设设设R R为为为为非空集合非空集合A A上的偏序关系，上的偏序关系，对对对对于任意元素于任意元素x x, , y y A A， 可能出可能出现现现现以下几种情况：以下几种情况： x x y y（或（或y y x x）；）； x x = = y y； x x与与y y不是可比的。不是可比的。 例例2.682.68 考察集合考察集合AA=2, 3, 4, 5, 6, 8=2, 3, 4, 5, 6, 8上的整除关系上的整除关系 R R =, =, ,。 可比的情况：可比的情况： 不可比的情况：不可比的情况： 盖住的情况：盖住的情况： 哈斯图哈斯图 pp 对对偏序关系偏序关系的关系图可进行如下简化：的关系图可进行如下简化： 自反：可以将各顶点上的环全部略去；自反：可以将各顶点上的环全部略去； 反对称：边为单向，可以规定向上方向为箭头方向，省略箭头；反对称：边为单向，可以规定向上方向为箭头方向，省略箭头； 传递：可以将由传递性导出的边省去。传递：可以将由传递性导出的边省去。 将经过上述简化后得到的关系图称为将经过上述简化后得到的关系图称为哈斯图哈斯图。 oo 哈斯图的绘制步骤：哈斯图的绘制步骤： （1 1）以）以“ “ ” ” 表示元素；表示元素； （2 2）若）若x x y y，则，则y y画在画在x x的上层；的上层； （3 3）若）若y y盖住盖住x x，则连线；，则连线； （4 4）不可比的元素可画在同一层。）不可比的元素可画在同一层。 例例 对于集合对于集合AA=2, 3, 4, 5, 6, 8=2, 3, 4, 5, 6, 8上的整除关系，画出其哈斯图。上的整除关系，画出其哈斯图。 解解: : 集合集合 A A 上的整除关系为上的整除关系为 R R =, =, , 该关系具有自反性、反对称性和传递性。所以，它是偏序关系。该关系具有自反性、反对称性和传递性。所以，它是偏序关系。 该关系的关系矩阵和关系图表示如下：该关系的关系矩阵和关系图表示如下： 6 2 5 3 4 8 R 8 4 6 2 3 5 关系R的哈斯图 哈斯图哈斯图 例例2.70:2.70:绘制如下偏序关系的哈斯图绘制如下偏序关系的哈斯图 集合集合A A = 1, 2, 3, 4, 6, 12= 1, 2, 3, 4, 6, 12上的整除关系；上的整除关系； 集合集合A A = 2, 3, 4, 5, 8= 2, 3, 4, 5, 8上的大于等于关系上的大于等于关系“ “ ” ”； 集合集合A A = 2, 3, 6, 12, 24, 36= 2, 3, 6, 12, 24, 36上的整除关系；上的整除关系； 集合集合A A = = a a, , b b, , c c 的幂集的幂集P P( (A)A)上的包含关系上的包含关系“ “ ” ”； 解：解：偏序关系偏序关系、和和的哈斯图绘制于图的哈斯图绘制于图 12 4 6 2 3 1 整除关系 2 3 4 5 8 大于等于关系 a,b,c a,b a,c b,c a b c 包含关系 24 36 12 6 2 3 整除关系 偏序集中的偏序集中的8 8个特殊元素个特殊元素( (最大元、最小元最大元、最小元) ) 定义定义2.30 2.30 对于偏序集对于偏序集和和集合集合AA的任意子集的任意子集 BB， 如果存在元素如果存在元素b b BB，使得任意，使得任意x x BB都有都有x x b b， 则称则称b b为为BB的的最大元素最大元素，简称为简称为最大元最大元； 如果存在元素如果存在元素b b BB，使得任意，使得任意x x BB都有都有b b x x， 则称则称b b为为BB的的最小元素最小元素，简称为简称为最小元最小元。 例例2.712.71 对对对对于例于例2.702.70中偏序关系中偏序关系 （即（即集合集合A A = 1, 2, 3, 4, 6, 12= 1, 2, 3, 4, 6, 12上的整除关系上的整除关系），）， 令令B B1= 1, 61= 1, 6、B B2= 1, 2, 32= 1, 2, 3、B B3= 4, 6, 123= 4, 6, 12、 B B4= 2, 4, 64= 2, 4, 6、B B5= 1, 2, 6, 125= 1, 2, 6, 12、B B6= 1, 2, 3, 4, 6, 126= 1, 2, 3, 4, 6, 12。 分分别别别别求出求出B B1 1、B B2 2、B B3 3、B B4 4、B B5 5和和B B6 6的最大元和最小元。的最大元和最小元。 解解: : 对于集合对于集合B B1= 1, 61= 1, 6，最大元为，最大元为6 6，最小元为，最小元为1 1； 对于集合对于集合B B2= 1, 2, 32= 1, 2, 3，元素，元素2 2和和3 3不可比，不可比， 所以，不存在最大元，最小元为所以，不存在最大元，最小元为1 1； 对于集合对于集合B B3= 4, 6, 123= 4, 6, 12，元素，元素4 4和和6 6不可比，不可比， 所以，不存在最小元，最大元为所以，不存在最小元，最大元为1212； 对于集合对于集合B B4= 2, 4, 64= 2, 4, 6，元素，元素4 4和和6 6不可比，不可比， 所以，不存在最大元，最小元为所以，不存在最大元，最小元为2 2； 对于集合对于集合B B5= 1, 2, 6, 125= 1, 2, 6, 12，最大元为，最大元为1212，最小元为，最小元为1 1； 对于集合对于集合B B6= 1, 2, 3, 4, 6, 126= 1, 2, 3, 4, 6, 12，最大元为，最大元为1212，最小元为，最小元为1 1。 练习练习 对对对对于例于例2.702.70中偏序关系中偏序关系 （即（即集合集合A A = 2, 3, 6, 12, 24, 36= 2, 3, 6, 12, 24, 36上的整除关系上的整除关系），）， 令令B B1= 6, 121= 6, 12、B B2= 2, 32= 2, 3、B B3= 12, 363= 12, 36、 B B4= 2, 3, 64= 2, 3, 6、B B5= 2, 3, 6, 125= 2, 3, 6, 12、B B6= 2, 3, 6, 12, 24, 366= 2, 3, 6, 12, 24, 36， 求求B B1 1、B B2 2、B B3 3、B B4 4、B B5 5和和B B6 6的最大元和最小元。的最大元和最小元。 偏序集中的偏序集中的8 8个特殊元素个特殊元素( (极大元、极小元极大元、极小元) ) 定义定义2.31 2.31 对于偏序集对于偏序集和和集合集合AA的任意子集的任意子集 BB， 如果存在元素如果存在元素b b BB，使得，使得BB中不存在其它元素中不存在其它元素x x满足满足b b x x， 则称则称b b为为BB的的极大元素极大元素，简称为简称为极大元极大元； 如果存在元素如果存在元素b b BB，使得，使得BB中不存在其它元素中不存在其它元素x x满足满足x x b b， 则称则称b b为为BB的的极小元素极小元素，简称为，简称为极小元极小元。 注意：注意：最大（小）元最大（小）元 vs. vs. 极大（小）元极大（小）元 最大（小）元必须与最大（小）元必须与BB中每个元素都可比，中每个元素都可比， 极大（小）元无此要求极大（小）元无此要求( (只要求没有比它更大或更小的元素只要求没有比它更大或更小的元素) )。 例例2.732.73 对对对对于例于例2.702.70中偏序关系中偏序关系 （即（即集合集合A A = 1, 2, 3, 4, 6, 12= 1, 2, 3, 4, 6, 12上的整除关系上的整除关系），）， 令令B B1= 1, 61= 1, 6、B B2= 1, 2, 32= 1, 2, 3、B B3= 4, 6, 123= 4, 6, 12、 B B4= 2, 4, 64= 2, 4, 6、B B5= 1, 2, 6, 125= 1, 2, 6, 12、B B6= 1, 2, 3, 4, 6, 126= 1, 2, 3, 4, 6, 12。 分分别别别别求出求出B B1 1、B B2 2、B B3 3、B B4 4、B B5 5和和B B6 6的极大元和极小元。的极大元和极小元。 解解: : 对于集合对于集合 B B 1= 1, 61= 1, 6，极大元为，极大元为6 6，极小元为，极小元为1 1； 对于集合对于集合 B B 2= 1, 2, 32= 1, 2, 3，极大元为，极大元为2 2和和3 3，极小元为，极小元为1 1； 对于集合对于集合 B B 3= 4, 6, 123= 4, 6, 12，极大元为，极大元为1212，极小元为，极小元为4 4和和6 6； 对于集合对于集合 B B 4= 24= 2，4 4，66，极大元为，极大元为4 4和和6 6，极小元为，极小元为2 2； 对于集合对于集合 B B 5= 1, 2, 6, 125= 1, 2, 6, 12，极大元为，极大元为1212，极小元为，极小元为1 1； 对于集合对于集合 B B 6= 1, 2, 3, 4, 6, 126= 1, 2, 3, 4, 6, 12，极大元为，极大元为1212，极小元为，极小元为1 1。 练习练习 对对对对于例于例2.702.70中偏序关系中偏序关系 （即（即集合集合A A = 2, 3, 6, 12, 24, 36= 2, 3, 6, 12, 24, 36上的整除关系上的整除关系），）， 令令B B1= 6, 121= 6, 12、B B2= 2, 32= 2, 3、B B3= 12, 363= 12, 36、 B B4= 2, 3, 64= 2, 3, 6、B B5= 2, 3, 6, 125= 2, 3, 6, 12、B B6= 2, 3, 6, 12, 24, 366= 2, 3, 6, 12, 24, 36， 求求B B1 1、B B2 2、B B3 3、B B4 4、B B5 5和和B B6 6的的极极大元和大元和极极小元。小元。 偏序集中的偏序集中的8 8个特殊元素个特殊元素( (上界、下界上界、下界) ) 定义定义2.32 2.32 对于偏序集对于偏序集和和集合集合AA的任意子集的任意子集BB， 如果存在元素如果存在元素a a AA，使得任意，使得任意x x BB都有都有x x a a， 则称则称a a为子集为子集BB的的上界上界； 如果存在元素如果存在元素a a AA，使得任意，使得任意x x BB都有都有a a x x， 则称则称a a为子集为子集BB的的下界下界。 注意：注意：BB的上（下）界不一定是的上（下）界不一定是BB中的元素！中的元素！ 例例2.752.75 对对对对于例于例2.702.70中偏序关系中偏序关系 （即（即集合集合A A = 1, 2, 3, 4, 6, 12= 1, 2, 3, 4, 6, 12上的整除关系上的整除关系），）， 令令B B1= 1, 61= 1, 6、B B2= 1, 2, 32= 1, 2, 3、B B3= 4, 6, 123= 4, 6, 12、 B B4= 2, 4, 64= 2, 4, 6、B B5= 1, 2, 6, 125= 1, 2, 6, 12、B B6= 1, 2, 3, 4, 6, 126= 1, 2, 3, 4, 6, 12。 分分别别别别求出求出B B1 1、B B2 2、B B3 3、B B4 4、B B5 5和和B B6 6的上界和下界。的上界和下界。 解解: : 对于集合对于集合B1= 1, 6B1= 1, 6，上界为，上界为6 6和和1212，下界为，下界为1 1； 对于集合对于集合B2= 1, 2, 3B2= 1, 2, 3，上界为，上界为6 6和和1212，下界为，下界为1 1； 对于集合对于集合B3= 4, 6, 12B3= 4, 6, 12，上界为，上界为1212，下界为，下界为1 1和和2 2； 对于集合对于集合B4= 2, 4, 6B4= 2, 4, 6，上界为，上界为1212，下界为，下界为1 1和和2 2； 对于集合对于集合B5= 1, 2, 6, 12B5= 1, 2, 6, 12，上界为，上界为1212，下界为，下界为1 1； 对于集合对于集合B6= 1, 2, 3, 4, 6, 12B6= 1, 2, 3, 4, 6, 12，上界为，上界为1212，下界为，下界为1 1。 练习练习 对对对对于例于例2.702.70中偏序关系中偏序关系 （即（即集合集合A A = 2, 3, 6, 12, 24, 36= 2, 3, 6, 12, 24, 36上的整除关系上的整除关系），）， 令令B B1= 6, 121= 6, 12、B B2= 2, 32= 2, 3、B B3= 12, 363= 12, 36、 B B4= 2, 3, 64= 2, 3, 6、B B5= 2, 3, 6, 125= 2, 3, 6, 12、B B6= 2, 3, 6, 12, 24, 366= 2, 3, 6, 12, 24, 36， 求求B B1 1、B B2 2、B B3 3、B B4 4、B B5 5和和B B6 6的的上界上界和下界。和下界。 偏序集中的偏序集中的8 8个特殊元素个特殊元素( (上确界上确界, ,下确界下确界) ) 定定义义义义2.33 2.33 对对对对于偏序集于偏序集 和和集合集合A A的任意子集的任意子集B B， 如果存在如果存在B B的某个上界的某个上界a a，使得，使得对对对对于于B B的任意上界的任意上界x x都有都有a a x x， 则则则则称称a a为为为为子集子集B B的的最小上界最小上界或或上确界上确界，记为记为记为记为 sup(sup(B B) = ) = a a； 如果存在子集如果存在子集B B的某个下界的某个下界a a，使得，使得B B的任意下界的任意下界x x都有都有x x a a， 则则则则称称a a为为为为子集子集B B的的最大下界最大下界或或下确界下确界，记为记为记为记为 inf(B) = ainf(B) = a。 说说说说明：明： 令令C C是由是由B B的所有上界的所有上界组组组组成的集合，成的集合， 则则则则C C的最小元的最小元c c称称为为为为B B的上确界；的上确界； 令令C C是是B B的所有下界的集合，的所有下界的集合， 则则则则C C的最大元的最大元c c称称为为为为B B的下确界。的下确界。 例例2.772.77 对对对对于例于例2.702.70中偏序关系中偏序关系 （即（即集合集合A A = 1, 2, 3, 4, 6, 12= 1, 2, 3, 4, 6, 12上的整除关系上的整除关系），）， 令令B B1= 1, 61= 1, 6、B B2= 1, 2, 32= 1, 2, 3、B B3= 4, 6, 123= 4, 6, 12、 B B4= 2, 4, 64= 2, 4, 6、B B5= 1, 2, 6, 125= 1, 2, 6, 12、B B6= 1, 2, 3, 4, 6, 126= 1, 2, 3, 4, 6, 12。 分分别别别别求出求出B B1 1、B B2 2、B B3 3、B B4 4、B B5 5和和B B6 6的的上确界和下确界。上确界和下确界。 解解: : 对于集合对于集合B1B1，上确界为，上确界为6 6，下确界为，下确界为1 1； 对于集合对于集合B2B2，上确界为，上确界为6 6，下确界为，下确界为1 1； 对于集合对于集合B3B3，上确界为，上确界为1212，下确界为，下确界为2 2； 对于集合对于集合B4B4，上确界为，上确界为1212，下确界为，下确界为2 2； 对于集合对于集合B5B5，上确界为，上确界为1212，下确界为，下确界为1 1； 对于集合对于集合B6B6，上确界为，上确界为1212，下确界为，下确界为1 1。 练习练习 对对对对于例于例2.702.70中偏序关系中偏序关系 （即（即集合集合A A = 2, 3, 6, 12, 24, 36= 2, 3, 6, 12, 24, 36上的整除关系上的整除关系），）， 令令B B1= 6, 121= 6, 12、B B2= 2, 32= 2, 3、B B3= 12, 363= 12, 36、 B B4= 2, 3, 64= 2, 3, 6、B B5= 2, 3, 6, 125= 2, 3, 6, 12、B B6= 2, 3, 6, 12, 24, 366= 2, 3, 6, 12, 24, 36， 求求B B1 1、B B2 2、B B3 3、B B4 4、B B5 5和和B B6 6的的上确界上确界和下和下确确界。界。 8 8大元的性质大元的性质 定理定理2.24 2.24 对于偏序集对于偏序集和集合和集合AA的任意子集的任意子集BB： 若若b b为为BB的的最大元最大元，则，则b b为为BB的的极大元极大元、上界上界和和上确界上确界； 若若b b为为BB的的最小元最小元，则，则b b为为BB的的极小元极小元、下界下界和和下确界下确界； 若若a a为为BB的的上界上界且且a a BB，则，则a a为为BB的的最大元最大元； 若若a a为为BB的的下界下界且且a a BB，则，则a a为为BB的的最小元最小元。 8 8大元的性质大元的性质 定理定理2.25 2.25 对于偏序集对于偏序集和集合和集合AA的任意子集的任意子集BB： 若若BB有最大元有最大元，则，则BB的的最大元惟一最大元惟一； 若若BB有最小元有最小元，则，则BB的的最小元惟一最小元惟一； 若若BB有上确界有上确界，则，则BB的的上确界惟一上确界惟一； 若若BB有下确界有下确界，则，则BB的的下确界惟一下确界惟一； 若若BB为为有限集有限集，则，则BB的的极大元、极小元恒存在极大元、极小元恒存在。 全序全序( (线序线序) )关系关系 / / 全序集全序集( (线序集线序集) ) 定义定义2.342.34 对于偏序集对于偏序集， 如果如果AA中中任意两个元素任意两个元素x x和和y y都是可比的都是可比的( (即即x x y y或者或者y y x)x)， 则称该偏序关系为则称该偏序关系为全序关系全序关系，或者，或者线