离散数学与证明 I：逻辑、集合、归纳、计数与图论入门｜第 3 章：条件命题、等价变形与推理规则 | 自在学

条件命题、等价变形与推理规则

上一章里，我们已经会把复合命题拆成命题变元和连接词，也会用真值表逐行计算真假。现在要把其中最容易“听错方向”的连接词单独拿出来：条件命题。

它难的地方不在符号 $\to$ ，而在日常语言给我们留下的习惯。平时说“如果下雨，我就带伞”，我们会联想到天气导致行为、事情发生的先后，甚至一个人的承诺是否可靠。数学暂时把这些背景全部拿掉，只问一件很窄的事：有没有出现前件已经成立、后件却失败的情况？

这一步看起来像是在抠字眼，其实后面的证明都靠它。直接证明是在假设前件以后寻找后件；逆否证明是在后件失败时排除前件；推理规则是在检查一条结论是否真的被前提锁定。把这条箭头读准，证明就不再是一串突然出现的句子，而会变成一条能逐步核对的路线。

条件命题到底承诺了什么

条件命题写作 $P \to Q$ ，读作“如果 $P$ ，那么 $Q$ ”。 $P$ 叫前件或假设， $Q$ 叫后件或结论。

先用一句话抓住它的意思：只要 $P$ 成立， $Q$ 就必须成立。于是，要证明这句话不守信用，必须同时看到两件事： $P$ 确实发生了， $Q$ 却没有发生。

真值表正是在记录这四种可能：

$P$	$Q$	$P \to Q$	判断理由
真	真	真	要求被触发，结果也做到
真	假	假	要求被触发，结果却失败
假	真	真	要求没有被触发，没有违背
假	假	真	要求没有被触发，仍没有违背

条件命题 P 到 Q 的四种真值情况，其中只有 P 真且 Q 假时命题为假 — 四种赋值中，只有“前件真、后件假”会让条件命题失败。

用“找违约”代替死背表格

考虑命题：“如果整数 $n$ 是 $4$ 的倍数，那么 $n$ 是偶数。”令

P: 4 \mid n

Q: 2 \mid n

原命题就是 $P \to Q$ 。若要推翻它，我们得找出一个既满足 $4\mid n$ 、又满足 $2\nmid n$ 的整数。可一旦 $n=4k$ ，就有 $n=2(2k)$ ，因此这样的整数不存在。

这里要分清“证明”和“试了几个数”。检查 $4,8,12$ 都是偶数，只能增加信心，不能覆盖所有整数；写出 $n=4k=2(2k)$ ，才说明任何 $4$ 的倍数都不会成为违背条件的例子。

再取 $n=6$ 。这时前件“ $n$ 是 $4$ 的倍数”为假，后件“ $n$ 是偶数”为真，所以整句仍为真。 $6$ 没有满足前件，当然不能拿它来反驳“满足前件以后会怎样”。

$P \to Q$ 没有说 $P$ 是 $Q$ 的原因，也没有说 $P$ 是让 $Q$ 成立的唯一办法。它只排除这一种组合。

前件为假为什么判真

初学时最别扭的是后两行：前件为假，无论后件真假， $P\to Q$ 都为真。这叫空真。

还是看一句承诺：“如果我今天提交作业，那么文件名里会写学号。”如果今天确实提交了，却没写学号，承诺失败；如果今天根本没提交，单凭文件名是否出现学号，无法说这句条件承诺被违背。数学把“没有出现违背情形”统一记为真。

这样规定还有一个很实用的结果。假设一个系统有十二条规则：在条件 $C_i$ 出现时执行动作 $A_i$ 。某次运行只有 $C_2$ 和 $C_{5}$ 出现，系统正确执行了和。我们希望说十二条规则都被遵守了，而不是说其余十条规则都失败了。把假前件的蕴含判为真，正好表达“未触发的规则没有被违反”。

空真不表示后件被前件“证明”了。它只是在判断整个条件命题的真值：这一次赋值没有落入唯一的失败行。

下面可以逐个切换 $P$ 与 $Q$ 。先故意切到“ $P$ 真、 $Q$ 假”，再比较另外三种状态，条件命题的规则会比背表格直观得多。

条件命题的否定不是另一个“如果”

否定一句话，是要准确描述它什么时候失败。 $P\to Q$ 唯一的失败情形是 $P$ 真而 $Q$ 假，所以

