《离散数学243(偏序关系).ppt》由会员分享，可在线阅读，更多相关《离散数学243(偏序关系).ppt（29页珍藏版）》请在金锄头文库上搜索。
1、主讲教师：常亮主讲教师：常亮主讲教师：常亮主讲教师：常亮E-mail:E-mail:QQQQ：737059669737059669办公室电话办公室电话办公室电话办公室电话:2291071:2291071手机手机手机手机:13481395869:13481395869辅导教师：周小川辅导教师：周小川辅导教师：周小川辅导教师：周小川答疑时间：星期四答疑时间：星期四答疑时间：星期四答疑时间：星期四 上午上午上午上午 10:20-11:5010:20-11:50答疑地点：答疑地点：答疑地点：答疑地点：5 5教教教教5 5楼楼楼楼 软件工程教研室软件工程教研室软件工程教研室软件工程教研室离散数学离散数学
2、回顾回顾o关系可能具有的性质：关系可能具有的性质：关系可能具有的性质：关系可能具有的性质：n n自反自反自反自反n n反自反反自反反自反反自反n n对称对称对称对称n n反对称反对称反对称反对称n n传递传递传递传递o特殊关系：具有上述某些性质的关系特殊关系：具有上述某些性质的关系特殊关系：具有上述某些性质的关系特殊关系：具有上述某些性质的关系n n等价关系：自反、对称、传递等价关系：自反、对称、传递等价关系：自反、对称、传递等价关系：自反、对称、传递n n偏序关系偏序关系偏序关系偏序关系：自反、：自反、：自反、：自反、反对称反对称反对称反对称、传递、传递、传递、传递2.4.3偏序关系偏序关系
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 是一个偏序关系。如果是一个偏序关系。如果
4、是一个偏序关系。如果是一个偏序关系。如果 R R, ,则记为则记为则记为则记为x x y y。oo如果集合如果集合如果集合如果集合AA上存在偏序关系，则称上存在偏序关系，则称上存在偏序关系，则称上存在偏序关系，则称AA为为为为偏序集偏序集偏序集偏序集，记为，记为，记为，记为。 oo例：集合例：集合例：集合例：集合A=2,4,6,8A=2,4,6,8A=2,4,6,8A=2,4,6,8上的小于等于关系上的小于等于关系上的小于等于关系上的小于等于关系 = , , , , , , = , , , , , , = , , , , , , = , , , , , , , , , , , , , , ,
5、, , , 。“偏序偏序”例例2.66判断下列关系是否为偏序关系判断下列关系是否为偏序关系判断下列关系是否为偏序关系判断下列关系是否为偏序关系 集合集合集合集合AA的幂集合的幂集合的幂集合的幂集合P P( (AA) )中元素之间的包含关系中元素之间的包含关系中元素之间的包含关系中元素之间的包含关系“ “ ” ”； 实数集合实数集合实数集合实数集合RR上的小于等于关系上的小于等于关系上的小于等于关系上的小于等于关系“ “ ” ”； 实数集合实数集合实数集合实数集合RR上的大于等于关系上的大于等于关系上的大于等于关系上的大于等于关系“ “ ” ”； 自然数集合自然数集合自然数集合自然数集合NN上的
6、模上的模上的模上的模n n同余关系；同余关系；同余关系；同余关系； 人群中的人群中的人群中的人群中的“ “父子父子父子父子” ”关系。关系。关系。关系。例例2.67判断集合判断集合判断集合判断集合AA=2,3,4,5,6,8=2,3,4,5,6,8上的整除关系是否为偏序关系？上的整除关系是否为偏序关系？上的整除关系是否为偏序关系？上的整除关系是否为偏序关系？并用关系矩阵和关系图表示。并用关系矩阵和关系图表示。并用关系矩阵和关系图表示。并用关系矩阵和关系图表示。解解解解: : : : 集合集合集合集合A A A A上的整除关系为上的整除关系为上的整除关系为上的整除关系为R R R R =, =,
7、 =, =, ,该关系具有自反性、反对称性和传递性。所以，它是偏序关系。该关系具有自反性、反对称性和传递性。所以，它是偏序关系。该关系具有自反性、反对称性和传递性。所以，它是偏序关系。该关系具有自反性、反对称性和传递性。所以，它是偏序关系。该关系的关系矩阵和关系图表示如下：该关系的关系矩阵和关系图表示如下：该关系的关系矩阵和关系图表示如下：该关系的关系矩阵和关系图表示如下： 62 5 3 4 8 R可比、盖住可比、盖住定定定定义义义义2.292.29设设设设R R为为为为非空集合非空集合非空集合非空集合A A上的偏序关系，上的偏序关系，上的偏序关系，上的偏序关系，对对对对于任意元素于任意元素于
8、任意元素于任意元素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且
9、且且且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.68考察集合考察集合考察集合考察集合AA=2,3,4,5,6,8=2,3,4,5,6,8上的整
10、除关系上的整除关系上的整除关系上的整除关系R R R R =, =, =, =, ,。可比的情况：可比的情况：可比的情况：可比的情况：不可比的情况：不可比的情况：不可比的情况：不可比的情况：盖住的情况：盖住的情况：盖住的情况：盖住的情况：哈斯图哈斯图pp对对对对偏序关系偏序关系偏序关系偏序关系的关系图可进行如下简化：的关系图可进行如下简化：的关系图可进行如下简化：的关系图可进行如下简化： 自反：可以将各顶点上的环全部略去；自反：可以将各顶点上的环全部略去；自反：可以将各顶点上的环全部略去；自反：可以将各顶点上的环全部略去； 反对称：边为单向，可以规定向上方向为箭头方向，省略箭头；反对称：边为单
11、向，可以规定向上方向为箭头方向，省略箭头；反对称：边为单向，可以规定向上方向为箭头方向，省略箭头；反对称：边为单向，可以规定向上方向为箭头方向，省略箭头； 传递：可以将由传递性导出的边省去。传递：可以将由传递性导出的边省去。传递：可以将由传递性导出的边省去。传递：可以将由传递性导出的边省去。将经过上述简化后得到的关系图称为将经过上述简化后得到的关系图称为将经过上述简化后得到的关系图称为将经过上述简化后得到的关系图称为哈斯图哈斯图哈斯图哈斯图。oo哈斯图的绘制步骤：哈斯图的绘制步骤：哈斯图的绘制步骤：哈斯图的绘制步骤：（1 1 1 1）以）以）以）以“ “ ”表示元素；表示元素；表示元素；表示元
12、素；（2 2 2 2）若）若）若）若x x x x y y y y，则，则，则，则y y y y画在画在画在画在x x x x的上层；的上层；的上层；的上层； （3 3 3 3）若）若）若）若y y y y盖住盖住盖住盖住x x x x，则连线；，则连线；，则连线；，则连线；（4 4 4 4）不可比的元素可画在同一层。）不可比的元素可画在同一层。）不可比的元素可画在同一层。）不可比的元素可画在同一层。例例对于集合对于集合对于集合对于集合AA=2,3,4,5,6,8=2,3,4,5,6,8上的整除关系，画出其哈斯图。上的整除关系，画出其哈斯图。上的整除关系，画出其哈斯图。上的整除关系，画出其哈斯
13、图。解解解解: : : : 集合集合集合集合A A A A上的整除关系为上的整除关系为上的整除关系为上的整除关系为R R R R =, =, =, =, ,该关系具有自反性、反对称性和传递性。所以，它是偏序关系。该关系具有自反性、反对称性和传递性。所以，它是偏序关系。该关系具有自反性、反对称性和传递性。所以，它是偏序关系。该关系具有自反性、反对称性和传递性。所以，它是偏序关系。该关系的关系矩阵和关系图表示如下：该关系的关系矩阵和关系图表示如下：该关系的关系矩阵和关系图表示如下：该关系的关系矩阵和关系图表示如下： 62 5 3 4 8 R84 62 3 5关系R的哈斯图哈斯图哈斯图例例例例2.7
14、0: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 的幂集的
15、幂集的幂集的幂集P P( (A)A)上的包含关系上的包含关系上的包含关系上的包含关系“ “ ” ”；解：解：解：解：偏序关系偏序关系偏序关系偏序关系、和和和和的哈斯图绘制于图的哈斯图绘制于图的哈斯图绘制于图的哈斯图绘制于图 12 4 6 2 3 1 整除关系 2 3 4 5 8 大于等于关系 a,b,ca,b a,c b,ca b c 包含关系 24 36 12 6 2 3 整除关系偏序集中的偏序集中的8个特殊元素个特殊元素(最大元、最小元最大元、最小元)定义定义定义定义2.302.30对于偏序集对于偏序集对于偏序集对于偏序集和和和和集合集合集合集合AA的任意子集的任意子集的任意子集的任意子集
16、 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.71对对对对于例于例于例于例2.702.70
17、中偏序关系中偏序关系中偏序关系中偏序关系（即（即（即（即集合集合集合集合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的最大元和最小元。的最大
18、元和最小元。的最大元和最小元。的最大元和最小元。解解解解: : 对于集合对于集合对于集合对于集合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不可比，
19、不可比，不可比，不可比，所以，不存在最小元，最大元为所以，不存在最小元，最大元为所以，不存在最小元，最大元为所以，不存在最小元，最大元为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；对于集合对于集合对
20、于集合对于集合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
21、,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个特殊元素个特殊元素(极大元、极小元极大元、极小元)定义定义定义定义2.312.31对于偏序集对于偏序集对于偏序集对于偏序集和和和和集合集合集合集合AA的任意子集的任意子集的任意子集的任意子集 BB，如果存在元素如果存在元素如果存在元素如果存在元素b b BB，使得，使得，使得，使得BB中不存在其它元素中不存在其它元素中不存
22、在其它元素中不存在其它元素x x满足满足满足满足b b x x，则称则称则称则称b b为为为为BB的的的的极大元素极大元素极大元素极大元素，简称为简称为简称为简称为极大元极大元极大元极大元；如果存在元素如果存在元素如果存在元素如果存在元素b b BB，使得，使得，使得，使得BB中不存在其它元素中不存在其它元素中不存在其它元素中不存在其它元素x x满足满足满足满足x x b b，则称则称则称则称b b为为为为BB的的的的极小元素极小元素极小元素极小元素，简称为，简称为，简称为，简称为极小元极小元极小元极小元。注意：注意：注意：注意：最大（小）元最大（小）元最大（小）元最大（小）元vs.vs.极大
23、（小）元极大（小）元极大（小）元极大（小）元最大（小）元必须与最大（小）元必须与最大（小）元必须与最大（小）元必须与BB中每个元素都可比，中每个元素都可比，中每个元素都可比，中每个元素都可比，极大（小）元无此要求极大（小）元无此要求极大（小）元无此要求极大（小）元无此要求( (只要求没有比它更大或更小的元素只要求没有比它更大或更小的元素只要求没有比它更大或更小的元素只要求没有比它更大或更小的元素) )。例例2.73对对对对于例于例于例于例2.702.70中偏序关系中偏序关系中偏序关系中偏序关系（即（即（即（即集合集合集合集合A A =1,2,3,4,6,12=1,2,3,4,6,12上的整除关
24、系上的整除关系上的整除关系上的整除关系），），），），令令令令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 B B1= 1, 61= 1, 61=
25、 1, 61= 1, 6，极大元为，极大元为，极大元为，极大元为6 6 6 6，极小元为，极小元为，极小元为，极小元为1 1 1 1；对于集合对于集合对于集合对于集合B B B B2= 1, 2, 32= 1, 2, 32= 1, 2, 32= 1, 2, 3，极大元为，极大元为，极大元为，极大元为2 2 2 2和和和和3 3 3 3，极小元为，极小元为，极小元为，极小元为1 1 1 1；对于集合对于集合对于集合对于集合B B B B3= 4, 6, 123= 4, 6, 123= 4, 6, 123= 4, 6, 12，极大元为，极大元为，极大元为，极大元为12121212，极小元为，极小元
26、为，极小元为，极小元为4 4 4 4和和和和6 6 6 6；对于集合对于集合对于集合对于集合B B B B4= 24= 24= 24= 2，4 4 4 4，6666，极大元为，极大元为，极大元为，极大元为4 4 4 4和和和和6 6 6 6，极小元为，极小元为，极小元为，极小元为2 2 2 2；对于集合对于集合对于集合对于集合B B B B5= 1, 2, 6, 125= 1, 2, 6, 125= 1, 2, 6, 125= 1, 2, 6, 12，极大元为，极大元为，极大元为，极大元为12121212，极小元为，极小元为，极小元为，极小元为1 1 1 1；对于集合对于集合对于集合对于集合B
27、 B B B6= 1, 2, 3, 4, 6, 126= 1, 2, 3, 4, 6, 126= 1, 2, 3, 4, 6, 126= 1, 2, 3, 4, 6, 12，极大元为，极大元为，极大元为，极大元为12121212，极小元为，极小元为，极小元为，极小元为1 1 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
28、,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个特殊元素个特殊元素(上界、下界上界、下界)定义定义定义定义2.322.32对于偏序集对于偏序集对于偏序集对于偏序集和和和和集合集合集合集合AA的任意子集的任意子集的任意子集的任意子集BB，如果存在元素如果存在元
29、素如果存在元素如果存在元素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.75对对对对于例于例于
30、例于例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的
31、上界和下界。的上界和下界。的上界和下界。的上界和下界。解解解解:对于集合对于集合对于集合对于集合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，
32、上界为，上界为，上界为，上界为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,
33、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个特殊元素个特殊元素(上确界上确界,下确界下确界)定定定定义义义义2.332.33对对对对于
34、偏序集于偏序集于偏序集于偏序集 和和和和集合集合集合集合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
35、，使得，使得，使得，使得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的所有下界的集合，的所有下
36、界的集合，的所有下界的集合，的所有下界的集合，则则则则C C的最大元的最大元的最大元的最大元c c称称称称为为为为B B的下确界。的下确界。的下确界。的下确界。 例例2.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,
37、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的的的的上确界和下确界。上确界和下确界。上确界和下确界。上确界和下确界。解解解解: : : : 对于集合对于集合对于集合对于集合B1B1B1B1，上确界为，上确界为，上确界为，上确界为6 6 6 6，下确界为，下确界为，下确界为，下确界为1 1 1 1；对于集合对于集合对于集合对于集合B2B2B2B2，上确界为，上确界为，上确界为，上确界为6 6 6 6，下确界为，下确界为，下确界为，下确界为1 1 1 1
38、；对于集合对于集合对于集合对于集合B3B3B3B3，上确界为，上确界为，上确界为，上确界为12121212，下确界为，下确界为，下确界为，下确界为2 2 2 2；对于集合对于集合对于集合对于集合B4B4B4B4，上确界为，上确界为，上确界为，上确界为12121212，下确界为，下确界为，下确界为，下确界为2 2 2 2；对于集合对于集合对于集合对于集合B5B5B5B5，上确界为，上确界为，上确界为，上确界为12121212，下确界为，下确界为，下确界为，下确界为1 1 1 1；对于集合对于集合对于集合对于集合B6B6B6B6，上确界为，上确界为，上确界为，上确界为12121212，下确界为，下
39、确界为，下确界为，下确界为1 1 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
40、 3、B B4 4、B B5 5和和和和B B6 6的的的的上确界上确界上确界上确界和下和下和下和下确确确确界。界。界。界。8大元的性质大元的性质定理定理定理定理2.242.24对于偏序集对于偏序集对于偏序集对于偏序集和集合和集合和集合和集合AA的任意子集的任意子集的任意子集的任意子集BB： 若若若若b b为为为为BB的的的的最大元最大元最大元最大元，则，则，则，则b b为为为为BB的的的的极大元极大元极大元极大元、上界上界上界上界和和和和上确界上确界上确界上确界； 若若若若b b为为为为BB的的的的最小元最小元最小元最小元，则，则，则，则b b为为为为BB的的的的极小元极小元极小元极小元、下
41、界下界下界下界和和和和下确界下确界下确界下确界； 若若若若a a为为为为BB的的的的上界上界上界上界且且且且a a BB，则，则，则，则a a为为为为BB的的的的最大元最大元最大元最大元； 若若若若a a为为为为BB的的的的下界下界下界下界且且且且a a BB，则，则，则，则a a为为为为BB的的的的最小元最小元最小元最小元。8大元的性质大元的性质定理定理定理定理2.252.25对于偏序集对于偏序集对于偏序集对于偏序集和集合和集合和集合和集合AA的任意子集的任意子集的任意子集的任意子集BB： 若若若若BB有最大元有最大元有最大元有最大元，则，则，则，则BB的的的的最大元惟一最大元惟一最大元惟一
42、最大元惟一； 若若若若BB有最小元有最小元有最小元有最小元，则，则，则，则BB的的的的最小元惟一最小元惟一最小元惟一最小元惟一； 若若若若BB有上确界有上确界有上确界有上确界，则，则，则，则BB的的的的上确界惟一上确界惟一上确界惟一上确界惟一； 若若若若BB有下确界有下确界有下确界有下确界，则，则，则，则BB的的的的下确界惟一下确界惟一下确界惟一下确界惟一； 若若若若BB为为为为有限集有限集有限集有限集，则，则，则，则BB的的的的极大元、极小元恒存在极大元、极小元恒存在极大元、极小元恒存在极大元、极小元恒存在。全序全序(线序线序)关系关系/全序集全序集(线序集线序集)定义定义定义定义2.342
43、.34对于偏序集对于偏序集对于偏序集对于偏序集，如果如果如果如果AA中中中中任意两个元素任意两个元素任意两个元素任意两个元素x x和和和和y y都是可比的都是可比的都是可比的都是可比的( (即即即即x x y y或者或者或者或者y y x)x)，则称该偏序关系为则称该偏序关系为则称该偏序关系为则称该偏序关系为全序关系全序关系全序关系全序关系，或者，或者，或者，或者线序关系线序关系线序关系线序关系；并称并称并称并称为为为为全序集全序集全序集全序集、线序集线序集线序集线序集、或者、或者、或者、或者链链链链。当一个偏序关系是全序时，其哈斯图将集合中元素排成当一个偏序关系是全序时，其哈斯图将集合中元素
44、排成当一个偏序关系是全序时，其哈斯图将集合中元素排成当一个偏序关系是全序时，其哈斯图将集合中元素排成一条线，像一条链子，充分体现了其一条线，像一条链子，充分体现了其一条线，像一条链子，充分体现了其一条线，像一条链子，充分体现了其“ “链链链链” ”的特征的特征的特征的特征。例例2.79判断下列关系是否为全序关系？并给出其哈斯图。判断下列关系是否为全序关系？并给出其哈斯图。判断下列关系是否为全序关系？并给出其哈斯图。判断下列关系是否为全序关系？并给出其哈斯图。 集合集合集合集合2,3,4,6,8,122,3,4,6,8,12上的整除关系上的整除关系上的整除关系上的整除关系RR1 1； 集合集合集
45、合集合2,3,5,7,92,3,5,7,9上的大于等于关系上的大于等于关系上的大于等于关系上的大于等于关系RR2 2； 实数集合上的小于等于关系实数集合上的小于等于关系实数集合上的小于等于关系实数集合上的小于等于关系RR3 3； 集合集合集合集合 a a, ,b b, ,c c 上的关系上的关系上的关系上的关系RR4=4=,；解解解解: : : : 关系关系关系关系、和和和和都是偏序关系。都是偏序关系。都是偏序关系。都是偏序关系。 、和和和和都是全序关系；都是全序关系；都是全序关系；都是全序关系；不是全序关系。不是全序关系。不是全序关系。不是全序关系。 良序关系良序关系/良序集良序集定义定义定
46、义定义2.352.35对于对于对于对于偏序集偏序集偏序集偏序集，如果如果如果如果AA的的的的任意一个非空子集都有最小元素任意一个非空子集都有最小元素任意一个非空子集都有最小元素任意一个非空子集都有最小元素，则称该偏序关系为则称该偏序关系为则称该偏序关系为则称该偏序关系为良序关系良序关系良序关系良序关系，简称为，简称为，简称为，简称为良序良序良序良序；并称并称并称并称称为称为称为称为良序集良序集良序集良序集。例例2.80判断下列关系是否为良序关系？判断下列关系是否为良序关系？判断下列关系是否为良序关系？判断下列关系是否为良序关系？ 集合集合集合集合2,3,4,6,8,122,3,4,6,8,12
47、上的整除关系上的整除关系上的整除关系上的整除关系RR1 1； 集合集合集合集合2,3,5,7,92,3,5,7,9上的大于等于关系上的大于等于关系上的大于等于关系上的大于等于关系RR2 2； 实数集合上的小于等于关系实数集合上的小于等于关系实数集合上的小于等于关系实数集合上的小于等于关系RR3 3； 集合集合集合集合 a a, ,b b, ,c c 上的关系上的关系上的关系上的关系RR4=4=,。解解解解: (: (: (: (首先判断是否为偏序关系，然后再判断其任何一个非空子集是否都有首先判断是否为偏序关系，然后再判断其任何一个非空子集是否都有首先判断是否为偏序关系，然后再判断其任何一个非空子集是否都有首先判断是否为偏序关系，然后再判断其任何一个非空子集是否都有最小元最小元最小元最小元) ) ) )。和和和和是良序关系。是良序关系。是良序关系。是良序关系。良序集一定是全序集；良序集一定是全序集；有限的全序集一定是良序集。有限的全序集一定是良序集。作业作业P72o第第52题题(1)(2)o第第54题题o第第56题题R1,R2,R6,R7
