离散数学课件-次序关系课件

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