祁东微信公众号开发【祁东网络推广】祁东建站、祁东网站维护、祁东网页制作、祁东微信小程序代运营公司

祁东微信公众号开发【祁东网络推广】祁东建站、祁东网站维护、祁东网页制作、祁东微信小程序代运营公司

祁东县，隶属湖南省衡阳市，地处衡阳市西南部、湘江中游北岸，东西狭长，北高南低，总面积1872平方千米。 [1]  截至2020年6月，祁东县下辖4个街道、17个镇、3个乡。 [2]  共368个行政村（社区居委会），总人口105.8万。

祁东县，因县城在祁山之东而得名。古为扬越之地，春秋时属楚国。祁东境内祁剧为全国优秀剧种之一。明朝重臣宁良、陈荐，清廷尚书陈大受，红军将领王如痴，革命志士曹炎，画家管锄非等都孕育于此。当前有祁东籍将军14人，两院院士2人，省部级领导7人，司级领导78人，处级领导1300多人。

湘桂铁路、娄底—衡阳高速公路、泉州—南宁高速公路、祁永高速穿过祁东境内，另有祁东港归阳港区。 [1]  祁东县是“中国黄花之乡”、“将军之乡”、“黑色金属之乡”、“中国曲艺之乡”、“省级文明县城”、“全省城乡环境卫生十佳县”。2018年4月23日，湖南省政府批准祁东县退出贫困县序列。

2.3.1　归纳证明为何有效

变量的替换

在需要替换变量，比如涉及同一变量的表达式，如S(n)中的n 时，常会产生混淆。例如，我们要用n+1替换S(n)中的n，以得出等式(2.3)。要进行这种替换，必须先标记出S 中每个出现n的地方。有个很实用的办法，就是先用某个未在S 中出现过的新变量（比如m）来代替n。例如，S(n)就成了

接着在每个出现m 的地方将其替换成所需的表达式，即本例中的n+1，就得到

若将(n+1)+1简化为n+2，就得到了等式(2.3)。

请注意，我们应该给用来替换的表达式加上括号，以避免意外改变运算顺序。例如，假设用n+1替换表达式2×m 中的m，但没有给n+1加上括号，那么就会得到2×n+1，而不是正确的表达式2×(n+1)（也就是2×n+2）。

在归纳证明中，我们先证明了S(0)为真。接下来要证明，如果S(n)为真，那么S(n+1)是成立的。不过为什么接着能得出S(n)对所有n≥0都为真呢？我们会提供两个“证据”。某位数学家曾指出，我们证实归纳法有效的每个“证据”，都需要归纳证据本身，因此就根本没有证据。从技术上讲，归纳肯定能作为公理，然而很多人会发现以下直觉认识也是有用的。

在接下来的内容中，我们假设作为依据的值是n=0。也就是说，我们知道S(0)为真，而且对于所有大于0的n，如果S(n)为真，那么S(n+1)为真。如果作为依据的值是其他整数，也可以做出类似的论证。

第一个“证据”：归纳步骤的迭代。假设要证明对某个特定的非负整数a 有S(a)为真。如果a=0，只要援引归纳依据S(0)的真实性即可。如果a>0，那么就要进行如下论证。从归纳依据可知S(0)为真。对于命题“S(n)可推出S(n+1)”，若将n 替换为0，就成了“S(0)可推出S(1)”。因为我们知道S(0)为真，现在就知道S(1)为真。类似地，如果用1替换n，就有“S(1)可推出S(2)”，这样一来就知道S(2)也为真。用2来替换n，则有“S(2)可推出S(3)”，所以S(3)也为真，以此类推。不管a取什么值，最终都能得到S(a)，这样就完成了归纳。

第二个“证据”：最少反例。假设至少有一个n 的值可以使S(n)不为真。设a是令S(a)为假的最小非负整数。如果a=0，就与我们的归纳依据S(0)相互矛盾，所以a 一定是大于0的。不过如果a>0，而且a是令S(a)为假的最小非负整数，那么S(a)肯定为真。现在，在归纳步骤中，如果用a-1代替n，就会有S(a-1)可推出S(a)。因为S(a-1)为真，那么S(a)肯定为真，又相互矛盾了。因为我们假设存在非负整数n 使S(n)为假，并引出了矛盾，所以S(n)对任何n≥0都一定为真。

2.3.2　检错码

