《第五章递归函数论.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
7、s(x，3) = x+2 x N2 rs(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)= A g(0)f(1)=A f(0)f(1) g(2)= A g(1)f(2)=
8、 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而得。,迭函算子,g(0)=f(0) g(n+1)= A g(n)f(n+1),A,g(n),g(n+1),f(n+1),迭加算子、迭乘算子,迭加算子：取A为加法，将An+1记为,迭乘算子：取A为乘法，将An+1记为,二、原始递归式,例(递归式) 阶乘函数,标准形式: (1) 不含参数的原始递归式的标准形式 (2) 含参数的原始递归式的标准形式,(1) 不含参数的原始递
9、归式,其中，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) 对已建立的原始递归函数使用迭置而得的函数仍为
10、原始递归函数； (3) 对已建立的原始递归函数使用原始递归式而得的函数仍为原始递归函数。,二、原始递归函数的构造过程,原始递归函数的例子: f(x,y)=x+y f(x,y)=xy f(x)=Nx f(x)=rs(x,2) f(x)=D(x),f(x,y)= min(x，y) f(x,y)= max(x，y) f(x, y)= x y f(x,y)=x y,例 (p60) f(x,y)=x+y,f(x,y) 可用含参数x的原始递归表示如下：,其中，B=SI33为函数的迭置。,例 f(x,y)=xy,可用原始递归表示如下：,其中，B为+(I33，I31)，它为函数的迭置。,例(p60),可用原始
11、递归表示如下：,其中，B为+(I22，g(SI21)，它为函数的迭置。,书上错f(x,n),例(p60),可用原始递归表示如下：,其中，B=N I22。,书上错 f(x+1,2),例 f(x)=Nx,可用原始递归表示如下：,其中，B=OI21为函数的迭置。,例 f(x, y)= x y,可用原始递归表示如下：,其中，B=DI33为函数的迭置。,书上没有证明,例(p60) min(x，y),因为 min(x，y)=x (x y)， 又因为x y是原始递归函数， 由它迭置所得的函数仍为原始递归函数。 故min(x，y)为原始递归函数。,例 max(x，y),试证明函数max(x，y)为原始递归函数
12、.,证明: 因为 max(x,y)= x+(y x) 且x+y 和 x y为原始递归函数， 所以max(x,y) 是由原始递归函数x+y 和x y 利用迭置而得。 根据原始递归函数的定义知， max(x,y)为原始递归函数。,例(p61) x y,证明: 因为 x y = (x y) +(y x) 且x+y 和 x y为原始递归函数，所以x y是由原始递归函数x+y 和x y 利用迭置而得。 根据原始递归函数的定义知， x y为原始递归函数.,例(p61) 试证明下列函数为原始递归函数,证明:,其中 B = (f(SI21),I22)， 也就是说 可用原始递归式表示， 所以 为原始递归函数。,例 Ca(x),解： 显然，Ca(x)可以写成迭置的形式如下： Ca(x)=SaO(x) 故Ca(x)为原始递归函数。 另解：Ca(x)可用原始递归表示如下：,其中，B=I22为已知函数。,第五章 递归函数论,5.1 数论函数和数论谓词 5.2 函数的构造 5.2.1 迭置法 5.2.2 算子法 5.2.3 原始递归函数 第六章 集合,