命题逻辑与证明

这一页教你两件互相咬合的事：一是用命题逻辑和谓词逻辑把日常推理改写成可以逐行检查的符号形式；二是掌握数学证明的标准方法——直接证明、逆否证明、反证法、存在性证明和数学归纳法。学完之后，你不仅看得懂教材定理的证明在干什么，还能自己写出”每一步都有依据”的论证，并识别肯定后件、否定前件这类常见谬误。

1. 命题与联结词

命题（proposition）是一个可以明确判定真假的陈述句。“北京是中国的首都”是命题（真）；"$2+2=5$"是命题（假）；“几点了？“和"$x+1=3$"（在 $x$ 未赋值时）都不是命题。我们用 $p,q,r$ 等字母表示命题，用联结词把简单命题组合成复合命题。下面五个是全部常用联结词，定义方式就是它们的真值表（$T$ 表示真，$F$ 表示假）。

否定 $\neg p$：真假取反。

$p$	$\neg p$
$T$	$F$
$F$	$T$

合取 $p\wedge q$（“且”）：两个都真才真。

$p$	$q$	$p\wedge q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$F$

析取 $p\vee q$（“或”）：相容或——只要有一个为真就为真，两个都真也为真。注意与自然语言里”要么米饭要么面条”那种排斥或（exclusive or，记作 $\oplus$，两真时反而为假）区分开：数学中的 $\vee$ 默认是相容或。

$p$	$q$	$p\vee q$
$T$	$T$	$T$
$T$	$F$	$T$
$F$	$T$	$T$
$F$	$F$	$F$

蕴含 $p\to q$（“如果 $p$ 那么 $q$”）：只在 $p$ 真而 $q$ 假时为假，其余三种情况全为真。

$p$	$q$	$p\to q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$F$	$T$

这一行最容易反直觉。$p$ 为假时，无论 $q$ 真假，$p\to q$ 都算真——“假的条件推出任何东西”都算作一个为真的条件句。换成日常直觉：你承诺”如果下雨我就带伞”，唯一让你食言的情形是下雨了（$p$ 真）而你没带伞（$q$ 假）；天没下雨时你带不带伞都不算违约。顺带一提：前件 $p$ 恒假的蕴含 $p\to q$ 是真的，这叫空真（vacuously true），“所有独角兽都是粉红色的”在逻辑上就是空真句，因为论域里不存在独角兽使前件成立。

等价 $p\leftrightarrow q$（“当且仅当”）：两边同真同假时为真，即 $p\leftrightarrow q$ 与 $(p\to q)\wedge (q\to p)$ 真值完全相同。

$p$	$q$	$p\leftrightarrow q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$T$

2. 真值表方法与逻辑等价

两个复合命题在所有真值组合下都取相同的真假值，就称它们逻辑等价，记作 $\equiv$。检验等价的标准方法就是列真值表：$n$ 个原子命题有 $2^n$ 种组合，逐一比对即可。这是最笨也最可靠的办法，对少量命题永远可行。

三组最常用的等价式：

德摩根律（De Morgan’s laws），“对合取或析取整体取反，要反进去并把符号互换”：

$$\neg (p\wedge q)\equiv \neg p\vee \neg q,\neg (p\vee q)\equiv \neg p\wedge \neg q.$$

分配律：

$$p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r),p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r).$$

蕴含的析取形式（去掉 $\to$ 的钥匙，反证法和逆否证明都靠它）：

$$p\to q\equiv \neg p\vee q.$$

例题 1（真值表证明等价式）。用真值表证明德摩根律 $\neg (p\vee q)\equiv \neg p\wedge \neg q$。

解：两个式子只含 $p,q$ 两个原子命题，共 4 种组合，列在表的前两列，然后分别算出 $\neg (p\vee q)$ 和 $\neg p\wedge \neg q$ 的每一列：

$p$	$q$	$p\vee q$	$\neg (p\vee q)$	$\neg p$	$\neg q$	$\neg p\wedge \neg q$
$T$	$T$	$T$	$F$	$F$	$F$	$F$
$T$	$F$	$T$	$F$	$F$	$T$	$F$
$F$	$T$	$T$	$F$	$T$	$F$	$F$
$F$	$F$	$F$	$T$	$T$	$T$	$T$

第 4 列与第 7 列在四行上完全相同，所以 $\neg (p\vee q)\equiv \neg p\wedge \neg q$。证毕。

这类证明没有任何技巧，唯一要求是行不漏、列不串。要证的等价式越长，真值表的行数按 $2^n$ 增长，这正是后面需要推理规则（等价变换、逻辑律）的原因。

