当前位置：文档之家 › 偏序关系

偏序关系

  • 格式：pptx
  • 大小：582.32 KB
  • 文档页数：15

下载文档原格式

  / 15

合集下载

第8节 偏序关系分析

第8节 偏序关系分析

6/20
集合论 与图论
哈斯(Hasse)图
首先偏序关系≤是自反的，所以偏序关系的关系图 中每个顶点都有一个环，因此可以省略每个顶点的环。
其次由于偏序关系是传递的，那么只要在前驱与 后继间联线即可。
最后由于反对称性，若x<y，xy，则点y画在x 的上方，这样就不必用矢线了，按上述方法画出的图 称为(X,≤)的哈斯图。
的每一个也只与这两个小伙中的一个跳过舞。
18/20
集合论 与图论
毕业舞会问题
不失一般性，不妨设有m个小伙，n个姑娘，分 别用集合B、G表示:
B={b1, b2, …, bm}， G={g1, g2, …, gn}.
令 Di={gk |与小伙子bi 跳过舞的姑娘gk, k=1, 2, …, n}， i=1, 2, …, m. 则有
A中有最大元素和最小元素吗？
A中没有最大元素也没有最小元素。 因为24与36不可比，2与3也不可比。
但是A中没有比24和36更大的元素，也没有比2与 3更小的元素。
称24和36都是极大元素,2与3都是极小论
极大元素与极小元素的定义
定义8 设(X,≤)是一个偏序集，AX，A中元素s称为 A的极大元素，如果A中没有元素m使得ms且s≤m。
已知每个小伙子至少与一个姑娘跳过舞，但未能与 所有姑娘跳过，所以
Di≠，1≤| Di | ≤ n-1，i=1, 2, …, m.
同样地，每个姑娘也至少与一个小伙子跳舞，但也
未能与所有的小伙子跳过舞，所以
D1∩D2∩… ∩Dm=.
19/20
集合论 与图论
毕业舞会问题
方法一：若存在 Di∩Dj=，则问题得证。 若不存在 Di∩Dj=，则……
17/20

9.6偏序关系

9.6偏序关系

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之前。

36偏序关系

36偏序关系

3.6.2字典序 字典序 A1×A2×…×An上的字典序： n个偏序集（A1，≤），（A2，≤），…，（An，≤） 在A1×A2×…×An上定义偏序关系： (a1,a2,…,an)<(b1,b2,…,bn)⇔∃i，1≤i≤n-1，使 a1=b1,a2=b2,…,ai=bi,且ai+1<bi+1 串上的字典序： 偏序集（S，≤），a1a2…am、b1b2…bn是S上的串， t=min(m,n) a1a2…am<b1b2…bn⇔(a1,a2,…,at)<(b1,b2,…,bt)或 (a1,a2,…,at)=(b1,b2,…,bt),且m<n
图3-11 三个偏序集 的哈斯图
例 21 偏序集(Z+,|)是格吗？ 解 设a和b是两个正整数。这两个整数的最小下界和最 大下界分别是他们的最小公倍数和最大公约数，读者应能 验证这一点。因此这个偏序集是格。 例 22 确定偏序集({1,2,3,4,5},|)和({1,2,4,8,16},|)是否为格. 解 因为2和3在({1,2,3,4,5},|)中没有上界，它们当然没 有最小上界，因此第一个偏序集不是格。 第二个偏序集的每两个元素都有最小上界和最大下界。 在这个偏序集中两个元素的最小上界是他们中间较大的元 素，而两个元素的最大下界是它们间较小的元素，读者 应能验证这一点。因此第二个偏序集是格。 例 确定(P(S), ⊆)是否是格，其中S是集合。 解 设A和B是S的两个子集。A和B的最小上界和最大下界分 别是A∪B和A∩B，因此(P(S), ⊆)是格。
上界： 上界：A⊆S，a∈S ， 若∀x∈A，x≤a，则称a是A的上界 下界： 下界：A⊆S，a∈S ， 若∀x∈A，a≤x，则称a是A的下界 例 17 找出在图3-10所示哈斯图的偏序集的子集 ｛a,b,c｝,{j,h}和｛a,c,d,f｝的下界和上界。 解 ｛a,b,c｝的上界是e,f,j和h，它的唯一的下界是a。{j,h} 没有上界，它的下界是a,b,c,d,e和f。{a,c,d,f}的上界是f， h和j，它的下界是a。

