什么算作一个有效证明？¶

先备知识¶

需要会读集合、量词和蕴含符号，并知道整数的奇偶性：偶整数可写成 \(2k\)，奇整数可写成 \(2k+1\)，其中 \(k\in\mathbb Z\)。高等代数、解析几何和 Python 都没有额外先备。本单元只要求把已经知道的定义和规则组织成可检查的推理链。

学习目标¶

完成本单元后，你应能：

从定义出发组织一个直接证明；
将蕴含命题改写为等价的逆否命题；
在反证法中清楚指出假设与矛盾；
用一个反例否定全称命题。

牵引问题¶

所有命题都有同一种证明吗？

例如，验证 \(1^2,3^2,5^2\) 都是奇数，不能证明“每个奇整数的平方都是奇数”；有限次检验只说明这些样本成立。证明必须说明：为什么任意一个符合前提的对象都逃不出结论。不同的命题会要求不同的路线：有时直接从定义推，有时改证逆否命题，有时假定结论失败而推出矛盾；若原命题是全称命题，找到一个反例就足以否定它。

探索与猜想¶

考虑命题

\[ P:\quad \text{若整数 }n^2\text{ 是偶数，则 }n\text{ 是偶数。} \]

直接从“\(n^2\) 是偶数”倒推出 \(n\) 的形式并不方便。它的逆否命题却是

\[ \text{若 }n\text{ 是奇数，则 }n^2\text{ 是奇数。} \]

只要把 \(n\) 写成 \(2k+1\)，就能计算平方。这揭示一个重要原则：\(P\Rightarrow Q\) 与 \(\neg Q\Rightarrow\neg P\) 永远同真同假，因此可以选择较易处理的一边证明。

另一方面，若有人断言“每个有界数列都收敛”，我们不必逐一检查所有数列。数列

\[ a_n=(-1)^n \]

始终落在 \([-1,1]\) 内，却在 \(1\) 与 \(-1\) 间交替。它不能越来越接近某一个单独的数，因此是一个反例。数列收敛的正式定义将在第二部给出；此处只用这个现象辨认错误的全称陈述。

概念与理论¶

证明不是样本检查¶

一个证明由明确的前提、已知定义或已证明结果，经过每一步都可核查的推理，得到结论。证明的对象通常是一个带量词的命题。例如要证明

\[ (\forall n\in\mathbb Z)\bigl(n\text{ 为奇数}\Rightarrow n^2\text{ 为奇数}\bigr), \]

必须任取一个奇整数 \(n\)，而不是只代入几个值。有限样本可以帮助猜想，却不能代替全称证明。

直接证明与逆否证明¶

证明 \(P\Rightarrow Q\) 的直接证明从 \(P\) 出发，利用定义和已知事实导出 \(Q\)。例如要证明“两个偶整数的和是偶整数”，可设 \(a=2r\)、\(b=2s\)，于是 \(a+b=2(r+s)\)。

同一蕴含还可以证明它的逆否命题：

\[ P\Rightarrow Q \quad\Longleftrightarrow\quad \neg Q\Rightarrow\neg P. \]

注意逆否命题不是逆命题 \(Q\Rightarrow P\)。只有逆否命题与原命题逻辑等价。

反证法与反例¶

要证明一个命题 \(P\)，反证法先假定 \(\neg P\)，再推出不可能同时成立的结论，例如某个整数既为奇数又为偶数，或 \(0=1\)。矛盾表明最初的否定不成立，因此 \(P\) 成立。反证法必须写清楚：假定了什么，矛盾具体是什么。

反例服务于相反的任务。一个全称命题 \((\forall x\in A)P(x)\) 被一个满足 \(x_0\in A\) 且 \(\neg P(x_0)\) 的对象否定。反例不是“看起来不对”的解释，而是同时给出范围内对象和失败条件的证据。

例题与迁移¶

例：用逆否命题证明平方的奇偶性¶