现在我们要介绍“检错码”的例子。检错码本身就是个有意思的概念，而且引出了一段有趣的归纳证明。当我们通过数据网络传输信息时，会将字符（字母、数字、标点符号，等等）编码成位串，即0和1组成的序列。此时假设字符是由7位表示的。不过通常每个字符要传输不止7位，而第8位可以用来检测一些简单的传输错误。也就是说，偶尔有那么一个0或1会因为传输噪声发生改变，结果接收到的就是相反的位，进入传输线路的0成了1，而1成了0。如果通信系统能在8位中的一位发生变化时发出通知，从而发出重传信号，将会很有用。

要检测某一位的改变，必须保证任意两个表示不同字符的位序列不只有一个位置不同。不然的话，如果那个位置发生变化，结果就成了代表另一个字符的代码，可能将没法检测到错误的发生。例如，如果一个字符使用位序列01010101表示，而另一个由01000101表示，那么如果左起第4个位置发生改变，就会将前者变成后者。

要确保不同字符的代码不只有一个位置不同，方法之一是在惯用于表示字符的7位码前加上一个奇偶校验位。如果位序列中有奇数个1，则称其具有奇校验。如果位序列中有偶数个1，则其具有偶校验。我们选择的编码方式是以具有偶校验的8位码来表示字符，也可以选用带奇校验的代码。通过明智地选择校验位，我们可使奇偶校验成为偶校验。

示例 2.5

用来表示字符A的传统的ASCII（音“ask-ee”，表示American Standard Code for Information Exchange，即“美国信息交换标准码”）7位码是1000001。该序列的7位中已经有偶数个1，所以我们为其加上前缀0，得到01000001。用来表示C的传统代码是1000011，这和表示A的7位码只在第6位是不同的。不过，这个代码具有奇校验，所以我们给它加上前缀1，从而产生具有偶校验的8位码11000011。请注意，在给表示A和C的代码前加上校验位后，就有了01000001和11000011这两个位序列，它们的第1位和第7位这两位是不同的，如图2-5所示。

图 2-5　可以选择初始奇偶校验位，使得8位码总是具有偶校验

我们总是能选择一个奇偶校验位加到7位码上，从而让得到的8位码中有偶数个1。如果表示字符的7位码本来就有偶校验，就选择0作为其奇偶校验位，而对本具有奇校验的7位码，则是选择奇偶校验位1。不管哪种情况，8位码中都是包含偶数个1。

两个具有偶校验的位序列不可能只有一个位置不同。如果两个这样的位序列只有一个位置不同，那么其中一个肯定要比另一个多一个1。因此，一个序列必然具有奇校验，而另一个则是偶校验，与我们都具有偶校验的假设是矛盾的。因此可得，通过加上奇偶校验位使1的数量为偶，可为字符创建检错码。

奇偶校验位模式是相当“高效”的，从某种意义上讲，它让我们可以传输很多不同的字符。请注意，n 位的位序列有2n个，因为我们可以为第一位选择二值（0或1）之一，可以为第二位选择二值之一，等等，总共可形成2×2×…×2（n 个2相乘）个位串，所以，最多有望能用8位来表示28=256个字符。

然而，在奇偶校验模式中，只能选择其中7位，第8位是无从选择的。因此最多可以表示27，即128个字符，而且能检测某一位上的错误。这样也不错，我们可以用256个中的128个，也就是8位码所有可能组合的一半，来作为字符的合法代码，还能检测某一位中出现的错误。

类似地，如果我们使用n 位的位序列，选择其中一位作为奇偶校验位，那么就能用n-1位的位序列加上合适的奇偶校验位前缀（其值由另外那n-1位确定）来表示2n-1个字符。n 位的位序列有2n个，我们可以表示2n中的2n-1个，或者说是可能字符数的一半，而且可以检测位序列中任意一位的错误。

有没有可能检测多个错误，并使用超过位序列多于一半的可能组合作为合法代码呢？下一个例子将告诉你这是不可能的。这里的归纳证明使用的命题对0来说不为真，所以我们必须选用一个更大的归纳依据，也就是1。

示例 2.6

我们要对n 进行归纳，以证明以下命题。

命题S(n)。如果C 是长度为n 的位串的检错（即两个不同的位串不会刚好只有一个位置不同）集合，那么C 最多含有2n-1个位串。

