《离散数学 2_4_3(偏序关系)[2014_10_15]》由会员分享，可在线阅读，更多相关《离散数学 2_4_3(偏序关系)[2014_10_15]（29页珍藏版）》请在金锄头文库上搜索。
1、主讲教师：常亮主讲教师：常亮 E-mail: E-mail: QQQQ：737059669737059669 办公室电话办公室电话: 2291071 : 2291071 手机手机: 13481395869: 13481395869辅导教师：周小川辅导教师：周小川 答疑时间：星期四答疑时间：星期四 上午上午 10:20-11:5010:20-11:50 答疑地点：答疑地点：5 5教教5 5楼楼 软件工程教研室软件工程教研室离散数学离散数学回顾回顾oo 关系可能具有的性质：关系可能具有的性质：n n 自反自反n n 反自反反自反n n 对称对称n n 反对称反对称n n 传递传递oo 特殊关系：
2、具有上述某些性质的关系特殊关系：具有上述某些性质的关系 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 是一个偏序关系。如果是一个偏序关
3、系。如果 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上的小于等于关系上的小于等于关系“ “ ” ”； 实数集合实
4、数集合RR上的大于等于关系上的大于等于关系“ “ ” ”； 自然数集合自然数集合NN上的模上的模n n同余关系；同余关系； 人群中的人群中的“ “父子父子” ”关系。关系。例例2.672.67判断集合判断集合AA=2, 3, 4, 5, 6, 8=2, 3, 4, 5, 6, 8上的整除关系是否为偏序关系？上的整除关系是否为偏序关系？ 并用关系矩阵和关系图表示。并用关系矩阵和关系图表示。 解解: : 集合集合A A上的整除关系为上的整除关系为R R=, =, , 该关系具有自反性、反对称性和传递性。所以，它是偏序关系。该关系具有自反性、反对称性和传递性。所以，它是偏序关系。 该关系的关系矩阵和
5、关系图表示如下：该关系的关系矩阵和关系图表示如下： 6 2 534 8R可比、盖住可比、盖住定定义义义义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且不存在
6、元素且不存在元素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=, =, ,。可比的情况：可比的情况：不可比的情况：不可比的
7、情况：盖住的情况：盖住的情况：哈斯图哈斯图pp 对对偏序关系偏序关系的关系图可进行如下简化：的关系图可进行如下简化： 自反：可以将各顶点上的环全部略去；自反：可以将各顶点上的环全部略去； 反对称：边为单向，可以规定向上方向为箭头方向，省略箭头；反对称：边为单向，可以规定向上方向为箭头方向，省略箭头； 传递：可以将由传递性导出的边省去。传递：可以将由传递性导出的边省去。 将经过上述简化后得到的关系图称为将经过上述简化后得到的关系图称为哈斯图哈斯图。oo 哈斯图的绘制步骤：哈斯图的绘制步骤： （1 1）以）以“ “ ” ” 表示元素；表示元素； （2 2）若）若x x y y，则，则y y画在画在
8、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 534 8R84 62 3 5关系R的
9、哈斯图哈斯图哈斯图例例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)上的包含关系上的包含关系“ “ ” ”
10、； 解：解：偏序关系偏序关系、和和的哈斯图绘制于图的哈斯图绘制于图124 62 31整除关系23458大于等于关系a,b,ca,b a,c b,ca b c包含关系24 361262 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
11、 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,
12、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不可比，不可比， 所以
13、，不存在最小元，最大元为所以，不存在最小元，最大元为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中偏序关系中偏序关系 （即
14、（即集合集合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
