离散算法处理的是可以被精确区分的对象:字符串、子集、整数、顶点或有限序列。一个证明必须说明哪些对象是允许的输入、过程承诺了什么,以及为什么每个允许的输入都能得到所承诺的结果。逻辑与计数为这些陈述提供了语言,同时也能暴露仅凭少数几次成功运行无法发现的错误。
动机
假设我们要计数长度为 、且不含两个相邻 1 的二进制字符串。对较小的 ,枚举全部 个字符串是可行的,但这会掩盖其中的结构。更好的做法是按结尾对合法字符串分类,并用较小输入的计数来表示所求的计数。在实现这个递推式之前,我们应当弄清楚:这些情形为什么覆盖了所有字符串,为什么它们互不重叠,以及空字符串会出现什么情况。
正确性证明中也有同样的责任。一个更新两个计数的循环可能看起来很合理,但一个错误的初始值就会悄悄地使整个序列发生偏移。不变量把程序所存储的值与它们本应计数的数学对象联系起来,随后归纳法再把这种联系变成对所有输入长度都成立的证明。
这些想法始于对量词的仔细处理。“对每个输入都存在一个正确答案”不同于“存在一个对每个输入都正确的答案”。同样,使字符串合法的充分条件不一定刻画了所有合法字符串。在公式或算法变得复杂之前就做好这些区分,会使离散数学的学习事半功倍。
定义
定义 12.3.1
(蕴含、逆命题与逆否命题)
命题是在所讨论的情境中具有真值的陈述。蕴含 仅当 为真而 为假时才不成立。它的逆否命题 与之等价;它的逆命题 则不一定等价。双条件 要求两个方向都成立。
定义 12.3.2
(量词、否定与空论域)
量词总是带有论域。 的否定是 ;存在陈述的否定是全称的失败陈述。因此,要反驳“每个合法输入都会终止”这一断言,必须给出一个不终止的合法输入。落在指定论域之外的畸形输入并不能反驳该断言。
如果论域为空,其上的全称命题为真:没有论域元素违反断言。存在命题则为假,因为找不到可用的见证。这一约定由否定规则决定,并不是规则的例外。这也说明算法规格应交代实际允许哪些输入;对空输入类作出的保证,并不会产生一个解对象。
定义 12.3.3
(基数、双射与划分)
对有限集合 ,以 表示其基数。双射 通过不遗漏、不重复地配对对象来证明 。划分把一个集合分成若干互不相交的部分,其并集为整个集合。加法法则用于计数一个划分;乘法法则用于计数相继的选择,前提是每一个先前的选择都有所述数目的可能后续。
定义 12.3.4
(循环不变量与正确性)
循环不变量是关于输入、程序状态与迭代变量的命题,在循环的前置条件下,它在每次迭代之前都成立。要在证明中使用它,需要建立初始化、保持性,以及退出时的推论。部分正确性是指:任何终止的、被允许的执行都给出所要求的答案。完全正确性在此基础上加上终止性,而终止性通常借助一个每次迭代都严格递减的非负整数量来证明。
定义 12.3.5
(合法二进制字符串的计数)
设 为长度为 、由 构成且不含相邻 1 的字符串的个数。空字符串只有一个,所以 ;长度为一的字符串给出 。空字符串是被计数的一个对象,并不意味着没有计数问题。
定理/命题
定理 12.3.6
(有限集合的容斥原理)
对某有限全集的子集 ,
这些子集不必互不相交,并且公式中的所有交集都是必需的。
定理 12.3.7
(递推式及其经过验证的迭代计算)
对 ,合法字符串的计数满足 。对每个整数输入 ,下面的过程都返回 :若 ,返回 1;否则从 开始,恰好重复 次 (右边使用旧值),然后返回 。
同时更新的约定是算法的一部分。若把它换成两条赋值语句,而第二条意外地重用了刚更新过的第一个坐标,过程就改变了。证明所验证的是一个确切的程序,而不是一族含糊相似的更新规则。
证明思路或证明
证明
(单个元素的净贡献)
对于容斥原理,考察全集中单个元素 的贡献。若它不属于任何一个集合,则它在两边的贡献都为零。若它恰属于 个集合,则它出现在 个由 个集合构成的交集中。它在右边的净贡献为
这是因为 。因此它在两边都恰好贡献一次。对有限全集求和即证明该恒等式。这个论证是针对单个元素的局部论证,它解释了为什么出现三重重叠时,仅仅减去两两交集是不够的。
证明
(按最后一个符号划分)
对于递推式,按最后一个符号划分长度为 的合法字符串。以 0 结尾的字符串,唯一地来自在长度为 的合法字符串后面添加 0。以 1 结尾的字符串必然以两符号块 结尾,并唯一地来自在长度为 的合法字符串后面添加该块。两种构造都保持合法性,都有相应的逆操作(删除),并且它们的像互不相交。两者的计数相加即得所求总数。
证明透视
递推式既需要划分,也需要逆构造
仅仅描述制造某些合法字符串的两种方式是不够的。删除操作证明每个目标字符串都来自所提出的来源,而唯一重构则防止同一情形内部重复计数。按最后一个符号的划分则防止不同情形之间重叠。这些正是递推式成为等式、而不仅仅是上界或下界的确切原因。
证明
(循环的状态不变量)
对于程序,把已执行的更新按 编号。经过 次更新之后的不变量是 。当 时,由两个初始计数知它成立。若它在 次更新后成立,则同时赋值给出 (由递推式),所以不变量得以保持。经过 次更新后,。单独的 分支返回正确的初始值。剩余的更新次数是每次减一的非负整数,从而保证了终止性。
这一证明展示了通过程序状态进行的普通归纳。强归纳法在逻辑上有同等效力,但允许归纳步骤使用所有更小的输入。对递推式本身而言,需要用到前面的两个计数,因此既可以使用强归纳法,也可以把两个相继的断言合并为一个不变量。选择得当的命题可以使证明更简单,而不会使结论变弱。
归纳法为什么能覆盖每个情形
设 是关于整数 的命题。普通归纳法要求先证明基础情形 ;再对任意 证明蕴含 。假设 只是暂时的,只能在证明该蕴含时使用。基础情形开启一条有效的蕴含链,因此每个固定的、不小于 的整数都能经过有限步到达。检查许多单独的情形,或只证明蕴含而没有基础情形,都不能提供这条链。
强归纳法则在证明 时,假设对每个满足 的整数 , 都成立。当 时没有这样的 ,所以该步骤必须不借助假设就建立基础情形。实际证明时,也可以先单独证明若干初始情形,之后才使用强归纳步骤。两种形式的效力相同:对命题 使用普通归纳,其中 断言对所有 都有 。强归纳步骤就把 推广为 。
同样的推理也可用良序原理表述:每个非空的非负整数集合都有最小元素。如果强归纳步骤成立,但某个 不成立,就从失败下标的偏移量 所成的非负整数集合中选取最小元素,并以 表示相应下标。所有更早的断言都成立,因而该步骤又证明了这个据称失败的断言,产生矛盾。这说明为什么在这里可以“选取最小反例”;没有下界的一般整数集合未必有最小元素。
例题 12.3.8
(用强归纳法证明素因子分解的存在性)
素数是大于一、且正因子只有一和自身的整数。每个整数 都是一个或多个素数的乘积。当 时显然成立。假设从 到 的每个整数都满足该断言。如果 是素数,由单个因子 构成的乘积即可。否则 ,其中整数 满足 。由归纳假设, 和 都可分解为素数乘积;把两个有限乘积接起来便得到 的分解。因此由强归纳法断言成立。例如 。这里证明的是分解的存在性,不是唯一性;唯一性需要进一步论证。
反例模式
归纳步骤不能弥补缺失的起始情形
考虑对所有 的错误断言 :“ 是偶数”。蕴含 为真, 也为真,但它们只能到达偶数下标。要到达奇数下标,还需要单独的情形 ,而它是假的。每次前进两步的步骤需要两个起始情形才能覆盖两条奇偶链;仅验证一个是不够的。
对于算法,当递归调用可能有几种不同的较小输入规模时,强归纳证明很有用。证明必须说明每个调用的规模都更小,且仍属于所述论域,然后才能对这些调用使用归纳假设。证明终止性还须考虑控制流程:如果每次调用只做有限的局部工作、发起有限次调用,且每次调用都使非负整数规模严格减小,那么不可能有无限调用链,计算因而终止。仅证明返回时的值正确,并不能保证终止。
例题详解
例题 12.3.9
(量词的顺序会改变命题)
对整数而言, 为真:取 。颠倒顺序后的命题 为假:对于任何给定的 ,取 即可。要证明第一个命题,见证元可以依赖于被全称选定的输入;第二个命题则要求一个固定的见证元,它独立于每一个输入而成立。用算法的语言来说,由输入计算得出的输出不同于声称能解决每个实例的某个常数输出。
例题 12.3.10
(通过重复计数的修正来计数)
在一到三十的整数中,设 为二的倍数, 为三的倍数。 中有十五个, 中有十个,交集有五个,即六的倍数。因此有二十个数可被二或三整除,有十个数二者都不能整除。若把十五与十相加而不减去五,则每个六的倍数被计了两次。全集很重要:改变区间会改变取整的计数,尽管容斥恒等式保持不变。
例题 12.3.11
(跟踪经过验证的状态,而不是猜测序列)
对 ,从 开始。四次更新依次给出 、、 和 ,所以答案是十三。第三次更新之后,状态的含义是 且 ;这并不意味着两个分量都在计数长度为五的字符串。把这一解释始终与状态绑定在一起,可以在把停止条件翻译成代码时避免差一错误。
迭代算法中算术加法的次数关于 是线性的,但其数值会增长。我们有 ,所以它们至多使用 个二进制位。在通常的逐位加法下,总的位运算代价以 的某个常数倍为界,因而是 。这个两变量状态使用 位。只有在明确地把任意大小的整数寄存器都算作单个单位时,才可以把它描述为“常数空间”。算术运算与位运算之间的区别在数论算法中还会再次出现。
常见错误
常见错误
(以几个算出的情形代替证明)
若干个算出的情形是有用的检验,但并不能证明一个全称命题。反过来,一个合法的反例就足以推翻它。当归纳尝试失败时,应当先检查归纳命题与基础情形,再考虑修改定理。使用 的递推式需要足够多的初始值,才能到达其第一个有效步骤。
常见错误
(误用乘法法则)
乘法法则并不要求各选择在概率意义上相互独立;它要求的是关于每个阶段后续数目的计数陈述。如果这个数目是变化的,就应当对相应的计数求和,而不是乘上某个方便的数值。计数有序选择与计数无序子集所得的对象也不同:在计数之后忽略顺序,需要每个对象对应的排列数是一个有依据的常数。
反例模式
顺序赋值可能使正确的递推式失效
若把更新实现为 之后再执行 ,则第二条指令使用的是新的 。从 开始,得到的是 而不是 。数学上的递推式是正确的,只是实现不再与它一致。使用临时变量或同时赋值即可修复该程序。
总结
量词规定了由谁选择每个对象,以及哪些量可以依赖于输入。划分与双射为精确计数提供依据;容斥原理修正重叠。归纳法证明递推恒等式,而不变量则把这些恒等式与变化中的程序状态联系起来。终止性与所选取的代价模型是另外的责任,应当与答案一同清楚地呈现。
练习
快速检查
(写出陈述“对每个整数 ,存在一个长度为 、以 1 结尾的合法二进制字符串”的否定,并判断该陈述是否为真。)
逐个量词取否定,再检验 。
解答 · 答案
否定是:存在整数 ,使得每个长度为 的合法字符串都不以 1 结尾。它在 时为真,因为唯一的长度为零的字符串是空字符串,它没有最后一个符号。因此原来的全称断言为假。把它限制在 即可修复:由 个 0 后接一个 1 构成的字符串是合法的。
快速检查
(计数一到六十的整数中,至少能被二、三、五之一整除的个数。写出所有容斥项。)
把单个集合的计数相加,减去两两交集,再加回三重交集。
解答 · 答案
单个集合的计数分别为三十、二十和十二。两两交集的大小为十、六和四,分别来自能被六、十和十五整除的数。三重交集的大小为二,来自三十的倍数。因此并集有 个元素。三重重叠需要加回,因为两两相减时把它减去的次数过多。
练习 12.3.12
(一个程序通过从 开始、把 恰好翻倍 次来计数 元集合的子集。陈述并证明一个不变量,包括 的情形。)
核心
解答(3)
- 1
陈述不变量
关键一步
经过 次加倍后,,即前 个元素的子集数目。
- 2
验证初始化与保持
起初 、,空集恰有一个子集。加入一个新元素时,每个旧子集给出两种互不相交的可能:包含或不包含该元素,所以加倍保持了这一诠释。
- 3
读出退出时的值并证明终止
当 时,答案是 。记录剩余迭代次数的计数器每次减一,由此证明终止性,包括 时立即终止的情形。
快速检查
(解释为什么以 1 结尾的合法字符串仅当 时才由 计数,并计算 。)
想想删去末尾的块 需要什么条件。
解答 · 答案
当 时,以 1 结尾的字符串只有单个符号 1,前面没有可删除的 0。因此两符号后缀的论证从 开始。基础值 处理这一单独的情形。利用经过验证的递推式,。
练习 12.3.13
(用强归纳法证明:每个整数 都是互不相同的二的非负整数次幂之和。写出 的一个这样的表示。)
核心证明
解答(4)
- 1
基础情形
。
- 2
分出奇偶
关键一步
对 ,令 、,则 ,且 为零或一。
- 3
对 应用归纳假设
是互不相同的二的幂之和。将其加倍,得到 的表示,其中各幂的指数都至少为一。
依据: 假设涵盖从 到 的每个整数。
- 4
补上余数
∎若 ,再加上 ,不会重复任何幂。因此结论对 成立。例如 。这个论证证明了存在性,但没有证明唯一性。