第五章递归函数论.ppt

第五章 递归函数论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) Nct A1(x1 ,…, xn) + f2(x1 ,…, xn) Nct A2(x1 ,…, xn) +…… + fk(x1 ,…, xn) Nct Ak(x1 ,…, xn)注意：这里仅当注意：这里仅当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 N2rs(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)= 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)Ag(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) 对已建立的原始递归函数使用原始递归式对已建立的原始递归函数使用原始递归式而得的函数仍为原始递归函数。

而得的函数仍为原始递归函数二、原始递归函数的构造过程原始原始递归递归函数的例子函数的例子:l f(x,y)=x+yl f(x,y)=xyl f(x)=Nxl f(x)=rs(x,2)l f(x)=D(x) l f(x,y)= min(x，，y)l f(x,y)= max(x，，y)l f(x, y)= x   yl f(x,y)=x   y例例 (p60) f(x,y)=x+yf(x,y) 可用可用含参数含参数x的的原始原始递归递归表示如下：表示如下：其中，其中，B=SI33为为函数的迭置函数的迭置例例 f(x,y)=xy 可用原始递归表示如下：可用原始递归表示如下：其中，其中，B为为+(I33，，I31)，它，它为为函数的迭置函数的迭置例例(p60) 可用原始可用原始递归递归表示如下：表示如下： 其中，其中，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)为原始递归函数为原始递归函数.证明证明: 因为因为 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为为已知函数已知函数本原本原函数函数原始递归函数原始递归函数+原始递归式原始递归式I(x)I(x)✔✔I Imnmn(x(x1 1，，…,x,xm m) )✔✔O(x)O(x)✔✔S(x)S(x)✔✔D(x)D(0)=0, D(x+1)=I21(x, D(x)) ✔✔NxNxF(0)=1, f(x+1)=OI21(x,f(x)) ✔✔x+yf(x,0)=x, f(x,y+1)=SI33(x,y,f(x,y)) ✔✔xyf(x,0)=0, f(x,y+1)=(I33+I31)(x,y,f(x,y) ✔✔f(0)=g(0), f(n+1)=+(f(SI21),I22)(n,f(n)) ✔✔f(0)=g(0), f(n+1)=×(f(SI21),I22)(n,f(n)) ✔✔本原本原函数函数原始递归函数原始递归函数+迭置迭置原始递归函数原始递归函数+原始递归式原始递归式x   yf(x,y+1)=D(f(x,y))✔✔? (x   y) +(y   x) ✔✔max(x,y)max(x,y) x   (x   y) ✔✔min(x,y)min(x,y) x +(y   x) ✔✔Ca(x)Ca(x)=SaO(x) ✔✔Ca(x+1)=I22(x, Ca(x)) ✔✔[ ][ ][x/y][x/y]rs(x,y)rs(x,y)rs(x,2) ✔✔dv(x,y)dv(x,y)lm(x,y)lm(x,y)x .. y第五章 递归函数论5.1 数论函数和数论谓词数论函数和数论谓词 5.2 函数的构造函数的构造 5.2.1 迭置法迭置法 5.2.2 算子法算子法 5.2.3 原始递归函数原始递归函数第六章第六章 集合集合。