下载文档原格式
离散数学偏序关系第9讲定义9.1设R为非空集合A上的关系, 如果R是自反的、反对称的和传递的, 则称R为A上的偏序关系。
简称偏序, 记作≼。
设≼为偏序关系。
如果<x,y > ∈ ≼, 则记作x≼y, 读作“x小于等于y”。
意即：依据这个序，x排在y的前面或x就是y。
定义9.2设R是非空集合A上的偏序关系，定义(1) ∀x,y∈ A, x与y可比⇔x ≼y ∨ y ≼x。
(2)∀x,y∈ A, x ≺y ⇔x ≼y ∧ x≠y。
其中x≺y读作“x小于y”。
由上面定义可知，在具有偏序关系≼的集合A中任取两个元素x和y，可能有下述几种情况发生：x与y不可比；x≺y；y≺x；x=y。
定义9.3集合A和A上的偏序关系≼一起叫做偏序集，记作<A, ≼>。
利用偏序关系的自反性，反对称性和传递性可以简化一个偏序关系的关系图，得到偏序集的哈斯图。
我们需要下面覆盖的定义。
定义9.4设<A, ≼> 是偏序集， x,y∈ A ，如果x≺y且不存在z ∈ A使得x≺z≺y ，则称y覆盖x。
例子例9.1<A,≼>是偏序集,其中A＝{1,2,3,4,5}, ≼是整除关系。
解: 对任意x∈A都有1≼x,所以1和1,2,3,4,5都是可比的,但是2不能整除3,3也不能整除2,所以2和3是不可比的。
对于1和2来说,1≺2,并且不存在z∈A使得1整除z并且z整除2,所以,2覆盖1。
同样,4覆盖2,但4不覆盖1,因为有1≺2≺4成立。
如果x与y不可比,则一定不会有x覆盖y或y覆盖x。
哈斯图——关系图的简化哈斯图的画法1在关系图中去掉所有的自环。
2若y覆盖x，则保留从x到y的边，其它的边全去掉。
3若y覆盖x，将x放在下方，y放在上方，去掉边上的方向。
这一点是能做到的，因为偏序关系的关系图中无有向圈。
例子画出<{1,2,…,12},R 整除>和<P({a,b,c}), R >的哈斯图.例9.2179361211510248<{1,2,…,12},R 整除>{a}{b}{c}{b,c}{a,c}{a,b,c}{a,b}∅<P({a,b,c}), R >⊆⊆基本概念定义9.5设<A,≼>为偏序集,B ⊆A .①y∈B, y是B 的最小元: 若∀x(x∈B→y ≼x)成立。
4.6偏序关系偏序关系：同时具有自反、反对称和传递性4.6 偏序关系定义4.21设R为非空集合A上的一个二元关系，如果R是自反的、反对称的和传递的，则称R为A上的偏序关系，记作≤。
设≤是偏序关系，若<x, y>∈≤，则记作x≤y，读作x“小于或等于”y。
集合A与A上的偏序关系≤一起组成的有序对<A, ≤>叫做偏序集。
如以下关系都是偏序关系：（1）非空集合A上的恒等关系I A。
（2）实数集R上的“≤”、“≥”关系。
4.6 偏序关系定义4.22设<A, ≤>为偏序集，定义（1）∀x, y∈A，x < y ⇔x ≤ y ∧x≠y，x<y读作x“小于”y，这里所说的“小于”是指在偏序中x排在y的前边。
（2）∀x, y∈A，x与y可比⇔x ≤y ∨y ≤x例如，<A, ≤>是偏序集，其中A＝{1, 2, 3, 4, 5}，是A上的整除关系，则有（1）1<2<4，1<3等。
（2）1=1，2=2，3=3等。
（3）2与3是不可比的。
4.6 偏序关系Sed ut perspiciatis unde omnis.68%设<A, ≤>为偏序集，若∀x, y ∈A ，x 与y 都是可比的，则称≤为A 上的全序关系（或线序关系）。
且称<A, ≤ >为全序集。
例如，集合A = {1, 2, 3, 4, 5}上的（1）“小于等于”关系是全序关系，因为任何两个数总是可比大小的。
（2）“整除关系”不是全序关系，因为2与3是不可比的。
定义4.234.6 偏序关系定义4.24设<A, ≤ >为偏序集，对于任意的x, y∈A，如果x < y并且不存在z∈A使得x<z<y，则称y盖住x。
作为集合A上的一个二元关系，盖住关系COV A可表示为：COV A={<x, y> | x, y∈A∧y盖住x}根据定义4.24，∀<x, y>，<x, y>∈COV A⇔y盖住x⇒x ≤ y⇔<x, y>∈ ≤所以COV A ⊆≤。
●定义：集合S上的关系R，如果它是自反的，反对称的和传递的，就称为偏序。
集合S与偏序R一起叫做偏序集，记做(S, R)●例子：●1、整数集合上的“大于或等于”关系●2、正整数集合上的整除关系●3、集合S的幂集合上的包含关系●符号：●通常用≼表示偏序关系,读作“小于等于”●<x,y>∈R ⇔ xRy ⇔ x≼y●使用这个记号是由于“小于或等于”关系是偏序关系的范例。
●“严格小于”: x≺y ⇔ x≼y ∧x≠y●当a与b是偏序关系（S, ≤）的元素时，不一定有a ≤b或b ≤a。
●定义2：偏序集（S, ≤）的元素a和b叫做可比的，如果a ≤b或b ≤a。
当a和b是S的元素且没有a ≤b，也没有b ≤a，则称a和b是不可比的。
●极大元素：偏序集的一个元素，它不小于这个偏序集的任何其他元素●极小元素：偏序集的一个元素，它不大于这个偏序集的任何其他元素●最大元素：偏序集的一个元素，它大于这个偏序集的所有其他元素●最小元素：偏序集的一个元素，它小于这个偏序集的所有其他元素设<S,≼>为偏序集, A⊆S, u,l∈A●上界(upper bound):u是A的上界⇔∀x( x∈A → x≼u )●下界(lower bound):l是A的下界⇔∀x( x∈A → l≼x )●例：<S,|>, S={1,2,3,4,5,6,9,10,15}●A1={1,2,3}, A2={3,5,15}, A3=S.●A1的上界是{6}, A1的下界是{1}●A2的上界是{15}, A2的下界是{1}●A3的上界集合的最小上界：集合的一个上界，它小于所有其他的上界●集合的最大下界：集合的一个下界，它大于所有其他的下界是{}, A3的下界I A R R∩I A=R=R R∩R-1 I A R R R最小元与极小元是不一样的。
最小元是B中最小的元素，它与B中其它元素都可比；而极小元不一定与B中元素可比，只要没有比它小的元素，它就是极小元。
偏序关系的定义偏序关系是集合上的一种二元关系，它是指集合中的元素之间存在一种偏序关系，即可以进行比较。
在偏序关系中，元素之间的比较是部分有序的，不存在全序或完全有序的情况。
偏序关系的定义和性质对于数学、计算机科学等领域有着重要的意义。
在偏序关系中，我们可以通过比较两个元素的大小来确定它们之间的关系。
假设有一个集合A，其中的元素a和b，若a小于等于b，则可以表示为a≤b。
偏序关系具有以下几个基本性质：1. 反自反性：对于任意的元素a，总有a≤a成立。
这意味着每个元素与自身之间存在一种偏序关系。
2. 反对称性：对于任意的元素a和b，若a≤b且b≤a成立，则a和b相等。
这意味着两个元素之间的偏序关系是互相排斥的。
3. 传递性：对于任意的元素a、b和c，若a≤b且b≤c成立，则a≤c 也成立。
这意味着偏序关系是具有传递性的。
在偏序关系中，元素之间可以存在不可比较的情况。
即存在两个元素a和b，既不满足a≤b，也不满足b≤a，这时称a和b是不可比较的。
偏序关系中的不可比较性是其与全序关系的一个重要区别。
举个简单的例子来说明偏序关系的概念。
假设有一个集合A，其中包含了一些人的年龄。
我们可以通过比较两个人的年龄来确定它们之间的偏序关系。
假设A={1, 2, 3, 4, 5}，其中的元素表示不同人的年龄。
在这个集合中，我们可以观察到以下的偏序关系：1≤2≤3≤4≤5根据这个偏序关系，我们可以得出结论：1岁的人小于等于2岁的人，2岁的人小于等于3岁的人，以此类推。
但是，我们无法比较不同年龄的人之间的大小关系，比如无法确定3岁的人和5岁的人之间的偏序关系。
在实际应用中，偏序关系有着广泛的应用。
比如在排序算法中，可以利用偏序关系对元素进行排序；在图论中，偏序关系可以用来描述有向图中节点的依赖关系；在关系数据库中，偏序关系可以用来定义关系的主键和外键等。
偏序关系是集合上的一种二元关系，它具有反自反性、反对称性和传递性等基本性质。
第五章序关系和结构5.1 Partially ordered sets(偏序集)集合的元素之间除了等价关系、函数关系之外，还有很重要的次序关系：“先后”关系。
如“先乘除，后加减”，“串行”与“并行”。
本节将讨论偏序关系和偏序集的基本概念和性质）定义5.1.1 (设A为集合，R⊆A×A，若R是自反的、反对称的和传递的，则称R是A上的偏序关系，并称(A, R)为偏序集)[例5.1.1] (1) Z，R上的“≤”、“≥”，Z+上的整除和倍数关系是偏序关系；(2) 设A为任一集合，则(P(A), ⊆)为一偏序集；(3) 但Z，R上的“〈”、“〉”不是偏序关系。
定义5.1.2 Let R be a partial order on a set A, and let R1- be the inverse relation of R. Then R1- is also a partial order and the poset (A,R1-) is called the dual(对偶) of the poset (A,R), and the partial order R1- is called the dual(对偶) of thepartial order.注：由于集合中的偏序关系是Z，R上的“≤”、“≥”的推广，故常用“≤”表示一般的偏序关系，偏序集用(A, ≤)表示，用≥表示偏序关系≤的对偶偏序关系。
Note that the symbol ≤ is being used to denote the distinct partial orders.具体理解时，我们应该从具体定义或上下文中了解这些偏序关系的意义。
定义5.1.3 The elements a and b of a poset (A,≤) are called comparable if either a≤b or b≤a. Otherwise we call a and b incomparable.(设≤是集合A上的偏序关系，a,b∈A。
偏序关系整理●定义：集合S上的关系R，如果它是自反的，反对称的和传递的，就称为偏序。
集合S与偏序R一起叫做偏序集，记做(S, R)●例子：●1、整数集合上的“大于或等于”关系●2、正整数集合上的整除关系●3、集合S的幂集合上的包含关系●符号：●通常用?表示偏序关系,读作“小于等于”●∈R ? xRy ? x?y●使用这个记号是由于“小于或等于”关系是偏序关系的范例。
●“严格小于”: x?y ? x?y ∧x≠y●当a与b是偏序关系（S, ≤）的元素时，不一定有a ≤b或b ≤a。
●定义2：偏序集（S, ≤）的元素a和b叫做可比的，如果a ≤b 或b ≤a。
当a和b是S的元素且没有a ≤b，也没有b ≤a，则称a和b是不可比的。
●极大元素：偏序集的一个元素，它不小于这个偏序集的任何其他元素●极小元素：偏序集的一个元素，它不大于这个偏序集的任何其他元素●最大元素：偏序集的一个元素，它大于这个偏序集的所有其他元素●最小元素：偏序集的一个元素，它小于这个偏序集的所有其他元素设为偏序集, A?S, u,l∈A●上界(upper bound):u是A的上界??x( x∈A → x?u )●下界(lower bound):l是A的下界??x( x∈A → l?x )●例：, S={1,2,3,4,5,6,9,10,15}●A1={1,2,3}, A2={3,5,15}, A3=S.●A1的上界是{6}, A1的下界是{1}●A2的上界是{15}, A2的下界是{1}●A3的上界集合的最小上界：集合的一个上界，它小于所有其他的上界●集合的最大下界：集合的一个下界，它大于所有其他的下界是{}, A3的下界I A R R∩I A=R=R R∩R-1 I A R R R最小元与极小元是不一样的。
最小元是B中最小的元素，它与B 中其它元素都可比；而极小元不一定与B中元素可比，只要没有比它小的元素，它就是极小元。
对于有穷集B，极小元一定存在，但最小元不一定存在。
