math/discrete_math/5-Induction-and-Recursion.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第5章 归纳与递归\n",
    "## 5.1 数学归纳法\n",
    "### 5.1.2 数学归纳法\n",
    "**数学归纳法原理**：为证明对所有的正整数n，P(n)为真，其中P(n)是一个命题函数，需要完成两个步骤：\n",
    "\n",
    "- `基础步骤`：证明命题P(1)为真。\n",
    "- `归纳步骤`：证明对每个正整数k来说，蕴含式$P(k) \\to P(k+1)$为真。\n",
    "\n",
    "P(k)为真的假设叫做`归纳假设`。\n",
    "\n",
    "作为推理规则的一种表达方式，这一证明技巧可描述为：\n",
    "\n",
    "$$(P(1) \\land \\forall k(P(k) \\to P(k+1))) \\to \\forall n P(n)$$\n",
    "\n",
    "其中的论域是正整数集合。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.2强归纳法与良序性\n",
    "### 5.2.2 强归纳法\n",
    "**强归纳法**： 要证明对所有的正整数n而言，都有P(n)为真，其中P(n)为命题函数，我们要完成如下两个步骤：\n",
    "\n",
    "- `基本步骤`：证明P(1)为真。\n",
    "- `归纳步骤`：要证明对对所有正整数k来说，蕴含式$[P(1) \\land P(2) \\land \\cdots \\land P(k)] \\to P(k+1)$也为真。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.3 归纳定义与结构归纳法\n",
    "### 5.3.2 递归地定义函数\n",
    "为了定义非负整数集合作为其定义域的函数，使用两个步骤：\n",
    "\n",
    "- `基础步骤`：规定这个函数在0处的值。\n",
    "- `递归步骤`：给出从较小的整数处的值来求出当前的值得规则。\n",
    "\n",
    "**例1** 假定f是用f(0)=3,f(n+1)=2f(n)+3来递归定义的。求出f(1)、f(2)、f(3)和f(4)。\n",
    "\n",
    "解：从这个递归定义得出\n",
    "\n",
    "$$f(1)=2f(0)+3=2 \\cdot 3 + 3 = 9$$\n",
    "\n",
    "$$f(2)=2f(1)+3=2 \\cdot 9 + 3 = 21$$\n",
    "\n",
    "$$f(3)=2f(2)+3=2 \\cdot 21 + 3 = 45$$\n",
    "\n",
    "$$f(4)=2f(3)+3=2 \\cdot 45 + 3 = 93$$\n",
    "\n",
    "递归定义的函数是`良定义的`。即对于每一个正整数，函数对应取值是清楚定义的。这意味着给定任意整数，我们可以使用定义的这两个部分得到对应整数的函数值，无论怎么使用这两部分定义都会得到同样的值。\n",
    "\n",
    "### 5.3.3 递归地定义集合与结构\n",
    "正如在函数的递归定义中那样，集合的递归定义有两个部分：`基础步骤`和`递归步骤`。在基础步骤中，规定初始的一些元素。在递归步骤中，给出用来从已知属于集合的元素来构造集合的新元素的规则。\n",
    "\n",
    "**例5**：考虑如下定义的整数集合的子集S。\n",
    "\n",
    "基础步骤：$3 \\in S$。\n",
    "\n",
    "递归步骤：若$x \\in S$ 且 $y \\in S$，则$x+y \\in S$。\n",
    "\n",
    "基础步骤中求出的S中的新元素是3，递归步骤的首次应用求出的是3+3=6，递归步骤的第二次应用求出的是3+6=6+3=9以及6+6=12，等。\n",
    "\n",
    "**定义1**：字母表$\\sum$上的字符串的集合$\\sum^*$递归地定义为：\n",
    "- 基础步骤：$\\lambda \\in \\sum^*$（其中$\\lambda$是不包含任何符号的空串）。\n",
    "- 递归步骤：若$w \\in \\sum^*$且$x \\in \\sum$时，则$wx \\in \\sum^*$。\n",
    "\n",
    "**定义2**：通过连接运算可以组合两个字符串。设$\\sum$是符号的集合，$\\sum^*$是$\\sum$中符号形成的字符串的集合。可以如下定义两个字符串的连接，用$\\cdot$表示：\n",
    "- 基础步骤：若$w \\in \\sum^*$，则$w \\cdot \\lambda=w$，其中$\\lambda$是空串。\n",
    "- 递归步骤：若$w_1 \\in \\sum^*$且$w_2 \\in \\sum^*$以及$x \\in \\sum$，则$w_1 \\cdot(w_2x)=(w_1 \\cdot w_2)x$。\n",
    "\n",
    "递归定义的另一种重要用途是定义各种类型的`合式公式`。\n",
    "\n",
    "**例8（复合命题的合式公式）**：可以定义关于T、F、命题变元以及集合$\\{\\lnot,\\land\\lor,\\to,\\leftrightarrow\\}$中运算的复合命题的合式公式的集合。\n",
    "- 基础步骤：T、F和s都是合式公式，其中s是命题变元。\n",
    "- 递归步骤：若E和F都是合式公式，则$(\\lnot E),(E \\land F),(E \\lor F),(E \\to F),(E \\leftrightarrow F)$都是合式公式。\n",
    "\n",
    "**定义3**：以下步骤可以递归地定义根树的集合，其中根树是由一个顶点集合和连接这些顶点的边组成的，顶点集合包含的一个特殊顶点，称为树根。\n",
    "- 基础步骤：单个顶点r是树根。\n",
    "- 递归步骤：假设$T_1,T_2,\\cdots,T_n$是根树，分别带有树根$r_1,r_2,\\cdots,r_n$。则如下形成的图也是根树：从树根r开始，r不属于根树$T_1,T_2,\\cdots,T_n$中的任何一个，从r到顶点$r_1,r_2,\\cdots,r_n$中的每个都加入一条边。\n",
    "\n",
    "**定义4**：以下这些步骤可以递归地定义扩展二叉树的集合：\n",
    "- 基础步骤：空集是扩展二叉树。\n",
    "- 递归步骤：如果$T_1$和$T_2$都是扩展二叉树，则存在一个表示为$T_1 \\cdot T_2$的扩展二叉树，它包含树根r和当左子树$T_1$和右子树$T_2$都非空时，连接从r到这两个子树各自的根的边。\n",
    "\n",
    "**定义5**：以下这些步骤可以递归地定义满二叉树的集合：\n",
    "- 基础步骤：存在一个只含有单个顶点的满二叉树。\n",
    "- 递归步骤：如果$T_1$和$T_2$都是满二叉树，则存在一个表示为$T_1 \\cdot T_2$的满二叉树，它包含树根r和连接从r到左子树$T_1$和右子树$T_2$各自的根的边。\n",
    "\n",
    "### 5.3.4 结构归纳法\n",
    "`结构归纳法`证明包含如下两个部分：\n",
    "- 基础步骤：证明对于递归定义的基础步骤所规定的属于该集合的所有元素来说，如果成立。\n",
    "- 递归步骤：证明如果对于定义的递归步骤中用来构造新元素的每个元素来说命题为真，则对于这些新的元素来说结果成立。\n",
    "\n",
    "### 5.3.5 广义归纳法\n",
    "可以定义$N \\times N$（非负整数的有序对）上的序，规定如果$x_1 < x_2$或者$x_1 =x_2$且$y_1 < y_2$，则$(x_1, x_2)$小于等于$(y_1, y_2)$。这称为`字典序`。具有这个序的集合$N \\times N$具有性质：$N \\times N$的每个子集合都有最小元。这意味着可以递归地定义满足$m \\in N$和$n \\in N$的项$a_{m,n}$，并且用数学归纳法的变种来证明关于这些项的结果。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.4 递归算法\n",
    "### 5.4.1 引言\n",
    "**定义1**：若一个算法通过把问题归约到带更小输入的相同问题的实例来解决原来的问题，则这个算法称为递归地。\n",
    "\n",
    "### 5.4.2 证明递归算法的正确性\n",
    "数学归纳法以及它的变种——强归纳法，都可以证明一个递归算法的正确性，即可以证明算法对所有可能得输入值，都能产生所需要的输出。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.5 程序正确性\n",
    "### 5.5.2 程序验证\n",
    "若对每个可能的输入来说程序都产生正确的输出，则说这个程序是**正确的**。一个程序的正确性证明包括两个部分。第一部分证明：若程序终止，则获得正确的答案。证明的第一部分证明了程序的`部分正确性`。证明的第二部分证明：程序总是终止。\n",
    "\n",
    "为了规定程序产生正确的输出是什么意思，使用两个命题。第一个是`初始断言`，它给出输入值必须具有地性质。第二个是`终结断言`，它给出假如程序做了要求它做的事情，则程序应当具有地性质，\n",
    "\n",
    "**定义1**：若当对一个程序或程序段S地输入值来说初始断言p为真时，就有对S的输出值来说终结断言q为真，则说S是相对于p和q部分正确的。记号p{S}q说明程序或程序段S是相对于初始断言p和终结断言q部分正确的。\n",
    "\n",
    "注意：记号p{S}q称为`霍尔三元组`。\n",
    "\n",
    "### 5.5.3 推理规则\n",
    "一条有用的推理规则是通过把一个程序分成一系列子程序，然后证明每个子程序为正确的来证明这个程序为正确的。\n",
    "\n",
    "假定把程序S分成子程序$S_1$和$S_2$。写$S=S_1;S_2$来表示S是由$S_1$后接$S_2$来组成的。假定已经证明了$S_1$相对于初始断言p和终结断言q地正确性，以及$S_2$相对于初始断言q和终结断言r的正确性。由此得出了若p为真且$S_1$执行并终止则q为真；若q为真且$S_2$执行并终止则r为真。因此，若p为真且$S=S_1;S_2$执行并终止则r为真。这条推理规则称为`合成规则`，它可以叙述成：\n",
    "\n",
    "$$p\\{S_1\\}q$$\n",
    "\n",
    "$$q\\{S_2\\}r$$\n",
    "\n",
    "$$------$$\n",
    "\n",
    "$$\\therefore p\\{S_1;S_2\\}r$$\n",
    "\n",
    "### 5.5.4 条件语句\n",
    "```pascal\n",
    "if condition then\n",
    "    S\n",
    "```\n",
    "\n",
    "$(p \\land condition)\\{S\\}q$\n",
    "\n",
    "$(p \\land \\lnot condition)\\to q$\n",
    "\n",
    "$---$\n",
    "\n",
    "$\\therefore p\\{if\\ condition\\ then\\ S\\}q$\n",
    "\n",
    "```pascal\n",
    "if condition then\n",
    "    S1\n",
    "else\n",
    "    S2\n",
    "```\n",
    "\n",
    "$(p \\land condition)\\{S_1\\}q$\n",
    "\n",
    "$(p \\land \\lnot condition)\\{S_2\\}q$\n",
    "\n",
    "$---$\n",
    "\n",
    "$\\therefore p\\{if\\ condition\\ then\\ S_1\\ else\\ S_2\\}q$\n",
    "\n",
    "### 5.5.5 循环不变量\n",
    "```pascal\n",
    "while condition\n",
    "    S\n",
    "```\n",
    "\n",
    "$(p \\land condition)\\{S\\}p$\n",
    "\n",
    "$---$\n",
    "\n",
    "$\\therefore p\\{while\\ condition\\ S\\}(\\lnot condition \\land p)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}