闭卷重建选题、命题与定义冻结的对象、状态、事件、不变量与一个失败反例。
离散数学与证明方法 · 小纸条
选一章打印。双面打印(按长边翻页)后沿虚线剪开,每张卡片正面题目、背面答案。
闭卷重建小规模枚举与反例发现的对象、状态、事件、不变量与一个失败反例。
闭卷重建引理分解与依赖图的对象、状态、事件、不变量与一个失败反例。
闭卷重建选择证明策略的对象、状态、事件、不变量与一个失败反例。
闭卷重建代码验证与形式证明对照的对象、状态、事件、不变量与一个失败反例。
闭卷重建严格写作、同伴审阅与修订的对象、状态、事件、不变量与一个失败反例。
闭卷重建答辩:从猜想到定理的对象、状态、事件、不变量与一个失败反例。
核心机制:小规模枚举与反例发现的核心是:用程序生成小对象、检查猜想、保存首个反例并据此修订命题;必须把对象类型、量词、构造或算法不变量和结论同时写清;实验入口:为小规模枚举与反例发现手推最小正常例、边界例和反例,再用有限枚举或结构验证器核对中间状态;边界:验证到n=12不能证明所有n,程序本身也需测试。
核心机制:选题、命题与定义冻结的核心是:把研究问题改写成精确命题,列对象、量词、假设、结论和非目标;必须把对象类型、量词、构造或算法不变量和结论同时写清;实验入口:为选题、命题与定义冻结手推最小正常例、边界例和反例,再用有限枚举或结构验证器核对中间状态;边界:项目中途偷换图类型、概率空间或复杂度口径会让证明失效。
核心机制:选择证明策略的核心是:根据量词与结构选择双射、归纳、反证、极值、概率或归约;必须把对象类型、量词、构造或算法不变量和结论同时写清;实验入口:为选择证明策略手推最小正常例、边界例和反例,再用有限枚举或结构验证器核对中间状态;边界:方法名不是证明,必须解释为何满足该方法前提。
核心机制:引理分解与依赖图的核心是:把主定理拆成可独立验收的引理,画无循环依赖图并标接口;必须把对象类型、量词、构造或算法不变量和结论同时写清;实验入口:为引理分解与依赖图手推最小正常例、边界例和反例,再用有限枚举或结构验证器核对中间状态;边界:多个引理都引用主定理会形成循环论证。
核心机制:严格写作、同伴审阅与修订的核心是:定义先行、符号一致、每步有依据、反例和适用范围明确,并记录审阅修订;必须把对象类型、量词、构造或算法不变量和结论同时写清;实验入口:为严格写作、同伴审阅与修订手推最小正常例、边界例和反例,再用有限枚举或结构验证器核对中间状态;边界:读者猜得出不等于证明写全,图示不能替代关键量词。
核心机制:代码验证与形式证明对照的核心是:将枚举器输出与证明中的对象、映射和不变量逐项对应;必须把对象类型、量词、构造或算法不变量和结论同时写清;实验入口:为代码验证与形式证明对照手推最小正常例、边界例和反例,再用有限枚举或结构验证器核对中间状态;边界:代码浮点、哈希顺序和边界约定可能与数学模型不同。
核心机制:答辩:从猜想到定理的核心是:提交命题版本史、实验、反例、引理链、主证明、复杂度与限制并接受现场变式;必须把对象类型、量词、构造或算法不变量和结论同时写清;实验入口:为答辩:从猜想到定理手推最小正常例、边界例和反例,再用有限枚举或结构验证器核对中间状态;边界:只展示最终正确稿会丢失可复核的发现过程。