偏序关系与偏序集PPT课件

1、偏序关系与偏序集偏序关系与偏序集1问题问题1 1：关系：关系具有哪些重要具有哪些重要性质？性质？自反性、对称性自反性、对称性/ /反反对称性、传递性对称性、传递性问题问题2 2：如果计算关系的闭包？：如果计算关系的闭包？自反闭包并上恒等关系、对称闭包并上逆关系、传递闭自反闭包并上恒等关系、对称闭包并上逆关系、传递闭包的包的WarshallWarshall算法算法问题问题3 3：什么是等价关系与等价类？什么是等价关系与等价类？等价关系：自反、对称、传递；具有等价关系的元素构等价关系：自反、对称、传递；具有等价关系的元素构成等价类；所有等价类的集合为商集，商集即划分成等价类；所有等价类的集合为商集

2、，商集即划分回顾回顾本节提要本节提要内容内容1 1：偏序关系：偏序关系与与偏序集偏序集内容内容2 2：偏序集中的特殊元素与偏序格：偏序集中的特殊元素与偏序格3偏序关系偏序关系(Partial Order)4偏序关系（续）偏序关系（续）5偏序集偏序集(poset)与哈斯图与哈斯图6()()()例例7例例8()()()()() () ()()()()()()()()()()()()() ()()()()()()例例9例例10哈斯图（哈斯图（Hasse Diagrams）11将偏序关系简化为哈斯图： 省略所有顶点上的环 省略所有因传递关系而引出的边 根据箭头的方向自下而上重排列所有顶点，而后将所有的

3、有向边替换为无向边例例12()()例例13例例14例例15例例16()() () () () () () () () ()本节提要本节提要内容内容1 1：偏序关系：偏序关系与与偏序集偏序集偏序关系：自反、反对称、传递；偏序集；哈斯图偏序关系：自反、反对称、传递；偏序集；哈斯图内容内容2 2：偏序集中的特殊元素与偏序格：偏序集中的特殊元素与偏序格17偏序集中的特殊偏序集中的特殊元素元素18()偏序集中的特殊偏序集中的特殊元素（续）元素（续）19()从哈斯图看特殊元素从哈斯图看特殊元素20从哈斯图看特殊元素（续）从哈斯图看特殊元素（续）21B2B1abdcefghabdcefghUpper bou

4、ndsLUBLower boundsUpper boundsGLB例例22()例例23()()()()()()例例24()() () ()()()()()偏序集与格偏序集与格n格格（latticelattice）作为一个代数系统可以通过两）作为一个代数系统可以通过两种方式进行定义：种方式进行定义： 通过偏序集与偏序关系定义通过偏序集与偏序关系定义 通过普通集合与特殊运算定义通过普通集合与特殊运算定义n本讲我们仅从偏序的角度去定义格，并研本讲我们仅从偏序的角度去定义格，并研究其中的若干基本运算究其中的若干基本运算25偏序集与偏序集与格格（续）（续）格作为偏序集的定义：格作为偏序集的定义：26()偏序集与偏序集与格格（续）（续）27()()()()例例28()()格的对偶原理格的对偶原理29格的格的对偶原理对偶原理（续）（续）30本节小结本节小结内容内容1 1：偏序关系：偏序关系与与偏序集偏序集偏序关系：自反、反对称、传递；偏序集；哈斯图偏序关系：自反、反对称、传递；偏序集；哈斯图内容内容2 2：偏序集：偏序集中的特殊中的特殊元素与偏序格元素与偏序格最大元、最小元、极小元、极大元；上届、上确界、最大元、最小元、极小元、极