五章节递归函数论.pptx

派生法派生法利利用旧函数构造新函数的方法用旧函数构造新函数的方法迭置法算子法派生法第1页/共41页5.2.1 迭置法迭置法已知函数已知函数f(x),g(x),h(x,y),f1(x),f2(x)，可以作，可以作复合函数如下：复合函数如下：g(f(x)f(g(x)h(f(x),g(x)h(f1(x),f2(x)函数的迭置(合成)第2页/共41页迭置与非迭置的例子迭置与非迭置的例子设有函数S(x)，S2(x)=S(S(x),S3(x)=S(S(S(x),考察:Sa(x)=S(S(S(x)a考察：Sy(x)=S(S(S(x)y其中,a为常数。第3页/共41页 迭置法迭置法定义：设新函数在某一变元处的值与诸旧函数的定义：设新函数在某一变元处的值与诸旧函数的n个值有关，如果个值有关，如果n不随新函数的变元组不随新函数的变元组的变化而变化，则称该新函数是由旧函数利用迭置而得。的变化而变化，则称该新函数是由旧函数利用迭置而得。第4页/共41页一、一、(m，n)标准迭置标准迭置 定义：设有一个定义：设有一个m元函数元函数f(y1,ym)，有，有m个个n元函数元函数 g1(x1,xn)、gm(x1,xn)，令：令：h(x1，xn)=f(g1，gm)称之为称之为(m，n)标准迭置标准迭置。并称函数并称函数h是由是由m个个g对对f作作(m，n)迭置而得，迭置而得，简记为：简记为：h=f(g1，gm)第5页/共41页例例 下面的迭置化为下面的迭置化为(m，n)标准迭置标准迭置:h(x1,x2)=f(x1,2,g(x2)解：解：h(x1,x2)=f(h1,h2,h3)其中，其中，h1(x1,x2)=I21(x1,x2)h2(x1,x2)=S2OI22(x1,x2)h3(x1,x2)=g(I22(x1,x2)故函数故函数h(x1，x2)是由函数是由函数h1、h2、h3对对f作作(3，2)迭置而得。迭置而得。第6页/共41页例例 下面的迭置化为下面的迭置化为(m，n)标准迭置标准迭置:h(x1,x2,x3)=f(3,g1(x1,2),g2(x1,x2),x3)解：解：h(x1,x2,x3)=f(h1,h2,h3,h4)其中，其中，h1(x1,x2,x3)=S3OI31(x1,x2,x3)h2(x1,x2,x3)=g1(I31(x1,x2,x3),S2OI32(x1,x2,x3)h3(x1,x2,x3)=g2(I31(x1,x2,x3)，I32(x1,x2,x3)h4(x1,x2,x3)=I33(x1,x2,x3)故函数故函数h(x1，x2，x3)是由函数是由函数h1、h2、h3、h4对对f作作(4，3)迭置而得。迭置而得。第7页/共41页例例 下面的迭置化为下面的迭置化为(m，n)标准迭置标准迭置:h(x1,x2,x3)=f(3,g1(x1,2),g2(x1,x2),x3)解：解：h(x1,x2,x3)=f(h1,h2,h3,h4)其中，其中，h1(x1,x2,x3)=S3OI31(x1,x2,x3)h2(x1,x2,x3)=g1(I31(x1,x2,x3),S2OI32(x1,x2,x3)h3(x1,x2,x3)=g2(I31(x1,x2,x3)，I32(x1,x2,x3)h4(x1,x2,x3)=I33(x1,x2,x3)故函数故函数h(x1，x2，x3)是由函数是由函数h1、h2、h3、h4对对f作作(4，3)迭置而得。迭置而得。第8页/共41页例例(6分分)下面的迭置化为下面的迭置化为(m，n)标准迭置标准迭置:第9页/共41页二、凑合定义法二、凑合定义法 假设数论语句假设数论语句A1、A2、Ak，对任何一个变元对任何一个变元组组(X1，X2，Xn)，有且仅有有且仅有一个语句一个语句Ai成立。成立。令令:称h为由旧函数f1、fk及数论语句A1、Ak利用凑合定义而得到的新函数。第10页/共41页化凑合定义化凑合定义为迭置为迭置 h(x1,xn)=f1(x1,xn)Nct A1(x1,xn)+f2(x1,xn)Nct A2(x1,xn)+fk(x1,xn)Nct Ak(x1,xn)注意：这里仅当注意：这里仅当Ai(x1,xn)为真时为真时,ct Ai(x1,xn)=0进而，进而，Nct A1(x1,xn)=1 显然显然,有有 Nct A1(x1,xn)+Nct Ak(x1,xn)=1第11页/共41页例例(p58)试用凑合定义法定义函数试用凑合定义法定义函数lm(x，3)，并把它化为迭置。并把它化为迭置。解：解：根据凑合定义法知：lm(x,3)=xNct(x为3的倍数)+3xNct(x不为3的倍数)=xN(N2 rs(x，3)+3x N(N rs(x，3)=xN3rs(x，3)+3x N2 rs(x，3)=xNrs(x，3)+3x N2 rs(x，3)=xNrs(x，3)+xN2 rs(x，3)+2 x N2rs(x，3)=x+2 x N2 rs(x，3)第12页/共41页例例 将下列凑合定义化将下列凑合定义化为迭置为迭置第13页/共41页例例 将下列凑合定义化将下列凑合定义化为迭置为迭置第14页/共41页第五章第五章 递归函数论递归函数论5.1 数论函数和数论谓词数论函数和数论谓词 5.2 函数的构造函数的构造 5.2.1 迭置法迭置法 5.2.2 算子法算子法 5.2.3 原始递归函数原始递归函数第15页/共41页5.2.2 算子法算子法定义：设新函数在某一变元组处的值与诸旧函数的定义：设新函数在某一变元组处的值与诸旧函数的n 个值有关，如果个值有关，如果n 随新函数的变元随新函数的变元组的变化而变化，则称该新函数是由旧函数利用算子而得。组的变化而变化，则称该新函数是由旧函数利用算子而得。第16页/共41页一、迭函算子一、迭函算子定义：设有一个二元函数定义：设有一个二元函数A(x,y)和一个一元函数和一个一元函数f(x)利用它们作如下函数：利用它们作如下函数：g(0)=f(0)g(1)=A g(0)f(1)=A f(0)f(1)g(2)=A g(1)f(2)=A2 f(0)f(1)f(2)g(n+1)=A g(n)f(n+1)=An+1 f(0)f(1)f(2)f(n+1)若把A(x,y)固定，而把函数f(x)看作为被改造函数，则称g(n)是由旧函数f(x)利用迭函算子A而得。第17页/共41页迭函算子迭函算子g(0)=f(0)g(n+1)=A g(n)f(n+1)Ag(n)g(n+1)f(n+1)第18页/共41页迭加算子、迭乘算子迭加算子、迭乘算子迭加算子：取A为加法，将An+1记为迭乘算子：取A为乘法，将An+1记为第19页/共41页二、原始递归式二、原始递归式 例例(递归式递归式)阶乘函数阶乘函数标准形式:(1)不含参数的原始递归式的标准形式 (2)含参数的原始递归式的标准形式第20页/共41页(1)不含参数的原始递归式不含参数的原始递归式其中，a为一常数，B(x，y)为已知函数。第21页/共41页阶乘函数阶乘函数n!不含参数的原始递归式表示：其中，函数B(x，y)为(SI21，I22)，是已知函数。书上少S，这里假定乘法已定义第22页/共41页(2)含参数的原始递归式含参数的原始递归式其中，A(u1,u2,uk)、B(u1,u2,uk,x,y)为已知函数。第23页/共41页第五章第五章 递归函数论递归函数论5.1 数论函数和数论谓词数论函数和数论谓词 5.2 函数的构造函数的构造 5.2.1 迭置法迭置法 5.2.2 算子法算子法 5.2.3 原始递归函数原始递归函数第24页/共41页一、原始递归函数的构造方法一、原始递归函数的构造方法原始递归函数由本原函数出发，利用迭置和原始递归式而得的函数。(1)本原函数为原始递归函数；(2)对已建立的原始递归函数使用迭置而得的函数仍为原始递归函数；(3)对已建立的原始递归函数使用原始递归式而得的函数仍为原始递归函数。第25页/共41页二、原始递归函数的构造过程二、原始递归函数的构造过程原始递归函数的例子:l f(x,y)=x+yl f(x,y)=xyl f(x)=Nxl f(x)=rs(x,2)l f(x)=D(x)l f(x,y)=min(x，y)l f(x,y)=max(x，y)l f(x,y)=x yl f(x,y)=x y第26页/共41页例例(p60)f(x,y)=x+yf(x,y)可用含参数x的原始递归表示如下：其中，B=SI33为函数的迭置。第27页/共41页例例 f(x,y)=xy 可用原始递归表示如下：可用原始递归表示如下：其中，B为+(I33，I31)，它为函数的迭置。第28页/共41页例例(p60)可用原始递归表示如下：其中，B为+(I22，g(SI21)，它为函数的迭置。书上错f(x,n)第29页/共41页例例(p60)可用原始递归表示如下：其中，B=N I22。书上错f(x+1,2)第30页/共41页例例 f(x)=Nx可用原始递归表示如下：可用原始递归表示如下：其中，B=OI21为函数的迭置。第31页/共41页例例 f(x,y)=x y 可用原始递归表示如下：可用原始递归表示如下：其中，B=DI33为函数的迭置。书上没有证明第32页/共41页例例(p60)min(x，y)因为 min(x，y)=x (x y)，又因为x y是原始递归函数，由它迭置所得的函数仍为原始递归函数。故min(x，y)为原始递归函数。第33页/共41页例例 max(x，y)试证明函数试证明函数max(x，y)为原始递归函数为原始递归函数.证明:因为 max(x,y)=x+(y x)且x+y 和 x y为原始递归函数，所以max(x,y)是由原始递归函数x+y 和x y 利用迭置而得。根据原始递归函数的定义知，max(x,y)为原始递归函数。第34页/共41页例例(p61)x y证明:因为 x y=(x y)+(y x)且x+y 和 x y为原始递归函数，所以x y是由原始递归函数x+y 和x y 利用迭置而得。根据原始递归函数的定义知，x y为原始递归函数.第35页/共41页例例(p61)试证明下列函数为原始递归函数试证明下列函数为原始递归函数证明:其中 B=(f(SI21),I22)，也就是说 可用原始递归式表示，所以 为原始递归函数。第36页/共41页例例 Ca(x)解：解：显然，显然，Ca(x)可以写成迭置的形式如下：可以写成迭置的形式如下：Ca(x)=SaO(x)故故Ca(x)为原始递归函数。为原始递归函数。另解：另解：Ca(x)可用原始递归表示如下：可用原始递归表示如下：其中，B=I22为已知函数。第37页/共41页本原本原函数函数原始递归函数原始递归函数+原始递归式原始递归式I(x)I(x)I Imnmn(x(x1 1，,x,xm m)O(x)O(x)S(x)S(x)D(x)D(0)=0,D(x+1)=I21(x,D(x)NxNxF(0)=1,f(x+1)=OI21(x,f(x)x+yf(x,0)=x,f(x,y+1)=SI33(x,y,f(x,y)xyf(x,0)=0,f(x,y+1)=(I33+I31)(x,y,f(x,y)f(0)=g(0),f(n+1)=+(f(SI21),I22)(n,f(n)f(0)=g(0),f(n+1)=(f(SI21),I22)(n,f(n)第38页/共41页本原本原函数函数原始递归函数原始递归函数+迭置迭置原始递归函数原始递归函数+原始递归式原始递归式x yf(x,y+1)=D(f(x,y)?(x y)+(y x)max(x,y)max(x,y)x (x y)min(x,y)min(x,y)x+(y x)Ca(x)Ca(x)=SaO(x)Ca(x+1)=I22(x,Ca(x)x/yx/yrs(x,y)rs(x,y)rs(x,2)dv(x,y)dv(x,y)lm(x,y)lm(x,y)x .y第39页/共41页第五章第五章 递归函数论递归函数论5.1 数论函数和数论谓词数论函数和数论谓词 5.2 函数的构造函数的构造 5.2.1 迭置法迭置法 5.2.2 算子法算子法 5.2.3 原始递归函数原始递归函数第六章第六章 集合集合第40页/共41页