终止变式与良基关系

从一个“已经测过”的程序开始

程序跑过样例并不等于性质已经成立。本节研究 终止变式与良基关系：先明确我们要对哪个程序、模型或状态机，证明哪一条性质，在什么输入、环境、调度和数值语义下成立。形式化不是把自然语言换成符号，而是把可以被反例推翻的主张写到足够精确。

本节专属对象

变式在循环中取良基集合值并每轮严格下降，证明不能无限执行。。把对象分成真实需求、形式规约、程序/模型状态、执行关系、证明义务和工具结果。每一层都要有版本与映射；工具显示绿色只说明它在当前编码和假设下没有找到违反，不能自动补上遗漏的需求或错误的模型。

公式或规则怎样成立

核心关系是：I∧b⇒V≥0 ∧ V′<V。。逐项说明符号的域、量词、前后状态、终止口径和数值模型，再从定义或推理规则推出结论。若求解器返回unknown、模型含未定义行为、循环缺少不变量、并发缺少公平假设或规格本身不可满足，应明确停止，不能把异常分支算成证明成功。

老师带着算完例子

i从0增到n，V=n−i；n=5,i=2时V=3，下一轮2。。这个例子给出了输入、推导中间量和结论。现在只改一个条件，先预测三元组、状态集合、验证条件或时序性质会变强、变弱还是失效，然后重新计算。方向不对时，依次检查蕴含方向、替换的新旧值、量词作用域、路径条件、状态可达性和内存/整数语义。

把证明拆成能审计的行

围绕“终止变式与良基关系”至少写四行：第一行写程序或状态机与语义；第二行写前置、后置、不变量或时序性质；第三行按“I∧b⇒V≥0 ∧ V′<V。”生成局部义务；第四行给有效证明、满足模型或反例路径。每行标明使用的假设和规则，并用“i从0增到n，V=n−i；n=5,i=2时V=3，下一轮2。”逐项代入。只写“显然”“工具通过”或最后布尔值均不合格。

完成正向推导后做两次反查。先从结论向后找到具体规则、约束、状态和源代码位置；再从源输入向前重放执行、调度或模型路径，确认首次偏差。最后注入“只证不增而非严格下降；自然数下界遗漏。”，判断它是真实缺陷、规约漏洞、模型偏差、证明不够强还是工具边界。

落到工具可执行的验证流程

写下界、严格下降和整数/字典序域，测试停滞分支。。实现时输出AST/CFG、路径条件、验证条件、求解状态、模型、不可满足核、反例状态或证明项，而不是只输出PASS。保存工具与求解器版本、参数、超时、随机种子和可信计算基，让另一个环境能够重放。

复杂度、可信边界与系统连接

分析“终止变式与良基关系”主要受路径数、状态数、变量域、公式规模、量词实例、BDD节点、抽象域高度或并发交错中的哪个量控制。小例证明编码语义，规模实验说明成本，失败注入说明边界。再把本节接到需求—规约—模型—实现—编译—运行环境证据链，指出哪些环节已证明、哪些仍靠测试或人工评审。

本节报告至少保留规约、程序/模型hash、全部假设、生成的义务、中间证据、结果和运行成本。手算“i从0增到n，V=n−i；n=5,i=2时V=3，下一轮2。”校验工具编码，再用“只证不增而非严格下降；自然数下界遗漏。”检查失败行为。库和求解器可以使用，但必须把valid、invalid、unknown、timeout和crash分成不同结果。

最短失败反例

本节边界是：只证不增而非严格下降；自然数下界遗漏。。构造最小程序、状态或约束使问题出现，指出被破坏的规则或假设，并给修正后的规约、代码或证明义务。反例必须能回放；若只能看到抽象内部变量，要继续映射回学生能理解的输入和执行步骤。

在线练习与闭卷自检

本节绑定单选、多选、计算和严格证明题；章节另有可运行Python验证算法，每题至少四组测试。闭卷重建五项：对象“变式在循环中取良基集合值并每轮严格下降，证明不能无限执行。”；核心关系“I∧b⇒V≥0 ∧ V′<V。”；算完例题“i从0增到n，V=n−i；n=5,i=2时V=3，下一轮2。”；验证流程；失败边界“只证不增而非严格下降；自然数下界遗漏。”。缺任一项，就还没有把“证明”接到真实程序上。