Randy's Notes

集合的关系之偏序

前言

格是一种特殊的偏序集。所以首先要复习偏序这个集合之间的关系,还有关于偏序关系的哈塞图,想当年我哈塞图画的还是很溜的,所以稍微看看就能想起来了。

关系

集合元素之间的关系可以表示成一种结构,这种结构叫关系。它其实是一种集合间的笛卡尔积的一个子集,所以 $A$ 和 $B$ 的关系并不等于 $B$ 和 $A$ 的关系。

设 $A$ 和 $B$ 是集合,一个从 $A$ 到 $B$ 的二元关系是 $A × B$ 的子集。

即一个从 $A$ 到 $B$ 的二元关系是集合 $R$,其中每个有序对的第一个元素取自 $A$ 而第二个元素取自 $B$。当 $(a, b)∈R$ 时,$a$ 与 $b$ 有关系 $R$ 。

函数作为关系

一个从集合 $A$ 到集合 $B$ 的函数 $f$ 对 $A$ 中的每个元素都指定 $B$ 中的一个唯一的元素。关系是函数的一般表示,可以用关系表示集合之间更为广泛的联系。

关系的性质

  • 若对每个元素 $a∈A$ 有 $(a, a)∈R$,则称定义在集合 A 上的关系 $R$ 为自反的。
  • 若对于任意 $a, b∈A$,只要 $(a, b)∈R$ 就有 $(b, a)∈R$,则称定义在集合 $A$ 上的关系 $R$ 为对称的。若对于任意 $a, b∈A$,只要 $(a, b)∈R$ 且 $(b, a)∈R$,一定有 $a = b$, 则称定义在集合 $A$ 上的关系 $R$ 为反对称的。
  • 若对于任意 $a, b, c∈A$,$(a, b)∈R$ 并且 $(b, c)∈R$ 则 $(a, c)∈R$,则称定义在集合 $A$ 上的关系 $R$ 为传递的

偏序(Partial Order)

定义在集合 $S$ 上的关系 $R$,如果它是自反的、反对称的和传递的,就称为偏序。集合 $S$ 和定义在其上的关系 $R$ 一起称为偏序集,记作 $(S, R)$。集合 $S$ 中的成员称为偏序集的元素。

通常在一个偏序集中,记号 $a≼b$ 表示 $(a, b)∈R$;记号 $a≺b$ 表示 $a≼b$,但 $a≠b$。当 $a$ 与 $b$ 是偏序集 $(S, ≼)$ 的元素时,不一定有 $a≼b$ 或 $b≼a$。

  • $a≼b$ 读作 “$a$ 小于或者等于 $b$”,表示任意偏序集中的关系,并不仅仅是小于或者等于的关系
  • $a≺b$ 读作 “$a$ 小于 $b$” 或者 “$b$ 大于 $a$”

例如: 包含关系 $⊆$ 是定义在集合 $S$ 的幂集上的偏序

  • 对于$S$ 的子集 $A$ ,有 $A⊆A$,满足自反关系
  • 对于$S$ 的子集 $A、B$ ,有 $A⊆B$ 且 $B⊆A$ 时,$A = B$,满足反对称关系
  • 对于$S$ 的子集 $A、B、C$,有 $A⊆B$ 且 $B⊆C$ 时,$A ⊆ C$,满足传递关系

因此 $⊆$ 是 $P(S)$ 上的偏序,$(P(S), ⊆)$ 是偏序集。

单调函数

给定一个偏序关系 $(S, ≼)$,当且仅当对任意 $a, b∈S$ 满足 $a≼b ⇒ f(a)≼f(b)$ 时,称定义在 $S$ 上的函数 $f$ 为单调函数。

例如:

  • $R$ 为包含关系 $⊆$,集合 $S$ = {$1, 2, 3, 4$},偏序关系 $(S, ≤)$,函数 $f = x$$2$
  • $R$ 为整除关系 $/$,集合 $S$ = {$2, 4, 6, 8$},偏序关系 $(S, /)$,函数 $f = -x$

哈塞图

在有穷偏序集的有向图中,既然它满足偏序关系,那么就有许多边是默认存在的。例如集合 {$1, 2, 3, 4$} 上的偏序 {$(a, b) | a ≤ b$} 的有向图,如图 a 所示;由于偏序满足自反关系,所以把每个顶点上的环去掉,如图 b 所示;由于偏序满足传递关系,所以把传递的边去掉,如图 c 所示;

极大元和极小元

具有极值性质的偏序集中的元素有许多重要作用。

  • 当偏序集中的一个元素不小于这个偏序集的任何其他元素时,即不存在 $b∈S$ 使得 $a≺b$,这个元素 $a$ 称为极大元
  • 当偏序集中的一个元素不大于这个偏序集的任何其他元素时,即不存在 $b∈S$ 使得 $b≺a$,这个元素 $a$ 称为极小元

使用哈塞图很容易识别极大元和极小元,它们是图中的“顶”元素和“底”元素。如偏序集 $(P(${$a, b, c$}$), ⊆)$ 和 $(${$2, 4, 5, 10, 12, 20, 25$}$, |)$ 的哈塞图所示

偏序集 $(P(${$a, b, c$}$), ⊆)$ 的极大元是 {$a, b, c$},极小元是 ∅;
偏序集 $(${$2, 4, 5, 10, 12, 20, 25$}$, |)$ 的极大元是 12 、20 和 25,极小元是 2 和 5。

