第五章递归函数论.ppt
《第五章递归函数论.ppt》由会员分享,可在线阅读,更多相关《第五章递归函数论.ppt(41页珍藏版)》请在三一文库上搜索。
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,考察: Sy(x)=S(S( (S(
2、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,
3、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),I
4、32(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(
5、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)Nct A1(x1 , xn) + f2(x1 , xn)Nct A2(x1 , xn) + + fk(x1 , xn)Nct Ak(x1 , xn),注意:这里
6、仅当Ai(x1,xn)为真时, ct Ai(x1 , xn)= 0 进而, Nct A1(x1 , xn)=1 显然, 有 Nct A1(x1 , xn)+ + Nct Ak(x1 , xn)=1,例 (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 N2r
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 递归 函数
链接地址:https://www.31doc.com/p-2571124.html