集合论--第9讲偏序关系

集合论--第9讲偏序关系

离散数学偏序关系第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中元素可比，只要没有比它小的元素，它就是极小元。

偏序关系



良序 全序 偏序 偏序/全序/良序的逆关系是否仍为偏序/全序/良序？ 良序的逆关系不一定是良序

例如(N， )
链与反链

链与反链


设C是偏序集(P,≼)的一个子集
如果C中任何两个元素均可比，则C构成一个链 如果C中任何两个元素均不可比，则B构成一个反链
链与反链（示例）
a
元素个数最多的反链，含k个元素


注：覆盖P的链数 P中任一反链的元素个数.
等价结论:有限偏序集中存在一个链覆盖和一个反链，它们 大小相等
Dilworth定理的归纳证明

证明. 按照P中元素个数（|P|=1, 2 …）进行归纳证明. 设a为P中的一个极大元素, P’ =P-{a} 设(P’,≼)有一个大小为k的反链{a1, a2, …, ak}，并有一个规模 为k的链覆盖{C1, C2, …, Ck}. 对任意Ci , P’中大小为k的任一反链均有唯一的元素属于Ci， 这些元素有一个最大元，记为xi. A={x1, x2, …, xk}必是反链。否则，不妨假设A中有两个元素 xi≼ xj. 根据xj的定义，P’中必有一个大小为k的反链Aj, xj是Aj 和Cj的公共元素，假设y是Aj和Ci的公共元素，则y≼ xi. 从而 y≼ xj.与Aj是反链矛盾.
离散数学集合论南京大学计算机科学与技术系极大小元最大小元格及其性质partialorder给定有限字符集合若在上有一个偏序关系类似上述办法可以对任意正整数k定义由中字符构成的长度为k的串的集合上的偏序关系
偏序关系
离散数学－关系
南京大学计算机科学与技术系
内容提要

偏序与全序


哈斯图

《离散数学课件》7偏序关系


