逻辑

数理逻辑（mathematical logic）研究数学陈述怎样组成，以及结论在什么条件下能由前提推出。它为“所有”“存在”“如果……那么……”等常用表达规定明确含义，也是组织数学证明的基础。

例如，“一个整数能被 4 整除，那么它是偶数”成立，因为 $n=4k$ 可以写成 $n=2(2k)$。反过来说“一个整数是偶数，那么它能被 4 整除”，却被 6 推翻。两句话使用相同的词，却表达了不同方向的要求。

从包含关系理解“如果……那么……”

下图的矩形表示全体整数 $\mathbb{Z}$，大椭圆表示偶数 $2\mathbb{Z}$，小椭圆表示 4 的倍数 $4\mathbb{Z}$。小椭圆完全位于大椭圆内，因此每个 4 的倍数也都是偶数。数字 6 在大椭圆中、小椭圆外，显示反向推理为何失败；3 在两个椭圆外。

“能被 4 整除”保证“是偶数”，而偶数中还包含额外的整数。

把“n 能被 4 整除”记为 P，把“n 是偶数”记为 Q，则原条件句写成 $P\Rightarrow Q$，读作“P 蕴含 Q”。它排除的是 P 成立而 Q 不成立的情况，也就是图中“小椭圆内却在大椭圆外”的点。

P 是 Q 的充分条件，因为 P 成立足以保证 Q；Q 是 P 的必要条件，因为 P 成立时 Q 不可缺少。若两个方向都成立，写作 $P\iff Q$，称为充要条件。例如对整数 n，“n 是偶数”与“n 的平方是偶数”互为充要条件，两个方向的证明将在后面给出。

命题与逻辑连接词

具有确定真值的陈述称为命题，例如“2 是偶数”是真命题，“3 是偶数”是假命题。“x 是偶数”还含有未确定的变量；指定 x 的值，或者说明“对所有整数 x”，才得到真值确定的陈述。

逻辑连接词把已有陈述组成新陈述：

• $\mathrm{\neg }P$ 表示“不是 P”，称为否定。
• $P\wedge Q$ 表示“P 并且 Q”，两者都真时才真。
• $P\vee Q$ 表示“P 或者 Q”，至少一个真时就真，允许两者同时真。
• $P\Rightarrow Q$ 表示“如果 P，那么 Q”，只有 P 真、Q 假时为假。

将 P、Q 的四种真假组合逐项写下，就得到真值表：

P	Q	$P\wedge Q$	$P\vee Q$	$P\Rightarrow Q$
真	真	真	真	真
真	假	假	真	假
假	真	假	真	真
假	假	假	假	真

最后两行表示：P 不成立时，并没有出现“满足 P 却违反 Q”的反例。例如 n=3 既不是 4 的倍数，也不是偶数，它没有推翻“每个 4 的倍数都是偶数”。但从 n=3 不满足前提，也得不出它是偶数。条件句的真假与结论 Q 单独的真假，是两件事。

逻辑蕴含表达这种真假约束，不自行表达时间先后或因果。现实问题中哪些因素导致哪些结果，还需要另行建立模型与证据。

逆命题与逆否命题

对原句“若 P 则 Q”，交换两者得到逆命题 $Q\Rightarrow P$；把前后都否定，得到 $\mathrm{\neg }P\Rightarrow \mathrm{\neg }Q$。开头的偶数例子已经表明，这两个变化后的句子可能为假。

另一种变换是既交换又否定，得到逆否命题 $$\mathrm{\neg }Q\Rightarrow \mathrm{\neg }P.$$ 它与原命题等价。原命题唯一排除的情况是 P 真、Q 假；逆否命题唯一排除的情况是“非 Q 真、非 P 假”，仍然是同一情况。因此 $$(P\Rightarrow Q)⟺(\mathrm{\neg }Q\Rightarrow \mathrm{\neg }P).$$ 在整数例子中，“若不是偶数，就不是 4 的倍数”与原句表达了同一项约束。

这一点给出两种有效推理：已知 P 和 $P\Rightarrow Q$，可推出 Q；已知非 Q 和同一条件句，可推出非 P。只知道 Q 则不能反推 P，因为 Q 可能包含图中 6 这样的额外对象。

