离散数学课件第四章(第5讲).ppt

《离散数学课件第四章(第5讲).ppt》由会员分享，可在线阅读，更多相关《离散数学课件第四章(第5讲).ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、偏序关系偏序关系n偏序关系及基本概念偏序关系及基本概念n哈斯图哈斯图n特殊元素特殊元素n其它序关系其它序关系 定义定义：设：设 A 是一个集合，如果是一个集合，如果A上的关系上的关系 R，满足自反性，满足自反性，反对称性和传递性，则称反对称性和传递性，则称 R 是是 A上上 的偏序关系，记作的偏序关系，记作“”.EX1：在实数集：在实数集 Z上，小于等于关系是偏序关系吗？上，小于等于关系是偏序关系吗？EX2：在实数集：在实数集Z上，小于关系是偏序关系吗？上，小于关系是偏序关系吗？EX3：设集合：设集合A的幂集的幂集 (A)上的包含关系是偏序关系吗？上的包含关系是偏序关系吗？EX4：正整数：正整

2、数 I+集合上的整除关系是偏序关系吗？集合上的整除关系是偏序关系吗？偏序关系及基本概念偏序关系及基本概念1 1、偏序关系定义、偏序关系定义 表示表示偏序关系偏序关系,如果如果 ,则记作则记作x y,读作读作“小于等于小于等于”.注意注意:这里的这里的“小于等于小于等于”不是指数的大小不是指数的大小,而是指而是指 偏偏 序序 关系中元素的顺序性关系中元素的顺序性.不同的偏序关系对不同的偏序关系对 有不同的序解释有不同的序解释.例如例如:正整数正整数I+集合上的整除关系是偏序关系集合上的整除关系是偏序关系,3 6的的含义是含义是3整除整除62 2、偏序集定义、偏序集定义定义：定义：集合集合A和和A

3、上的偏序关系合在一起叫做偏序集上的偏序关系合在一起叫做偏序集,记作记作例如例如:实数集合实数集合Z和数的小于等于关系和数的小于等于关系 构成偏序集构成偏序集 集合集合A的幂集的幂集P(A)和包含关系和包含关系 构成偏序集构成偏序集正整数正整数 I+集合和整除关系构成偏序集集合和整除关系构成偏序集哈斯图哈斯图(Hasse Diagram)是偏序关系的关系图，要画出哈斯图，是偏序关系的关系图，要画出哈斯图，需要先定义偏序集中顶点之间的盖住关系。需要先定义偏序集中顶点之间的盖住关系。COV A=|xA yAy盖住盖住x定义定义：在偏序集：在偏序集中，对中，对A上任意元素上任意元素x和和y,若有若有

4、x y和x y，且没有其它元素z,满足x z且且z y,则称元素则称元素y盖住盖住x。盖住集。盖住集(盖住关系盖住关系)记为：记为：3、盖住集、盖住集(盖住关系盖住关系)说明：给定偏序集说明：给定偏序集，它的盖住集，它的盖住集(盖住关系盖住关系)是唯一的。是唯一的。例：设例：设A=2，3，4，6，8，则定义在，则定义在A上的整除关系上的整除关系R=，求，求COV A 按照盖住集定义分析得：按照盖住集定义分析得：COV A =COV A=|xA yAy盖住盖住x定义定义：在偏序集合：在偏序集合A，中，对中，对A上任意元素上任意元素x和和y,若有若有 x y和x y，且没有其它元素z,满足x z且

5、且z y,则称元素则称元素y盖住盖住x.盖住集盖住集(盖住关系盖住关系)记为：记为：4、分析研究盖住集、分析研究盖住集(盖住关系盖住关系)定义定义结论：结论：(1)盖住集中不存在任何序偶盖住集中不存在任何序偶且且xA(2)若存在其它元素z，满足x z且且z y，可通过复合运算获，可通过复合运算获得序偶得序偶(3)通过复合运算获得的序偶通过复合运算获得的序偶不属于盖住集。不属于盖住集。定义定义:设设R是集合是集合A上的偏序关系，上的偏序关系，IA是集合是集合A上的恒等关系，上的恒等关系，R1=R-IA,则则R1-(R1 o R1)为盖住集为盖住集COV A。以上所给的盖住集定义是立足于集合运算的

6、观点以上所给的盖住集定义是立足于集合运算的观点,应用此应用此等价定义判定偏序关系的盖住集等价定义判定偏序关系的盖住集,不仅有条理不仅有条理,而且步骤清而且步骤清晰。晰。可从以下几步求盖住集可从以下几步求盖住集:(1)计算计算R1=R-IA(2)将将R1 与其自身复合与其自身复合,得集合得集合R2,即即 R2=R1 o R1(3)计算集合计算集合R1 和和R2 的差的差,则盖住集为则盖住集为:COV A=R1-R2 5、盖住集、盖住集(盖住关系盖住关系)的等价定义的等价定义例：设例：设A=2，3，4，6，8，则定义在，则定义在A上的整除关系上的整除关系R=，求，求COV A 解解:IA=R1=R

