离散数学——递归

数学归纳法

数学归纳法证明的是 $\forall nP(n)$ 的成立，其中 $P(n)$ 是一个谓词，数学归纳法有两个步骤：

1. 基础步骤：证明 $P(1)$ 成立。
2. 归纳步骤：证明 $\forall n(P(n)\to P(n+1))$ 成立。

为了证明第二点，我们先假设 $P(k)$ 成立，这个技巧叫做归纳假设。

在数学归纳中，还有一类称为强归纳的数学归纳法：

1. 基础步骤：证明 $P(1)$ 成立。
2. 归纳步骤：证明 $\forall n({\bigcap }_{i=1}^{n}P(n)\to P(n+1))$ 成立。

强归纳也称第二类数学归纳法，完全归纳法。可以证明，强归纳和第一类数学归纳法是等价，即可以用数学归纳法证明的也可以用强归纳证明，反之也一样。

良序原理是数学归纳法的原理和基础，良序原理说明，一个非空的非负整数集合，都有一个最小元素。

关于欧几里得算法的证明

1. 基础步骤： $\gcd (a,0)=a$ ，正确性显然。
2. 归纳步骤：$\gcd (a,b)=\gcd (b,a\mathrm{m}\mathrm{o}\mathrm{d}b)$ 。

对于归纳步骤来说，如果我们能够证明 $(a,b)$ 的任何一个公因子和 $(b,r)$ 一样，那么归纳步骤得证。

其中 $r=a-nb$ 其中 $n$ 是商数，如果 $(a,b)$ 存在公因子 $d$ ，那么$(a-nb)/d$ 一定是整数，那么 $r/d$ 一定是整数，因此 $d$ 是 $(b,r)$ 的一个公因子。

其中 $a=r+nb$ ，如果 $(b,r)$ 存在公因子 $d$ 那么 $a/d$ 也是一个整数，因此 $(a,b)$ 也有公因子 $d$ 。

递归定义

递归定义函数包括一下两步：

1. 基础步骤：指定函数在 $0$ 处的函数值。
2. 递归步骤：给定一个规则，能够通过 $0$ 到 $k$ 的函数值计算出 $k+1$ 的函数值。

上述定义称为递归定义或者归纳定义，递归定义是良定义的，这也就是说，在 $k$ 处的函数值是唯一定义的且没有歧义的。

除了递归定义的函数，还有递归定义的离散结构。

递归定义的离散结构同样包括两个步骤：

1. 基础步骤：指定了一个离散结构中的初始元素。
2. 递归步骤：由离散结构中的已知元素构造出更多元素的规则。

递归定义有时也包含排除规则，指出了离散结构除了基础步骤和递归步骤定义的元素外，不包含的元素。

字符串是一种递归定义的离散结构。

定义： 集合 ${\sum }^{\ast }$ 是在 $\sum$ 上定义的字符串集合，递归定义为：

基础步骤： $\lambda \in {\sum }^{\ast }$ 其中 $\lambda$ 是空字符串。

递归步骤：如果 $\omega \in {\sum }^{\ast }$ 并且 $x\in \sum$ ，那么 $\omega x\in {\sum }^{\ast }$ 。

合法形式是一种递归定义的离散结构。

例如合法括号序列的定义：

基础步骤：() 和空序列是一个合法的括号序列。
归纳步骤：如果 A 和 B 都是合法的括号序列，那么 (A) 是合法的括号序列， AB 也是合法的括号序列。

结构化归纳

结构化归纳是一种证明离散结构中某些元素具有某种性质的证明方法：

1. 基础步骤：证明在递归定义中的基础元素都满足该性质。
2. 归纳步骤：证明通过递归步骤得出的新元素也满足性质。

递归算法

我们说一个算法是递归的，当一个算法将问题通过解决相同实例的更小的子问题解决。

递归算法是一个自顶向下的过程，而迭代算法是一个自底向上的过程。

程序正确性

程序正确性指的是每一个合法输入，程序都会给出一个正确的结果，这是程序正确性的感性定义。

而程序正确性分为两个部分：

1. 部分正确性：给出一个合法输入，如果程序能终止，那么程序的结果一定是正确的。
2. 完全正确性：给出一个合法输入，程序总是是终止。

为了证明一个程序是满足正确性的，我们需要两个断言，第一个断言称为初始断言，指出了输入值所需要的属性，和最终断言，指出如果程序按照预期执行，那么一定有输出结果。

定义：如果一个程序 $S$ 是相对于初始断言 $p$ 和最终断言 $q$ 是部分正确的，如果 $p$ 是真的对于 $S$ 的输入来说，并且 $S$ 也能正常终止，那么 $q$ 就是正确的对于 $S$ 的输出来说。记为 p{S}qp\{S\}qp{S}q 。

记号 p{S}qp\{S\}qp{S}q 称为霍尔三元组。

部分正确性是好证明的，本节我们讨论部分正确性的证明，完全正确性不在本章的讨论范围内。

组合推导过程

有时候，使用推导规则能够简化程序的正确性证明：

如果 p{S1}qp\{S_1\}qp{S1​}q 并且 q{S2}rq\{S_2\}rq{S2​}r 那么 p{S1;S2}rp\{S_1;S_2\}rp{S1​;S2​}r 。

条件推导过程

证明程序：

if cond then S

也就是证明：

(p∧cond){S}q(p∧¬cond)→q (p \wedge cond)\{S\}q \\ (p \wedge \neg cond) \to q (p∧cond){S}q(p∧¬cond)→q

同样的证明程序：

if cond then S1 else S2

也就是证明：

(p∧cond){S1}q(p∧¬cond){S2}q (p \wedge cond)\{S_1\}q \\ (p \wedge \neg cond)\{S_2\}q (p∧cond){S1​}q(p∧¬cond){S2​}q

循环不变式

下一步，证明我们讨论如何证明循环程序的正确性。

while cond
    S

注意这个程序是一个循环程序，直到 $cond$ 为假时结束，可以看着是多次 if 条件语句，因此我们引出循环不变式。

循环不变式指的是一个断言，每次执行完 $S$ 之后，该断言保持为真。换句话说，如果 $p$ 是一个循环不变式，即 if(p∧cond){S}pif(p \wedge cond)\{S\}pif(p∧cond){S}p 是真的。

证明一个循环程序的正确性，也就是证明：

(p∧cond){S}p (p \wedge cond) \{S\}p (p∧cond){S}p

那么

p{while(cond)S}(¬cond∧p) p\{while(cond) S\}(\neg cond \wedge p) p{while(cond)S}(¬cond∧p)

成立。