重言式（tautology）是在所有真值组合下都为真的复合命题，比如 $p\vee \neg p$；矛盾（contradiction）是在所有组合下都为假的，比如 $p\wedge \neg p$；可满足（satisfiable）是指至少存在一种真值组合使其为真。判定 $p\to q$ 与 $p\leftrightarrow q$ 这类推理关系，本质上就是在问相应的复合命题是不是重言式。

3. 谓词逻辑

命题逻辑表达不了"$x>3$"这种含变量的陈述。谓词是把变量变成命题的函数，如 $P(x):x>3$。变量必须绑定在一个明确的取值范围——论域（domain of discourse，也叫全集）——上，$P(x)$ 才有真假可言。

全称量词 $\forall$ 与存在量词 $\exists$ 是两种绑定方式：

$$\forall xP(x)$$

读作”论域中每个 $x$ 都满足 $P(x)$”；

$$\exists xP(x)$$

读作”论域中至少有一个 $x$ 满足 $P(x)$”。

量词否定遵循德摩根式的翻转规则：整体取否定，量词换种类，否定落到谓词上：

$$\neg (\forall xP(x))\equiv \exists x\neg P(x),\neg (\exists xP(x))\equiv \forall x\neg P(x).$$

读法就是”不是所有都……”等价于”存在一个不……”。在多个量词连用时，否定要从左到右逐层翻转。

量词顺序不可交换。 $\forall x\exists y$ 和 $\exists y\forall x$ 表达的是完全不同的强度。反例：取论域为实数 $\mathbb{R}$，谓词 $P(x,y):x+y=0$。

• $\forall x\exists y(x+y=0)$ 为真：任给一个 $x$，取 $y=-x$ 即可，$y$ 可以依赖于 $x$。
• $\exists y\forall x(x+y=0)$ 为假：它要求存在一个固定的 $y$ 对所有 $x$ 都成立，代入 $x=1$ 与 $x=2$ 立刻矛盾。

直觉：$\forall x\exists y$ 允许 $y$ “看着 $x$ 选”，$\exists y\forall x$ 要求 $y$ 一次定终身。只有同种量词相邻时可以互换，$\forall x\forall y$ 与 $\forall y\forall x$ 等价，$\exists x\exists y$ 与 $\exists y\exists x$ 等价。

4. 论证有效性

论证是一串前提加一个结论；它有效（valid），是指只要所有前提为真，结论必然为真。注意有效性只关心”前提真能否保证结论真”，不承诺前提本身为真。检验有效性的办法：把论证写成 $(p_1\wedge p_2\wedge \cdots \wedge p_n)\to q$，它是重言式当且仅当论证有效。

有效论证的例子（肯定前件，modus ponens）：

前提一：如果数据集通过质检，则模型可以上线（$p\to q$）。 前提二：数据集通过了质检（$p$）。 结论：模型可以上线（$q$）。

验证：列出 $p\to q$ 的真值表，删掉 $p\to q$ 为假的第 2 行和 $p$ 为假的 3、4 行，只剩第 1 行，而第 1 行里 $q$ 恰为真。所以两个前提为真时结论不可能假，论证有效。

谬误的例子（肯定后件，affirming the consequent）：

前提一：如果数据集通过质检，则模型可以上线（$p\to q$）。 前提二：模型上线了（$q$）。 结论：数据集通过了质检（$p$）。

这个论证无效。真值表第 3 行（$p=F,q=T$）中两个前提都真而结论假——模型上线完全可能有别的原因，比如走的是紧急通道。类似的还有否定前件（denying the antecedent）：“如果 $p$ 则 $q$；$p$ 不成立；所以 $q$ 不成立”，同样无效，反例在真值表第 4 行。

5. 证明方法体系

一个数学命题通常形如”对所有满足前提 $P$ 的对象，结论 $Q$ 成立”，即 $\forall x(P(x)\to Q(x))$。证明方法的不同，对应着处理这个蕴含式时选择的方向。

直接证明：假设 $P(x)$ 成立，用定义、已知定理和代数推理一步步推出 $Q(x)$。最常用、也最该优先尝试的方法。

逆否证明（proof by contraposition）：要证 $P\to Q$，改证等价的逆否命题 $\neg Q\to \neg P$。当”假设 $Q$ 不成立”比”假设 $P$ 成立”更容易操作时特别有效。典型场景是整除与奇偶性论证，见下面的例题 2。

反证法与归谬（proof by contradiction）：要证命题 $S$，假设 $\neg S$ 成立，推导出一个矛盾（即某个命题 $R$ 与 $\neg R$ 同时为真）。其合法性来自等价式 $\neg S\to (R\wedge \neg R)$ 为真等价于 $S$ 为真。“归谬”即拉丁文 reductio ad absurdum，与反证法同义；特化到命题逻辑里，它正是等价式 $p\to q\equiv \neg p\vee q$ 的另一面：若 $\neg p$ 与 $p$ 的某种推论冲突，则 $p\to q$ 成立。$\sqrt{2}$ 是无理数这个经典证明（例题 2）就是它的范本。

