离散数学课件 第六章 序关系和结构

第六章序关系和结构Order Relations and

Structures

§6.1 偏序集Partial Ordered Sets

关系 Relation

定义

A Relation R From A to B is a subset of AB

A relation on A is a subset of AA

矩阵表示，图表示。

性质

自反 reflextive

R

对称 symmetric, asymmetric, antisymmetric

R-1=R, R-1R, R-1R=

传递 transive

R2R or R=R 传递闭包 Wallshall算法O(n3)

等价关系 =

偏序关系Partial Order 

Definition

1. 自反 Reflexive

aA, (a,a)R

2．反对称antisymmetric

a,bA (a,b)∈R∧(b,a)∈R  a=b

3．传递Transitive

a,b,cA (a,b)∈R ∧ (b,c)∈R  (a,c)∈R.

Examples

, , , , 例4． R，S都是A上等价关系,

RSxRy→xSy, R：A上全体等价关系， (R ，)构成偏序。

对偶偏序集：

如果R是A上偏序，则R－1也是A上偏序。（A，R－1）称为（A，R）的对偶偏序集。 （A，≥）是（A，≤）的对偶偏序。

全序关系，线性序关系linear order，链chain

偏序1.2.3.＋4

4． a,bA,(a,b)R∨(b,a)∈R.

字典序

偏序乘积

定理1如果(A,≤)，(B,≤)是偏序，则(A×B，≤)是乘积偏序product partial order，其中≤定义为： (a,b)≤(a’,b’)a≤a’b≤b’

偏序与严格序

设（A，≤）是偏序， 令a

大于，小于都是严格线性序。

反之若（A，<）是严格序， 令a≤ba

字典序

二元

(A×B，≤)中，令(a,b)<(a’,b’)a

a=a’,b

