排列、排序与多重集合

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

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

本节专属对象

排序证明需要有序性和元素守恒两部分；仅有序会允许丢元素。。把对象分成真实需求、形式规约、程序/模型状态、执行关系、证明义务和工具结果。每一层都要有版本与映射；工具显示绿色只说明它在当前编码和假设下没有找到违反，不能自动补上遗漏的需求或错误的模型。

公式或规则怎样成立

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

老师带着算完例子

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

把证明拆成能审计的行

围绕“排列、排序与多重集合”至少写四行：第一行写程序或状态机与语义；第二行写前置、后置、不变量或时序性质；第三行按“sorted(out) ∧ multiset(out)=multiset(in)。”生成局部义务；第四行给有效证明、满足模型或反例路径。每行标明使用的假设和规则，并用“输入[2,1,2]输出[1,2,2]两性质均满足；[1,2]只满足有序。”逐项代入。只写“显然”“工具通过”或最后布尔值均不合格。

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

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

分开证明局部有序、不变量和交换保持多重集合。。实现时输出AST/CFG、路径条件、验证条件、求解状态、模型、不可满足核、反例状态或证明项，而不是只输出PASS。保存工具与求解器版本、参数、超时、随机种子和可信计算基，让另一个环境能够重放。

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

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

本节报告至少保留规约、程序/模型hash、全部假设、生成的义务、中间证据、结果和运行成本。手算“输入[2,1,2]输出[1,2,2]两性质均满足；[1,2]只满足有序。”校验工具编码，再用“把集合代替多重集合丢掉重复计数。”检查失败行为。库和求解器可以使用，但必须把valid、invalid、unknown、timeout和crash分成不同结果。

最短失败反例

本节边界是：把集合代替多重集合丢掉重复计数。。构造最小程序、状态或约束使问题出现，指出被破坏的规则或假设，并给修正后的规约、代码或证明义务。反例必须能回放；若只能看到抽象内部变量，要继续映射回学生能理解的输入和执行步骤。

在线练习与闭卷自检

本节绑定单选、多选、计算和严格证明题；章节另有可运行Python验证算法，每题至少四组测试。闭卷重建五项：对象“排序证明需要有序性和元素守恒两部分；仅有序会允许丢元素。”；核心关系“sorted(out) ∧ multiset(out)=multiset(in)。”；算完例题“输入[2,1,2]输出[1,2,2]两性质均满足；[1,2]只满足有序。”；验证流程；失败边界“把集合代替多重集合丢掉重复计数。”。缺任一项，就还没有把“证明”接到真实程序上。