\neg(P \to Q) \equiv P \land \neg Q

例如，“如果下雨，那么地面湿”的否定是“下雨了，并且地面不湿”。它不是“如果不下雨，那么地面不湿”；后一句仍是一个条件命题，而且谈的是另一种方向。

这条等价式也是反例为什么有用的根源。一个全称条件命题声称所有研究对象都不会出现 $P\land\neg Q$ 。只要找到一个对象同时满足 $P$ 与 $\neg Q$ ，整句就被推翻。

否定箭头时，不要把两边分别加上否定号。 $\neg(P\to Q)$ 是 $P\land\neg Q$ ，不是 $\neg P\to\neg Q$ 。

逆命题、否命题与逆否命题

从 $P\to Q$ 出发，交换两端、否定两端，会得到三个相关命题。名字容易混，最稳妥的办法是先做符号操作，再贴名称。

名称	形式	做了什么
原命题	$P \to Q$	保持原方向
逆命题	$Q \to P$	交换前件、后件
否命题	$\neg P \to \neg Q$	两边同时否定
逆否命题	$\neg Q \to \neg P$

真正的等价关系只有两组：

P \to Q \equiv \neg Q \to \neg P

Q \to P \equiv \neg P \to \neg Q

原命题、逆命题、否命题与逆否命题的关系图，突出原命题与逆否命题等价、逆命题与否命题等价 — 交换与否定会产生四种形式；对角线上的两组分别等价。

为什么原命题与逆否命题等价

不要只记“原命题等价于逆否命题”，我们顺着失败情形看一次。

原命题 $P\to Q$ 失败，需要 $P$ 真、 $Q$ 假。逆否命题 $\neg Q\to\neg P$ 失败，需要 $\neg Q$ 真、 $\neg P$ 假，翻回去仍然是假、真。两者在同一个情形失败，其余情形同时为真，所以真值始终一致。

也可以用等价变形写成：

P \to Q \equiv \neg P \lor Q

而

\neg Q \to \neg P \equiv \neg(\neg Q) \lor \neg P \equiv Q \lor \neg P \equiv \neg P \lor Q

最后只用了双重否定和析取交换律。两个式子都化到了同一个形状。

一个反例把“逆”和“否”一起拆开

继续使用“如果 $n$ 是 $4$ 的倍数，那么 $n$ 是偶数”。四种形式分别是：

原命题：若 $4\mid n$ ，则 $2\mid n$ 。
逆命题：若 $2\mid n$ ，则 $4\mid n$ 。
否命题：若 $4\nmid n$ ，则。

原命题为真，逆否命题也为真。取 $n=6$ ，逆命题的前件为真而后件为假，所以逆命题为假；同一个 $6$ 也使否命题的前件为真、后件为假，因此否命题为假。

这不是巧合。逆命题与否命题本来就等价，因此能推翻其中一个的对象，也会推翻另一个。

写四种命题时的可靠顺序

设原命题是：“如果整数 $n$ 能被 $6$ 整除，那么 $n$ 能被 $3$ 整除。”

先只提取两个完整命题。令 $P$ 表示“ $6\mid n$ ”，令 $Q$ 表示“ $3\mid n$ ”。暂时不要在中文句子里直接换词。

证明 $P\to Q$ 时改证 $\neg Q\to\neg P$ ，证明目标没有变弱。逆否命题是同一个逻辑内容的另一种写法。

充分条件、必要条件与双条件

如果 $P\to Q$ 为真，我们可以从两个方向描述同一支箭头：

$P$ 是 $Q$ 的充分条件，因为有了 $P$ 就足以得到 $Q$ 。
$Q$ 是 $P$ 的必要条件，因为缺少 $Q$ 时 $P$ 不可能成立。

“充分”和“必要”不是两条箭头。它们是对 $P\to Q$ 的两种读法。

集合 P 完全包含在集合 Q 内，表示 P 是 Q 的充分条件，Q 是 P 的必要条件 — 把满足条件的对象看成集合：若 $P\subseteq Q$ ，进入 $P$ 就一定进入 $Q$ 。

例如，在整数范围内，“是 $4$ 的倍数”对应的集合包含在“是偶数”的集合中。因此，“是 $4$ 的倍数”是“是偶数”的充分条件；“是偶数”是“是 $4$ 的倍数”的必要条件。

