# 证明(Proofs)

• 数学证明(Mathematical proofs)与计算机程序(Computer programs)之间有着非常紧密的联系。
• 具体来说：
  • 对于一个程序$P$，它是否对任意的输入都会中止(有结果)？这个程序能否对任意的输入$x$，正确计算$f(x)$？（注意这里$x$代表的是无穷多的输入）
  • 为了确保对无穷多的输入都能正确输出，我们就需要严格的证明(proof)。

# 什么是证明？

• 证明指代的是用一系列有限的推导步骤（称为逻辑推理logical deductions），建立一个我们想得到的命题（结论）的过程。
• 证明的强大之处就在于它可以用有限的手段保证结论适用于无限的情况。
• 具体而言，一个证明是按照以下方式架构的：
  • 首先，将一些特定的命题（被称为公理(axioms)或先决假设(postulates)。这些命题是公认的，无需证明）作为证明的起点。
  • 然后，进行一系列逻辑推理（基于简单的逻辑规则），这样可以使得在当前命题为真的条件下，后续的命题一定为真。（即一系列的“蕴含”$\Longrightarrow$）
  • 上面的这种逻辑规则在人类思维中起到了非常重要的作用，同时也是计算机设计的基石。更进一步，这也是人工智能不可或缺的一部分，因为它的目标就是用计算机模仿人类思维。

# 一些数学符号约定及事实

• $\mathbb{Z}=\{\cdots,-2,-1,0,1,2,\cdots\}$：整数集
• $\mathbb{N}=\{0,1,2,\cdots\}$：自然数集
• 注意到，整数集和自然数集在加法与乘法运算上都是封闭的。
• 关于整除：给定整数$a$和$b$，如果存在整数$q$使得$b=aq$，那么我们称$a$整除$b$($a|b$)。
• 我们称自然数$p (p\geq 2)$为质数，当且仅当它能被$1$和自身整除。
• 最后，我们使用$\coloneqq$表示定义。（比如： $a\coloneqq 6657$定义了$a$的值为$6657$）

# 直接证明(Direct proof)

• 从一个简单的例子开始：
• 对于任意$a,b,c\in\mathbb{Z}$，当$a|b$且$a|c$，那么$a|(b+c)$。
  • 注：当我们用$P(x,y)$代表“$x|y$”，那么上述定理可记为$(\forall a,b,c\in\mathbb{Z})(P(a,b)\land P(b,c))\Longrightarrow P(a,(b+c))$
• 直接证明的过程：
  1. 确定需要证明的命题：$P(x)\Longrightarrow Q(x)$
  2. 假设P(x)对满足条件的$x$都成立，再通过一条蕴含链(chain of implications)得到命题$Q(x)$成立的结论。
• 具体来说，对于上面这个例子：
  • 假设$a|b$且$a|c$，那么存在$q_{1},q_{2}\in\mathbb{Z}$使得$b=q_{1}a,c=q_{2}a$
  • 然后有$b+c=(q_{1}+q_{2})a$，又因为整数集加法封闭，有$q_{1}+q_{2} \in \mathbb{Z}$
  • 于是得到$a|(b+c)$，正是我们想要得到的结论。
  • 那么在证明中，$a,b,c$的“$\forall$”性如何体现呢？实际上，在证明过程中，$a,b,c$都没有被赋予特定的值，所以它们自然就是任意的！
• 有时，我们想要证明$P(x)\Longleftrightarrow Q(x)$，那么就需要证明以下两个命题都成立：$P(x)\Longrightarrow Q(x)$和$Q(x)\Longrightarrow P(x)$
  • 这有点像数学证明中的充分性必要性证明

# 利用逆否命题证明(Proof by Contraposition)

• 在CS70 Chapter1中，我们已经知道$P\Longrightarrow Q$和$\lnot Q\Longrightarrow \lnot P$等价
• 而有时，证明$\lnot Q\Longrightarrow \lnot P$要比直接证明$P\Longrightarrow Q$容易得多
• 因此，我们有时会用逆否命题$\lnot Q\Longrightarrow \lnot P$来证明
• 例子略

# 利用反证法证明(Proof by Contradiction)

• 反证法的思路核心：假定结论不成立，再通过条件与结论两边的推理得出矛盾(Contradiction)，由此得到结论成立。
  • 这基于一个重要定律：排中律（见于CS70 Chapter1）
  • 更加严谨的证明：
    • 反证法证明过程：目标是证明$P$成立(条件为$R$)。先假设$\lnot P$成立，通过逻辑推理得到$\lnot R$，得到结论$\lnot P\Longrightarrow R\land\lnot R$。
    • 而$\lnot P\Longrightarrow R\land\lnot R\equiv False$，它的逆否命题就是$True\Longrightarrow P$，即$P$成立。