7、-IA=R2=R1 o R1=COV A=R1 R2=例例 设集合设集合A=a,b,c,d,e,R 是是A 上的偏序关系。上的偏序关系。R=,求求盖住集盖住集COV A。解解:IA=R1=R-IA=R2=R1 o R1=COV A=R1 R2=偏序集偏序集的哈斯图画法的哈斯图画法:(1)用小圆圈代表用小圆圈代表集合集合A中的元素中的元素(2)若若x y且且x y,则将则将x画在画在y的下方的下方(3)若若COV A,就用一条线段连接就用一条线段连接x和和y 给定偏序集给定偏序集A，它的盖住集是唯一的。根据盖住集可，它的盖住集是唯一的。根据盖住集可以画出偏序关系的关系图，这个关系图称为偏序关系的

8、哈斯图。以画出偏序关系的关系图，这个关系图称为偏序关系的哈斯图。哈斯图哈斯图说明：普通的关系图各元素之间的位置无关，而哈斯图中元素说明：普通的关系图各元素之间的位置无关，而哈斯图中元素的上下位置有关。的上下位置有关。=COV P=则哈斯图为：则哈斯图为：例：设例：设P=1,2,3,其中其中表示表示P中元素的小于等于关系，中元素的小于等于关系，画出偏画出偏序集序集的哈斯图。的哈斯图。321例：设例：设A=2,3,6,12,24,36,定义为定义为A上的整除关系，画出上的整除关系，画出偏序集偏序集哈斯图。哈斯图。例：设例：设A=2,3,6,12,24,36=COV A=则哈斯图为：则哈斯图为：23

9、6122436例：设例：设S=a,b,(S)=，a,b,a,b,画出偏序集画出偏序集的哈斯图的哈斯图.=COV S=则哈斯图为：则哈斯图为：aba,b1、极大元与最大元、极大元与最大元定义定义 设设为偏序集为偏序集,B A.(1)若若 y B，使得，使得B中没有任何元素中没有任何元素x,满足满足yx且且yx，则称，则称y为为B的极大元的极大元(2)若若 x(x Bx y)成立成立,则称则称y为为B的最大元的最大元特殊元素特殊元素极大元、最大元举例：极大元、最大元举例：例：设有集合例：设有集合A=1,2,3,4,5,6,9,10,15上的整除关系上的整除关系 R，B1=1,2,3，B2=3,5,

10、15，B3=AB1的极大元是的极大元是2,3，B1无最大元；无最大元；B2的极大元是的极大元是15，B2的最大元是的最大元是15；B3的极大元是的极大元是4,6,9,10,15，B3无最大元；无最大元；42153610915142536109152、极小元与最小元、极小元与最小元定义定义 设设为偏序集为偏序集,B A.(1)若若 y B，使得，使得B中没有任何元素中没有任何元素x,满足满足yx且且xy，则，则称称y为为B的极小元的极小元(2)若若 x(x By x)成立成立,则称则称y为为B的最小元的最小元;极小元、最小元举例：极小元、最小元举例：例：设有集合例：设有集合A=1,2,3,4,5

11、,6,9,10,15上的整除关系上的整除关系 R，B1=1,2,3，B2=3,5,15，B3=AB1的的极小极小元是元是1，B1的最小元是的最小元是1；B2的的极小极小元是元是3，5，B2无最小元；无最小元；B3的的极小极小元是元是1，B3的最小元是的最小元是1；42153610915142536109151综合举例综合举例例：设例：设A=2,3,6,12,24,36,定义为定义为A上的整除关系，其偏序集上的整除关系，其偏序集哈斯图如下。分别求下列集合的极大元、极小元、最哈斯图如下。分别求下列集合的极大元、极小元、最大元、最小元。大元、最小元。236122436子集子集B极大元极大元极小元极小

12、元最大元最大元最小元最小元2,3,6,12,24,3624，362，3无无无无6,121261262,3,662，36无无66666讨论定义讨论定义：(1)(1)y B，B的极大元，极小元，最大元，最小元，若有的极大元，极小元，最大元，最小元，若有的话，必定在的话，必定在B中。中。(2)极大元是哈斯图中最顶层的元素极大元是哈斯图中最顶层的元素,极小元是哈斯图中最极小元是哈斯图中最低层的元素低层的元素 (3)B中最大，最小元不一定存在中最大，最小元不一定存在,如果有最大，最小元则一如果有最大，最小元则一定是唯一的，极大，极小元一定存在，且不一定是唯一的。定是唯一的，极大，极小元一定存在，且不一定

