用Lean证明加法器:软件工程师指南

Anatomy of a Lean proof for software engineers

我最近尝试将计算理论教材中关于有限自动机的经典问题,用Lean语言进行了形式化证明。文章从DFA和正则语言的基础讲起,展示了如何构建一个加法器DFA来验证二进制加法性质。关键在于利用语言反转的闭包性质,将难以直接处理的从左到右读取问题,转化为从低位到高位处理的加法逻辑。通过拆解Lean证明的每一步,包括不变量、归纳步骤和状态转移,希望能帮助软件工程师理解形式化验证的核心思路,让抽象的数学证明变得像编写代码一样直观。

我尝试让这篇文章易于理解,如果你熟悉现代静态类型编程语言、二进制算术、基本命题逻辑和归纳证明,应该就能跟上思路。
  1. thom

    所以这一切都很棒,但既然我们被要求接受那些超过 50 万行、能通过检查却可能隐藏着重大语义错误的 Lean 证明,那么计划是什么?尽管运行时做出了出色且稳健的承诺,这些证明似乎仍然是极其脆弱的软件产物。

  2. WalterGR

    楼主:你的文章里显示的是“[Contents]”,这里应该显示目录才对。

  3. woggy

    我很好奇人们能否主要将 Lean 用作软件规范语言,而不一定非要证明所有内容。

    我们能否用它来规范模块的含义和定律,使设计更精确且可验证,并允许我们在实现中为这些定律编写基于属性的测试?这样,Lean 就成了帮助我们更精确地思考设计的工具。

同日更多故事

2026-10-02