例 找出极大、极小元与最大、最小元
极小：1 极大：5，6，7，8，9 最小：1 最大：无
极小：φ
极大：{a，b，c}
最小：φ
最大：{a，b，c}
3、上界、下界
设(A，≺)是一个偏序集， BA, yA。
若x(x∈B→x≼y) 成立, 则称 y 为B的上界 若x(x∈B→y≼x) 成立, 则称 y 为B的下界
d c
e b
a
特点： 每个结点没有环， 两个连通的结点之间的有序关系通
过结点位置的高低表示，位置低的元素 的顺序在前，具有覆盖关系的两个结点 之间连边。
哈斯图实例
例 <{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }, R整除> <P({a, b, c}), R>
例 试画出哈斯图
设A={ {1}, {2}, {3}, {4}, {1,2}, {1,5}, {3,6},
d c b
a
({ a, b, c, d }, ≺) 链
({ a, d, e }, ≺) 链
e ({ b, e }, ≺)
反链
({ c, e }, ≺) 反链
全序集
设(A，≺)是一个偏序集， 如果它本身就是一条链， 那么称之为全序集，并称≺ 为全序关系。
例 A={ a, b, c, d, e} d c e b
R={(1,1), (2,2), (3,3), (4,4),
(1,2), (1,3), (1,4), (2,4)}
R是A上一个偏序关系。
例2 (p109)
设Z+={n∊Z│n>0}，即Z+是正整数的集合。 在Z+上定义一个二元关系R如下: 对于任意的x,y∊Z+，

偏序关系


一、偏序关系
（2） 偏序集 ＜A, R 意指在一个集合 A 中给定于一 个序列关系。若 x, y A且xy ，我们就说 y 在 x 的 后面或 x 在 y 的前面或 x 包含在 y 中。 例 1：说明实数集 R 上的小于等于关系是偏序 关系，即 R, ；任意集合 S 的幂集上的包含 关系是偏序关系,即 P(S ),
一、偏序关系 定义 4-24 设偏序集<A, >，如果对于 A 中任意
两个元素 a, b A ,必有 a b 或 b a ，则称 是 A

上的全序关系。称 A, 为全序集。 例如，实数集 R 上的小于等于关系就是全序关 系。但是，整数集 Z 上的整除关系就不是全序 关系。
一、偏序关系
例 4-2 设 A {2,3,4,5,6,12,24,30} ， R 是 A 上 的整除关系， R { x, y x y} ，证明 R 是偏序 关系。 定义 4-23 对于集合 A 上的偏序关系 R ，如果 A 中两个 a ， b ，有 aRb ,则称 a 与 b 是可比较 的。
二、哈斯图
偏序集 A, 可以通过哈斯图表示，它是对关系图的

简化。 （1）由于偏序关系是自反的，即对每个元素 a ，都有 aRa ，因此在图上省去自环。 （2）由于偏序关系是传递的，即若有 aRb 和 bRc ，则 必有 aRc ，因此在图中省去 a 与 c 之间的连线。 （3）对于 aRb ，规定 b 在 a 的上方，则可省去箭头。 这样的图称为哈斯图。
4.上确界和下确界
注：一个子集 B 的上界和下界未必存在，也未必唯一，上 确界和下确界也未必存在。若上（下）确界存在，则必是 唯一的，上（下）确界的符号分别是 sup 与inf 。 例 设 集 合 A {1,2,3,4,5} ， A 上 的 二 元 关 系 R 为

fldr离散数学

fldr是一个在离散数学中常见的概念，通常指的是一个偏序关系（Partial Order Relation）。

在离散数学中，偏序关系是一种特殊的关系，它满足部分有序性（即关系中的任意两个元素至少有一个是另一个的子集）。

fldr的应用范围非常广泛，可以用于描述许多现实世界中的概念和结构。

首先，让我们了解一下偏序关系的基本概念。

在偏序关系中，元素之间存在一种层次关系，即一个元素可以位于另一个元素的上方或下方。

这种关系通常用箭头表示，其中上方元素用实线表示，下方元素用虚线表示。

偏序关系是一种弱化的有序关系，因为它只考虑了元素之间的相对位置，而没有考虑它们之间的完全有序性。

对于fldr这个概念，我们可以将其解释为一种特定的偏序关系，其中"d"元素可以被视为"f"元素的父元素或子元素，"r"元素则处于这两个元素之间。

因此，"fldr"表示的是一个由元素"f"、"d"和"r"组成的有序集合，其中"d"和"f"之间的元素都是"r"，且"r"既不是"f"的父元素也不是"d"的子元素。

fldr在离散数学中有许多应用。

首先，它可以用于描述一些现实世界中的概念和结构，例如家族、等级体系等。

在某些问题中，我们需要对这些结构进行排序或分类，这时fldr就非常有用。

例如，我们可以使用fldr来描述一个人从孩子到成年人的成长过程，或者描述一种物质的组成元素和化学成分的关系。

另外，fldr在证明逻辑推理、公理系统等逻辑结构中也发挥着重要作用。

例如，在某些公理系统中，我们需要对某些对象进行排序或分类，这时fldr就可以作为一种有效的工具来帮助我们进行推理和证明。

除此之外，fldr还可以用于解决一些组合优化问题。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
4.6 偏序关系
偏序关系：同时具有自反、反对称和传递性
4.6 偏序关系
定义4.21
设R为非空集合A 上的一个二元关系，如果R是自反的、反对 称的和传递的，则称R为A 上的偏序关系，记作≤。设≤是 偏序关系，若<x, y>≤，则记作x≤y，读作x“小于或等 于”y。集合A 与A 上的偏序关系≤一起组成的有序对<A, ≤> 叫做偏序集。 如以下关系都是偏序关系： 1 非空集合A 上的恒等关系IA。 2 实数集R上的“”、“”关系。
4.6 偏序关系
定义4.24
设<A, ≤ > 为偏序集，对于任意的x, yA，如果x < y并且不存在z∈A使得 x<z<y，则称y盖住x。作为集合A 上的一个二元关系，盖住关系C O V A 可表示 为：
C O V A={<x, y> |x, y∈A y盖住x} 根据定义4.24，<x, y>，
<x, y > ∈ C O V A y盖住x x ≤y <x, y>∈ ≤ 所以C O V A ≤ 。
4.6 偏序关系
对于偏序集<A, ≤ >，它的盖住关系C O V A 是唯一的，所以可以利用盖住关系 作图，表示该偏序集<A, ≤ > 。这个图叫作哈斯图。 偏序集<A, ≤>的哈斯图的画法如下： 1 用“”表示A 中的每一个元素； 2 x, yA，若x<y，则把x画在y的下面； 3 x, yA，若y盖住x ，则用一条线段连接x和y。
例 33
已知偏序集<A, R > 的哈斯图如下 解： 图,试求出集合A 和关系R的 表达式.
A = {a, b, c,d, e, f,g, h }
R = {<b,d>, <b,e>, <b,f>, <c,d>, <c,e>, <c,f>, <d,f>, <e,f>, <g,h> }∪ IA
4.6 偏序关系4.Fra bibliotek 偏序关系定义4.23
设<A, ≤>为偏序集，若x, yA，x与y都是可比的，则称≤为A 上 的全序关系（或线序关系）。且称<A, ≤ > 为全序集。 例如，集合A = {1, 2, 3, 4, 5}上的 1 “小于等于”关系是全序关系，因为任何两个数总是可比大小 的。 2 “整除关系”不是全序关系，因为2与3是不可比的。
定义4.25
设<A, ≤>为偏序集，BA，yB， 1 若x(xB → y ≤ x)成立，则称y是B的最小元。 2 若x(xB → x ≤ y)成立，则称y是B的最大元。 3 若x(xB x ≤ y)成立，则称y是B的极小元。 4若x(xB y ≤ x)成立，则称y是B的极大元。 最 小元是B中最小的元素,它与B中其它元素都可比; 极小元不一定与B中元素都可比,只要没有比它小的元素,它就是极小元. 对于有穷集B, 极小元一定存在,而且还可能有多个. 若B中只有一个极小元,则它一定是B的最小元. 类似的,极大元与最大元也有这种区别.
偏序集<{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },R 整除> 的哈斯图 如右图所示.
4.6 偏序关系 4.6 偏序关系
P({a, b, c}) = {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}。 P({a, b, c})上的盖住关系为： COV P({a, b, c}) = {<, {a}>, <, {b}>, <, {c}>,
例 32
解:
COV({ 1, 2, 3, 4, 5, 6, 7, ,9 })
画出偏序集<{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
={<1,2>,<1,3>,<2,4>,<1,5>,<2,6>, <3,6>,<1,7>,<4,8>,<3,9>}
R整除> 和<P({ a, b, c }),R>的哈 斯图.
解 极小元:a, b, c,g. 极大元:a, f,h. 没有最小元与最大元. 由这个例子可以知道,哈斯图中的孤立顶点既是
极小元也是极大元.
4.6 偏序关系
定义4.26
设<A, ≤>为偏序集，BA，yA， 1 若x(xB → x ≤ y)成立，则称y是B的上界。 2 若x(xB → y ≤ x) 成立，则称y是B的下界。 3 令C={y |y为B的上界}，则称C 的最小元为B的最小上界或上确界。 4 令D={y |y为B的下界}，则称D 的最大元为B的最大下界或下确界。
4.6 偏序关系
定义4.22
设<A, ≤>为偏序集，定义 1x, yA，x < y x ≤ y xy，x<y读作x“小于”y，这里所 说的 “小于”是指在偏序中x排在y的前边。 2 x, yA，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是不可比的。
由上面定义可知: B的最小元一定是B的下界,同时也是B的最大下界; B的最大元一定是B的上界,同时也是B的最小上界. 反过来不一定正确,B的下界不一定是B的最小元,因为它可能不是B中的元素,B 的上界也不一定是B的最大元. B的上界,下界,最小上界,最大下界都可能不存在.如果存在,最小上界与最大下 界是唯一的.
4.6 偏序关系
当B＝A 时，B的最大元、最小元、极大元和极小元称为偏序 集<A, ≤ > 的最大元、最小元、极大元和极小元。
定定义4理.244.24 设<A, ≤ > 是偏序集，BA，如果B有最大元（最
小元），则必唯一。
例 34
设偏序集<A, ≤ > 如下图所示, 求A 的极小元,最小元,极大元, 最大元.
<{a}, {a, b}>, <{a}, {a, c}>, <{b}, {a, b}>, <{b}, {b, c}>, <{c}, {a, c}>, <{c}, {b, c}>, <{a, b}, {a, b, c}>, <{a, c}, {a, b, c}>, <{b, c}, {a, b, c}>} 哈斯图如右图所示：
小结
（1）偏序关系同时具有自反、反对称和传递性，可以通过 关系矩阵和关系图判断某关系是否是偏序关系。 2 偏序集、全序关系、小于、可比和盖住等常用的概念。 3 哈斯图是偏序关系的简化关系图，哈斯图的画法。 4偏序集中的一些特殊元素的定义、性质与求解：最大 元 、最小元、极大元和极小元；上界、上确界、下界和下 确 界。