《递归函数论》ppt课件

《递归函数论》ppt课件

ID:27324365

大小:451.50 KB

页数:41页

时间:2018-11-30

《递归函数论》ppt课件_第1页
《递归函数论》ppt课件_第2页
《递归函数论》ppt课件_第3页
《递归函数论》ppt课件_第4页
《递归函数论》ppt课件_第5页
资源描述:

《《递归函数论》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)

2、)…)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

3、,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)

4、=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

5、,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,

6、…,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

7、例(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

8、迭置法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)

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。