数理逻辑16-3 3 递归定义

1、数理逻辑 Mathematical Logic,第三章 数学推理 Chapter 3 Mathematical Reasoning,复习,数学归纳法有效性的来源是： 良序性 注意： 数学归纳法只能证明通过其它方式获得的结果 它不是发现公式或公理的工具 数学归纳法用来证明形如nP(n)的命题，其中论域是正整数集合,复习,数学归纳法的两个步骤 基础步骤 归纳步骤 注意： 不假定对所有正整数来说P(n)为真， 只是证明了：若假定P(n)为真，则P(n+1)也为真 数学归纳法第二原理,3.3 递归定义 Recursive Definitions,一、引言,用自己来定义自己的过程，称为递归,递归可以用来

2、定义序列、函数和集合 序列： 用显式的公式来定义序列里的项 2的幂的序列 对n=0,1,来说an=2n 给出该序列的第一项，即a0=1 给出从前一项来求当前项的规则，即对n=0,1,2来说an+1=2an,二、递归地定义序列,三、递归地定义函数,为了定义以非负整数集合作为其定义域的函数，就要： 规定这个函数在0处的值 给出从较小的整数处的值来求出当前的值的规则 这样的定义称为递归定义或归纳定义,例：假定f是用 f(0)=3; f(n+1)=2f(n)+3 来定义的。求出f(1),f(2),f(3)和f(4)。 许多函数都可以利用它们的递归定义来研究。,三、递归地定义函数,例：给出阶乘函数F(n

3、)=n!的归纳定义 解：可以通过规定阶乘函数的初值，即F(0)=1，并且给出从F(n)求出F(n+1)的规则，来定义这个函数 n!乘以n+1就得到(n+1)! F(0)=1； F(n+1)=(n+1)F(n)。,三、递归地定义函数,求F(5)=5！ F(5)=5F(4)=54F(3)=543F(2) =5432F(1)=54321F(0) =54321F(0)=543211 多次使用F(n+1)=(n+1)F(n)，一旦F(0)是出现的唯一的函数值，将F(0)的值插入公式。,三、递归地定义函数,例：给出an的递归定义，其中a是非零实数而且n是非负整数 解：递归定义包含两部分，首先规定a0，即a

4、0=1； 然后给出从an求出an+1的规则，即对n=0,1,2,来说an+1=aan 这两个等式对所有非负整数唯一地定义了an。,三、递归地定义函数,例：给出 的递归定义 解：这个递归定义的第一部分是： 第二部分是：,三、递归地定义函数,在函数的某些递归定义中， 规定了函数在前k个正整数处的值； 给出了从一个较大的整数之前的部分或全部k个整数处的函数值来确定在该整数处的函数值的规则。 斐波那契数的递归定义： f0=0，f1=1； fn=fn-1+fn-2，对n=2,3,4,来说,三、递归地定义函数,可以用斐波那契数的递归定义来证明这些数的许多性质 例：证明：每当n3时，就有fnn-2，其中(

5、)/2。 解：可以用数学归纳法第二定理来证明这个不等式 设P(n)是命题：fnn-2。,三、递归地定义函数,首先，f32; f4=3,由于2( )/2,所以f42; 因此，P(3),P(4)都为真； 现在假定P(k)为真，即对所有满足3kn的整数k来说有fkk-2，其中n4； 必须证明P(n+1)为真，即fn+1n-1； fn+1=fn+fn-1n-2+n-3=n-1(-1+-2)=n-1；证毕。,三、递归地定义函数,定理（拉梅定理）：设a和b是满足ab的正整数，则欧几里德算法为了求出gcd(a,b)而使用的除法的次数小于或等于b的十进制位数的5倍。 证：当用欧几里德算法求满足ab的gcd(a

6、,b)时，得出下面的等式序列（其中a=r0，br1）：,三、递归地定义函数,r0=r1q1+r2，0r2r1； r1=r2q2+r3，0r3n-1； 又因为log100.2081/5，所以，log10b(n-1)log10(n-1)/5；,三、递归地定义函数,因此，n-15log10b； 现在假定b有k个十进制位，则b10k； 因此，n-15k，由于k是整数，所以n5k，证毕。,三、递归地定义函数,因为b的十进制位数等于 ，它小于或等于log10b1，由拉梅定理，求出满足ab的gcd(a,b)所需要的除法次数小于或等于5(log10b1)。 因为5(log10b1)是O(logb)，故每当ab

