《(34)--3.9 什么是偏序关系.ppt》由会员分享，可在线阅读，更多相关《(34)--3.9 什么是偏序关系.ppt（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、什么是偏序关系偏序关系：偏序关系：A上的关系上的关系R是是自反自反的、的、反对称反对称的和的和传递传递的，的，则称则称R为偏序关系。记作为偏序关系。记作若若 偏序关系偏序关系，则可记作，则可记作xy。（读作：（读作：x小于等于小于等于y，但不是指但不是指数数的大小。的大小。）偏偏 序序 集：集：一个集合一个集合A与与A上的偏序关系上的偏序关系R一起叫作偏序集。记作一起叫作偏序集。记作。例如例如：集合：集合A上的恒等关系，幂集上的恒等关系，幂集P(A)上的包含关系，有理数集上的小于等上的包含关系，有理数集上的小于等于关系，正整数集上的整除关系都是偏序关系，分别记作偏序集于关系，正整数集上的整除关
2、系都是偏序关系，分别记作偏序集，。偏序关系的概念 (3)对任意对任意 R，R有有xy yz，则，则xz，于是于是 R，所以，所以R是是传递传递的。的。例例：设设A=1,2,3，A上关系上关系R是通常意义下的小于或等于关系，是通常意义下的小于或等于关系，试写出试写出R并验证它是偏序关系。并验证它是偏序关系。解解：R=,(1)因因,均属于均属于R，所以，所以R是是自反自反的。的。(2)对任意对任意 R有有xy，当，当x y时时 R，所以所以R是是反对称反对称的。的。偏序关系的概念对于偏序集对于偏序集，例如：例如：A 1,2,3,4,5,为整除关系，为整除关系，为偏序集。对任意的为偏序集。对任意的x
3、 A，1 x，所以，所以1与与1,2,3,4,5 都是可比的，但都是可比的，但2与与3就不可比，因为就不可比，因为2不能整除不能整除3，3也不能整除也不能整除2。对于。对于1 2，因为，因为1 2 且不存在且不存在z A，使，使1 z 2，所以，所以2盖住盖住1，同理，同理，4盖住盖住2，但，但4不盖住不盖住1，因为，因为1 2 4。(1)如果对任意如果对任意x,y A，或者，或者xy 或者或者yx成立，则称成立，则称x 与与y 可比可比。(2)如果如果x y且不存在且不存在z A，使，使(x z)(z y)，则称，则称y 盖住盖住 x。偏序关系的概念全序关系：全序关系：偏序集偏序集，若对任意
4、的，若对任意的x,y A，都有都有x 与与y 可比，则称可比，则称为为A上的全序关系。上的全序关系。且称且称为全序集。为全序集。偏序关系的概念例如：设 A 1,2,3,4,5，是全序集，不是全序集。偏序集偏序集的哈斯图（的哈斯图（Hasse）：）：特别地，全序集的哈斯图是一条直线。特别地，全序集的哈斯图是一条直线。(1)用小圆圈分别表示用小圆圈分别表示A的每一个元素的每一个元素(称为结点称为结点)。(2)按每个元素在偏序中的次序从底向上排列结点位置。按每个元素在偏序中的次序从底向上排列结点位置。(若若xy，则结点，则结点x排在结点排在结点y下方。下方。)(3)如果如果y盖住盖住x，则在，则在x 和和y 之间连一条线。之间连一条线。哈斯图例：画出例：画出和和的哈斯图。的哈斯图。912 846102513711acba,bb,ca,ca,b,c偏序关系的概念画哈斯图的基本步骤：（1）用圆圈代表元素，首先去掉每个元素的环；（2）确定偏序集中的极小元，并将极小元放在哈斯图的最底层；（3）如果y盖住x且xy，则将y所代表元素放在x所代表元素之上；（注意：把盖住元素较多的节点放在中间，将只盖住一个元素的节点放在两边，以减少连线的交叉。）（4）将相邻两层的节点，根据盖住关系进行连线。偏序关系的概念THANK YOU