# 一个经典的例子

• 欧几里得质数定理 ：证明质数有无穷多个。
  • 如果尝试直接证明，会发现似乎很困难。
  • 于是我们选择换个角度：假设结论不成立，即质数只有有限个，我们尝试推出矛盾。
  • 在进一步推理之前，先给出一个引理(lemma)：
    • 对于任意的大于$1$的自然数，它要么是质数，要么能被一个质数整除。
    • 这个引理的证明将会在后面归纳的章节进行，在此不赘述。
  • 有了这个引理，我们可以有继续证明：
    • 设质数只有有限个，将它们记为$p_{1},p_{2},\cdots,p_{k}$；
    • 现在定义$q\coloneqq p_{1}\times p_{2}\times\cdots\times p_{k}+1$，根据条件与引理可知，$q$不是质数，于是$q$可以被一个质数整除，设这个质数为$p$；
    • 则$p$一定在$p_{1},p_{2},\cdots,p_{k}$之中，所以$p|r\coloneqq p_{1}\times p_{2}\times\cdots\times p_{k}$；
    • 因此，有$p|q$且$p|r$，那么$p|(q-r)$，又$q-r=1$，于是$p\leq 1$，$p$不是质数。这就与上述条件矛盾，最终得到结论成立。

# 另一个经典的例子

• 证明$\sqrt{2}$为无理数。
  • 同样先给出一个引理，这个引理同样也可以用反证法证明（过程略）：
    • 引理：如果$a^{2}$是偶数，那么$a$也是偶数。
  • 下面用反证法证明：
    • 假设$\sqrt{2}$为有理数，那么存在互质的整数$p,q$，使得$\sqrt{2}=\frac{p}{q}$；
    • 有等式可知$2=\frac{p^2}{q^2}$，即$p^2=2q^2$。而$q$是整数，因此$p^2$为偶数，由引理得$p$为偶数，即存在整数$r$使得$p=2r$；
    • 那么带入可得$4r^2=2q^2\longrightarrow q^2=2r^2$，类似可得$q$也是偶数。
    • 那么$p$和$q$就有公因子$2$，这与$p,q$互质矛盾，因此结论成立。

# 分情况证明(Proof by cases)

• 有时将条件作为整体去证明结论比较困难，那么就可以选择将条件进行分解，通过分类讨论证明同一个结论。
• 在分类讨论时，有时也不一定需要严格的枚举，对于每一种情况，只要能找到一个具体的取值（案例）能得到结论就可以。

# 例子

• 证明：存在无理数$x,y$使$x^y$为有理数。
• 注意到命题中使用了“存在”，那么只需要举出一对$x,y$满足条件和结论就可以了。
• 我们先取$x=\sqrt{2},y=\sqrt{2}$，并将结果分为两种情况：
  1. $x^y=\sqrt{2}^{\sqrt{2}}$是有理数，那么已经满足条件和结论；
  2. $\sqrt{2}^{\sqrt{2}}$是无理数，那么我们再取$x=\sqrt{2}^{\sqrt{2}},y=\sqrt{2}$，有$x^y=(\sqrt{2}^{\sqrt{2}})^{\sqrt{2}}=(\sqrt{2})^{\sqrt{2}\sqrt{2}}=(\sqrt{2})^2=2$是有理数，满足条件和结论。
  3. 因为所有情况只会归为1和2中的一个，所以结论成立。
• 事实上，我们在上述证明过程中甚至都不知道真正满足条件的$x$是什么，但我们还是完成了证明。这种证明可以称为非构造性证明(non-constructive proof)。

# 一些证明时的注意事项

1. 不要将结论直接当作条件——这有可能得到错误的结果。
2. 注意“$0$”的存在——等式两边同时有$0$时不能同时消去。
3. 不等式推导中注意两边同时乘负数时不等号方向改变。
4. 其实这些感觉都是从小就培养的思维了，应该不会有什么问题

# 书写证明的风格

1. 关于逻辑推理的步骤：在书写下一步之前，确保当前得到的命题已经被严格证明成立（基于公理和之前的推理）。必要时可能需要将一个步骤分解为若干个步骤，以让读者理解并接受。
2. 关于引理的使用：引理本质是由一个相对简单的命题得到的结论。一个复杂的命题可以分解为若干个引理，就像一个计算机程序可以分解为几个子程序一样。当然，设置引理的目标还是让引理尽量具有普适性。
3. 另外，引理其实和定理之间没有明确的界限。在一个特定的命题中，定理一般是最终得到的结论，而引理可视为在证明中使用的命题。（然而实际上有一些著名的引理常被用来作为命题以证明，如the Pumping Lemma and the Lifting Lemma）