7、时，欧几里德算法就用O(logb)次除法来求出gcd(a,b)。,三、递归地定义函数,四、递归地定义集合,集合的递归定义： 给出初始的一些元素； 给出用来从已知属于集合的元素来构造集合的其他元素的规则。 利用集合的递归定义可以证明关于它们的定理 例：设S是用3S；若xS且yS，则x+yS来递归定义的。证明：S是被3整除的正整数集合。,解：设A是被3整除的所有正整数集合 为了证明A=S，必须证明它们互为子集 首先证明A是S的子集，即被3整除的每个正整数都属于S（数学归纳法）： 设P(n)是命题：3n属于S； 基础步骤：31=，根据S的递归定义的第一部分；,四、递归地定义集合,归纳步骤：假定(n)

8、为真，即3n属于S，又因为3属于S，所以从S的递归定义的第二部分得出，3n+3=3(n+1)也属于S 然后证明S是A的子集（S的递归定义）： 该定义的第一部分规定3属于S，因为 3=31，所以在这一步规定的属于S的元素都被3整除； 必须证明所有用递归定义第二部分生成的属于S的元素都属于A；,四、递归地定义集合,需要证明每当x和y都是S中的元素并且假定它们都属于A时，就有x+y属于A； 若x和y都属于A，则可以得出3|x，3|y，由此得出3|x+y A和S互为子集，证毕。 在集合的递归定义中隐含着： 只有在初始元素中列出的元素； 或者可以用构造新元素的规则来生成的那些元素才属于这个集合。,四、递

9、归地定义集合,集合的递归定义最普遍的用途之一是定义各种系统里的合式公式 例：由变量、数字和+,-,*,/,中的运算符（代表乘幂）所组成的合式公式定义为： 若x是数字或变量，则x是合式公式； 若f和g是合式公式，则(f+g),(f-g), (f*g),(f/g)和(fg)都是合式公式,四、递归地定义集合,根据以上定义，由于x和3都是合式公式，所以(x+3),(x-3),(x*3),(x/3)和 (x3)都是合式公式； 又因为y也是合式公式，所以(x+3)+y)(y-(x*3)也是合式公式； 语义上是有意义的，含义是唯一的。,四、递归地定义集合,例：包含着T、F、命题变元以及运算符, ,的复合命题

10、的合式公式定义为： T、F和p都是合式公式，其中p是命题变元； 若p和q是合式公式，则(p)，(pq)，(pq)，(pq)，(pq)都是合式公式。,四、递归地定义集合,若p,q和r是命题变元，则重复使用上述递归定义，就证明(pq),(rT)和(pq)(rT)都是合式公式 字母表上的字符串是里的符号的有穷序列 *表示上的字符串的集合 连接运算：x=abc，y=ade，x和y的连接是xy=abcade,四、递归地定义集合,字符串集合的递归定义： 字母表上的字符串的集合*递归地定义为： *，其中是不包含任何符号的空串； 每当*和x时，就有x*。 第一部分说明空串属于*，第二部分说明把*的字符串与的符

11、号连接起来产生新的字符串。,四、递归地定义集合,字符串的长度是该字符串中符号的个数，其也可以递归地定义 例：给出字符串的长度l()的递归定义。 解：字符串的长度定义为： l()=0； l(x)= l()+1，若*且x。,四、递归地定义集合,例：用数学归纳法证明：l(xy)=l(x)+l(y)，其中x和y属于*。 解：设P(y)是命题：每当x*时就有l(xy)=l(x)+l(y)； 基础步骤：证明P()为真，即必须证明对所有x*来说有l(x)=l(x)+l()，因为对每个字符串x来说l(x)=l(x) =l(x)+0 =l(x)+l()，所以P()为真；,四、递归地定义集合,归纳步骤：假定P(y)为真，证明这个假定蕴含着每当a时，就有P(ya)为真 即：需要证明对每个a来说有l(xya)=l(x)+l(ya) 根据l()