第二章逻辑和证明（六）-Read.ppt

第二章 逻辑和证明 2.6 递归定义 递归定义： 用自己定义自己的方法 对照递归程序 2.6.1 函数的递归定义 递归地定义函数f（以非负整数集为定义域）： (1)定义（规定）f(0)的值 (2)定义f(n+1)，给出从f(0)、f(1)、…、f(n)和n导出f(n+1)的值的方法 例1 给出阶乘函数f(n)=n!的归纳定义。 解 可以通过规定阶乘函数的初值，即f(0)=1，并且给出从f(n)求出f(n+1)的规则，来定义这个函数。要得出这个结果，注意通过乘以n+1就从n!计算出(n+1)!因此，所需要的规则是f(n+1)=(n+1)f(n). 递归地定义函数是唯一的（严格定义的） 例2 斐波那契数（Fibonacci）f0, f1, f2,…是用等式f0 =0， f1=1，以及对n=2,3,4,…来说fn= fn-1+ fn-2来定义的。Fibonacci f2, f3, f4, f5是什么？ 解 因为这个定义的第一部分说f0 =0和f1=1，所以从这个定义的第二部分得出： f2 = f1 + f0 =1+0=1 f3 = f2 + f1 =1+1=2 f4 = f3 + f2 =2+1=3 f5 = f4 + f3 =3+2=5 例3 斐波那契不等式 证明：每当n?3时，就有fnan-2，其中a=(1+ )/2。 证明： 可以用数学归纳法第二原理来证明这个不等式。设P(n)是命题： fnan-2 。想要证明每当n是大于或等于3的整数时就有P(n)为真。 首先，注意到 a2= f3, a2=(3+ )/23= f4 。所以P(3)和P(4)都为真。现在假定P(k)为真，即对所有满足3 ? k ? n 的正整数k来说有fkak-2 ，其中n ? 4。必须证明P(n+1)为真，即fn+1an-1 。因为a是x2- x -1 = 0的解，所以得出a2=a+1。因此， an-1=a2*an-3=(a+1) an-3 =a* an-3 +1* an-3 = an-2 + an-3 根据归纳假设，若n?5，则得出 fn-1an-3, 因此就有 fn+1=fn+fn-1 an-2 + an-3 = an-1由此可得出P(n+1)为真， 证毕。 2.6.2集合的递归定义 递归地定义集合S： (1)定义S中的某些元素 (2)定义S中的其他元素，给出从S中的元素构造出其他元素的方法 例4 设S是用3?S；若x?S且y?S，则x+y?S来递归定义的。证明：S是被3整除的正整数集合。 （注意在这个定义里隐含着假定所以属于S的东西都是用S的递归定义里的两个命题来生成的。） 证明： 设A是被3整除的所有正整数的集合。为了证明A=S，必须证明A是S的子集并且S是A的子集。为了证明A是S的子集，必须证明被3整除的每个正整数都属于S。将用数学归纳法来证明它。 （接下页） (接上页证明) 设P(n)是命题：3n属于S。基础步骤成立，因为根据S的递归定义的第一部分，3*1=3是属于S的。为了证明归纳步骤，假定P(n)为真，即3n属于S。因为3n属于S而且因为3属于S，所以从S的递归定义的第二部分得出3n+3=3(n+1)也属于S。 为了证明S是A的子集，使用S的递归定义。首先，该定义的基础步骤规定3属于S。因为3=3*1，所以所有在这个步骤里被规定属于S的元素都被3整除。为了完成证明，必须证明所有用该递归定义的第二部分所生成的属于S的元素都属于A。这包括证明每当x和y都是S中的元素并且假定它们都属于A时，就有x+y属于A。现在若x和y都属于A，则可以得出3|x和3|y。这就得出3|x+y，证毕。 字符串集合的递归定义 字母表?上的字符串的集合?*递归的定义成：a??*，其中a是不包含任何符号的空串，以及每当b??*和x??时，就有bx??*。 这个定义的第一部分说明空串属于?*。第二部分说明?*的字符串与?的符号连接起来就产生新的字符串。 例6 给出字符串w的长度l (w)的递归定义。 解 字符串的长度可以定义为： l(?)=0; l(wx)=l(w)+1，若w??*且x??。 习题 1.求出f(2),f(3),f(4)和f(5)，若f递归定义成f(0)=f(1)=1,而且对n=1,2,…来说f(n+1)=f(n)+3f(n-1). 2.给出序列{fn }的递归定义，n=1,2,3,…，若fn =n2。 3.证明：由数字、变量以及{+，-，*，/，?}里的运算符所组成的任何合式公式，都包含同样数目的左括号和右括号。