第五章-递归函数论

第五章递归函数论,5.1数论函数和数论谓词5.2函数的构造5.2.1迭置法5.2.2算子法5.2.3原始递归函数,派生法,利用旧函数构造新函数的方法,迭置法算子法,派生法,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),函数的迭置(合成),迭置与非迭置的例子,设有函数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为常数。,迭置法,定义：设新函数在某一变元处的值与诸旧函数的n个值有关，如果n不随新函数的变元组的变化而变化，则称该新函数是由旧函数利用迭置而得。,一、(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),例下面的迭置化为(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)迭置而得。,例下面的迭置化为(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)迭置而得。,例下面的迭置化为(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)迭置而得。,例(6分)下面的迭置化为(m，n)标准迭置:,二、凑合定义法,假设数论语句A1、A2、Ak，对任何一个变元组(X1，X2，Xn)，有且仅有一个语句Ai成立。令:,称h为由旧函数f1、fk及数论语句A1、Ak利用凑合定义而得到的新函数。,化凑合定义为迭置,h(x1,xn)=f1(x1,xn)NctA1(x1,xn)+f2(x1,xn)NctA2(x1,xn)+fk(x1,xn)NctAk(x1,xn),注意：这里仅当Ai(x1,xn)为真时,ctAi(x1,xn)=0进而，NctA1(x1,xn)=1显然,有NctA1(x1,xn)+NctAk(x1,xn)=1,例(p58)试用凑合定义法定义函数lm(x，3)，并把它化为迭置。,解：,根据凑合定义法知：lm(x,3)=xNct(x为3的倍数)+3xNct(x不为3的倍数)=xN(N2rs(x，3)+3xN(Nrs(x，3)=xN3rs(x，3)+3xN2rs(x，3)=xNrs(x，3)+3xN2rs(x，3)=xNrs(x，3)+xN2rs(x，3)+2xN2rs(x，3)=x+2xN2rs(x，3),例将下列凑合定义化为迭置,例将下列凑合定义化为迭置,第五章递归函数论,5.1数论函数和数论谓词5.2函数的构造5.2.1迭置法5.2.2算子法5.2.3原始递归函数,5.2.2算子法,定义：设新函数在某一变元组处的值与诸旧函数的n个值有关，如果n随新函数的变元组的变化而变化，则称该新函数是由旧函数利用算子而得。,一、迭函算子,定义：设有一个二元函数A(x,y)和一个一元函数f(x)利用它们作如下函数：,g(0)=f(0)g(1)=Ag(0)f(1)=Af(0)f(1)g(2)=Ag(1)f(2)=A2f(0)f(1)f(2)g(n+1)=Ag(n)f(n+1)=An+1f(0)f(1)f(2)f(n+1),若把A(x,y)固定，而把函数f(x)看作为被改造函数，则称g(n)是由旧函数f(x)利用迭函算子A而得。,迭函算子,g(0)=f(0)g(n+1)=Ag(n)f(n+1),A,g(n),g(n+1),f(n+1),迭加算子、迭乘算子,迭加算子：取A为加法，将An+1记为,迭乘算子：取A为乘法，将An+1记为,二、原始递归式,例(递归式)阶乘函数,标准形式:(1)不含参数的原始递归式的标准形式(2)含参数的原始递归式的标准形式,(1)不含参数的原始递归式,其中，a为一常数，B(x，y)为已知函数。,阶乘函数n!,不含参数的原始递归式表示：,其中，函数B(x，y)为(SI21，I22)，是已知函数。,书上少S，这里假定乘法已定义,(2)含参数的原始递归式,其中，A(u1,u2,uk)、B(u1,u2,uk,x,y)为已知函数。,第五章递归函数论,5.1数论函数和数论谓词5.2函数的构造5.2.1迭置法5.2.2算子法5.2.3原始递归函数,一、原始递归函数的构造方法,原始递归函数由本原函数出发，利用迭置和原始递归式而得的函数。,(1)本原函数为原始递归函数；(2)对已建立的原始递归函数使用迭置而得的函数仍为原始递归函数；(3)对已建立的原始递归函数使用原始递归式而得的函数仍为原始递归函数。,二、原始递归函数的构造过程,原始递归函数的例子:f(x,y)=x+yf(x,y)=xyf(x)=Nxf(x)=rs(x,2)f(x)=D(x),f(x,y)=min(x，y)f(x,y)=max(x，y)f(x,y)=xyf(x,y)=xy,例(p60)f(x,y)=x+y,f(x,y)可用含参数x的原始递归表示如下：,其中，B=SI33为函数的迭置。,例f(x,y)=xy,可用原始递归表示如下：,其中，B为+(I33，I31)，它为函数的迭置。,例(p60),可用原始递归表示如下：,其中，B为+(I22，g(SI21)，它为函数的迭置。,书上错f(x,n),例(p60),可用原始递归表示如下：,其中，B=NI22。,书上错f(x+1,2),例f(x)=Nx,可用原始递归表示如下：,其中，B=OI21为函数的迭置。,例f(x,y)=xy,可用原始递归表示如下：,其中，B=DI33为函数的迭置。,书上没有证明,例(p60)min(x，y),因为min(x，y)=x(xy)，又因为xy是原始递归函数，由它迭置所得的函数仍为原始递归函数。故min(x，y)为原始递归函数。,例max(x，y),试证明函数max(x，y)为原始递归函数.,证明:因为max(x,y)=x+(yx)且x+y和xy为原始递归函数，所以max(x,y)是由原始递归函数x+y和xy利用迭置而得。根据原始递归函数的定义知，max(x,y)为原始递归函数。,例(p61)xy,证明:因为xy=(xy)+(yx)且x+y和xy为原始递归函数，所以xy是由原始递归函数x+y和xy利用迭置而得。根据原始递归函数的定义知，xy为原始递归函数.,例(p61)试证明下列函数为原始递归函数,证明:,其中B=(f(SI21),I22)，也就是说