最大元和最小元

  • 当偏序中存在一个元素大于每个其他的元素时,即对于 $∀b∈S$,有 $b≼a$,这个元素 $a$ 称为最大元。即只有一个极大元的时候,这个极大元就是最大元。
  • 当偏序中存在一个元素小于每个其他的元素时,即对于 $∀b∈S$,有 $a≼b$,这个元素 $a$ 称为最小元。即只有一个极小元的时候,这个极小元就是最小元。

例如偏序集 $(P(${$a, b, c$}$), ⊆)$ 的最大元是 {$a, b, c$},极小元是 ∅;偏序集 $(${$2, 4, 5, 10, 12, 20, 25$}$, |)$ 没有最大元和最小元。

上界和下界

有时候可以找到一个元素大于或者等于偏序集 $(S, ≼)$ 的子集 $A$ 中的所有元素。

  • 如果 $u∈S$,使得 $∀a∈A$ 有 $a≼u$,那么 $u$ 称为 $A$ 的一个上界;
  • 如果 $l∈S$,使得 $∀a∈A$ 有 $l≼a$,那么 $l$ 称为 $A$ 的一个下界。

例如以下哈塞图中,偏序集的子集 {$a, b, c$} 的上界是 $e, f, j, h$,下界是 $a$;{$j, h$} 没有上界,下界是 $a, b, c, d, e, f$;{$a, c, d, f$} 的上界是 $f, h, j$,下界是 $a$。

最小上界和最大下界

  • 如果 $x$ 是子集 $A$ 的一个上界并且它小于 $A$ 的任何其他的上界,那个元素 $x$ 是子集 $A$ 的最小上界(也叫并(join: $∨$));
  • 如果 $x$ 是子集 $A$ 的一个下界并且它大于 $A$ 的任何其他的下界,那个元素 $x$ 是子集 $A$ 的最大下界(也叫交(meet: $∧$))。

例如偏序集的子集 $A$ = {$a, b, c$} 的并是 $e$,交是 $a$。

格(Lattice)

Lattice: 晶格,点阵。

如果一个偏序集的每对元素(非空有限子集)都有并交,就称这个偏序集为格。

如下哈塞图中,图 a 和 图 c 是格,图 b 不是,因为子集 {$b, c$} 虽然有上界 $d, e, f$,但没有并(最小上界)。

半格(Semilattice)

如果一个偏序集的每对元素都有并或者每对元素都有交,就称这个偏序集为半格。

半格的高度: 半格的哈塞图中任意两个结点的最大距离 +1

交汇运算和并函数

  • 如果一个偏序集的每对元素都有交,那么交汇运算(meet operation $∧$)就是集合 $A$ 中的一个二元运算
  • 如果一个偏序集的每对元素都有并,那么并函数(join operation $∨$)就是集合 $A$ 中的一个二元运算

交汇运算(并函数$∨$也满足)满足下列三个条件($x, y, z∈A$):

  1. $x ∧ y = y ∧ x$ (交换律),
  2. $x ∧ (y ∧ z) = (x ∧ y) ∧ z$ (结合律)
  3. $x ∧ x = x$ (幂等率)

例如对于下图中子集 $A =$ {$a, b$} 来说,它的交为 $∧A = a∧b$;它的并为 $∨A = a∨b$

交半格(meet-semilattice)和并半格(join-semilattice)

  1. 如果二元运算 $∧$ 在集合 $A$ 上满足上面的三个条件,那么它就是交汇运算。有序对 $(A, ∧)$ 就是交半格。

  2. 我们可以在集合 $A$ 上定义一种二元关系 $≼$,当且仅当$x ∧ y = x$ 时,$x≼y$,实际上,这个关系是在 $A$ 上的偏序。

  • $x ≼ x$,因为满足幂等率所以 $x ∧ x = x$;
  • 如果 $x ≼ y$ 并且 $y ≼ x$,那么由交换律得 $ x = x ∧ y = y ∧ x = y$;
  • 如果 $x ≼ y$ 并且 $y ≼ z$,那么由结合律得 $x ∧ z = (x ∧ y) ∧ z = x ∧ (y ∧ z) = x ∧ y = x$,所以 $x ≼ z$

所以只要当且仅当 $x ∧ y = x$ 时,有 $x ≼ y$,我们就可以得到一个交半格。然后就可以利用交半格的性质去解传递方程和控制流方程。例如

  • 交汇运算是交集操作 $(∩)$ 时,偏序关系是被包含关系$(⊆)$,顶元素是较大的集合;
  • 交汇运算是并集操作 $(∪)$ 时,偏序关系是包含关系$(⊇)$,顶元素是较小的集合;

上面两种定义能得到一个等价的交半格,具体证明看维基百科。第二种在数据流分析中比较常用,因为只要满足一个关系就能得到一个交半格。

  • 交半格有一个顶元素$ㄒ$,使得对于 $A$ 中的所有 $x$,$ㄒ∧x = x$;
  • 交半格课能还有一个底元素$⊥$,使得对于 $A$ 中的所有 $x$,$⊥∧x = ⊥$。

对于一个交半格,如果颠倒它的偏序集的关系,也就是将这个半格倒过来,那么它就是并半格。龙书上提到传统的数据流文献讲的是交半格,所以我们也使用交半格。

总结

运用哈塞图和半格的概念与性质,对静态分析中的程序数据流的分析非常重要。学习这部分内容也确实晦涩难懂,特别是关于半格那部分,花了两三天的时间还是感觉模棱两可,希望学到后面能越来越清晰。

疏影横斜水清浅,暗香浮动月黄昏