资源描述：
《第五章 递归函数论ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章递归函数论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考察：
2、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,x
3、2)=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(x
4、1,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(x
5、1,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
6、及数论语句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)，并把它化为迭置。解：根据凑合定义法
7、知：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算子法定义：设新函数在某一变元组处的值与诸旧
8、函数的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)
