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

1,离散数学,离散数学,2,7.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如下：,试判断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, 表示整除关系，则是个偏序。,关系图,哈斯图,画法：一般先从最下层结点(全是射出的边与之相连)，逐层向上画，直到最上层结点(全是射入的边与之相连)。,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图,11,偏序集中的特殊元素,一.极小元与极大元 设集合A上有一个偏序关系且设B是 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就是极大元),12,举例给定,Hasse图如图所示： 从Hasse图找极小(大)元：子集中处在最下(上)层 的元素是极小(大)元。,13,例：是偏序集， ，,定理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图找最小(大)元：子集中如果只有唯一的极 小(大)元，则这个 极小(大)元，就是 最小(大)元。否则 就没有最小(大)元。 下面介绍最小(大)元的唯一定理。,15,定理2：是偏序集，B是A的非空子集，如果B有 最小元(最大元)，则最小元(最大元)是唯一的。 证明：假设B有两个最小元x、y,则 因为x是最小元，yB，根据最小元定义，有xy; 类似地，因为y是最小元，xB，根据最小元定义，有yx。因为有反对称性，所以有x=y。 同理可证最大元的唯一性。 小结：(A,)是偏序集，B是A的非空子集，则 B的极小(大)元总是存在的，就是子集中处在最下(上) 层的元素是极小(大)元。 如果有唯一的极小(大)元，则这个极小(大)元就是最小(大)元。否则就没有最小(大)元。,16,3.上界与下界 (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中找！,17,4. 最小上界(上确界)和最大下界(下确界) (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,都有a a 则称a是B的最大下界(下确界) 。 若令Da|a为B的下界，则称D的最大元为B的最大下 界或下确界. (即a是下界中最大的。如果B有下确界，则是唯一的),18,举例，给定（C,）的Hasse图如图所示：,19,求(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,的特殊元素。,20,解答：设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，下界、下确界都 是。,21,非空子集极小(极大)元总是存在的。但极大元、极小元并不是唯一，且同一元素可以既是极大元又是极小元。如果有唯一的极小(大)元，则这个极小(大)元就是最小(大)元。否则就没有最小(大)元。,2.极大元、极小元必须是子集B中的元素。,3.最大元（最小元）本身应属于子集B，且与B中任一元素都有关系。最大元（最小元）可能存在也可能不存在，如果存在是唯一的。,总结：,22,4. 子集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的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界。,a,b,c,d,e,f,h,g,a,b,d,e,a,b,c,无,无,无,c,c,d,e,f,g,h,h,无,c,a,b,c,c,h,无,B1,B2,24,次序关系,偏序关系 拟序关系 全序关系 良序关系,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.正整数集N上的小于或等于关系“”也是N上的一个全序；而N上的整除关系就仅是一个偏序而不是全序; 。 【注意】：(1）全序的含义：中每两个元素均能比较大小，即任何两个元素都能排序；而偏序则是部分有序。 （2）二者的关系：全序一定是偏序但偏序不一定是全序。,28,例1(续) B=1,2,4,8,表示整除关系,关系图,哈斯图,29,例：判断下列关系是否为全序关系，如果是，请画出哈斯图 1. 设集合A=a，b，c，其上的关系“”=,； 2. 实数集合R上定义的小于等于关系“”； 3. 实数集合R上定义的小于关系“” 4. 集合A的幂集P(A)上定义的包含关系“”,解：1.是全序关系。哈斯图见图(a)。 2. 是全序关系。哈斯图是实数轴，见图(b)。 3. 不是全序关系。 4. 当|A|2时，P(A)上定义的“”是