下载文档原格式
偏序关系整理●定义：集合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，极小元一定存在，但最小元不一定存在。
偏序关系与偏序集定义1 设R为非空集合A上的关系。
如果R是自反的、反对称的和传递的，则称R 为A 上的半序(偏序)关系，记为≼。
对一个偏序关系≼，如果<x, y> ≼，则记为x ≼y。
注：1. 集合A上的恒等关系IA是A上的偏序关系，但空关系和全域关系EA 一般不是A上的偏序关系。
2. 实数域上的小于等于关系（大于等于关系），自然数域上的整除关系，集合的包含关系等都是偏序关系。
定义2 设R为非空集合A上的偏序关系，定义(1) x, y A, x ≺y当且仅当x ≼y且x≠y(2) x, y A, x 与y 可比当且仅当x ≼y 或y ≼x注：在具有偏序关系的集合A中任二元素x 和y 之间必有下列四种情形之一：x ≺y ，y ≺x ，x=y ，x 与y 不可比。
例设A={1, 2, 3}(1) ≼是A上的整除关系，则：1 ≺2, 1 ≺3, 1＝1, 2＝2, 3＝3，2 和3 不可比；(2)≼是A 上的大于等于关系，则: 2 ≺1, 3 ≺1, 3 ≺2, 1＝1, 2＝2，3＝3。
定义3 设R为非空集合A上的偏序关系，如果 x, y A, x 与y 都是可比的, 则称R为A上的全序关系。
例如大于等于关系（小于等于关系）是全序集，但整除关系一般不是全序集。
定义4 带有某种指定的偏序关系≼的集合A称为偏序集，记为<A, ≼>.例如整数集Z和数的小于等于关系≤构成偏序集<Z, ≼>;集合A的幂集P(A)和集合的包含关系 构成偏序集<P(A), >.定义5 设<A, ≼> 为偏序集， x, y A, 如果x ≺y且不存在z A, 使得x ≺z ≺y, 则称y 覆盖x。
例如A={1, 2, 4, 6}上的整除关系，有2覆盖1，4和6都覆盖2，但4不覆盖1,6不覆盖4。
哈斯图利用偏序关系的自反性、反对称性和传递性可简化偏序关系的关系图，得到偏序集的哈斯图。
等价关系和偏序关系等价关系和偏序关系是数学中常见的两种关系，它们在数学领域和其他学科中都具有重要的应用价值。
本文将从定义、性质和应用等方面，对等价关系和偏序关系进行详细介绍，并希望能够给读者提供一些指导意义。
首先，我们来介绍等价关系。
等价关系是指集合中的元素之间存在一种对等的关系，它可以将集合划分成若干个等价类。
在等价关系中，具有相同特征或性质的元素被划分到同一个等价类中，而具有不同特征或性质的元素则被划分到不同的等价类中。
换句话说，等价关系将集合中的元素划分为互不相交的子集，每个子集都代表一个等价类。
等价关系具有以下性质：1. 自反性：对于任意元素 a，a 和 a 相关。
2. 对称性：如果 a 和 b 相关，则 b 和 a 相关。
3. 传递性：如果 a 和 b 相关，b 和 c 相关，则 a 和 c 相关。
等价关系在数学中有广泛的应用，例如在代数、几何和数论等领域。
在代数中，等价关系可以帮助我们定义等价类，进而对集合进行分类和研究。
在几何中，等价关系可以帮助我们研究和描述图形的对称性质。
在数论中，等价关系可以帮助我们解决一些重要的数学问题，如素数分布等。
接下来，我们来介绍偏序关系。
偏序关系是指集合中的元素之间存在一种偏序的关系，它可以将集合中的元素按照某种方式进行排序。
在偏序关系中，元素的排列顺序可能是不确定的，即两个元素之间可能不存在比较关系。
与等价关系不同，偏序关系不能将集合划分为互不相交的子集，而是通过排序来比较元素之间的关系。
偏序关系具有以下性质：1. 反自反性：对于任意元素 a，a 和 a 不相关。
2. 反对称性：如果 a 和 b 相关且 b 和 a 相关，则 a 和 b 是相同的元素。
3. 传递性：如果 a 和 b 相关，b 和 c 相关，则 a 和 c 相关。
偏序关系在数学中也有广泛的应用，特别是在集合论、拓扑学、优化理论和离散数学等领域。
在集合论中，偏序关系可以帮助我们定义集合的包含关系和子集关系。
9.6偏序关系9.6偏序关系(Partial Order)偏序(Partial Order)定义:偏序(Partial order)：定义在A上的集合R是偏序关系iff(当且仅当)其具有以下性质:1. ⾃反性(reflexive)2. 反对称性(antisymmetric)3. 传递性(transtive)NOTE: R记作≼，注意这⾥的≼不必是指⼀般意义上的“⼩于或等于”,若有x≼y，我们也说x排在y前⾯（x precedes y).偏序集(Partially ordered set)/(或简写为poset): 集合A及定义在其上的偏序关系R⼀起称为偏序集，记作(A, R)，A中的元素也称为偏序集中的元素.线序/全序(Linear Order)如果(A, ≤)是⼀个偏序集(poset)，那么对于其中的元素a和b,1. a≤b 或者 b≤a,那么称为可⽐的(Comparable)2. 即不存在a≤b，也不存在b≤a,那么称为不可⽐的(Imcomparable)如果偏序集A中每对元素(every pair of elements)都是可⽐的，那么我们就称A是线序集合(linearly ordered set)或全序集合(totally ordered set),称偏序关系R为线序或全序关系(linear order). 我们也称A为链(chain).良序集(Well-ordered set)定义:设集合(S,≤)为⼀全序集，≤是其全序关系，若对任意的S的⾮空⼦集，在其序下都有最⼩元素，则称≤为良序关系，(S,≤)为良序集。
拟序(Quasiorder)定义:定义在A上的关系R是拟序关系iff其具有以下关系1. 反⾃反性(irreflexive)2. 传递性(transitive)NOTE:满⾜反对称性的拟序关系就称为偏序关系乘积偏序(Product Partial Order)如果(A, ≤)和(B, ≤)都是偏序集，那么他们的笛卡尔积也是个偏序集，其偏序关系≤被定义为:如果在A中有a ≤ a'，在B中有b ≤ b'，那么(a, b) ≤ (a', b')词典顺序(Lexicographic Order)对于⼀个乘积偏序，(a, b) ＜ (a', b')在a ＜ a'(或a == a'并且b ＜ b')时成⽴那么我们称其为词典顺序(Lexicographic Order)或字典序(“dictionary” order)哈斯图(Hasse Diagram)哈斯图是有限集A上的偏序图，并且:删除了所有的⾃环(self-cycles)消除了由传递性⽣成的边⾃底向上的制图设(S, ≤)是⼀个poset. 若x＜y且不存在元素z∈S，使得x＜z＜y，则称y∈S覆盖x∈S.⽽y覆盖x的有序对(x, y)的集合也称为(S, ≤)的覆盖关系.可以看出，(S, ≤)的哈斯图的边与其覆盖关系是⼀⼀对应的.同构(Isomorphism)对应原理(Principle of Correspondence)两个有限同构偏序集必定具有相同的Hasse图.拓扑排序(Topological Sorting)极⼤元(maximal element)和极⼩元(minimal element)定义:偏序集中的⼀个元素称为极⼤(⼩)元，当它不⼩(⼤)于这个偏序集中的任何其他元素, 利⽤哈斯图很容易判别它们就是图中的"顶"("底")元素极⼤(⼩)元⼀定存在，且可能是不唯⼀的最⼤元(greatest element)和最⼩元(least element)定义:如果在偏序集中存在⼀个元素⼤(⼩)于任何其他的元素，那么称这样的元素为最⼤(⼩)元最⼤(⼩)元可能不存在，若存在则唯⼀最⼩上界(least upper bound)和最⼤上界(greatest lower bound)定义:如果存在⼀个元素u(l)∈S，使得对于偏序集(S, ≤)的⼦集A中的所有元素a，有a≼u(l≼a)，那么称u(l)为A的⼀个上(下)界，如果u(l)是所有上(下)界中最⼩(⼤)的，就叫最⼩上界(LUB)(最⼤下界(GLB))上界的最⼩元就叫最⼩上界；下界的最⼤元叫最⼤下界(Topological Sorting)定义:对⼀个有向⽆环图DAG(Directed Acyclic Graph)G进⾏拓扑排序，是将G中所有顶点排成⼀个线性序列，使得图中任意⼀对顶点u 和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。
离散数学偏序关系第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)成立。