分情况证明：把论域按条件分成若干穷尽的情形，每种情形分别直接证明结论。依据是重言式

$$(p_1\vee p_2\vee \cdots \vee p_n)\to q\equiv (p_1\to q)\wedge (p_2\to q)\wedge \cdots \wedge (p_n\to q).$$

例如”任何整数的平方模 4 余 0 或 1”，把整数分成偶数与奇数两种情况各算一次即得。

存在性证明：要证 $\exists xP(x)$。构造性证明直接给出一个具体的 $a$ 并验证 $P(a)$；非构造性证明只论证这样的 $a$ 必然存在而不指明它是谁。非构造性的经典例子：存在两个无理数 $a,b$ 使得 $a^b$ 是有理数。证明：考察 ${\sqrt{2}}^{\sqrt{2}}$。若它是有理数，取 $a=b=\sqrt{2}$ 即完成构造；若它是无理数，取 $a={\sqrt{2}}^{\sqrt{2}},b=\sqrt{2}$，则

$$a^b={\left({\sqrt{2}}^{\sqrt{2}}\right)}^{\sqrt{2}}=(\sqrt{2}{)}^2=2$$

是有理数。两种情形必居其一，所以这样的无理数对必然存在——虽然这个论证本身没有告诉你究竟是哪一对。这个例子也顺带说明了一个事实：${\sqrt{2}}^{\sqrt{2}}$ 确实是无理数（由格尔丰德–施耐德定理保证），上面的二分论证把”找出它”转化成了”排除不存在”。

数学归纳法：处理”对所有正整数 $n$，$P(n)$ 成立”的标准工具，对应良序原理：正整数集的每个非空子集都有最小元。模板分两步：

1. 基础情形：验证 $P(1)$（或某个起点 $n_0$）成立。
2. 归纳步：假设对某个任意 $k\ge 1$，$P(k)$ 成立（这一假设叫归纳假设），用它推出 $P(k+1)$。

两步合起来就排除了所有反例：若 $P(n)$ 对某些 $n$ 失败，取最小的失败点，它的前一个点必成功，与归纳步矛盾。例题 3 给出完整示范。两个只提名字的推广：强归纳法把归纳假设加强为”$P(1),\dots ,P(k)$ 都成立”，适合后项依赖多个前项的情形（如”每个大于 1 的整数都可分解为素数乘积”）；结构归纳法作用在递归定义的对象上（如树、公式串），归纳对象是结构的”高度”或”构造步骤”，是证明语法性质和算法正确性的主力。

6. 例题

例题 2（反证法：$\sqrt{2}$ 是无理数）。

命题：不存在有理数 $r$ 使得 $r^2=2$；换言之，$\sqrt{2}$ 是无理数。

证明：用反证法。假设 $\sqrt{2}$ 是有理数，则它可以写成最简分数

$$\sqrt{2}=\frac{a}{b},a,b\in \mathbb{Z},b\ne 0,\gcd (a,b)=1.$$

两边平方得 $a^2=2b^2$。这说明 $a^2$ 是偶数。而一个奇数的平方仍是奇数，所以 $a$ 本身必为偶数，记 $a=2c$。代回得

$$(2c{)}^2=2b^2⟹4c^2=2b^2⟹b^2=2c^2,$$

于是 $b^2$ 也是偶数，同理 $b$ 也是偶数。这样 $a$ 与 $b$ 有公因数 2，与 $\gcd (a,b)=1$ 矛盾。所以假设不成立，$\sqrt{2}$ 是无理数。证毕。

整个证明只用了一条数论事实：奇数的平方是奇数（其逆否命题”平方为偶则底为偶”正是逆否证明的用武之地），外加”任何有理数都能约成最简分数”这条良序原理的推论。

例题 3（数学归纳法：前 $n$ 个正整数之和）。

命题：对所有正整数 $n$，

$$\sum _{i=1}^{n}i=1+2+\cdots +n=\frac{n(n+1)}{2}.$$

证明：对 $n$ 作数学归纳。

基础情形：$n=1$ 时，左边 $=1$，右边 $=\frac{1\cdot 2}{2}=1$，两边相等，$P(1)$ 成立。

归纳步：假设对某个 $k\ge 1$，

$$1+2+\cdots +k=\frac{k(k+1)}{2}$$

成立（归纳假设）。考察 $n=k+1$：

