偏序集与格论 偏序集（partially ordered set，简称poset）是一个集合 \( P \) 配上一个二元关系 \( \leq \)，满足以下三条公理： 自反性 ：对任意 \( a \in P \)，有 \( a \leq a \)。 反对称性 ：若 \( a \leq b \) 且 \( b \leq a \)，则 \( a = b \)。 传递性 ：若 \( a \leq b \) 且 \( b \leq c \)，则 \( a \leq c \)。 例如，实数集配备普通的“小于等于”关系构成偏序集，但集合的幂集配以子集关系 \( \subseteq \) 也是偏序集的典型例子。 格（Lattice）的定义 若偏序集 \( (L, \leq) \) 中任意两个元素 \( a, b \) 都有： 最小上界（上确界） ：记为 \( a \vee b \)，满足 \( a \leq a \vee b \)，\( b \leq a \vee b \)，且对任意上界 \( c \)（即 \( a \leq c, b \leq c \)）有 \( a \vee b \leq c \)。 最大下界（下确界） ：记为 \( a \wedge b \)，满足 \( a \wedge b \leq a \)，\( a \wedge b \leq b \)，且对任意下界 \( c \)（即 \( c \leq a, c \leq b \)）有 \( c \leq a \wedge b \)。 则称 \( L \) 为一个 格 。例如，幂集 \( P(X) \) 配子集关系构成格，其中 \( A \vee B = A \cup B \)，\( A \wedge B = A \cap B \)。 格的代数视角 格也可通过二元运算 \( \vee \)（并）和 \( \wedge \)（交）定义，满足： 交换律 ：\( a \vee b = b \vee a \)，\( a \wedge b = b \wedge a \)。 结合律 ：\( (a \vee b) \vee c = a \vee (b \vee c) \)，对 \( \wedge \) 同理。 吸收律 ：\( a \vee (a \wedge b) = a \)，\( a \wedge (a \vee b) = a \)。 从代数定义可推出偏序结构：定义 \( a \leq b \) 当且仅当 \( a \wedge b = a \)（或等价地 \( a \vee b = b \)）。 完备格 若格的任意子集 \( S \subseteq L \) 都有上确界 \( \bigvee S \) 和下确界 \( \bigwedge S \)，则称 \( L \) 为 完备格 。例如，幂集格是完备的，但有理数集配通常序不是完备格（因为无理数缺口的存在）。完备格必存在最大元（上确界空集）和最小元（下确界空集）。 分配格与模格 若格满足 分配律 ： \[ a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c), \] 则称为 分配格 。但并非所有格都分配，例如五元素菱形格 \( M_ 3 \) 不满足分配律。 弱化分配律得到 模格 ：若 \( a \leq c \)，则 \[ a \vee (b \wedge c) = (a \vee b) \wedge c. \] 模格在代数结构（如子模格）中常见。 布尔代数 若分配格中存在最大元 \( 1 \) 和最小元 \( 0 \)，且每个元素 \( a \) 有 补元 \( \neg a \) 满足： \[ a \wedge \neg a = 0, \quad a \vee \neg a = 1, \] 则构成 布尔代数 。例如集合的补运算、逻辑中的真值代数均为布尔代数。布尔代数可建模古典逻辑的命题演算。 格在逻辑与计算中的应用 程序分析 ：格用于抽象解释（abstract interpretation），通过格上的不动点计算程序语义。 类型系统 ：子类型关系构成格，如类型 \( \top \)（最大类型）和 \( \bot \)（最小类型）。 知识表示 ：概念格（concept lattice）用于形式概念分析，从数据中提取层次结构。 通过逐步扩展格的约束（从偏序到分配格再到布尔代数），可灵活适配不同逻辑系统的需求。