如果你去翻数学系或者计算机系的课表格Lattice通常是个薛定谔的存在——在离散数学里它出现在偏序关系之后在布尔代数之前不少老师只花两节课带过学生却在之后的抽象解释、模态逻辑、格密码论文里反复撞见它。我自己第一次真正被迫自学格论是读一篇程序静态分析的论文满篇都是完备格不动点单调函数当时只有一个念头这东西到底是什么鬼为什么编译器分析里全是它这篇是系列的第一篇按从偏序集出发 → 定义格 → 构造经典例子 → 认识格的优良性质 → 回到实际应用这条主线展开对标研究生入门课的第一讲。适合有三高等代数和基础离散数学背景、想系统补上格论这块拼图的读者也适合那些在论文里反复看到 Lattice、却一直没搞懂它和格子点阵有什么区别的朋友。下面每个概念我都会给出定义来源和为什么这样定义的理由尽量让你读完不是记住结论而是能自己推出来。1. 从偏序集看起格论的第一块基石1.1 为什么必须先建立偏序的概念任何一本格论教材都会告诉你格是一种特殊的偏序集。这句话听起来像废话但它其实在暗示一个重要方法论——格论不是在真空中定义出来的它的全部味道都来自怎么把集合里的元素排出层次感。偏序集poset就是集合 P 配上二元关系 ≤满足三条公理自反性对任意 x有 x ≤ x、反对称性x ≤ y 且 y ≤ x 则 x y、传递性x ≤ y 且 y ≤ z 则 x ≤ z。这三条公理里反对称性最容易被新手忽略。它保证了偏序不会出现你比我大、我比你大但咱俩还不是同一个元素的死循环自反性保证每个元素至少和自己可比传递性负责把排名一级一级传下去。为什么偏偏是这三条你可以把偏序想象成公司里的汇报关系谁能向谁汇报是多对一的不是所有人都能互相比较——一个程序员和一个产品经理谁级别高要看组织架构图不能简单比职级数字——但任何一条汇报链都不会成环也不会出现两个不同的人互相汇报。这就是反对称性的现实意义。1.2 哈斯图把序关系画出来光有定义是不够的。偏序集的命根子是可视化因为它太抽象了。哈斯图Hasse diagram就是用一个无向图的点表示元素按下小上大的规则摆放然后只画覆盖关系。什么叫覆盖a 覆盖 b记作 b ⋖ a表示 b a且不存在 c 使得 b c a。画图时把所有传递关系省略只保留覆盖边。这一招非常实用画一个偏序集之前先花一分钟列出所有的覆盖对能避免画出一堆冗余连线。我自己的经验是学格论的头两周笔不要离开草稿纸。遇到一个新概念先画一个具体的偏序集然后反复问自己在这个例子里这个定义到底在说什么哈斯图画多了你会慢慢形成一种直觉——看见一个格脑子里会自动浮现它的形状不需要每次都从公理推起。1.3 全序与偏序别把比较大小想窄了很多初学者默认 ≤ 就是实数的小于等于。如果你带着这个惯性读格论会在后面的整除格那里被狠狠教育一顿。偏序里的 ≤ 是抽象关系换到不同领域可以是集合的包含 ⊆整除关系 |逻辑蕴含 →程序抽象值域的偏序 ⊑。它们都满足那三条公理但表现形式完全不同。格论的价值恰恰在于把所有这些看起来不相关的序关系统一起来用同一套语言讨论。这就像你突然发现工资条排名体育积分榜图书馆书目分类其实是同一种数学结构的化身这种统一性就是格论的美感所在。2. 格的两种定义序视角与代数视角2.1 序理论定义上确界与下确界定了偏序集我们一步步逼近格的定义。对于集合 P 的子集 S如果存在元素 u 使得对所有 s ∈ S 都有 s ≤ u就称 u 是 S 的一个上界。注意上界不唯一——一个子集可能有一大堆上界。在所有上界中如果存在一个最小的记作 sup S 或 ∨S就称为最小上界也叫上确界对称地下界中最大的记作 inf S 或 ∧S称为最大下界、下确界。格的序理论定义来了一个偏序集 (L, ≤)如果其中任意两个元素 x、y 都存在最小上界 x ∨ y 和最大下界 x ∧ y那么这个偏序集就是一个格。必须强调的是任意两个元素——这是格与一般偏序集的关键区别。有些偏序集对某些子集有确界对其他子集没有那它就不是格。如果要求的是每个非空子集都有确界那就是更高阶的完备格我们到 4.3 节再展开。一个常见困惑是那单元素集合的 sup 和 inf 是什么很简单就是它本身。空集的 sup 和 inf 则不一定存在这直接引出了完备格中的 ⊥ 和 ⊤。2.2 代数定义并运算与交运算格还可以换个视角定义一个集合 L 配上两个二元运算 ∨并和 ∧交满足四条公理交换律x ∨ y y ∨ xx ∧ y y ∧ x结合律x ∨ (y ∨ z) (x ∨ y) ∨ zx ∧ (y ∧ z) (x ∧ y) ∧ z吸收律x ∨ (x ∧ y) xx ∧ (x ∨ y) x幂等律x ∨ x xx ∧ x x。这个定义完全是代数式的看起来和序关系八竿子打不着。但吸收律是分水岭——它的作用在于让交换律和结合律不至于退化成纯粹的对称运算而是真正确立了某种序。你可以试着在一组没有吸收律的运算上展开得到的结构会失控地膨大。吸收律的本质是截断无论 x ∧ y 多么小x 和它取并之后结果永远回到 x。这正是序关系夹在中间的代数体现。这里多提一句幂等律其实可以由吸收律推导出来。把吸收律中第一个公式的 y 换成 x ∨ y经过交换律和结合律运算可以推出 x ∨ x x。所以严格的教材里有时只列交换、结合、吸收三组公理但初学者列全四条更保险不容易绕晕。2.3 两种定义为什么殊途同归这两个定义是等价的若 (L, ≤) 按序定义是格可以令 x ∨ y sup{x, y}x ∧ y inf{x, y}然后验证四条代数公理成立反过来若 (L, ∨, ∧) 按代数定义是格可以定义 x ≤ y 当且仅当 x ∨ y y等价地x ∧ y x然后验证它是偏序并且 ∨ 恰好是最小上界、∧ 恰好是最大下界。为什么我要花一整节讲这个等价性因为在实际工作中两个视角各有用途序视角适合证明格的性质因为它能画图、有直觉代数视角适合做计算因为运算可以直接写进程序里。我做程序分析相关工作时处理类型系统里的 join 逻辑几乎全用代数视角而在思考这个类型格到底长什么样时又切回序视角。两种定义切换得像左右手一样熟练才算真正进了格论的门。3. 先别抽象看看格的三个经典实例3.1 幂集格信息合并的原型设 S {a, b, c}考虑它的所有子集构成的集合 2^S配上集合包含 ⊆。任意两个子集 A、B 的最小上界是 A ∪ B最大下界是 A ∩ B。因此这是一个格称为幂集格。这个例子为什么重要因为它是理解几乎所有格的原型你可以把格里的元素想成信息量把 ∨ 想成合并信息把 ∧ 想成提取公共信息。这套解释在程序分析里直接对应着路径合并和取交集——后面 5.1 节会用到。另外注意幂集格有最大元 S 和最小元 ∅且每个元素都有补集。它是一个布尔格见 4.4也是初学者最容易想象、最容易验证各种公式的试验场。任何关于格的性质先拿到 2^S 上试一遍通常能立刻看出对不对。3.2 整除格数论里的 lcm 与 gcd取自然数 n考虑它的所有正因子集合 D_n {d : d | n}序关系定义为整除。比如 n 12 时D12 {1, 2, 3, 4, 6, 12}。任意两个因子 a、b 在整除关系下的最小上界是它们的最小公倍数 lcm(a, b)——它一定是 n 的因子最大下界是最大公约数 gcd(a, b)。因此 (D_n, |) 构成格称为整除格。注意这里 lcm 和 gcd 在代数定义中扮演的角色正好对应着幂集格里的 ∪ 和 ∩。这说明格的概念不是孤立玩具在数论里就有深刻对应。顺着这个例子还能引出一个经典问题什么时候 D_n 是分配格答案是 n 无平方因子。也就是说n 12 2² × 3 时 D12 不是分配格但 n 30 2 × 3 × 5 时 D30 是分配格。这种结构性质跟着数论性质走的现象是格论最迷人的地方之一。3.3 划分格与子群格从组合到群论第三个经典例子稍微进阶一点集合 S 的所有划分配上加细关系 ≤定义划分 A ≤ 划分 B 当且仅当 A 的每个块都包含于 B 的某个块。两个划分的最小上界是共同加细取块的并集后不断拆分使满足划分公理最大下界是共同细分取每个块的块内交叠。这个格叫划分格结构比幂集格复杂得多。划分格在群论里有对应物给定群 G它的全体子群按包含构成子群格。很多群论定理其实都在和这个格打交道。比如 Lagrange 定理说若 H 是 G 的子群则 |H| 整除 |G|——在子群格视角下这相当于在两个层级节点之间标注了数值比例。再比如正规子群在子群格里的地位特殊正规子群的集合配上某种运算可以继续构成格结构。学会用格的语言读这些定理你会发现很多看似分散的结论突然被一根线串起来了。4. 格的优良性质分配律、模律与完备性逐级解锁4.1 分配格加在分布上的强假设一个格如果额外满足分配律x ∧ (y ∨ z) (x ∧ y) ∨ (x ∧ z)x ∨ (y ∧ z) (x ∨ y) ∧ (x ∨ z)就叫分配格。经典事实是在格中这两条分配律互为充要条件证明一个就能推出另一个不需要两条都验证。幂集格是分配格整除格当 n 无平方因子时也是分配格。分配格最伟大的地方在于它保证了格再往下走可以退化出布尔代数一旦缺少分配律你就完全不能把 ∨ 和 ∧ 当成集合的 ∪ 和 ∩ 来用。我见过不少初学者看到格的定义就默认分配律成立——这是最大的误区。只满足基本公理的格完全不保证 ∨ 对 ∧ 的分配性。这里必须引入两个反例里程碑钻石格 M3 和五角格 N5。M3 是五个元素构成的结构一个底、一个顶中间夹着三个两两不可比的元素N5 是五个元素构成的一条链和一个分叉的组合。格论的经典定理说一个格是分配格当且仅当它里面不包含 M3 和 N5 作为子格。一个格是模格见 4.2当且仅当它不包含 N5。这两句话是你判断带公式时最强的武器——看见一个具体小格先找找里面有没有这两个禁品。4.2 模格比分配更宽松的高频结构模律长这样x ≤ z ⟹ x ∨ (y ∧ z) (x ∨ y) ∧ z。它只在 x ≤ z 时才要求成立因此比分配律弱。为什么要研究这个弱化版本因为群论中的子群格是模格但未必是分配格。子群格天然满足模律这被称为 Dedekind 模律。模格的意义在于很多在分配格中成立的漂亮结论在模格中依然有对应版本而子群格恰好落在这一档。如果说分配格是纪律严明的班级模格就是稍微宽松但仍有序的班级。在格论的层级谱系里布尔代数 ⊂ 分配格 ⊂ 模格 ⊂ 格每一级放宽一个条件就覆盖更多实际结构。4.3 完备格与不动点程序分析的武器如果格中每个子集——注意不只是二元集——都存在最小上界和最大下界就称为完备格。空集也要处理空集的最小上界是格的最小元 ⊥最大下界是最大元 ⊤。完备格必定有 ⊥ 和 ⊤这两个元素在程序分析里就是无信息和矛盾的顶。完备格在程序分析中地位极高因为静态分析的核心工具是 Tarski 不动点定理完备格上的单调函数一定有最小不动点和最大不动点。程序分析的基本套路是把程序状态抽象成一个完备格把每条语句的效果建模成格上的单调函数然后从 ⊥ 出发反复迭代最终收敛到最小不动点得到所有能到达状态的保守估计。这是我读论文时第一次通上电的地方原来格论不是束之高阁的抽象结构它直接就是编译器里数据流分析、程序验证的理论骨架。而且 Tarski 定理不要求函数连续、不要求格有限只要求完备格 单调函数适用范围极广——这就是为什么抽象解释领域几乎所有论文都围着它转。4.4 有补格与布尔代数一个具有最大元 ⊤ 和最小元 ⊥ 的格如果对每个元素 x 都存在 y 使得 x ∨ y ⊤ 且 x ∧ y ⊥就说这个格是有补格。布尔代数就是分配的有补格。集合代数、命题逻辑的 Lindenbaum–Tarski 代数都是布尔代数的代表。布尔代数最漂亮的一点是它把逻辑运算的语义完全代数化真值表里 0/1 的运算、集合的 ∪/∩/补集、命题的 ∨/∧/¬其实是同一个结构的三种不同实现。布尔代数的表示定理说每个布尔代数都同构于某个幂集代数的子代数。这个定理是格论中先写好结论再慢慢证明的经典范例也是理解布尔代数归根结底就是集合代数的钥匙。5. Lattice 的现实出场程序分析、格密码与概念格5.1 抽象解释用格给程序做静态分析抽象解释abstract interpretation是建立在格之上的一套程序分析大理论。核心思想是程序的真实语义通常活在一个巨大的状态空间上例如所有整型变量的所有可能取值直接计算不可行于是你构造一个抽象域——也就是一个格——把真实状态映射到更粗糙的抽象值上。举个简单例子符号值域分析里抽象值可能是 {负数, 零, 正数, 未定} 这四个元素按信息含量排成一个格底部是未定什么都不知道顶部是矛盾分析出错误中间三个互不可比。程序里每条语句的作用被定义成这个格上的单调函数整个程序的效果就是把这些函数依次复合再求最小不动点。学术语言叫用可计算的抽象语义逼近不可计算的具体语义。说人话就是用格给程序算一卦结果不保证精确但保证不遗漏任何可能的路径。这也是为什么现代编译器里的优化器、各种 lint 工具、程序验证器背后都站着一个格。5.2 格密码几何点阵走上后量子舞台这里的 Lattice 与序理论中的格是兄弟但不同路它指 R^n 中的一个离散加法子群可以理解成整系数线性组合生成的点阵也就是一个个整齐排列的格点。格密码lattice-based cryptography是目前后量子密码抵御量子计算机攻击的密码体制里最热门的候选方向之一。它依赖的困难问题是最短向量问题SVP和最近向量问题CVP给定一个高维格和一个目标点找出距离它最近的格点极难求解。有意思的是格密码在学术界受追捧是因为它的安全性有严格归约证明——可以从格上某个最坏情况困难问题归约到平均情况这让密码学家觉得心里有底。实际落地算法如 NTRU、Kyber 等底层都在反复操作这些点阵。我在这篇基础文里只点一句很多读者学完格论基础后最常问Lattice 到底有什么用格密码和程序分析就是两个最值得在入门阶段就埋下期待的答案。5.3 概念格让数据层级可视化形式概念分析FCA里有一个漂亮应用叫概念格给定一个对象集合 × 属性集合的二元关系可以诱导出一个格每个节点是一个形式概念——由一组对象和它们共同拥有的属性构成。概念格的边代表更一般/更特殊的层级。这个概念格描述了哪些属性组合可以同时出现在数据库、推荐系统、信息检索里都有应用。它最大的优点是极其直观你可以把一堆商品、顾客、标签数据直接画成一个格子图让没有数学背景的领域专家也能看懂数据里的层级结构。这也是格论从纯数学走向工程应用的又一证明——格不只是纸面上的抽象公理它还能当可视化工具用。6. 学格容易踩的坑以及我给初学者的三点建议6.1 最大的坑把 ∨ 当成 max我见过太多初学者把格里的 ∨ 无脑当成实数的 max把 ∧ 当成 min。它们在自然数全序上确实退化成 max/min但在任意格上完全不是一回事。特别是处理幂集格时∨ 是集合并∧ 是集合交根本不能用谁大谁小概括。这个直觉偏差会导致什么后果你会在验证分配律时完全想当然把分配律对所有格成立这种错误结论记进脑子里。正确做法是每验证一个公式先翻译成具体例子——子集、整除因子、命题逻辑——看它在这几个例子里到底在说什么再去判断公式的真假。符号本身永远不会告诉你直觉对不对实例才会。6.2 实用工具画图、反例与脚本枚举学习格的实操工具我推荐三件套手画哈斯图、纸笔推反例、写脚本枚举有限格。写脚本特别有用你可以从包含两三个元素的有限格出发把它们所有可能的运算表列出来检查某个猜想是否对每个结构都成立。我第一次验证模律比分配律弱这个说法就是写了个小脚本枚举 5 个元素以内的所有格统计哪些满足分配律、哪些只满足模律。过程虽然笨但几秒钟跑出来的结果比读十页教材都印象深刻。反例方面记住两个结构就够了——M3 和 N5。它们在证明分配律不是必然的、模律不是必然的时是万能弹药。任何XX性质是否推出 YY 性质的问题先拿这两个结构去撞一下。6.3 下一步阅读路线如果你读完这篇想继续深入我建议按下面这条路线走先把子格、格同态、格同构、格同余这些基本操作补齐——这些属于本系列第二部分的内容再学分配格表示定理每个有限分配格都同构于某个偏序集的全体序理想所成的格。这是格论进入结构理论的关键一步然后接触闭包算子和伽罗瓦连接Galois connection它们是抽象解释和形式概念分析里的核心工具最后按兴趣分支走代数方向去读布尔代数与 Heyting 代数直觉主义逻辑的代数语义走应用方向去读抽象解释、类型系统里的 join 半格或者转向格密码去啃 SVP/CVP 与 LLL 格基约化算法。说一点我自己的体会格论这门学科入门门槛其实不高难的是放下对数字大小的执念。一旦你接受元素可以不可比这件事并且养成先画图后推公式的习惯后面所有内容都会变得顺理成章。本系列下一篇会接着讲子格与格同态到时候我们再深入。
格论入门：从偏序集到程序分析与格密码
如果你去翻数学系或者计算机系的课表格Lattice通常是个薛定谔的存在——在离散数学里它出现在偏序关系之后在布尔代数之前不少老师只花两节课带过学生却在之后的抽象解释、模态逻辑、格密码论文里反复撞见它。我自己第一次真正被迫自学格论是读一篇程序静态分析的论文满篇都是完备格不动点单调函数当时只有一个念头这东西到底是什么鬼为什么编译器分析里全是它这篇是系列的第一篇按从偏序集出发 → 定义格 → 构造经典例子 → 认识格的优良性质 → 回到实际应用这条主线展开对标研究生入门课的第一讲。适合有三高等代数和基础离散数学背景、想系统补上格论这块拼图的读者也适合那些在论文里反复看到 Lattice、却一直没搞懂它和格子点阵有什么区别的朋友。下面每个概念我都会给出定义来源和为什么这样定义的理由尽量让你读完不是记住结论而是能自己推出来。1. 从偏序集看起格论的第一块基石1.1 为什么必须先建立偏序的概念任何一本格论教材都会告诉你格是一种特殊的偏序集。这句话听起来像废话但它其实在暗示一个重要方法论——格论不是在真空中定义出来的它的全部味道都来自怎么把集合里的元素排出层次感。偏序集poset就是集合 P 配上二元关系 ≤满足三条公理自反性对任意 x有 x ≤ x、反对称性x ≤ y 且 y ≤ x 则 x y、传递性x ≤ y 且 y ≤ z 则 x ≤ z。这三条公理里反对称性最容易被新手忽略。它保证了偏序不会出现你比我大、我比你大但咱俩还不是同一个元素的死循环自反性保证每个元素至少和自己可比传递性负责把排名一级一级传下去。为什么偏偏是这三条你可以把偏序想象成公司里的汇报关系谁能向谁汇报是多对一的不是所有人都能互相比较——一个程序员和一个产品经理谁级别高要看组织架构图不能简单比职级数字——但任何一条汇报链都不会成环也不会出现两个不同的人互相汇报。这就是反对称性的现实意义。1.2 哈斯图把序关系画出来光有定义是不够的。偏序集的命根子是可视化因为它太抽象了。哈斯图Hasse diagram就是用一个无向图的点表示元素按下小上大的规则摆放然后只画覆盖关系。什么叫覆盖a 覆盖 b记作 b ⋖ a表示 b a且不存在 c 使得 b c a。画图时把所有传递关系省略只保留覆盖边。这一招非常实用画一个偏序集之前先花一分钟列出所有的覆盖对能避免画出一堆冗余连线。我自己的经验是学格论的头两周笔不要离开草稿纸。遇到一个新概念先画一个具体的偏序集然后反复问自己在这个例子里这个定义到底在说什么哈斯图画多了你会慢慢形成一种直觉——看见一个格脑子里会自动浮现它的形状不需要每次都从公理推起。1.3 全序与偏序别把比较大小想窄了很多初学者默认 ≤ 就是实数的小于等于。如果你带着这个惯性读格论会在后面的整除格那里被狠狠教育一顿。偏序里的 ≤ 是抽象关系换到不同领域可以是集合的包含 ⊆整除关系 |逻辑蕴含 →程序抽象值域的偏序 ⊑。它们都满足那三条公理但表现形式完全不同。格论的价值恰恰在于把所有这些看起来不相关的序关系统一起来用同一套语言讨论。这就像你突然发现工资条排名体育积分榜图书馆书目分类其实是同一种数学结构的化身这种统一性就是格论的美感所在。2. 格的两种定义序视角与代数视角2.1 序理论定义上确界与下确界定了偏序集我们一步步逼近格的定义。对于集合 P 的子集 S如果存在元素 u 使得对所有 s ∈ S 都有 s ≤ u就称 u 是 S 的一个上界。注意上界不唯一——一个子集可能有一大堆上界。在所有上界中如果存在一个最小的记作 sup S 或 ∨S就称为最小上界也叫上确界对称地下界中最大的记作 inf S 或 ∧S称为最大下界、下确界。格的序理论定义来了一个偏序集 (L, ≤)如果其中任意两个元素 x、y 都存在最小上界 x ∨ y 和最大下界 x ∧ y那么这个偏序集就是一个格。必须强调的是任意两个元素——这是格与一般偏序集的关键区别。有些偏序集对某些子集有确界对其他子集没有那它就不是格。如果要求的是每个非空子集都有确界那就是更高阶的完备格我们到 4.3 节再展开。一个常见困惑是那单元素集合的 sup 和 inf 是什么很简单就是它本身。空集的 sup 和 inf 则不一定存在这直接引出了完备格中的 ⊥ 和 ⊤。2.2 代数定义并运算与交运算格还可以换个视角定义一个集合 L 配上两个二元运算 ∨并和 ∧交满足四条公理交换律x ∨ y y ∨ xx ∧ y y ∧ x结合律x ∨ (y ∨ z) (x ∨ y) ∨ zx ∧ (y ∧ z) (x ∧ y) ∧ z吸收律x ∨ (x ∧ y) xx ∧ (x ∨ y) x幂等律x ∨ x xx ∧ x x。这个定义完全是代数式的看起来和序关系八竿子打不着。但吸收律是分水岭——它的作用在于让交换律和结合律不至于退化成纯粹的对称运算而是真正确立了某种序。你可以试着在一组没有吸收律的运算上展开得到的结构会失控地膨大。吸收律的本质是截断无论 x ∧ y 多么小x 和它取并之后结果永远回到 x。这正是序关系夹在中间的代数体现。这里多提一句幂等律其实可以由吸收律推导出来。把吸收律中第一个公式的 y 换成 x ∨ y经过交换律和结合律运算可以推出 x ∨ x x。所以严格的教材里有时只列交换、结合、吸收三组公理但初学者列全四条更保险不容易绕晕。2.3 两种定义为什么殊途同归这两个定义是等价的若 (L, ≤) 按序定义是格可以令 x ∨ y sup{x, y}x ∧ y inf{x, y}然后验证四条代数公理成立反过来若 (L, ∨, ∧) 按代数定义是格可以定义 x ≤ y 当且仅当 x ∨ y y等价地x ∧ y x然后验证它是偏序并且 ∨ 恰好是最小上界、∧ 恰好是最大下界。为什么我要花一整节讲这个等价性因为在实际工作中两个视角各有用途序视角适合证明格的性质因为它能画图、有直觉代数视角适合做计算因为运算可以直接写进程序里。我做程序分析相关工作时处理类型系统里的 join 逻辑几乎全用代数视角而在思考这个类型格到底长什么样时又切回序视角。两种定义切换得像左右手一样熟练才算真正进了格论的门。3. 先别抽象看看格的三个经典实例3.1 幂集格信息合并的原型设 S {a, b, c}考虑它的所有子集构成的集合 2^S配上集合包含 ⊆。任意两个子集 A、B 的最小上界是 A ∪ B最大下界是 A ∩ B。因此这是一个格称为幂集格。这个例子为什么重要因为它是理解几乎所有格的原型你可以把格里的元素想成信息量把 ∨ 想成合并信息把 ∧ 想成提取公共信息。这套解释在程序分析里直接对应着路径合并和取交集——后面 5.1 节会用到。另外注意幂集格有最大元 S 和最小元 ∅且每个元素都有补集。它是一个布尔格见 4.4也是初学者最容易想象、最容易验证各种公式的试验场。任何关于格的性质先拿到 2^S 上试一遍通常能立刻看出对不对。3.2 整除格数论里的 lcm 与 gcd取自然数 n考虑它的所有正因子集合 D_n {d : d | n}序关系定义为整除。比如 n 12 时D12 {1, 2, 3, 4, 6, 12}。任意两个因子 a、b 在整除关系下的最小上界是它们的最小公倍数 lcm(a, b)——它一定是 n 的因子最大下界是最大公约数 gcd(a, b)。因此 (D_n, |) 构成格称为整除格。注意这里 lcm 和 gcd 在代数定义中扮演的角色正好对应着幂集格里的 ∪ 和 ∩。这说明格的概念不是孤立玩具在数论里就有深刻对应。顺着这个例子还能引出一个经典问题什么时候 D_n 是分配格答案是 n 无平方因子。也就是说n 12 2² × 3 时 D12 不是分配格但 n 30 2 × 3 × 5 时 D30 是分配格。这种结构性质跟着数论性质走的现象是格论最迷人的地方之一。3.3 划分格与子群格从组合到群论第三个经典例子稍微进阶一点集合 S 的所有划分配上加细关系 ≤定义划分 A ≤ 划分 B 当且仅当 A 的每个块都包含于 B 的某个块。两个划分的最小上界是共同加细取块的并集后不断拆分使满足划分公理最大下界是共同细分取每个块的块内交叠。这个格叫划分格结构比幂集格复杂得多。划分格在群论里有对应物给定群 G它的全体子群按包含构成子群格。很多群论定理其实都在和这个格打交道。比如 Lagrange 定理说若 H 是 G 的子群则 |H| 整除 |G|——在子群格视角下这相当于在两个层级节点之间标注了数值比例。再比如正规子群在子群格里的地位特殊正规子群的集合配上某种运算可以继续构成格结构。学会用格的语言读这些定理你会发现很多看似分散的结论突然被一根线串起来了。4. 格的优良性质分配律、模律与完备性逐级解锁4.1 分配格加在分布上的强假设一个格如果额外满足分配律x ∧ (y ∨ z) (x ∧ y) ∨ (x ∧ z)x ∨ (y ∧ z) (x ∨ y) ∧ (x ∨ z)就叫分配格。经典事实是在格中这两条分配律互为充要条件证明一个就能推出另一个不需要两条都验证。幂集格是分配格整除格当 n 无平方因子时也是分配格。分配格最伟大的地方在于它保证了格再往下走可以退化出布尔代数一旦缺少分配律你就完全不能把 ∨ 和 ∧ 当成集合的 ∪ 和 ∩ 来用。我见过不少初学者看到格的定义就默认分配律成立——这是最大的误区。只满足基本公理的格完全不保证 ∨ 对 ∧ 的分配性。这里必须引入两个反例里程碑钻石格 M3 和五角格 N5。M3 是五个元素构成的结构一个底、一个顶中间夹着三个两两不可比的元素N5 是五个元素构成的一条链和一个分叉的组合。格论的经典定理说一个格是分配格当且仅当它里面不包含 M3 和 N5 作为子格。一个格是模格见 4.2当且仅当它不包含 N5。这两句话是你判断带公式时最强的武器——看见一个具体小格先找找里面有没有这两个禁品。4.2 模格比分配更宽松的高频结构模律长这样x ≤ z ⟹ x ∨ (y ∧ z) (x ∨ y) ∧ z。它只在 x ≤ z 时才要求成立因此比分配律弱。为什么要研究这个弱化版本因为群论中的子群格是模格但未必是分配格。子群格天然满足模律这被称为 Dedekind 模律。模格的意义在于很多在分配格中成立的漂亮结论在模格中依然有对应版本而子群格恰好落在这一档。如果说分配格是纪律严明的班级模格就是稍微宽松但仍有序的班级。在格论的层级谱系里布尔代数 ⊂ 分配格 ⊂ 模格 ⊂ 格每一级放宽一个条件就覆盖更多实际结构。4.3 完备格与不动点程序分析的武器如果格中每个子集——注意不只是二元集——都存在最小上界和最大下界就称为完备格。空集也要处理空集的最小上界是格的最小元 ⊥最大下界是最大元 ⊤。完备格必定有 ⊥ 和 ⊤这两个元素在程序分析里就是无信息和矛盾的顶。完备格在程序分析中地位极高因为静态分析的核心工具是 Tarski 不动点定理完备格上的单调函数一定有最小不动点和最大不动点。程序分析的基本套路是把程序状态抽象成一个完备格把每条语句的效果建模成格上的单调函数然后从 ⊥ 出发反复迭代最终收敛到最小不动点得到所有能到达状态的保守估计。这是我读论文时第一次通上电的地方原来格论不是束之高阁的抽象结构它直接就是编译器里数据流分析、程序验证的理论骨架。而且 Tarski 定理不要求函数连续、不要求格有限只要求完备格 单调函数适用范围极广——这就是为什么抽象解释领域几乎所有论文都围着它转。4.4 有补格与布尔代数一个具有最大元 ⊤ 和最小元 ⊥ 的格如果对每个元素 x 都存在 y 使得 x ∨ y ⊤ 且 x ∧ y ⊥就说这个格是有补格。布尔代数就是分配的有补格。集合代数、命题逻辑的 Lindenbaum–Tarski 代数都是布尔代数的代表。布尔代数最漂亮的一点是它把逻辑运算的语义完全代数化真值表里 0/1 的运算、集合的 ∪/∩/补集、命题的 ∨/∧/¬其实是同一个结构的三种不同实现。布尔代数的表示定理说每个布尔代数都同构于某个幂集代数的子代数。这个定理是格论中先写好结论再慢慢证明的经典范例也是理解布尔代数归根结底就是集合代数的钥匙。5. Lattice 的现实出场程序分析、格密码与概念格5.1 抽象解释用格给程序做静态分析抽象解释abstract interpretation是建立在格之上的一套程序分析大理论。核心思想是程序的真实语义通常活在一个巨大的状态空间上例如所有整型变量的所有可能取值直接计算不可行于是你构造一个抽象域——也就是一个格——把真实状态映射到更粗糙的抽象值上。举个简单例子符号值域分析里抽象值可能是 {负数, 零, 正数, 未定} 这四个元素按信息含量排成一个格底部是未定什么都不知道顶部是矛盾分析出错误中间三个互不可比。程序里每条语句的作用被定义成这个格上的单调函数整个程序的效果就是把这些函数依次复合再求最小不动点。学术语言叫用可计算的抽象语义逼近不可计算的具体语义。说人话就是用格给程序算一卦结果不保证精确但保证不遗漏任何可能的路径。这也是为什么现代编译器里的优化器、各种 lint 工具、程序验证器背后都站着一个格。5.2 格密码几何点阵走上后量子舞台这里的 Lattice 与序理论中的格是兄弟但不同路它指 R^n 中的一个离散加法子群可以理解成整系数线性组合生成的点阵也就是一个个整齐排列的格点。格密码lattice-based cryptography是目前后量子密码抵御量子计算机攻击的密码体制里最热门的候选方向之一。它依赖的困难问题是最短向量问题SVP和最近向量问题CVP给定一个高维格和一个目标点找出距离它最近的格点极难求解。有意思的是格密码在学术界受追捧是因为它的安全性有严格归约证明——可以从格上某个最坏情况困难问题归约到平均情况这让密码学家觉得心里有底。实际落地算法如 NTRU、Kyber 等底层都在反复操作这些点阵。我在这篇基础文里只点一句很多读者学完格论基础后最常问Lattice 到底有什么用格密码和程序分析就是两个最值得在入门阶段就埋下期待的答案。5.3 概念格让数据层级可视化形式概念分析FCA里有一个漂亮应用叫概念格给定一个对象集合 × 属性集合的二元关系可以诱导出一个格每个节点是一个形式概念——由一组对象和它们共同拥有的属性构成。概念格的边代表更一般/更特殊的层级。这个概念格描述了哪些属性组合可以同时出现在数据库、推荐系统、信息检索里都有应用。它最大的优点是极其直观你可以把一堆商品、顾客、标签数据直接画成一个格子图让没有数学背景的领域专家也能看懂数据里的层级结构。这也是格论从纯数学走向工程应用的又一证明——格不只是纸面上的抽象公理它还能当可视化工具用。6. 学格容易踩的坑以及我给初学者的三点建议6.1 最大的坑把 ∨ 当成 max我见过太多初学者把格里的 ∨ 无脑当成实数的 max把 ∧ 当成 min。它们在自然数全序上确实退化成 max/min但在任意格上完全不是一回事。特别是处理幂集格时∨ 是集合并∧ 是集合交根本不能用谁大谁小概括。这个直觉偏差会导致什么后果你会在验证分配律时完全想当然把分配律对所有格成立这种错误结论记进脑子里。正确做法是每验证一个公式先翻译成具体例子——子集、整除因子、命题逻辑——看它在这几个例子里到底在说什么再去判断公式的真假。符号本身永远不会告诉你直觉对不对实例才会。6.2 实用工具画图、反例与脚本枚举学习格的实操工具我推荐三件套手画哈斯图、纸笔推反例、写脚本枚举有限格。写脚本特别有用你可以从包含两三个元素的有限格出发把它们所有可能的运算表列出来检查某个猜想是否对每个结构都成立。我第一次验证模律比分配律弱这个说法就是写了个小脚本枚举 5 个元素以内的所有格统计哪些满足分配律、哪些只满足模律。过程虽然笨但几秒钟跑出来的结果比读十页教材都印象深刻。反例方面记住两个结构就够了——M3 和 N5。它们在证明分配律不是必然的、模律不是必然的时是万能弹药。任何XX性质是否推出 YY 性质的问题先拿这两个结构去撞一下。6.3 下一步阅读路线如果你读完这篇想继续深入我建议按下面这条路线走先把子格、格同态、格同构、格同余这些基本操作补齐——这些属于本系列第二部分的内容再学分配格表示定理每个有限分配格都同构于某个偏序集的全体序理想所成的格。这是格论进入结构理论的关键一步然后接触闭包算子和伽罗瓦连接Galois connection它们是抽象解释和形式概念分析里的核心工具最后按兴趣分支走代数方向去读布尔代数与 Heyting 代数直觉主义逻辑的代数语义走应用方向去读抽象解释、类型系统里的 join 半格或者转向格密码去啃 SVP/CVP 与 LLL 格基约化算法。说一点我自己的体会格论这门学科入门门槛其实不高难的是放下对数字大小的执念。一旦你接受元素可以不可比这件事并且养成先画图后推公式的习惯后面所有内容都会变得顺理成章。本系列下一篇会接着讲子格与格同态到时候我们再深入。