$$\begin{array}{rl}1+2+\cdots +k+(k+1)& =\frac{k(k+1)}{2}+(k+1)\text{（用了归纳假设）}\\ & =(k+1)\left(\frac{k}{2}+1\right)=\frac{(k+1)(k+2)}{2}=\frac{(k+1)((k+1)+1)}{2}.\end{array}$$

这正是 $n=k+1$ 时命题的形式。由数学归纳法，命题对所有正整数 $n$ 成立。证毕。

注意归纳步里那一步”用了归纳假设”是整段证明的灵魂：如果推导 $P(k+1)$ 的过程中始终没有调用 $P(k)$，那它就不是归纳证明，而只是分别验证了两个孤立命题（这正是最常见的错误，见第 7 节）。

例题 4（鸽巢原理的小应用）。

命题：任意 13 个人中，至少有两人生日在同一个月份。

证明：把 12 个月份看成 12 个盒子，13 个人看成 13 个物体，每个人的生日月份决定他放进哪个盒子。鸽巢原理说：把 $n+1$ 个物体放进 $n$ 个盒子，必有一个盒子至少装两个物体。假设结论不成立，即每个月份至多有一人，那么总人数至多 12 人，与有 13 人矛盾。所以至少有一个月份装有至少两人。证毕。

这个 $n+1$ 对 $n$ 的版本是计数章节里一般鸽巢原理（若物体数超过平均数，则某盒必超过平均数）的最简形态。

7. 常见错误

• 肯定后件：由 $p\to q$ 和 $q$ 推出 $p$。无效，反例见第 4 节真值表第 3 行。“模型上线了，所以数据集通过质检了”——上线可能有别的原因。
• 否定前件：由 $p\to q$ 和 $\neg p$ 推出 $\neg q$。同样无效，反例是真值表第 4 行。“今天没下雨，所以地面一定不湿”——洒水车不答应。
• 归纳步没用归纳假设：写出”假设 $P(k)$ 成立”，却在推导 $P(k+1)$ 时从头到尾没用到它。这通常意味着两种可能：证明有误，或者那一步其实可以直接证明、根本不需要归纳（比如对 $n$ 恒等的代数恒等式有时会被误套上归纳格式）。自查方法：在草稿上把归纳假设那一行圈出来，确认后面至少引用过一次。
• 混淆”反例”与”证明”：全称命题 $\forall xP(x)$ 只需一个反例即可否定，但要证明它为真必须覆盖整个论域——枚举再多例子也不算证明，归纳法和直接证明才是工具。
• 量词顺序随意交换：$\forall x\exists y$ 与 $\exists y\forall x$ 强度不同，交换后命题可能已经改变（见第 3 节反例）。

8. 练习

1. 用真值表验证 $\neg (p\to q)\equiv p\wedge \neg q$。
2. 写出命题”所有数据集都通过了质检”的否定，并说明它何时为真。
3. 判断并说明理由：“如果该算法是多项式时间的，那么它能处理大规模数据。这个算法不是多项式时间的，所以它处理不了大规模数据。”
4. 用数学归纳法证明：对所有正整数 $n$，$1+3+5+\cdots +(2n-1)=n^2$。
5. 用逆否证明（contraposition）证明：若整数 $n$ 的平方 $n^2$ 是偶数，则 $n$ 是偶数。

答案与提示：

1. 四行真值表中，$p\to q$ 只在第 2 行（$p=T,q=F$）为假，故 $\neg (p\to q)$ 只在第 2 行为真；而 $p\wedge \neg q$ 也恰在第 2 行为真。两列相同，等价成立。这个等价式很实用：它把”蕴含为假”精确翻译成了”前提真且结论假”。
2. 按量词否定律，$\neg (\forall xP(x))\equiv \exists x\neg P(x)$：否定是”存在至少一个数据集没有通过质检”。原命题为假、否定为真，当且仅当确实存在未过质检的数据集。
3. 无效，这是否定前件谬误。算法不是多项式时间，并不排除它通过并行化、近似或针对特定分布仍然能处理大规模数据——反例结构正是真值表中 $p=F,q=T$ 的那一行。
4. 基础情形：$n=1$ 时左边 $=1$，右边 $=1^2=1$。归纳步：假设 $1+3+\cdots +(2k-1)=k^2$，则 $1+3+\cdots +(2k-1)+(2k+1)=k^2+2k+1=(k+1{)}^2$。归纳步确实用到了归纳假设。由归纳法得证。
5. 逆否命题是”若 $n$ 是奇数，则 $n^2$ 是奇数”。设 $n=2m+1$，则 $n^2=4m^2+4m+1=2(2m^2+2m)+1$，形如 $2t+1$，是奇数。逆否命题得证，故原命题成立。

学习路径

• 返回 离散数学总览
• 返回 数学基础专题首页
• NEXT：集合、关系与函数