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，因此原命题其实为假。

这个故意失败的例子说明：见证必须逐项满足公式中的每个条件，不能只“看起来接近”。

一个成立的构造性例子是：对每个整数 n，存在比它大的偶数 m。取 m=2|n|+2，它显然是 2 的整数倍，且 m≥|n|+2>n，所以同一构造对正数、零和负数都成立。给出见证后，仍需验证前提覆盖的所有情况。

换一个成立命题：存在两个无理数 a,b，使 a^b 为有理数。一个经典的非构造思路是考虑：

x = (√2)^(√2)

• 若 x 有理，则取 a=b=√2；
• 若 x 无理，则取 a=x, b=√2，此时 a^b=2。

这个分类证明说明某个见证存在，但没有先确定落在哪一支。若需要实际计算对象，构造性证明通常更有用。

唯一性分成两半

证明“存在唯一的 x 满足 P(x)”：

1. 存在性：构造一个 x₀ 并证明 P(x₀)；
2. 至多一个：假设 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。

数据库非空键的唯一约束只保证“每个键值至多一行”，不保证某个指定键已经有记录。若允许 NULL，还应核对数据库对 NULL 与唯一性的具体约定，不能把数学上的“存在且唯一”直接等同于加一个 UNIQUE。

反证法：假设结论为假并导出矛盾

证明 √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 会尝试简化输入，但“某种删减策略下不能再缩小”不一定是所有度量下的全局最小。并发故障还要保留能触发失败的调度，固定随机 seed 不保证系统调度完全复现。

下面用 Python 3 标准库把“排序保持长度”的反例缩到两个相同元素；所有输入都是合法整数列表：

def bad_sort(values):
    return sorted(set(values))

def violates_length(values):
    return len(bad_sort(values)) != len(values)

for values in [[8, 5, 5, 3], [5, 5], [0, 0]]:
    assert violates_length(values)
minimal = [0, 0]
assert all(not violates_length(minimal[:i] + minimal[i + 1:])
           for i in range(len(minimal)))
print(bad_sort(minimal))  # [0], although the input has two elements.

去重把“排列元素”变成了“保留不同值”。零个或一个元素不会触发这个长度错误，因此两个元素已经是该性质按长度计的最小反例。完整排序规格还需约束顺序与每个值的次数，长度保持只检查其中一项。

完成检查

1. 推翻“两个无理数之和一定无理”；
2. 为“存在一个整数，其平方等于自身”给出两个见证；
3. 证明方程 3x+6=0 有唯一实数解；
4. 用反证法证明不存在最大的整数；
5. 为一个生产故障写出最小反例，并说明它满足被反驳性质的所有前提。

参考资料

• Open Logic Project