离散数学课件-次序关系

《离散数学课件-次序关系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学离散数学17.2等价关系7.3次序关系学习内容2次序关系偏序关系拟序关系全序关系良序关系3偏序关系定义1：R是A上的关系，如果它是自反、反对称和传递的，则称R是A上的偏序关系。并称是偏序集。例试判断下列关系是否为偏序关系(1)集合A的幂集P(A)上的包含关系“”；(2)实数集合R上的小于或等于关系“≤”是是因为数值的“≤”是熟知的偏序关系，所以用符号“≤”表示任意偏序关系但要注意：“≤”不一定是“小于或等于”的含义;不是指数值的大小而是指偏序中元素位置的先后。例:A={1,2,4,6},设≤是A中的整除关系。显然“≤”是自反、反对称和

2、传递的，即它是个偏序。4补充定义：x与y是可比较的：是偏序集，如果对x,y∈A，必有x≤y,或y≤x,则称x与y是可比较的。上例中1,2,4或1,2,6间是可比较的，而4与6间是不可比较的【注意】若“≤”是集合A上的一个偏序关系，这意味着对于任意x,y∈A，当x≠y时，x≤y和y≤x至多一个成立。5例7.3.5考虑任务集T，它包含了拍摄一张室内开启闪光灯的照片必须按顺序完成的任务。1.打开镜头盖2.照相机调焦3.开启闪光灯4.按下快门按钮在T上定义关系R如下：试判断R是否是T上的偏序关系并画出它的关系图。解：(1)列出R中的元素(2)判断是否满

3、足属性(3)画出关系图6偏序关系的关系图特点：(1)每个结点都有环(2)两个不同结点之间要么有且仅有一条边相连，要么没有边相连哈斯图(Hasse图)(1).用小圆圈或点表示A中的元素，省掉关系图中所有的自环。(2).如果x≤y,且x≠y，则结点x要画在结点y的下方。(3).如果x≤y,且在集A中不存在任何z∈A,使得z介于x与y之间，则x与y之间用一条直线连接。偏序关系的关系图：不能直观地反映出元素之间的次序，所以下面介绍另外一种图---哈斯图(Hasse图)。通过这个图，就能够清晰地反映出元素间的层次。下面介绍Hasse图。7例A={1,2,4,6},

4、≤表示整除关系，则≤是个偏序。2。。1。。64１。２。４。６。关系图哈斯图画法：一般先从最下层结点(全是射出的边与之相连)，逐层向上画，直到最上层结点(全是射入的边与之相连)。8例7.3.7A={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}。

5、>10偏序集中的特殊元素一.极小元与极大元设集合A上有一个偏序关系≤且设B是A的子集，则(1）如果存在一个元素b∈B且在B中找不到元素b’有b’≠b且b≤b’则称b是B的极小元.）（在B中没有比b更小的元素了，b就是极小元）（2）如果存在一个元素b∈B且中找不到元素b’有b’≠b且b’≤b，则称b是B的极大元.(在B中没有比b更大的元素了，b就是极大元)11举例给定,Hasse图如图所示：从Hasse图找极小(大)元：子集中处在最下(上)层的元素是极小(大)元。６。１。３。12。２。24。36。子集B极小元极大元{2,3}{1,

6、2,3}{6,12,24}C2,32,312,3624124,3612例：<Ｎ，

7、>是偏序集，Ａ＝｛２，３，４，５，６，７，８，９｝定理1：设是偏序集，B是A的非空有限子集，则B一定存在极大（小）元。则Ａ中极大元：８，６，９，５，７极小元：２，３，５，７13二.最小元与最大元（1）如果存在一个元素b∈B对每一个b’∈B均有b≤b’则称b是B的最小元(最小元b是B中元素，该元素比B中所有元素都小)（2）如果存在一个元素b∈B对每一个b’∈B均有b’≤b则称b是B的最大元(最大元b是B中元素，该元素比B中所有元素都大)举例，给定的Hass

8、e图如图所示：从Hasse图找最小(大)元：子集中如果只有唯一的极小(大)元，则这个极小(大)元，就是最小(大)元。否则就没有最小(大)元。下面介绍最小(大)元的唯一定理。６。１。３。12。２。24。36。子集B最小元最大元{2,3}{1,2,3}{6,12,24}C无无1无6241无14定理2：是偏序集，B是A的非空子集，如果B有最小元(最大元)，则最小元(最大元)是唯一的。证明：假设B有两个最小元x、y,则因为x是最小元，y∈B，根据最小元定义，有x≤y;类似地，因为y是最小元，x∈B，根据最小元定义，有y≤x。因为≤有反对称性，所以有x=

9、y。同理可证最大元的唯一性。小结：(A,≤)是偏序集，B是A的非空子集，则⑴B的