n元(A，≤）是偏序，

An＝A×A×……×A

(a1,a2,……,an)<(b1,b2,……,bn)

 a1

∨a1=b1∧……∧an

不等长

(a1,a2,……,an)<(b1,b2,……,bm) If n=m

If n

If n>m (a1,a2,……,am)<(b1,b2,……,bm)

定理2. 偏序集的有向图中没有长度大于1的圈。

哈斯图Hasse Diagram

parital order，digraph and the matrix of D6？

从关系图到哈斯图

Deleting all the self-circles

Deleting all the edges which can be induced

by transive property

Replacing vertices by dots

Make sure the greater elements are located at

higher place. 2 4

3

1 12 例11．D12 的哈斯图？

例12．S＝{a,b,c}, A=P(S).

问题（6.1.1）

给定偏序关系R，哈斯图是否唯一？

计算哈斯图的算法？

传递闭包逆运算？

拓扑排序

（A，≤）是偏序集，构造一个线性序（A，≤’）使 a

算法原理：

1. 选择一个没有前驱的顶点输出，

2. 去掉这个顶点以及从这点出发的所有边。

重复1.2.直到所有顶点都输出完毕

时间复杂性？

O(n3)

同构Isomorphic

定义 0 f：（A, ≤）→（A’, ≤’）

f是A→A’的一一对应，

a≤b iff f(a)≤’f(b)。

例15．（Z，≤）→（2Z，≤）

f：（Z，≤）→（2Z，≤）是同构。

f(a)=2a

a≤b iff 2a≤2b

定理3. 设f：(A,≤) (A’,≤’)。则A,

A’对应的性质都相同。

序同构与哈斯图的关系

1． 如果f是同构，则A的哈斯图中所有标记a换成对应的标记f(a), 得到A’的哈斯图。

2． 如果A的哈斯图中所有标记a换成对应的标记f(a), 得到A’的哈斯图，则f是同构。 例17．A＝{1,2,3,6},

A’=P({a,b})={ ,{a},{b},{a,b}}

Homework P200－201

5，6，14，16，24，28，35，36

§6.2偏序集的极大极小元 Extremal

elements of Partial Ordered Sets

极大元maximal element：

a∈A，b∈A，a

极小元minimal element：

a∈A，b∈A，b

定理1. 有限偏序集A中，至少有一个极大元，至少有一个极小元。

最大元greatest element：

a∈A，任意b∈A，ba.

最小元least element：

a∈A，任意b∈A，ab. 定理2. 类似定理1

偏序集A中，至多有一个最大元，至多有一个最小元。

偏序集A中，如果有最大元，称之为单位元1，如果有最小元，称之为零元0。

上界 upper bound

偏序集A中，BA，a∈A，b∈B，ba.

下界lower bound

偏序集A中，BA，a∈A，b∈B，ab.

上确界LUB least upper bound

偏序集A中，BA，a是B的最小上界，即a是B的上界，对B的任意上界a’，aa’.

下确界GLB greatest lower bound

偏序集A中，BA，a是B的最大下界，即a是B的下界，对B的任意下界a’，a>a’. 定理3. 偏序集A中，BA，B至多一个上确界，至多一个下确界。

定理4. 设f：（A，≤）→（A’,≤’）

是偏序同构，

（a） a是A的极大（极小）元，则f(a)是A’的极大（极小）元。

（b） a是A的最大（最小）元，则f(a)是A’的最大（最小）元。

（c） BA，a是B的上（下）界，则f(a)是f(B)的上（下）界

（d） BA，a是B的上确（下）界，则f(a)是f(B)的上（下）确界

Homework P206－207

16，26，33

§6.3 格 Lattices

定义 格是一个偏序集（L，≤），任意a，b∈L，a，b有上下确界。

令a∨b＝LUB(a,b), a∧b＝GLB(a,b).

格 (L,≤，∨，∧)

例1．（P(S), ）是格，

A∨B＝A∪B，A∧B＝A∩B。

记做（P(S), ,∪,∩）

例2．（Z＋，| ）是格，

a∨b＝LCM(a,b),

a∧b＝GCD(a,b).

例3．令Dn是n的所有正因子的集合，（Dn，|）是格。

D20＝{1,2,4,5,10,20},

D30={1,2,3,5,6,10,15,20} 线性序是格

例4． Hasse图是否格的判断。

abcd abcd

abcde abcde

eabcd abcdefg

例5． R：A上全体等价关系，偏序（R ，）是格。

R∧S＝R∩S

R∨S＝(R∪S)∞

设（L，≤）是格，则对偶（L，≥）也是格。

问题6.3.1 1)格的判定算法？2)格的运算表生成？

定理1.乘积格

设（L1,≤,∨,∧），

（L2,≤,∨,∧）都是格。

则（L1×L2，≤,∨,∧）也是格。

(a,b)∨(c,d)=(a∨c, b∨d)

(a,b)∧(c,d)=(a∧c, b∧d) 子格sublattice

设（L，≤）是格，SL，S对∨，∧封闭，

即a，b∈Sa∨b，a∧b∈S。

记做(S，≤,∨,∧)  (L，≤,∨,∧)或 格S  L。

例如(Dn，|, LCM, GCD) (Z+, |, LCM,GCD) 例9

egabcdf

egbcf egabcdf

abcd 格的同构Isomorphic Lattices

f：(L1,≤,∨,∧)→(L2,≤,∨,∧)，

f是L1到L2的序同构，则f保持

∨，∧运算，

f(a∨b)=f(a)∨f(b)

f(a∧b)=f(a)∧f(b)

格同构也记做L1L2。

D6P({a,b}).

问题 （6.3.2） 1） Dn 同构与 (P(S), ≤)的充分必要条件？ 2）Dn 同构与Dm的充分必要条件是什么？

格的性质Properties of Lattices

定理2

设L是格，

则a≤b  a∨b＝b  a∧b＝a.

定理3.

设L是格，则L具有如下性质：

幂等律