立,则P(k+1)成立。Р强原则也称为完全归纳原则,或course-of-values归纳。你可以总是使用强原则。Р递归定义Р例子:n! = 1 if n=0Р n*(n-1)! otherwiseР很容易发现递归定义与数学归纳法的相似性。许多定义既可以采用递归方式,又可以采用非递归方式,但递归定义具有一些优点:直观、揭示了运算的过程,更符合事务的本质,且提供了构造数学归纳法的自然的方法。РL*的递归定义:Р1)LÎL*Р2)如果xÎL*,yÎL*,则xyÎL*Р3)仅由规则1)和规则2)得到的字符串Р回文pal的递归定义:Р1)LÎpalР2)如果aÎå,则aÎpalР3)如果aÎå,xÎpal,则axaÎpalР4)仅由上面3个规则产生的字符串Р回文的非递归定义是:正序和倒序相同的字符串。显然,递归定义提供了一个构造和判别回文的方法。人类擅长描述性定义,而计算机擅长构造性定义,递归定义则是构造性定义的一种。两种定义的转换是一个难点。Р规则的最后一条的更精确说法是有限次应用上述规则。Р结构归纳法Р结构归纳法原理:假设U是一个集合,I是U的一个子集,Op是U上的一组操作,集合L递归定义如下:Р1)IÍLР2)L在Op操作下保持封闭性Р3)L是满足条件1)和条件2)的最小集合Р要证明集合L中的每个元素满足性质P,只要证明下面两条:Р1)I中每个元素满足性质PР2)L中元素在操作Op下保持性质PР结构归纳法是专用于递归定义的证明方法。理解“保持封闭性”和“保持性质”的含义。Р例子2.22,要分清集合是什么?性质是什么?操作是什么?Р证明对每个xÎå*和yÎå*,连接后的字符串长度是两个字符串长度之和,即|xy|=|x|+|y|。Р首先递归定义字符串长度,然后将x看成固定量,对y进行结构归纳法证明,见61页和62页。Р最后指出,结构归纳法实质上是数学归纳法,两种方法可以互相转换。
全文预览