这个命题对n=0来说不为真。S(0)表示长度为0的位串的检错集合最多只有2-1个，也就是半个位串。从技术上讲，只由空位串（不含任何位置的位串）组成的集合C，是长度为0的位串的检错集合，因为C 中任意两个位串不会只有一个位置不同。集合C 中不只是有半个位串，它其实有一个位串。因此，S(0)为假。不过，对于所有的n≥1，S(n)都为真，正如我们在下文将会看到的。

依据。依据为S(1)，也就是，任何检错的长度为1的位串的集合最多只有21-1=20=1个位串。长度为1的位串只有两个，一个是位串0，一个是位串1。然而，在检错的集合中，我们不能同时拥有这两者，因为它们正好只有一个位置不同。因此，每个n=1的检错集合肯定最多只有一个位串。

归纳。设n≥1，假定归纳假设——长度为n的位串的检错集合最多只有2n-1个位串——为真。我们必须用这一假设证明，任何长度为n+1的位串的检错集合C 最多只有2n个位串。因此，将C 分为两个集合：C0，即C 中0开头的位串组成的集合，以及C1，即C 中1开头的位串组成的集合。例如，假设n=2，C 就是长度为n+1＝3，而且有一个奇偶校验位的位串的集合。那么，如图2-6所示，C 由位串000、101、110和011组成，C0由位串000和011组成，C1则由位串101和110组成。

图 2-6　集合C 被分为0开头位串的集合C0和1开头位串的集合C1，D0和D1则分别由删除了开头的0和1的位串组成

考虑一下集合D0，它含有删除了C0中那些位串开头的0后形成的位串。在上面的例子中，D0含有位串00和11。我们要求D0不能含有两个只有一位不同的位串。原因在于，如果有这样两个位串，比方说a1a2…an和b1b2…bn，然后恢复它们开头的0，就会给出两个C0中的位串，0a1a2…an和0b1b2…bn，而这两个位串也只有一位是不同的。不过C0中的位串也是C 中的元素，而且我们知道C 中不能有两个位串只有一个位置不同。因此，D0也不行，所以D0是检错集合。

现在可以应用该归纳假设得出，D0作为一个长度为n的位串的检错集合，最多有2n-1个位串。因此，C0最多有2n-1个位串。

同样，可以对C1集合作出类似推论。设D1集合内的元素是删除C1中位串开头的1形成的位串。D1是长度为n的位串的检错集合，而根据归纳假设，D1最多只有2n-1个位串。因此，C1也最多只有2n-1个位串。然而，C中的每个位串不是在C0中就是在C1中。因此，C中最多有2n-1+2n-1，也就是2n个位串。

我们已经证明了S(n)可推出S(n+1)，所以可以得出结论，S(n)对所有的n≥1都为真。我们在声明中排除了n=0的情况，因为归纳依据是n=1，而不是n=0。现在看到带奇偶校验检查的检错集合是尽可能大的，因为它们在使用n个位来构成位串时能有2n-1个位串。

如何构造归纳证明

没有什么可以保证给出任意（真）命题S(n)的归纳证明。找到归纳证明，就像找到任意类型的证明那样，或者就像写出能正常运行的程序那样，是项挑战智力的任务，而且我们只有几句话的意见可提。如果大家研究了示例2.4和示例2.6中的归纳步骤，就会注意到，每种情况下，都必须对试图证明的命题S(n+1)加以处理，使其由归纳假设S(n)和某些额外内容组成。在示例2.4中，我们将和

1+2+4+…+2n+2n+1

表示为归纳假设告诉我们的和

1+2+4+…+2n

加上2n+1这一项。

在示例2.6中，我们用两个长度为n的位串集合（称为D0和D1）表示长度为n+1的位串集合C，这样一来，就可以将归纳假设应用到这些集合上，并推断出这两个集合都是大小有限的。

当然，对命题S(n+1)加以处理，从而使我们能应用归纳假设，只是更普遍的解题箴言“运用给定条件”的一个特例。当必须处理S(n+1)的“额外”部分，并利用S(n)完成对S(n+1)的证明时，才是最让人头疼的。不过，以下规则是普遍适用的。

• 归纳证明必须在某个地方表述“……而且通过归纳假设我们可知……”。如果没有的话，就不算是归纳证明。

祁东微信公众号开发【祁东网络推广】祁东建站、祁东网站维护、祁东网页制作、祁东微信小程序代运营公司