离散数学-次序关系.ppt

离散数学;7.2 等价关系 7.3 次序关系;次序关系;偏序关系;补充定义： x与y是可比较的： A,≤是偏序集，如果对x,y∈A，必有x≤y,或y≤x, 则称x与y是可比较的。 上例中1,2,4或1,2,6间是可比较的，而4与6间是不可比较的;例7.3.5 考虑任务集T，它包含了拍摄一张室内开启闪光灯的照片必须按顺序完成的任务。;偏序关系的关系图特点： (1) 每个结点都有环 (2) 两个不同结点之间要么有且仅有一条边相连，要么没有边相连;例 A={1,2,4,6}, ≤表示整除关系，则≤是个偏序。;例7.3.7 A={2,3,6,12,24,36}, ≤ 是A上整除关系。画出关系图及哈斯图。;课堂小测验： (1) D={1,2,3,5,6,10,15,30},≤ 是D上整除关系， 求D, ≤ Hasse图， （2）A={a,b,c} ，求P(A),?的Hasse图 ;偏序集中的特殊元素;举例给定C,≤,Hasse图如图所示： 从Hasse图找极小(大)元：子集中处在最下(上)层 的元素是极小(大)元。;例：Ｎ，|是偏序集， Ａ＝｛２，３，４，５，６，７，８，９｝;二.最小元与最大元 （1）如果存在一个元素b∈B对每一个b’∈B 均有b ≤ b’ 则称b是B的最小元 (最小元b是B中元素，该元素比B中所有元素都小) （2）如果存在一个元素b∈B对每一个b’∈B 均有b’ ≤ b 则称b是B的最大元 (最大元b是B中元素，该元素比B中所有元素都大) 举例，给定C,≤的Hasse图如图所示： 从Hasse图找最小(大)元：子集中如果只有唯一的极 小(大)元，则这个 极小(大)元，就是 最小(大)元。否则 就没有最小(大)元。 下面介绍最小(大)元的唯一定理。;定理2：A,≤是偏序集，B是A的非空子集，如果B有 最小元(最大元)，则最小元(最大元)是唯一的。 证明：假设B有两个最小元x、y,则 因为x是最小元，y∈B，根据最小元定义，有x≤y; 类似地，因为y是最小元，x∈B，根据最小元定义，有y≤x。因为≤有反对称性，所以有x=y。 同理可证最大元的唯一性。 小结：(A,≤)是偏序集，B是A的非空子集，则 ⑴B的极小(大)元总是存在的，就是子集中处在最下(上) 层的元素是极小(大)元。 ⑵如果有唯一的极小(大)元，则这个极小(大)元就是最小(大)元。否则就没有最小(大)元。;3.上界与下界 (Upper Bound and Lower Bound) (1)设A，≤是偏序集，B?A，若存在a∈A，使得 对 ?b∈B，b≤a,称a为B的上界。 （上界a是A中元素，该元素比B中所有元素都大) (2) 设A，≤是偏序集，B?A，若存在a∈A，使得 对 ?b∈B，a≤b,称a为B的下界。 （下界a是A中元素，该元素比B中所有元素都小) 举例，给定C,≤的Hasse图如图所示： 从Hasse图找上(下)界：注意是在A中找！;4. 最小上界(上确界)和最大下界(下确界) (Least Upper Bound and Greatest Lower Bound) 1： a是B的上界，并且对B的所有上界a’,都有a≤a’, 则称a是B的最小上界(上确界) 。 即若令C＝{a|a为B的上界}，则C的最小元为B的最小上 界或上确界. (即a是上界中最小的。如果B有上确界，则是唯一的) 2： a是B的下界，并且对B的所有下界a’,都有a’ ≤a 则称a是B的最大下界(下确界) 。 若令D＝{a|a为B的下界}，则称D的最大元为B的最大下 界或下确界. (即a是下界中最大的。如果B有下确界，则是唯一的);子集B; 求(1)B={{a,b}，{a,c}，{b,c}，{a}，{b}，{c},Ф};解答：设A＝{a,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}，下界、下确界都 是Ф。;非空子集极小(极大)元总是存在的。但极大元、极小元并不是唯一，且同一元素可以既是极大元又是极小元。如果有唯一的极小(大)元，则这个极小(大)元就是