3.2 反例、反证与存在性：知道该找一个还是排除全部
证明“所有输入都安全”和推翻它，工作量完全不同。全称命题需要覆盖整个范围；要推翻它，只需找到一个满足前提却违反结论的对象。选错证明目标，会把简单问题做得很难。
量词决定证据形状
| 命题 | 证明需要 | 推翻需要 |
|---|---|---|
∀x P(x) | 任意 x 的通用证明 | 一个 x 使 ¬P(x) |
∃x P(x) | 一个具体见证 | 证明任意 x 都不满足 P |
∃!x P(x) | 存在 + 唯一 | 不存在，或至少两个不同见证 |
看到命题后先圈出量词，再决定要构造对象还是建立通用推理。
反例必须命中前提
命题：
对任意整数 n，若 n 为质数，则 n 为奇数。反例 n=2：它满足前提“质数”，却不满足结论“奇数”。
n=4 不是反例，因为它根本不满足前提。程序测试中也一样：若要反驳“所有合法请求都不会返回 500”，必须提供一个合法请求导致 500；畸形请求得到 500 只说明另一个性质可能有问题。
反例还要使用题目规定的域。对“所有实数”成立与对“所有整数”成立是不同命题。
构造性存在证明：给出见证
证明：存在一个大于 10 的偶质数平方。
可以给出 4 的平方 16，并验证：
4 是偶数；
4 不是质数。这个见证不满足“偶质数”的要求，所以证明失败。真正的偶质数只有 2，其平方为 4，又不大于 10，因此原命题其实为假。
这个故意失败的例子说明：见证必须逐项满足公式中的每个条件，不能只“看起来接近”。
换一个成立命题：存在两个无理数 a,b，使 a^b 为有理数。一个经典的非构造思路是考虑：
x = (√2)^(√2)- 若
x有理，则取a=b=√2； - 若
x无理，则取a=x, b=√2，此时a^b=2。
这个分类证明说明某个见证存在，但没有先确定落在哪一支。若需要实际计算对象，构造性证明通常更有用。
唯一性分成两半
证明“存在唯一的 x 满足 P(x)”：
- 存在性：构造一个
x₀并证明P(x₀)； - 至多一个：假设
P(x)与P(y)都成立，推出x=y。
例如线性方程 ax+b=0 在 a≠0 时有唯一实数解：
- 存在：
x₀=-b/a，代入成立； - 唯一：若
ax+b=0且ay+b=0，相减得a(x-y)=0，由a≠0得x=y。
数据库唯一约束也包含相似思想：必须先有一条记录，唯一约束本身只保证“至多一条”，不保证存在。
反证法：假设结论为假并导出矛盾
证明 √2 不是有理数。假设相反，存在互质正整数 p,q：
√2 = p/q平方得：
p² = 2q²所以 p² 偶，进而 p 偶。设 p=2k，代回：
4k²=2q²
q²=2k²于是 q 也偶，与 p,q 互质矛盾。故假设不成立。
这里真正的矛盾是“p,q 互质”与“二者都有公因子 2”同时成立，而不是“结果看着不合理”。
何时用反证，何时用逆否
要证 p→q：
- 逆否法假设
¬q，目标是推出¬p； - 反证法假设
p∧¬q，目标是推出任意明确矛盾。
若 ¬q 能自然转化为结构信息，逆否法通常更直接。若结论是否定存在、无理性或不可能性，反证法常更顺手。方法没有高低，选择能让假设最有信息量的一种。
常见无效推理
肯定后件
p→q
q
所以 p // 无效服务宕机会触发告警；现在有告警，不代表一定是服务宕机，也可能是探针故障。
否定前件
p→q
¬p
所以 ¬q // 无效通过缓存会加快响应；没走缓存，不代表响应一定慢。
循环论证
把结论换个说法当作前提。例如“这个函数无副作用，因为它是纯函数”，若“纯函数”正是待证性质，就没有提供新依据。
从有限样例推出全称结论
一千次测试通过能增加信心，也能覆盖重要场景，但除非输入域已被穷尽，不能单独推出“所有输入都成立”。反过来，一次有效失败足以推翻全称命题。
隐含除零或越界操作
代数推导中两边除以 x-y 前必须证明 x≠y。程序证明中读取 a[i] 前也必须有边界条件。非法操作会让后续推导失去意义。
把反例缩小
找到失败输入后，尽量缩成仍能触发问题的最小反例：
- 删除无关字段；
- 缩短序列；
- 降低数值；
- 减少并发参与者；
- 固定随机种子和执行顺序。
最小反例能暴露错误规则，也更适合加入回归测试。属性测试工具的 shrinking 正是在自动做这件事。
完成检查
- 推翻“两个无理数之和一定无理”；
- 为“存在一个整数，其平方等于自身”给出两个见证；
- 证明方程
3x+6=0有唯一实数解； - 用反证法证明不存在最大的整数；
- 为一个生产故障写出最小反例，并说明它满足被反驳性质的所有前提。