但“是偶数”不充分，因为 $6$ 是偶数而不是 $4$ 的倍数。一个条件可以必要却不充分，也可以充分却不必要。

把自然语言先翻成箭头

方向最容易藏在“只要”“只有”“仅当”这些词里。不要靠语感抢答，先问：谁成立以后，谁必须跟着成立？

自然语言	逻辑形式	方向判断
如果 $P$ ，那么 $Q$	$P\to Q$	$P$ 足以推出 $Q$
只要 $P$ ，就有

例如，“只有完成身份验证，才能提交申请”。令 $P$ 表示“可以提交申请”， $Q$ 表示“完成身份验证”。真正的箭头是

P \to Q

它并没有说完成验证以后一定提交申请，所以不能反过来写成 $Q\to P$ 。

判断充分、必要的机械方法很可靠：先写出 $P\to Q$ ，再读成“ $P$ 对 $Q$ 充分， $Q$ 对 $P$ 必要”。

当且仅当要求两个方向

双条件 $P\leftrightarrow Q$ 为真，表示 $P$ 与 $Q$ 真值相同：要么都真，要么都假。它等价于两个条件命题同时成立：

P \leftrightarrow Q \equiv (P \to Q) \land (Q \to P)

也等价于“两者同时真，或者两者同时假”：

P \leftrightarrow Q \equiv (P \land Q) \lor (\neg P \land \neg Q)

因此，证明“ $P$ 当且仅当 $Q$ ”不能只证一个方向。只证明 $P\to Q$ ，最多说明 $P$ 充分、 $Q$ 必要；还差 $Q\to P$ ，才能得到充要关系。

下面的分类练习不会让你凭词语猜答案。每题都显示 $A\to B$ 和 $B\to A$ 是否成立，可以用它训练“先看箭头，再叫名称”的习惯。

等价变形：把命题换成更好用的形状

两个命题逻辑等价，意思是：无论其中的命题变元怎样取真值，它们都同真同假。写作 $A\equiv B$ 。

这里的“等价”比“碰巧都为真”强得多。某次取值下 $A$ 与 $B$ 都真，只说明这一行相同；逻辑等价要求真值表的每一行都相同。所以，等价变形可以在任何论证中把一边替换成另一边，而不会改变命题内容。

条件命题的三种常用面孔

最常用的第一条是消去箭头：

P \to Q \equiv \neg P \lor Q

右边说“前件不成立，或者后件成立”，正好排除了 $P\land\neg Q$ 。再结合逆否等价，我们得到：

P \to Q \equiv \neg P \lor Q \equiv \neg Q \to \neg P

手绘白板展示 P 到 Q、非 P 或 Q、非 Q 到非 P 三种等价形式 — 三个式子真值完全一致；选择哪一种，取决于哪种形状更方便继续推理。

消去箭头以后，否定条件命题也能一步一步推出来：

\begin{aligned} \neg(P \to Q) &\equiv \neg(\neg P \lor Q) \\ &\equiv \neg\neg P \land \neg Q \\ &\equiv P \land \neg Q \end{aligned}

第二步是德摩根律，第三步是双重否定。这比单独背一个结论更牢靠：忘记时，可以重新推一遍。

一组常用的命题代数

真值表能检验等价，但变元一多，行数会按 $2^n$ 增长。三个变元有 $8$ 行，十个变元已有 $1024$ 行。实际变形时，我们通常像做代数那样，一次使用一条已经确认的等价律。

名称	等价式
双重否定	$\neg\neg P\equiv P$
交换律	$P\land Q\equiv Q\land P$ ， $P\lor Q\equiv Q\lor P$

逻辑代数与普通数的代数长得相似，却不能完全照搬。尤其是“或”也能对“且”分配：

P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)

普通加法对乘法没有对应规律，所以不要只凭外形猜等价式。拿不准时，用真值表检查。

范式：把任意公式整理成统一结构

命题代数还有一个很实用的目标：把复杂公式整理成只含“且、或、非”的标准形状。命题变元或它的否定叫文字，例如 $P$ 、 $\neg Q$ 都是文字。

析取范式是“若干合取项用或连接”。每个合取项内部只有文字，例如：

(P\land Q)\lor(P\land\neg R)

合取范式则把结构反过来，是“若干析取项用且连接”：

(P\lor Q)\land(\neg P\lor R)