13、是唯一的。定义定义 设设为偏序集为偏序集,B A,y A.(1)若若 x(x Bx y)成立成立,则称则称y为为B的上界的上界;(2)令令C=y|y为为B的上界的上界,若若 C 有最小元，则有最小元，则称该最小元为称该最小元为 B 的的最小上界或上确界最小上界或上确界,记为记为LUB上界、上确界举例：上界、上确界举例：例：设有集合例：设有集合A=1,2,3,4,5,6,9,10,15上的整除关系上的整除关系 R，B1=1,2,3，B2=3,5,15，B3=A。B1的上界是的上界是6，B1的上确界是的上确界是6；B2的上界是的上界是15，B2的上确界是的上确界是15；B3无无上界上界，B3无无上

14、上确确界界；4215361091514253610915定义定义 设设为偏序集为偏序集,B A,y A.(3)若若 x(x By x)成立成立,则称则称y为为B的下界的下界;(4)令令D=y|y为为B的下界的下界,若若 D 有最大元，则称有最大元，则称该最大元该最大元为为B的最大下界或下确界的最大下界或下确界,记为记为GLB下界、下确界（最大下界）举例：下界、下确界（最大下界）举例：例：设有集合例：设有集合A=1,2,3,4,5,6,9,10,15上的整除关系上的整除关系 R，B1=1,2,3，B2=3,5,15，B3=A。B1的的下界下界是是1，B1的下确界是的下确界是1；B2的的下界下界是

15、是1，B2的下确界是的下确界是1；B3的的下界下界是是1，B3的下确界的下确界是是1；4215361091514253610915子集子集上界上界LUB下界下界GLBaca,ca,b,ca,c abca,b,ca,b,c a,bb,ca,b,ca,b,cb,bbba,bb,ca,b,cbb,b例：设例：设X=a,b,c,是一偏序集合，是一偏序集合，其哈斯图如右，其哈斯图如右，求下列子集的上界、下界、求下列子集的上界、下界、最小上界和最大下界最小上界和最大下界讨论定义：讨论定义：(1)上，下界是对上，下界是对B中所有元素比较而言的。中所有元素比较而言的。(2)B的上界的上界,下界都可能不存在下界

16、都可能不存在,如果存在如果存在,则不一定是则不一定是唯一的。唯一的。(3)B的最小上界的最小上界(LUB),最大下界最大下界(GLB)都可能不存在都可能不存在.如果存在如果存在,最小上界与最大下界是唯一的最小上界与最大下界是唯一的.(4)若若 B只有一个上界和下界，则该上界和下界一定是只有一个上界和下界，则该上界和下界一定是最小上界与最大下界最小上界与最大下界 定义定义 在偏序集合在偏序集合A，中，若中，若 且具有且具有xy或或yx，则称，则称x和和y是可以比较的，是可以比较的，否则称否则称x,y是不可比较的。是不可比较的。定义定义 设设R为非空集合为非空集合A上的偏序关系上的偏序关系,如果如

17、果x,y A,x与与y都是可比较的都是可比较的,则称则称R为为A上的全序关系上的全序关系(或线序关系或线序关系).例如例如:数集上的小于等于关系是全序关系数集上的小于等于关系是全序关系,因为任因为任何两个数总是可以比较大小的何两个数总是可以比较大小的.一般来说一般来说,整除关系不是全序关系整除关系不是全序关系.如如:集合集合 1,2,3 上的整除关系就不是全序关系上的整除关系就不是全序关系,因为因为2和和3不可整除不可整除.全序关系的定义：全序关系的定义：定义定义 若集合若集合X上的二元关系上的二元关系R是全序关系，且是全序关系，且X的任的任一非空子集，都有一个最小元素，则称一非空子集，都有一

18、个最小元素，则称R为良序关系，为良序关系，并称并称为良序集合。为良序集合。讨论定义：讨论定义：（1）良序关系比全序关系多了一个条件，即在全序关系中，）良序关系比全序关系多了一个条件，即在全序关系中，X集合的任一非空子集均有一个最小元素；集合的任一非空子集均有一个最小元素；（2）每一个有限集合）每一个有限集合X上的全序关系必定是良序关系。上的全序关系必定是良序关系。例：设例：设A=1,2,3,4定义定义A上的上的“”=良序关系的定义：良序关系的定义：拟序关系的定义：拟序关系的定义：设设 A 是一个集合，如果是一个集合，如果A上的一个关系上的一个关系 R，满，满足反自反性，反对称性和传递性，则称足反自反性，反对称性和传递性，则称 R 是是 A上的一个拟序关系，或称上的一个拟序关系，或称 R 在在 A 上是拟序的，上是拟序的，记作记作“”；例：由集合例：由集合 A 所组成的幂集所组成的幂集 (A)上的关系上的关系“”是是是拟序关系？是拟序关系？例：在整数集例：在整数集 Z 上小于关系是拟序关系？上小于关系是拟序关系？