证明：若整数 \(n^2\) 是偶数，则 \(n\) 是偶数。

证明。 证明其逆否命题：若 \(n\) 是奇数，则 \(n^2\) 是奇数。设 \(n=2k+1\)，其中 \(k\in\mathbb Z\)。则

\[ n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1. \]

括号内是整数，故 \(n^2\) 是奇数。逆否命题成立，因而原命题成立。\(\square\)

迁移：修复一个伪证明¶

下面的“证明”试图说明“若 \(x^2=1\)，则 \(x=1\)”：

由 \(x^2=1\)，开平方得 \(x=1\)，所以结论成立。

它遗漏了负数平方也为 \(1\) 的情形。正确的因式分解是 \((x-1)(x+1)=0\)，所以 \(x=1\) 或 \(x=-1\)。原命题是假命题，\(x=-1\) 就是反例。修复推理并不总是让原结论成立；有时它帮助我们发现必须修改结论或补充假设。

即时检验与回望¶

为什么验证十个偶整数的平方仍不能证明“每个偶整数的平方是偶数”？

答案

因为待证命题涉及所有偶整数；十个样本没有覆盖任意的偶整数。应设 \(n=2k\) 并证明 \(n^2=2(2k^2)\)。

写出“若 \(x>0\)，则 \(x^2>0\)”的逆否命题。

答案

若 \(x^2\le0\)，则 \(x\le0\)。这是原蕴含的逆否命题；不要把它写成“若 \(x^2>0\)，则 \(x>0\)”，后者是逆命题且为假。

数列 \(a_n=(-1)^n\) 为什么能否定“每个有界数列都收敛”？

答案

它有界，因为 \(-1\le a_n\le1\)；但它在 \(1\) 和 \(-1\) 之间交替，不能靠近一个单独的数。严格的收敛定义将在第二部学习。

下列伪证明少了什么前提：“对任意实数 \(x\)，\(\sqrt{x^2}=x\)。”

答案

应补充 \(x\ge0\)。一般地 \(\sqrt{x^2}=|x|\)；取 \(x=-1\) 即得到反例。

回看牵引问题：证明方法由命题的逻辑形状决定。直接推导、逆否、反证和反例不是套话，而是分别处理“推出”“等价改写”“否定导致矛盾”和“全称命题失败”的工具。

习题与答案¶

ex-u-01-01-03-01¶

证明：两个奇整数的和是偶整数。

答案

设 \(a=2r+1\)、\(b=2s+1\)，其中 \(r,s\in\mathbb Z\)。则

\[ a+b=2r+2s+2=2(r+s+1). \]

因为 \(r+s+1\in\mathbb Z\)，所以 \(a+b\) 是偶整数。

ex-u-01-01-03-02¶

用逆否法证明：若整数 \(n^2\) 是奇数，则 \(n\) 是奇数。

答案

证明其逆否命题：若 \(n\) 是偶数，则 \(n^2\) 是偶数。设 \(n=2k\)，其中 \(k\in\mathbb Z\)。则

\[ n^2=4k^2=2(2k^2). \]

因为 \(2k^2\in\mathbb Z\)，\(n^2\) 是偶数。逆否命题成立，故原命题成立。

ex-u-01-01-03-03¶

用反证法完整证明：不存在最小的正有理数。

答案

完整解答。 反设存在最小的正有理数 \(r\)。由于 \(r>0\)，数 \(r/2\) 仍是正有理数；又 \(r/2<r\)。这与 \(r\) 是所有正有理数中最小的相矛盾。因此不存在最小的正有理数。\(\square\)

ex-u-01-01-03-04¶

否定下列全称命题并给出反例：对每个实数 \(x\)，若 \(x^2\ge x\)，则 \(x\ge1\)。

答案

否定是：存在实数 \(x\)，使 \(x^2\ge x\) 但 \(x<1\)。取 \(x=0\)，有 \(0^2\ge0\) 且 \(0<1\)，所以 \(x=0\) 是反例。