偏序和格是离散数学中的重要概念，在计算机科学中有着广泛的应用，特别是在数据结构、数据库理论和计算理论领域。偏序是一种二元关系，它描述了一组在某种意义上有序的元素，但这种顺序不一定是线性的。而格则是一种具有额外性质的特定类型的偏序集。
偏序是定义在集合 P 上的二元关系 ≤，它满足三个性质：自反性、反对称性和传递性。
- 自反性： 对于集合 P 中的所有元素 a，都有 a ≤ a。
- 反对称性： 对于集合 P 中的所有元素 a 和 b，如果 a ≤ b 且 b ≤ a，那么 a = b。
- 传递性： 对于集合 P 中的所有元素 a, b, c，如果 a ≤ b 且 b ≤ c，那么 a ≤ c。
一个集合 P 连同其上的偏序关系 ≤ 被称为偏序集。
偏序示例
让我们考虑集合 P={1,2,3}，并定义关系 ≤ 为通常的数值大小顺序：
- 自反性： 1 ≤ 1, 2 ≤ 2, 3 ≤ 3。
- 反对称性： 如果 a ≤ b 且 b ≤ a，那么 a = b。
- 传递性： 如果 1 ≤ 2 且 2 ≤ 3，那么 1 ≤ 3。
在这种顺序下，集合 P 就是一个偏序集。
格 是一种特殊的偏序集，其中每一对元素都满足以下条件：
- 最小上界（并/Join）： a 和 b 的并，记作 a ∨ b，是同时大于或等于 a 和 b 的最小元素。
- 最大下界（交/Meet）： a 和 b 的交，记作 a ∧ b，是同时小于或等于 a 和 b 的最大元素。
这意味着对于集合中的任意两个元素，我们总能找到唯一的并和交。
> 示例：在整除关系下（如果 a 能整除 b，则 a ≤ b）的整数集就是一个格。
格示例
让我们考虑集合 L = {1,2,3,6} 并使用整除关系：
- 并：2 和 3 的并是 6，因为 6 是能同时被 2 和 3 整除的最小的数。
- 交：2 和 6 的交是 2，因为 2 是能同时整除 2 和 6 的最大的数。
在这种顺序下，集合 L 就是一个格。
关键性质
—
自反、反对称、传递
偏序 + 每一对元素都有并和交
下面我们通过示例来详细解释格和偏序集的概念：
这是一个格的 Hasse 图，它是一种偏序集 (poset)，其中每一对元素都有一个最小上界（并）和一个最大下界（交）。
!HasseHasse 图
元素
- 图中标记为 INLINECODEea5f3721, INLINECODE9c8beab9, INLINECODEe7710e37，中间点，INLINECODE7a695087, INLINECODEd514f66d, 和 INLINECODE53cc97b2 的节点代表偏序集中的元素。
- 底部元素 (
0) 是最小元素，其他所有元素都在它之上。 - 顶部元素 (
1) 是最大元素，它位于所有其他元素之上。
解释
- 从一个节点向上的路径指向另一个节点，意味着根据偏序关系，较低的节点小于或等于较高的节点。
- 例如：
- INLINECODE61e803e5 和 INLINECODE0a09ed4f 都在 INLINECODEf8c3152a 之上，所以 INLINECODE057b5918 且
0 ≤ d。 - 中间的节点（图中未标记，代表 INLINECODEde8e4335 和 INLINECODE6b92050a 的并，或者 INLINECODE9ee58d8f 和 INLINECODE4b3c836a 的交）位于 INLINECODE788350d5 和 INLINECODE14041b75 之上，同时位于 INLINECODEe90b7369 和 INLINECODE8e27162b 之下。
- INLINECODE1b8bb6a4 位于 INLINECODE65f1dff3 和 INLINECODEebb5105c 之上，所以 INLINECODEfa71ab50 且
b ≤ 1。
交与并示例
- INLINECODE813b91b9 和 INLINECODE3d2141f9 的并（最小上界）是那个中间节点。
- INLINECODEf7d93ff9 和 INLINECODEc5a90ef1 的交（最大下界）也是那个中间节点。
这个结构展示了任意两个元素（例如 INLINECODEcb9abbb8 和 INLINECODE6eccc8d6，或者 INLINECODE25fcbbca 和 INLINECODE8b52a348）如何同时拥有一个交和一个并，这正是该集合成为格的原因。
工程应用
#### 任务调度
- 偏序用于对任务之间的依赖关系进行建模。
- 必须按特定顺序发生的任务被表示为偏序集，从而实现高效的调度和并行执行。
#### 数据结构
#### 数据库理论
- 偏序和格是以下方面的基础：
- 查询优化 —— 确定执行查询的最有效方式。
- 模式设计 —— 对关系数据库中的层次结构和约束进行建模。
#### 形式化验证
- 用于形式化方法以确保系统的正确性。
- 特别是在并发系统中非常有用，因为并发系统中的事件可能不具有全序关系。
- Par