真值表解释了为什么任何命题公式都能写成这两类范式。构造析取范式时，逐个查看公式为真的行：为每一行写一个只在该行成立的合取项，再把这些合取项用“或”连起来。构造合取范式时，逐个查看公式为假的行：为每一行写一个只在该行失败的析取项，再把这些析取项用“且”连起来。

例如， $A\land(B\lor C)$ 只在 $A$ 真且 $B,C$ 至少一个为真时成立。从三条真值行直接读出的完整析取形式是：

(A\land B\land C) \lor(A\land B\land\neg C) \lor(A\land\neg B\land C)

再使用分配律和吸收律，可以把它缩短为：

(A\land B)\lor(A\land C)

原式 $A\land(B\lor C)$ 本身已经是合取范式。范式不一定是最短写法，它的价值是提供统一结构：比较两个公式、设计逻辑电路或把约束交给求解程序时，统一形状往往比表面简短更重要。

真值表给出一种保证能完成的范式构造法，等价律则可能更快地得到简洁结果。前者稳定，后者依赖你是否看得出合适的变形路线。

例题：把一个条件拆成两个条件

证明下面的等价式：

P \to (Q \land R) \equiv (P \to Q) \land (P \to R)

我们先想它为什么合理。左边说：只要 $P$ 发生， $Q$ 和 $R$ 都要发生。那自然等于同时提出两个要求：“ $P$ 发生就有 $Q$ ”以及“ $P$ 发生就有 $R$ ”。正式变形如下：

\begin{aligned} P \to (Q \land R) &\equiv \neg P \lor (Q \land R) \\ &\equiv (\neg P \lor Q) \land (\neg P \lor R) \\ &\equiv (P \to Q) \land (P \to R) \end{aligned}

第一、三步消去或恢复箭头，第二步使用析取对合取的分配律。每一行都与上一行等价，所以整条变形链可以双向使用。

例题：否定一串规则

设有两条规则 $P\to Q$ 与 $Q\to R$ 。要说“这两条规则没有同时被遵守”，我们否定它们的合取：

\begin{aligned} \neg\bigl((P\to Q)\land(Q\to R)\bigr) &\equiv \neg(P\to Q)\lor\neg(Q\to R) \\ &\equiv (P\land\neg Q)\lor(Q\land\neg R) \end{aligned}

结果说得很具体：至少有一条规则出现了“前件成立、后件失败”。等价变形的价值就在这里——它能把一句抽象的“不满足规则”，改写成可以实际检查的失败状态。

等价、永真与可满足不要混在一起

一个公式在所有真值赋值下都为真，叫永真式，也叫有效公式。例如：

P \lor \neg P

一个公式只要在至少一种赋值下为真，就叫可满足。例如 $P\land Q$ 不是永真式，但在 $P,Q$ 都真时成立，因此可满足。

等价与永真之间有一条很方便的桥： $F$ 与 $G$ 等价，当且仅当 $F\leftrightarrow G$ 是永真式。

F \equiv G \quad\Longleftrightarrow\quad F \leftrightarrow G\text{ 在每一种赋值下都为真}

这也告诉我们怎样否定“两个公式等价”：不必说明它们处处不同，只要找一组赋值，使一个真、另一个假，就足够了。

有效推理规则：结论有没有被前提锁定

逻辑等价是在比较两个公式是否同真同假；推理有效性是在问另一件事：当前提全部为真时，结论有没有可能为假？

设前提是 $A_1,A_2,\ldots,A_k$ ，结论是 $C$ 。推理有效，恰好表示下面这个条件命题是永真式：

(A_1\land A_2\land\cdots\land A_k)\to C

换句话说，我们允许前提在某些赋值下为假，也允许结论在某些赋值下单独为假；唯一不允许的是“这一组前提全真，而结论假”。

“推理有效”不等于“每条前提都符合事实”。有效性只保证：如果前提全真，结论就不能假。要得到可靠结论，还要另外确认前提确实为真。

四条与条件命题直接相关的规则

规则	前提与结论	为什么有效
肯定前件	$P\to Q,\ P\ \therefore Q$	唯一失败行 $P\land\neg Q$ 已被排除
否定后件	$P\to Q,\ \neg Q\ \therefore \neg P$

肯定前件

前提一：“如果 $n$ 能被 $12$ 整除，那么 $n$ 能被 $3$ 整除。”

前提二：“ $84$ 能被 $12$ 整除。”

