程序员数学 02：逻辑、集合与程序不变量

程序里的 if 是对一个命题作判断。数学逻辑可以帮助我们检查分支是否覆盖了预期情况，但必须先说清变量代表什么。

布尔条件先列真值表

设 $A$ 表示“已经登录”，$B$ 表示“具有编辑权限”。允许编辑的规则为 $A\wedge B$，拒绝规则就是它的否定。

A	B	允许 A 且 B	拒绝
假	假	假	真
假	真	假	真
真	假	假	真
真	真	真	假

由表可见，$\mathrm{\neg }(A\wedge B)=\mathrm{\neg }A\vee \mathrm{\neg }B$。这就是一个德摩根律；另一个是 $\mathrm{\neg }(A\vee B)=\mathrm{\neg }A\wedge \mathrm{\neg }B$。因此拒绝条件应为 !loggedIn || !canEdit，写成两个否定的“且”会错误放过其中一项不满足的情况。

这里假定变量已经是明确的布尔值。若变量可能为 null、缺失或非布尔对象，应先确定语言转换规则；数学里的两值逻辑不会自动替你处理数据清洗。

必要条件不能倒过来用

“提交成功蕴含校验通过”写成 $S\Rightarrow V$。它不意味着“校验通过就一定提交成功”，还可能因磁盘写入失败而终止。

原命题与逆否命题 $\mathrm{\neg }V\Rightarrow \mathrm{\neg }S$ 等价，与逆命题 $V\Rightarrow S$ 一般不等价。读文档中的 only if 时尤其容易犯这个错误，可结合英语文档阅读篇。

集合与量词：所有还是至少一个

设用户权限集合为 $U=\{read,write\}$，某操作要求的权限集合为 $R=\{read,admin\}$。“拥有任一权限”检查交集非空；“拥有全部权限”检查 $R\subseteq U$。这两项在此例中的结果分别为真和假。

const owned = new Set(['read', 'write']);
const required = ['read', 'admin'];
console.log(required.some(p => owned.has(p))); // true
console.log(required.every(p => owned.has(p))); // false
console.log([].every(p => owned.has(p)));       // true

空数组的 every 返回真，对应“没有反例”的全称命题。数学上自洽，不表示业务上空权限配置一定应该放行。如果业务要求权限列表必须非空，就应把“非空”明确加入条件。

全称命题“所有记录都有效”的否定是“至少一条记录无效”，不是“所有记录都无效”。这也是 every 与 some 常见的换写依据。

循环不变量：每一步都维持的事实

计算数组前缀和时，可以选不变量：“开始处理下标 $i$ 前，sum 等于下标 $0$ 到 $i-1$ 的元素之和”。

const values = [2, 5, 3];
let sum = 0;
for (let i = 0; i < values.length; i++) {
  sum += values[i];
}
console.log(sum); // 10

初始化时 $i=0$，空前缀的和为 0；每步加上当前元素后，不变量对下一位置仍成立；循环结束时前缀覆盖整个数组，因此结果正确。这个推理假设运算符合所用数值模型，溢出和浮点误差仍需另外检查。

练习

1. 只有“文件存在且可读”时才读取，拒绝条件怎样写？
2. “至少一条记录通过校验”的否定是什么？
3. 对空数组求和，上述不变量证明是否仍成立？

查看答案与讲解

1. !exists || !readable。任一前提不满足即拒绝；实际文件访问仍可能受检查后状态变化影响，条件检查不能替代处理读取失败。
2. “所有记录都没有通过校验”。空记录集合上，“至少一条通过”为假，其否定为真。
3. 成立。初始化后直接结束，空和为 0。业务若认为空输入非法，应另外校验，不能让求和函数的数学结果暗中决定业务规则。

资料与延伸

MIT 6.042J 阅读目录 中的逻辑、证明与不变量章节可用于系统学习。下一步可以给二分查找写出“答案仍在当前区间中”的不变量，而不是只记循环模板。