归纳模型检查与k-induction

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

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

本节专属对象

基例检查前k步，归纳步假设连续k状态安全并证下一状态安全。。把对象分成真实需求、形式规约、程序/模型状态、执行关系、证明义务和工具结果。每一层都要有版本与映射；工具显示绿色只说明它在当前编码和假设下没有找到违反，不能自动补上遗漏的需求或错误的模型。

公式或规则怎样成立

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

老师带着算完例子

1-induction失败可能是归纳假设太弱；加入辅助不变量后可成功。。这个例子给出了输入、推导中间量和结论。现在只改一个条件，先预测三元组、状态集合、验证条件或时序性质会变强、变弱还是失效，然后重新计算。方向不对时，依次检查蕴含方向、替换的新旧值、量词作用域、路径条件、状态可达性和内存/整数语义。

把证明拆成能审计的行

围绕“归纳模型检查与k-induction”至少写四行：第一行写程序或状态机与语义；第二行写前置、后置、不变量或时序性质；第三行按“Base_k ∧ Step_k。”生成局部义务；第四行给有效证明、满足模型或反例路径。每行标明使用的假设和规则，并用“1-induction失败可能是归纳假设太弱；加入辅助不变量后可成功。”逐项代入。只写“显然”“工具通过”或最后布尔值均不合格。

完成正向推导后做两次反查。先从结论向后找到具体规则、约束、状态和源代码位置；再从源输入向前重放执行、调度或模型路径，确认首次偏差。最后注入“归纳步反例直接当真实系统反例。”，判断它是真实缺陷、规约漏洞、模型偏差、证明不够强还是工具边界。

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

分别输出基例和归纳反例，判断是真路径还是不可达状态。。实现时输出AST/CFG、路径条件、验证条件、求解状态、模型、不可满足核、反例状态或证明项，而不是只输出PASS。保存工具与求解器版本、参数、超时、随机种子和可信计算基，让另一个环境能够重放。

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

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

本节报告至少保留规约、程序/模型hash、全部假设、生成的义务、中间证据、结果和运行成本。手算“1-induction失败可能是归纳假设太弱；加入辅助不变量后可成功。”校验工具编码，再用“归纳步反例直接当真实系统反例。”检查失败行为。库和求解器可以使用，但必须把valid、invalid、unknown、timeout和crash分成不同结果。

最短失败反例

本节边界是：归纳步反例直接当真实系统反例。。构造最小程序、状态或约束使问题出现，指出被破坏的规则或假设，并给修正后的规约、代码或证明义务。反例必须能回放；若只能看到抽象内部变量，要继续映射回学生能理解的输入和执行步骤。

在线练习与闭卷自检

本节绑定单选、多选、计算和严格证明题；章节另有可运行Python验证算法，每题至少四组测试。闭卷重建五项：对象“基例检查前k步，归纳步假设连续k状态安全并证下一状态安全。”；核心关系“Base_k ∧ Step_k。”；算完例题“1-induction失败可能是归纳假设太弱；加入辅助不变量后可成功。”；验证流程；失败边界“归纳步反例直接当真实系统反例。”。缺任一项，就还没有把“证明”接到真实程序上。