半格

半格描述“合并两个对象后，只保留共同信息”或“汇总两个对象的最小共同上界”。交换性让输入次序无关，结合性让多项合并无须括号，幂等性让重复证据不产生额外效果。

一个半格运算会反过来决定“谁的信息更少”这套偏序。因此代数与序不是两份独立数据：选定 meet 后，次序由 $x\wedge y=x$ 恢复；选定 join 后则由 $x\vee y=y$ 恢复。

幂集按包含关系排序，交集给出 meet，并集给出 join。正整数按整除关系排序时，$gcd$ 给出 meet，$\mathrm{lcm}$ 给出 join：例如 $gcd(12,18)=6$，而每个同时整除 $12,18$ 的数都整除 $6$，所以 $6$ 是整除序中的最大下界。全序集合上的 $min$ 与 $max$ 也分别给出两种半格。

取集合族 $S=\{\varnothing ,\{a\},\{b\}\}$，其中 $a\ne b$，并按包含关系排序。它对交集封闭，所以是 meet-semilattice，底元为 $\varnothing$。但 $\{a\}$ 与 $\{b\}$ 在 $S$ 中连共同上界都没有，因此没有 join。

再取一个不同于 $a,b$ 的元素 $c$，补入集合 $\{a,b,c\}$。得到的四元素偏序就成为格：$\{a\}$ 与 $\{b\}$ 的 join 是 $\{a,b,c\}$。虽然普通并集 $\{a,b\}$ 仍不在其中，最小上界已经存在，因为最小上界只在当前偏序的元素中寻找。

对至少含两个元素的集合，左零运算 $x\ast y=x$ 给出幂等半群理路幂等半群Idempotent semigroup · Band每个元素都满足平方等于自身的半群，又称 band。，满足结合律与幂等律，却不交换。若仍用 $x\ast y=x$ 定义 $x\le y$，就会让任意两个不同元素同时满足 $x\le y$ 与 $y\le x$，破坏反对称性。这说明交换律在恢复偏序时起了什么作用。

每个格在 meet 与 join 运算下分别形成半格。meet 的单位元是顶元，因为 $x\wedge 1=x$；join 的单位元是底元，因为 $x\vee 0=x$。对于有限 meet-semilattice，若还有顶元，则每对元素的共同上界组成非空有限集，把这些上界全部取 meet，就得到二者的 join，因而整个结构成为格。

在按集合并汇总信息的数据流分析中，交换律使汇总次序无关，结合律允许分批合并，幂等律则保证重复收到同一份信息不会改变结果。Sparse Table理路稀疏表Sparse table预计算长度为二次幂的静态区间答案，以 $O(1)$ 或 $O(\log n)$ 回答区间查询。 的重叠区间查询也利用结合律和幂等律：重叠部分计算两次后，汇总值仍保持不变。这个算法只需幂等半群；常用的 min/max/gcd 还满足交换律，因此也是半格运算。