归纳法

Posted on

自然数上的一般归纳原理

假设$P$是自然数上的一个性质，则如果

  1. $P(0)$成立 – base case
  2. 对所有的自然数$k$，$P(k)$蕴涵$P(k+1)$ – induction step

则$P(n)$对所有自然数$n$成立

$$
\ \ \ \ \ \ \ \ \ \ [P(k)]\
\frac{P(0)\ P(k+1)}{P(n)}
$$

$[P(k)]$为归纳假设，$k$不能出现在$P(k + 1)$的任何假设中

定理：每个自然是要么是偶数，要么是奇数。
用归纳法来证明：

  1. 0 是偶数 -> 0 是偶数或奇数
  2. 假设 k 是偶数或奇数，证明 k + 1 是奇数或偶数：
    1. k 是偶数，则 k + 1 是奇数
    2. k 是奇数，则 k + 1 是偶数
  3. 得证

自然数上的完全归纳原理

假设$P$是自然数上的一个性质，则：
如果对每个自然数$k$，假定$P(i)$对所有自然数$i(i < k)$成立，则可以证明$P(k)$成立

$$
[\forall i < k.P(i)]\
\frac{P(k)}{P(n)}
$$

$k$不能出现在其他前提条件的其他假设中

定理：所有$n \geq 2$的自然数都可以写成素数的乘积$n = p_1…p_k$
对$n$进行完全归纳：

  1. $n$是素数，那么$n = n$
  2. $n$不是素数，则$\exists\ n % m = 0(1 < m < n)$所以$n = m * \frac{n}{m}$，
    对$m$和$\frac{n}{m}$再次归纳，得$m = p_1…p_k$且$\frac{n}{m} = q_1…q_k$
    得
    $$n = m * \frac{n}{m} = p_1…p_kq_1…q_k$$
  3. 得证

字典序归纳原理

假设$P$是自然数序对上的一个性质，则：
如果对每个自然数序对$(m, n)$，假定$P(m’, n’)$对所有的$(m’, n’) < (m, n)$成立，则可以证明$P(m, n)$成立

结构归纳法

形式 1

假设$P$是某个文法产生的任一表达式$e$上的一个性质，则：

  • 对每个原子表达式$e$，证明$P(e)$为真
  • 对直接子表达式为$e_1,…,e_k$的任何复合表达式$e$，证明如果$P(e_i)(i = 1, …, k)$都为真，则$P(e)$也为真

形式 2

假设$P$是某个文法产生的任一表达式$e$上的一个性质，则：

  • 对每个原子表达式$e$，证明$P(e)$为真
  • 对任何表达式$e$的任何子表达式$e’$，证明如果$P(e’)$都为真，则$P(e)$也为真

表的结构归纳法

假设 P 是元素类型为$\tau$的表(list)上的一个性质，则：

  • $P([])$, []表示空表
  • 对类型为$\tau$的所有元素$y$以及类型为$\tau$ list 的表$ys$都有$P(ys)$蕴涵$P(y::ys)$，则$P(xs)$对所有类型为$\tau$ list 的表$xs$成立
    $$
    \ \ \ \ \ \ \ \ \ \ [P(ys)]\
    \frac{P([])\ P(y::ys)}{P(xs)}
    $$
    $y$和$ys$不能出现在$P(y::ys)$的其他假设中

定理：所有的表都不等于自己的表尾
对$xs$结构归纳：

  • $\forall x.[x] \neq []$，两个表是相等的当且仅当它们具有相同的长度且对应的元素也相等
  • 假定$\forall x.x::ys \neq ys$成立，并对于任意的$y$和$ys$证明$\forall x.x::(y::ys) \neq y::ys$，所以只要证明两边表尾不相等：即证明$y::ys \neq ys$
    不适用于无穷表，$[n, n, …]$等于它自己的表尾

定理：对于所有的表 xs 和 ys，有$len(xs@ys) = len\ xs + len\ ys$（@连接运算）
对 xs 结构归纳：

  • $len([]@ys) = len[] + len\ ys$成立
  • 假定$len(xs\ @\ ys) = len\ xs + len\ ys$成立，那么我们可以证明对于所有的$x$和$xs$，有$len((x::xs)\ @\ ys) = len(x::xs) + len\ ys$也成立
    $$
    len((x::xs)@ys) = len(x::(xs@ys))\
    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 1 + len(xs@ys)\
    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 1 + (len\ xs + len\ ys)\
    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = (1 + len\ xs) + len\ ys\
    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = len(x::xs) + len\ ys
    $$

树的结构归纳法

假设 P 是类型$\tau$ tree 的树的一个性质，则：

  • $P(empty)$
  • 对于所有类型为$\tau$的元素$x$以及类型为$\tau$ tree 的树$t_1$和$t_2$都有，$P(t_1)$和$P(t_2)$蕴涵$P(node(x, t_1, t_2))$
    $$
    \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [P(t_1), P(t_2)]\
    \frac{P(empty)\ P(node(x, t_1, t_2))}{P(t)}
    $$
    $x$、$t_1$和$t_2$不能出现在$P(node(x, t_1, t_2))$的其他假设中

证明上的归纳

假设一个公式可以证明的，那么：
推理规则：若一组公式可证，则另一个公式也证$\frac{A_1…A_n}{B}$，如果$A_1,…,A_n$（前提）都可证，那么 B（结论）也可证

  • 相等性的自反公理： $e = e$
  • 相等性的传递规则：$\frac{e_1 = e_2\ e_2 = e_3}{e_1 = e_3}$

所以一个证明可以定义为一个公式序列，该序列中的每个公式都是公理或是由先前的公式通过一条推理规则得到的结论。可以有两个方法来归纳：

  • 对公式序列的长度进行自然数归纳法
  • 把证明看成树，所用的公理看叶节点，推理规则看成内部节点，由对$A_1, …, A_n$的证明来构造对$B$的证明

在某个证明系统中，证明对每个证明$\alpha$，$P(\alpha)$为真：

  • 对该系统中的每个公理，证明$P$成立
  • 假定对$\alpha_1,…,\alpha_k$，$P$都成立，证明$P(\alpha)$也成立，则$\alpha$是$\alpha_1,…,\alpha_k$延伸出的一个证明

证明系统的可靠性：在公式的某种特定解释下，每个可证的公式都为真。