结论：“ $84$ 能被 $3$ 整除。”

令 $P$ 表示“ $12\mid84$ ”， $Q$ 表示“ $3\mid84$ ”。形式就是：

P\to Q,\quad P\quad\therefore Q

这条规则常被称为肯定前件。我们已经知道 $P$ 成立，而 $P\to Q$ 禁止 $P$ 真、 $Q$ 假，所以 $Q$ 只能为真。

否定后件

前提一：“如果输入通过校验，程序就进入计算步骤。”

前提二：“程序没有进入计算步骤。”

结论：“输入没有通过校验。”

形式是：

P\to Q,\quad \neg Q\quad\therefore \neg P

这条规则其实没有增加新魔法。把第一条前提换成等价的逆否命题 $\neg Q\to\neg P$ ，再和 $\neg Q$ 一起使用肯定前件，就得到 $\neg P$ 。

假言三段论

如果“服务器过载会触发限流”，而“触发限流会延迟部分请求”，那么“服务器过载会延迟部分请求”。

P\to Q,\quad Q\to R\quad\therefore P\to R

注意结论仍是条件命题。我们没有断言服务器已经过载，也没有断言请求已经延迟；我们只是把两段可靠的箭头接成了一段更长的箭头。

析取三段论

如果已经确认“文件在目录 $A$ 或目录 $B$ ”，又确认“不在目录 $A$ ”，就可以推出“文件在目录 $B$ ”。

P\lor Q,\quad \neg P\quad\therefore Q

这条规则依赖第一条前提真的是逻辑上的“至少一个成立”。如果原句只是“我猜在 $A$ 或 $B$ ”，那只是前提不可靠，不是规则本身失效。

几条基础组合规则

证明中还会频繁用到一些不带箭头的规则：

规则	形式	用法
合取消去	$P\land Q\ \therefore P$	已知两件事都真，可取其中任一件
合取引入	$P,\ Q\ \therefore P\land Q$	分别得到两件事，可把它们合在一起
析取引入	$P\ \therefore P\lor Q$

这些规则看起来很朴素，但正式证明里常常缺的就是其中一步。例如，要证明 $R\to(P\land Q)$ ，分别推出 $P$ 和 $Q$ 后，还应明确用合取引入得到 $P\land Q$ 。

用“寻找坏的一行”检查规则

如果不确定一条推理是否有效，可以按下面的顺序检查：

先把自然语言中的完整命题分别记成 $P,Q,R$ ，不要把关键词相似当成逻辑结构相同。

强制让结论为假。有效性的唯一危险情形就是“前提全真、结论假”，所以从结论假开始找最快。

在结论为假的条件下，尝试让所有前提同时为真。如果做得到，就找到一个反赋值，推理无效。

例如，要检查肯定前件，先让结论 $Q$ 为假。为了让前提 $P$ 为真，只能取 $P$ 真；但这会使另一个前提 $P\to Q$ 为假。因此无法让两个前提全真而结论假，规则有效。

下面的检查器把有效规则和常见谬误混在一起。做题时不要先看结论听起来是否正确，先把前提和结论压成符号骨架。

两个最像正确推理的谬误

无效推理并不一定得出假结论。它真正的问题是：前提没有把结论锁住。某个例子里结论碰巧为真，也救不了一个无效的推理形式。

肯定后件：看见结果就倒推原因

肯定后件的形式是：

P\to Q,\quad Q\quad\therefore P

它和肯定前件只差一个字，却是无效的。 $P\to Q$ 允许 $Q$ 通过别的条件成立。

例如：

如果一个整数是 $4$ 的倍数，那么它是偶数。 $10$ 是偶数。所以 $10$ 是 $4$ 的倍数。

第一条前提真，第二条前提也真，结论却假。 $10$ 直接给出了“前提全真、结论假”的反例。

哪怕把 $10$ 换成 $12$ ，结论碰巧变真，这段推理的形式仍然无效。我们需要的是“一切满足前提的情况都保住结论”，不能靠刚好猜对一次。

否定前件：一个办法失效就否定结果

否定前件的形式是：

P\to Q,\quad \neg P\quad\therefore \neg Q

它和否定后件也很像，但方向错了。 $P$ 不成立，只能说明这条通往 $Q$ 的路没有启用，不能说明 $Q$ 没有别的成立方式。

例如：

