回 帖 发 新 帖 刷新版面

主题:[讨论]离散数学中的全序和偏序

我正在学习数据结构,在其中学习有向无环图的时候遇到了离散数学中全序和偏序的概念,我看了很长时间还是没有弄明白,到底全序和偏序的定义是什么意思?希望知道的人向我讲解一下!

回复列表 (共2个回复)

沙发

偏序是由实数中的>=和<=抽象出来的
在一个集合F中定义一个比较关系, 这个关系不要求任意两个元素都能比较
这个关系可以任意定义,记为< , 但是定义的关系要满足以下3个条件
1) 任意a属于F,有a < a;               ...说明元素自己可以和自己比较
2) 如果a和b能比较 且a < b, b和c能比较,且 b < c
   那么a和c就能比较,且a < c          ...说明比较关系具有传递性
3) 如果a和b能比较,且a < b, b < a, 那么a = b 
你定义的这种满足以上3条公理的比较关系就叫偏序,和所在的集合记为( F, < )

全序首先是偏序,但是比偏序多一个要求:集合中的任意两个元素都是可比的

不知道我说清楚没有

板凳

如果一个定义在集合S上的关系R是自反的、反对称的和传递的,那么R就是一个S上的偏序关系

自反:   设a属于S,若有aRa,则R是自反的
反对称: 设a、b属于S,若aRb且bRa能推出a=b,则R是反对称的
传递:   设a、b、c属于S,若aRb且bRc能推出aRc,则R是传递的

例如实数集上的关系“>=”

我来回复

您尚未登录,请登录后再回复。点此登录或注册