离散数学离散数学17.2 7.2 等价关系等价关系7.3 7.3 次序关系次序关系学习内容2次序关系n偏序关系n拟序关系n全序关系n良序关系3偏序关系n n定义定义1 1：R是A上的关系，如果它是自反、反对称和传递的 ，则称R 是A A上的偏序关系上的偏序关系。并称是偏序集。例 试判断下列关系是否为偏序关系 (1)集合A的幂集P(A)上的包含关系“ ”； (2)实数集合R上的小于或等于关系“ ”是是因为数值的因为数值的“”“”是熟知的偏序关系，所以用符号是熟知的偏序关系，所以用符号“ “ ” ” 表示任意偏序关系表示任意偏序关系但要注意：但要注意：“ “ ” ”不一定是不一定是“ “小于或等于小于或等于” ”的含义的含义; ;不是不是 指数值的大小而是指偏序中元素位置的先后。指数值的大小而是指偏序中元素位置的先后。例例 : A=1,2,4,6, : A=1,2,4,6, 设设 是是A A中的整除关系。显然中的整除关系。显然“”“” 是自反、反对称和传递的，即它是个偏序。是自反、反对称和传递的，即它是个偏序。4补充定义：补充定义： x x与与y y是可比较的是可比较的：是偏序集，如果对x,yA，必有xy,或yx, 则称x与y是可比较的。上例中1,2,4或1,2,6间是可比较的，而4与6间是不可比较的【注意】若“”是集合A上的一个偏序关系，这意味着对于 任意x,yA，当xy时，xy和yx至多一个成立。 5例7.3.5 考虑任务集T，它包含了拍摄一张室内开启闪光 灯的照片必须按顺序完成的任务。1. 打开镜头盖2. 照相机调焦3. 开启闪光灯4. 按下快门按钮在T上定义关系R如下：试判断R是否是T上的偏序关系并画出它的关系图 。解：(1)列出R中的元素(2) 判断是否满足属性(3) 画出关系图6偏序关系的关系图特点：(1) 每个结点都有环(2) 两个不同结点之间要么有且仅有一条边相连，要么没有 边相连哈斯图(Hasse图)(1). (1). 用小圆圈或点表示用小圆圈或点表示A A中的元素，省掉关系图中所有中的元素，省掉关系图中所有 的自环。的自环。 (2).(2).如果如果xyxy, ,且且xyxy，则结点则结点x x要画在结点要画在结点y y的的下下方。方。 (3). (3). 如果如果xyxy, ,且在集且在集A A中不存在任何中不存在任何zAzA, ,使得使得z z介于介于x x 与与y y之间，之间，则则 x x与与y y之间用一条直线连接。之间用一条直线连接。偏序关系的偏序关系的关系关系图图：不能直观地反映出元素之间的次序，所以 下面介绍另外一种图-哈斯图(Hasse图)。通过这个图，就能够 清晰地反映出元素间的层次。下面介绍Hasse图。7例 A=1,2,4,6, 表示整除关系，则是个偏序。2。1。64。关系图哈斯图画法：一般先从最下层结点一般先从最下层结点( (全是射出的边与之相连全是射出的边与之相连) )， 逐层向上画，直到最上层结点逐层向上画，直到最上层结点( (全是射入的边与之相连全是射入的边与之相连) ) 。8例7.3.7 A=2,3,6,12,24,36, 是A上整除关系。画出关系图 及哈斯图。9课堂小测验： (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。10偏序集中的特殊元素一.极小元与极大元 设集合设集合A A上有一个偏序关系上有一个偏序关系 且且设设B B是是 A A的子集，的子集，则则 (1）如果存在一个元素bB且在B中找不到元素b有b b且b b 则称b是B的极小元 .） （在B中没有比b更小的元素了，b就是极小元） （2）如果存在一个元素bB且中找不到元素b有b b且 b b ，则称b是B的极大元 . (在B中没有比b更大的元素了，b就是极大元)11举例给定,Hasse图如图所示：从Hasse图找极小小(大)元：子集中处在最下子集中处在最下(上)层层 的元素是极小的元素是极小( (大大) )元元。12。24。36。子集B极小元极大元 2,3 1,2,3 6,12,24 C2, 32, 3 12, 3 624 124,3612例：是偏序集，定理定理1 1：设是偏序集，B是A的非空有限子集， 则B一定存在极大（小）元。则 中极大元：，极小元：，13二.最小元与最大元（1）如果存在一个元素bB对每一个bB 均有b b 则 称b是B的最小元(最小元b b是B中元素，该元素比B中所有元素都小)（2）如果存在一个元素bB对每一个bB 均有b b 则称 b是B的最大元(最大元b是B中元素，该元素比B中所有元素都大) 举例，给定的Hasse图如图所示： 从Hasse图找最小(大)元：子集中如果只有唯一的极 小(大)元，则这个 极小(大)元，就是 最小(大)元。否则 就没有最小(大)元。下面介绍最小(大)元的唯一定理。12。24。36。子集B最小元最大元 2,3 1,2,3 6,12,24C无无 1无 624 1无14定理2：是偏序集，B是A的非空子集，如果B有 最小元(最大元)，则最小元(最大元)是唯一的。 证明：假设B有两个最小元x、y,则因为x是最小元，yB，根据最小元定义，有xy; 类似地，因为y是最小元，xB，根据最小元定义，有 yx。因为有反对称性，所以有x=y。同理可证最大元的唯一性。小结：(A,)是偏序集，B是A的非空子集，则B的极小(大)元总是存在的，就是子集中处在最下(上) 层的元素是极小(大)元。如果有唯一的极小(大)元，则这个极小(大)元就是最小 (大)元。否则就没有最小(大)元。153.上界与下界 (Upper Bound and Lower Bound)(1)设是偏序集，BA，若存在aA，使得对 bB，ba,称a为B的上界。（上界a是A中元素，该元素比B中所有元素都大) (2) 设是偏序集，BA，若存在aA，使得对 bB，ab,称a为B的下界。 （下界a是A中元素，该元素比B中所有元素都小) 举例，给定的Hasse图如图所示：从Hasse图找上(下)界：注意是在A中找！。12。24。36。子集B上界下界 2,3 1,2,3 6,12,24C1 6,12,24,361 246,2,3,11无6,12,24,36164. 最小上界(上确界)和最大下界(下确界) (Least Upper Bound and Greatest Lower Bound)1： a是B的上界，并且对B的所有上界a,都有aa,则称a是B的最小上界(上确界) 。即若令即若令C C a|aa|a为为B B的上界的上界 ，则，则C C的最小元为的最小元为B B的最小上的最小上界或界或上确界.(即a是上界中最小的。如果B有上确界，则是唯一的) 2： a是B的下界，并且对B的所有下界a,都有a a 则称a是B的最大下界(下确界) 。若令若令D D a|aa|a为为B B的下界的下界 ，则称，则称D D的最大元为的最大元为B B的最大下的最大下界或界或下确界. (即a是下界中最大的。如果B有下确界，则是唯一的)17子集B上界下界 2,3 1,2,3 6,12,24 C1 6,12,24,361 241,2,3,6 1无6,12,24,36上确界下确界 6 6 24 无1 1 6 1。12。24。36。举例，给定（C,）的Hasse图如图所示：18求(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 的特殊元素。19解答：设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, ；它的上界与上确界是相同的即是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。201. 非空子集极小(极大)元总是存在的。但极大元、极小元并不 是唯一，且同一元素可以既是极大元又是极小元。如果有唯 一的极小(大)元，则这个极小(大)元就是最小(大)元。否则就 没有最小(大)元。2.2.极大元、极小元必须是子集B中的元素。3.最大元（最小元）本身应属于子集B，且与B中任一元素都 有关系。最大元（最小元）可能存在也可能不存在，如果存 在是唯一的。总结总结：214. 子集B的上/下界和最小上/最大下界必须在集合A中寻找；5. 子集B的上/下界不一定存在，如果存在，可以不唯一的；6. 子集B的上界/下界、最小上/最大下界不一定存在，如果存在， 则最小上界与最大下界是唯一的；7. 子集B有最小上/最大下界，一定有上(下)界；反之不然。8. B的最小元一定是B的下界，同时也是B的最大下界。 同样，B的最大元一定是B的上界，同时也是B的最小上界。9. 但反过来不一定正确，B的下界不一定是B的最小元，因为它可 能不是B中的元素。同样的，B的上界也不一定是B的最大元。22课堂小练习设集合A=a,b,c,d,e,f,g,h，对应哈 斯图见右图。令B1=a,b，B2=c,d,e 。求出B1，B2的极大元、极小元、最 大元、最小元、上界、下界、上确界 、下确界。 abcdefhg极 大 元极 小 元最 大 元最 小 元上界下界上 确 界下 确 界B1B2a,bd,ea,bc无无无cc,d,e,f,g,hh无c,a,bcch无B1B223次序关系n偏序关系n拟序关系n全序关系n良序关系24实数集R上的“”关系不是偏序关系。 A上的真包含关系“ ”也不是偏序关系。定义定义1 1：R是A上的关系，如果它是反自反的、传递的则称 R 是A A上的拟序关系上的拟序关系。并称是拟序集。定理1：集合A上的关系R是拟序的，则必是反对称的。定理2 :设R是集合A上的关系，则(1)如果R是一个拟序关系，则 r(R)=R I是一个偏序关系(2)如果R是一个偏序关系，则 R I是一个拟序关系证明：假设A不是反对称的，则必存在x，y A，且xy， 满足 R并且 R。因为R是拟序关系，所以R 具有传递性，从而有 R。这与R是反自反的矛盾。25次序关系n偏序关系n拟序关系n全序关系n良序关系并不是所有的元素都可以比较所有的元素都可以比较26全序(线序、链)1.定义：是偏序集，如果对任何x,yA，如果x与y都 是可比较的（即都有xy，或yx）则称是全序关系(线 序、链)。 例1 . B=1,2,4,8, “ ”表示整除关系， 则“” 是全序关系，有向图：例2.正整数集N上的小于或等于关系“”也是N上的一个全 序；而N上的整除关系就仅