如果一个整数是 $4$ 的倍数，那么它是偶数。 $6$ 不是 $4$ 的倍数。所以 $6$ 不是偶数。

前两句都真，结论假。问题恰好在于把原命题误当成了否命题。

手绘警示对照图展示肯定后件和否定前件两种无效推理 — 肯定后件是在偷用逆命题，否定前件是在偷用否命题；原命题并不保证这两个方向。

为什么这两种错误总让人觉得顺耳

日常表达经常省略背景。有人说“如果刷卡成功，门会开”，听者可能自动补成“门只会因为刷卡成功而开”。一旦补上“只有这一种原因”，逆命题也成立，整句话就变成双条件。但原来的 $P\to Q$ 并没有包含这层信息。

所以，遇到肯定后件或否定前件时，不要争论故事是否合理，直接问：我们是否另有前提 $Q\to P$ ？如果有，便能合法反向；如果没有，就只能停在原箭头上。

看到 $P\to Q$ 后，不能自动得到 $Q\to P$ ，也不能自动得到 $\neg P\to\neg Q$ 。能保证等价的是逆否命题 $\neg Q\to\neg P$ 。

反例与反赋值是最短的诊断

要说明一个推理形式无效，最有力的办法不是说“感觉不严谨”，而是给出一组真值：

推理	取值	前提	结论
肯定后件	$P=\mathrm{F},Q=\mathrm{T}$	$P\to Q$ 真， $Q$ 真	$P$ 假
否定前件

同一组取值同时拆穿了两种谬误。它表达的核心就是：前件可以不成立，而后件仍然成立。

把条件推理真正写成证明

证明不是把所有脑内尝试原样写下来，也不是直接端出一个看似漂亮的结论。比较可靠的工作方式分两层：草稿阶段寻找路线，成稿阶段把路线写成可核查的推理链。

草稿可以问得很直白：“假设给我的条件后，我能写出什么定义？”“结论要我得到一个存在式，那个对象该怎么构造？”“直接走不顺，是不是否定结论以后结构更清楚？”这些问题不一定出现在最终证明里，但它们解释了下一步从哪里来。

条件命题的两条证明路线，直接证明从 P 到 Q，逆否证明从非 Q 到非 P — 证明 $P\to Q$ 时，先比较直接路线与逆否路线，选择结构更清楚的一条。

直接证明：假设前件，推出后件

证明 $P\to Q$ 的标准骨架很短：

假设 $P$ 成立。
使用定义、已知事实和有效规则推出 $Q$ 。
明确说明 $Q$ 已成立，因此 $P\to Q$ 得证。

真正费脑筋的是第二步。看下面这个命题：若实数 $x$ 满足 $0\le x\le2$ ，则 $-x^3+4x+1>0$ 。

直接看三次式，很难从“ $0\le x\le2$ ”立刻看出它为正。草稿阶段可以先观察：负项是 $-x^3$ ，正项是 $4x$ ，也许能把它们合并并因式分解：

-x^3+4x=x(4-x^2)=x(2-x)(2+x)

现在假设中的两个端点条件都派上了用场： $x\ge0$ ， $2-x\ge0$ ，而 $2+x\ge0$ 。于是三个非负数的乘积非负，再加 $1$ 就严格为正。

把草稿整理成证明：

假设 $0\le x\le2$ 。于是 $x\ge0$ 、 $2-x\ge0$ ，并且。

这段证明没有隐藏关键灵感：因式分解的目的，是把题目给的区间条件变成三个因子的符号信息。

逆否证明：结论的否定更容易展开时

有些命题直接从 $P$ 推 $Q$ 很别扭，但 $\neg Q$ 有清楚的结构。这时证明等价的逆否命题 $\neg Q\to\neg P$ 。

证明：如果整数 $n^2$ 是偶数，那么 $n$ 是偶数。

直接假设 $n^2$ 是偶数，只能写出 $n^2=2k$ ，很难从平方中“开出”一个整数因子。反过来， $n$ 不是偶数意味着 $n$ 是奇数，而奇数有明确形式 $2k+1$ 。这就是选择逆否路线的理由。

我们证明逆否命题：如果 $n$ 不是偶数，那么 $n^2$ 不是偶数。

假设整数 $n$ 不是偶数。整数非奇即偶，所以是奇数，存在整数使。

逆否证明不是“先假设结论错误，再导出矛盾”。它直接证明 $\neg Q\to\neg P$ 。反证法会假设整个目标命题的否定，两者在写法和使用时机上并不相同。