完整证明：整数与其平方同奇偶

先证正向：若 n 为偶数，就存在整数 k 使 $n=2k$，因此 $$n^2=4k^2=2(2k^2).$$ 括号内仍为整数，所以平方是偶数。

反向要证“若平方为偶数，则 n 为偶数”。证明它的逆否命题更直接：若 n 是奇数，写成 $n=2k+1$，展开得到 $$n^2=4k^2+4k+1=2(2k^2+2k)+1.$$ 这说明平方也是奇数。整数按奇偶两类划分，因而逆否命题成立，所需反向也成立。两个方向合并，才得到“n 为偶数当且仅当 n² 为偶数”。

“所有”与“存在”怎样写清楚

全称量词 $\mathrm{\forall }$ 表示“对所有”，存在量词 $\mathrm{\exists }$ 表示“至少存在一个”。例如 $$\mathrm{\forall }n\in \mathbb{Z},4\mid n\Rightarrow 2\mid n$$ 说明对每个整数，4 整除它时，2 也整除它。而 $$\mathrm{\exists }n\in \mathbb{Z},2\mid n\wedge 4\nmid n$$ 说明存在偶数不是 4 的倍数，取 n=6 就能证实。

量词给出的对象范围同样重要。方程 $x^2=4$ 在实数范围有两个解 2、−2，在非负实数范围只有一个解。若说“存在唯一解”，就同时要求存在一个解，以及任意两个解都相等；找到一个候选并不能独自证明唯一性。

全称陈述也不自动保证有对象存在。如果方程没有实数解，“它的每个实数解都是正数”没有反例，仍为真；但“存在一个正实数解”为假。这与空集上的量词有关：空集上所有元素满足某条件为真，空集中存在满足条件的元素为假。通常一阶逻辑的总论域取非空，空集可以作为其中用于限制量词的子集。

量词顺序表示谁可以依赖谁

在实数范围考虑 $$\mathrm{\forall }x\in ℝ\mathrm{\exists }y\in ℝ,y>x.$$ 它说：先任意给一个 x，再找一个比它大的 y。选择 $y=x+1$ 就够了，y 可以随 x 改变。

交换量词，得到 $$\mathrm{\exists }y\in ℝ\mathrm{\forall }x\in ℝ,y>x.$$ 这回要先选定一个 y，然后让它比所有 x 都大。对于任何候选 y，取 $x=y$ 就使严格不等式失败，因此这个陈述为假。两个句子的差别，不在于能否写出两个数，而在于第二个数能否依赖第一个数。

图中左排让 y 在知道 x 后选择，下面三组数只是同一规则 y=x+1 的实例；右排先固定 y=a，再取 x=a，就得到无法成立的 a>a。这里 a 可以是任意实数，所以右边的失败并不限于某一个数值。

量词顺序规定后面的对象可以依赖哪些已知选择。

极限定义中的“对任意正误差，都存在一个足够小的输入邻域”，采用前一种次序。邻域可以根据误差选择；选定以后，又必须同时适用于该邻域内的所有输入点。这些依赖关系是定义内容的一部分。

否定一句话，需要否定到哪里

“所有整数都是偶数”的否定，是“存在一个整数不是偶数”。它不要求所有整数都不是偶数，一个反例就足够。相应地， $$\mathrm{\neg }(\mathrm{\forall }xP(x))⟺\mathrm{\exists }x\mathrm{\neg }P(x),$$ $$\mathrm{\neg }(\mathrm{\exists }xP(x))⟺\mathrm{\forall }x\mathrm{\neg }P(x).$$ 多层量词需要逐层处理。例如“每个学生都做对至少一道题”，否定后是“有一个学生一道题也没做对”。若 $P(s,q)$ 表示学生 s 做对题 q，则原句为 $\mathrm{\forall }s\mathrm{\exists }qP(s,q)$，否定为 $\mathrm{\exists }s\mathrm{\forall }q\mathrm{\neg }P(s,q)$。

