3.4次序关系

离散数学
Discrete Mathematics
3.4次序关系
张晓 西北工业大学计算机学院 zhangxiao@ 2011-1-10


目录
3.4.1 偏序集合 3.4.2 拟序集合 3.4.3 线序集合和良序集合 3.4.4 词典序和标准序
2011-1-10
离散数学
2


3.4.1 偏序集合
定义3.4―1 如果集合A上的二元关系R是自反 的,反对称的和传递的,那么称R为A上的偏序关 上的偏序关 系（partial order）,称序偶〈 称序偶〈A,R〉为偏序 集合， 集合，记为<A,≼>
通常用≼表示偏序关系,读作“小于等于 小于等于” 小于等于 <x,y>∈R ⇔ xRy ⇔ x≼y “严格小于”（拟序）: x≺y ⇔ x≼y ∧ x≠y 如果R是集合A上的偏序，则R-1也是A上的偏序。

如果用≤表示R,可用≥表示R-1.〈A,≤〉和〈A,≥〉都是偏序集 合,并互为对偶。

2011-1-10
离散数学
3


例3.4-1
(a)〈I,≤ 〉 是偏序集合,这里≤ 表示整数中的“小于或等 于”关系。

(b)〈ρ(A),⊆〉是偏序集合,这里⊆是集合间的包含关系。

(c) A={2,4,6,8}, D代表整除关系 整除关系, M代表整倍数关系 整倍数关系, 则 D={〈2,2〉,〈4,4〉,〈6,6〉,〈8,8〉,〈2,4〉,〈2,6〉, 〈2,8〉,〈4,8〉} M={〈2,2〉,〈4,4〉,〈6,6〉,〈8,8〉,〈4,2〉,〈6,2〉, 〈8,2〉, 〈8,4〉} 〈A,D〉,〈A,M〉都是偏序集合,且互为对偶
2011-1-10
离散数学
4


关于偏序
“小于或等于”不是指数的大小，而是在偏序关系中的 小于或等于 顺序性。

顺序性 x“小于或等于” 小于或等于”y的含义是：依照这个序，x排在y的 前边或者x就是y。

根据不同偏序的定义， 根据不同偏序的定义，对序有着不同的解释。

对序有着不同的解释。

例如 整除关系是偏序关系 ，3 ≼ 6的含义是3整除6。

大于或等于关系也是偏序关系， 大于或等于关系也是偏序关系，针对这个关系写 5 ≼ 4是说大于 或等于关系中5排在4的前边， 的前边，也就是5比4大。

集合A上的恒等关系IA和空关系 都是A上的偏序关系。

上的偏序关系。

小于或等于关系， 小于或等于关系，整除关系和包含关系也是相应集合上的偏序关 系。

2011-1-10
离散数学
5


哈斯图(Hasse diagram)
设<A,≼>是偏序集, x,y∈A 覆盖(cover): y覆盖x ⇔ x≺y ∧ ┓∃z( z∈A ∧ x≺z≺y ) 哈斯图: 当且仅当y覆盖x时,在x与y之间画 无向边, 并且x画在y下方。

2011-1-10
离散数学
6


补充例1 画出偏序集的哈斯图
偏序集 <{1,2,3,4,5,6,7,8,9}，R整除> 偏序集 <ρ({a,b,c}),R⊆ >


补充例2：由哈斯图给出关系R
已知偏序集<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 e


图 3.4―1 (b)为例3.4-1(3)中〈A,D〉的哈斯图


例3.4-2
(a)P={1,2,3,4},〈P,≤〉 的 哈 斯 图 为 图 3.4―2 (b)A={2,3,6,12,24,36},〈A,整除〉的哈 斯图为图3.4―3 (c)A={1,2,…,12},〈A, 整除〉的哈斯图为 图3.4―4
2011-1-10
离散数学
10


例3。

4-3
考虑在偏序“整除”下整数1到6的集合,其哈斯图为图
3.4―5
(a)如果B={1,2,3,6},那么1是B的最小元素,6是B的
最大元素
(b)如果B={2,3},因为2和3互相不能整除,那么B没有
最小元素和最大元素。

(c)如果B={4},那么4是B的最大元素,也是B的最小元
素。

图 3.4―5
的下界：〈0,0〉和〈1,0〉,〈1,0〉是最大下界
图
3.4―7
例6
(a)P={∅,{a},{a,b},{a,b,c}},〈P,⊆〉
是线序集合,其哈斯图如图3.4―8所
示。

(b)〈I,≤〉是线序集合,其哈斯图(不完
全)如图3.4―9所示。

(c)设S是区间套的集合{［0,a)｜
a∈R+},则〈S,⊆〉是线序集合。

(d)〈{1,2,3,6},整除〉不是线序集合;
(e)如果A是多于一个元素的集合,那么
〈ρ(A),⊆〉不是线序集合.
图3.4―8 图3.4―9。