双条件证明：把两个方向分别交代

证明 $P\leftrightarrow Q$ 最稳妥的模板是先证 $P\to Q$ ，再证 $Q\to P$ 。两个方向可以使用不同方法。

证明：整数 $n$ 是偶数，当且仅当 $n^2$ 是偶数。

先证正向。假设 $n$ 是偶数，则存在整数 $k$ 使 $n=2k$ 。于是 $n^2=4k^2=2(2k^2)$ ，所以是偶数。

另一种写法是构造等价链：

P\equiv P_1\equiv P_2\equiv\cdots\equiv Q

这种写法很短，但每一步都必须可逆。如果某一步只证明了左边推出右边，就只能写 $\to$ ，不能写 $\leftrightarrow$ 。初学阶段如果拿不准可逆性，分成两个方向写通常更安全。

一份能实际使用的证明检查表

先写清目标的逻辑形状。它是 $P\to Q$ 、 $P\leftrightarrow Q$ ，还是某个复合命题？形状决定证明的外层结构。

若目标是条件命题，比较直接路线和逆否路线。看哪一边的假设能更快落到定义或已知事实上。

从命题箭头走向量词

到这里，我们一直把 $P,Q$ 当成已经能判断真假的完整命题。实际定理往往还带着变量，例如：

\text{如果整数 }n\text{ 是 }4\text{ 的倍数，那么 }n\text{ 是偶数}

它背后真正完整的结构是：

\forall n\in\mathbb Z,\quad 4\mid n\to2\mid n

箭头负责描述“对一个固定的 $n$ ，前件和后件怎样关联”；全称量词负责说明“这种关联要覆盖哪些 $n$ ”。这两个层次不能混在一起。

因此，后面处理量词时，今天的规则仍然保留：否定箭头会得到“前件真且后件假”。新的问题是，否定“对所有 $n$ ”还会把全称量词变成存在量词。直观上，就是从“每个对象都守规则”变成“至少有一个对象违背规则”。

我们将在下一章把这件事写成严格的符号变形。现在先记住连接点：反例之所以能推翻全称条件命题，是因为它找到了一个具体对象，让 $P\land\neg Q$ 成立。

练习：先看结构，再做计算

基础辨析

练习一：写出命题“如果四边形是正方形，那么它是矩形”的逆命题、否命题和逆否命题，并判断真假。

令 $P$ 表示“四边形是正方形”， $Q$ 表示“四边形是矩形”。逆命题 $Q\to P$ 是“如果四边形是矩形，那么它是正方形”，为假；否命题 $\neg P\to\neg Q$ 是“如果四边形不是正方形，那么它不是矩形”，也为假；逆否命题 $\neg Q\to\neg P$ 是“如果四边形不是矩形，那么它不是正方形”，为真。原命题与逆否命题等价，逆命题与否命题等价。

练习二：把 $P\to(Q\lor R)$ 改写成只含 $\neg,\land,\lor$ 的形式，再写出它的否定。

练习三：判断推理是否有效：“如果 $a$ 是大于 $2$ 的质数，那么 $a$ 是奇数。 $a$ 不是大于 $2$ 的质数。所以 $a$ 不是奇数。”

证明练习

练习四：证明：如果整数 $n$ 是奇数，那么 $n^2$ 是奇数。写证明前，先说明你准备如何使用“奇数”的定义。

练习五：证明：对整数 $n$ ， $n$ 能被 $6$ 整除，当且仅当 $n$ 同时能被 $2$ 和 $3$ 整除。

练习六：有人写道：“若程序通过全部测试，则程序没有缺陷。这个程序没有通过全部测试，所以它有缺陷。”指出逻辑形式，并说明还缺少什么信息才能得到结论。

令 $P$ 表示“程序通过全部测试”， $Q$ 表示“程序没有缺陷”。原推理是 $P\to Q,\neg P\therefore\neg Q$ ，属于否定前件。没有通过全部测试可能是环境、配置或测试本身的问题，也可能确实有缺陷；现有前提没有锁定原因。若要合法推出“程序有缺陷”，还需要另一个方向 $\neg P\to\neg Q$ ，或者其他足以排除替代原因的前提。

P \land \neg Q

C_5

Q

Q

P = F, Q = T

P=\mathrm{F},Q=\mathrm{T}

n