连接词的否定则遵循德摩根律： $$\mathrm{\neg }(P\wedge Q)⟺\mathrm{\neg }P\vee \mathrm{\neg }Q,$$ $$\mathrm{\neg }(P\vee Q)⟺\mathrm{\neg }P\wedge \mathrm{\neg }Q.$$ 例如“输入合法并且余额足够”不成立，可能是输入非法，也可能是余额不足，或者两者都失败。这种否定与集合中交、并、补的关系一致。

最小正实数的命题与否定

“存在最小正实数”可以写为 $$\mathrm{\exists }a>0\mathrm{\forall }x>0,a\le x.$$ 否定时，先把存在 a 改为对每个 a，再把对所有 x 改为存在 x，最后否定不等式，得到 $$\mathrm{\forall }a>0\mathrm{\exists }x>0,x<a.$$ 这句话能直接证明：给定任意正数 a，取 $x=a/2$，便有 $0<x<a$。所以每个正实数都不是最小的，最小正实数不存在。

如果对象换成正整数，这个结论就改变了。1 是最小正整数，而将 a=1 除以 2 会离开整数范围。证明里的构造既要满足关系，也要留在量词指定的集合内。

证明怎样覆盖全部情形

要证明一个全称陈述，可以任取一个满足条件的对象，再用这些条件推出结论。前面的偶数平方证明采用了任意整数 k，因而同时覆盖所有偶数。

要推翻全称陈述，只需一个反例。例如“所有素数都是奇数”被 2 推翻；但列出许多奇素数只能提供一些实例，不能证明全部素数都如此。

反证法从相反假设出发，推出矛盾。例如假设有最大的整数 N，那么 N+1 仍是整数且大于 N，与最大性矛盾，所以最大的整数不存在。这里的加一给出了对任意候选 N 都有效的反驳。

数学归纳法为何不是检查前几项

要证明对所有非负整数 n 都成立的公式 $$1+2+\cdots +n=\frac{n(n+1)}{2},$$ 先检查 n=0：左边为空和，取值 0，右边也为 0。这是基础步。

接着设公式在某个任意的非负整数 k 处成立。再加下一项 k+1： $$\begin{array}{cc}1+2+\cdots +k+(k+1)& =\frac{k(k+1)}{2}+(k+1)\\ & =\frac{(k+1)(k+2)}{2}.\end{array}$$ 这正是 n=k+1 时的公式，故完成归纳步。

基础步使命题从 0 启动；归纳步保证每次成立都能传到下一个整数。因此所有非负整数都被覆盖。归纳步没有先假设全部 n 的结论，而是在一个任意 k 处作条件假设，再证明下一步。这与仅计算前若干个数值有本质不同。

真值、证明与形式系统

真值表处理有限个命题变量的真假组合。例如可逐行核验原命题与逆否命题在四种赋值下总有相同真假。如果一个公式在所有赋值下都为真，称为重言式。

带量词的陈述还涉及变量取值的集合及关系的解释。例如 $\mathrm{\forall }x{x}^2\ge 0$ 在实数及其通常运算下成立；变量范围和符号的意义提供了判断陈述的背景。数理逻辑进一步研究怎样精确定义这些语言、解释和推导规则。

一个形式证明是依照已规定规则组成的有限推导。证明是否有效，与所采用的公理是否适合描述某个现实问题，也是不同问题。数学建模既需要有效推理，也需要为模型中的假设提供现实依据。上述真值与证明方法使用经典逻辑；其他逻辑体系可以采用不同的规则。

历史

George Boole 在 1847 年的《The Mathematical Analysis of Logic》和 1854 年的《An Investigation of the Laws of Thought》中发展了逻辑的代数处理，将部分推理关系写成可以计算的符号形式。University College Cork 的 Boole 纪念项目介绍了两部作品及其研究背景。

布尔式运算后来成为数字电路与程序条件的重要语言。前面表中的“并且”“或者”“否定”，既可连接数学命题，也可组织程序判断；加入量词以后，又能表达“每个元素满足什么”及“是否存在满足要求的对象”等数学陈述。

参考资料

• Oscar Levin：命题逻辑。
• Oscar Levin，Discrete Mathematics: An Open Introduction，第 0、3 章：量词与证明方法。
• University College Cork：Boole 的逻辑研究。
• MacTutor：George Boole。
• 相关条目：集合、极限、组合数学、数学建模。