递归函数论专题培训市公开课一等奖百校联赛特等奖课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第五章 递归函数论,5.1,数论函数和数论谓词,5.2,函数结构,5.2.1,迭置法,5.2.2,算子法,5.2.3,原始递归函数,第1页,派生法,利,用旧函数结构新函数方法,迭置法,算子法,派生法,第2页,5.2.1,迭置法,已知函数,f(x),g(x),h(x,y),f,1,(x),f,2,(x),，能够作复合函数以下：,g(f(x),f(g(x),h(f(x),g(x),h(f,1,(x),f,2,(x),函数迭置,(,合成,),第3页,迭置与非迭置例子,设有函数,S(x),，,S,2,(x)=S(S(x),S,3,(x)=S(S(S(x),考查,:,S,a,(x)=,S(S(S(x),a,考查：,S,y,(x)=,S(S(S(x),y,其中,a,为常数。,第4页,迭置法,定义：设新函数在某一变元处值与诸旧函数,n,个值相关，假如,n,不随新函数变元组改变而改变，则称该新函数是由旧函数利用迭置而得。,第5页,一、,(,m,，,n,),标准迭置,定义：设有一个,m,元函数,f(y,1,y,m,),，有,m,个,n,元函数,g,1,(x,1,x,n,),、,、,g,m,(x,1,x,n,),，,令：,h(x,1,，,，,x,n,)=f(g,1,，,，,g,m,),称之为,(m,，,n),标准迭置,。,并称函数,h,是由,m,个,g,对,f,作,(m,，,n),迭置而得，,简记为：,h=f(g,1,，,，,g,m,),第6页,例,下面迭置化为,(m,，,n),标准迭置,:,h(x1,x2)=f(x1,2,g(x2),解：,h(x1,x2)=f(h1,h2,h3),其中，,h1(x1,x2)=,I,21,(x1,x2),h2(x1,x2)=S,2,O,I,22,(x1,x2),h3(x1,x2)=g(,I,22,(x1,x2),),故函数,h(x1,，,x2),是由函数,h1,、,h2,、,h3,对,f,作,(3,，,2),迭置而得。,第7页,例,下面迭置化为,(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)=S,3,O,I,31,(x1,x2,x3),h2(x1,x2,x3)=g1(I,31,(x1,x2,x3),S,2,O,I,32,(x1,x2,x3),),h3(x1,x2,x3)=g2(I,31,(x1,x2,x3),，,I,32,(x1,x2,x3),h4(x1,x2,x3)=I,33,(x1,x2,x3),故函数,h(x1,，,x2,，,x3),是由函数,h1,、,h2,、,h3,、,h4,对,f,作,(4,，,3),迭置而得。,第8页,例,下面迭置化为,(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)=S,3,O,I,31,(x1,x2,x3),h2(x1,x2,x3)=g1(I,31,(x1,x2,x3),S,2,O,I,32,(x1,x2,x3),),h3(x1,x2,x3)=g2(I,31,(x1,x2,x3),，,I,32,(x1,x2,x3),h4(x1,x2,x3)=I,33,(x1,x2,x3),故函数,h(x1,，,x2,，,x3),是由函数,h1,、,h2,、,h3,、,h4,对,f,作,(4,，,3),迭置而得。,第9页,例,(6,分,),下面迭置化为,(m,，,n),标准迭置,:,第10页,二、凑合定义法,假设数论语句,A,1,、,A,2,、,、,A,k,，,对任何一个变元组,(X,1,，,X,2,，,，,X,n,),，,有且仅有,一个语句,A,i,成立。,令,:,称,h,为由旧函数,f,1,、,、,f,k,及数论语句,A,1,、,、,A,k,利用凑合定义而得到新函数。,第11页,化凑合定义,为迭置,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,第12页,例,(p58),试用凑合定义法定义函数,lm(,x,，,3),，并把它化为迭置。,解：,依据凑合定义法知：,lm(x,3)=xNct(x,为,3,倍数,)+3xNct(x,不,为,3,倍数,),=xN(N,2,rs(x,，,3)+3x N(N rs(x,，,3),=xN,3,rs(x,，,3)+3x N,2,rs(x,，,3),=xNrs(x,，,3)+3x N,2,rs(x,，,3),=xNrs(x,，,3)+xN,2,rs(x,，,3)+2 x N,2,rs(x,，,3),=x+2 x N,2,rs(x,，,3),第13页,例 将以下凑合定义化,为迭置,第14页,例 将以下凑合定义化,为迭置,第15页,第五章 递归函数论,5.1,数论函数和数论谓词,5.2,函数结构,5.2.1,迭置法,5.2.2,算子法,5.2.3,原始递归函数,第16页,5.2.2,算子法,定义：设新函数在某一变元组处值与诸旧函数,n,个值相关，假如,n,随新函数变元组改变而改变，则称该新函数是由旧函数利用算子而得。,第17页,一、迭函算子,定义：设有一个二元函数,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)=,A,2,f,(0),f,(1),f,(2),g,(,n,+1)=,A g,(,n,),f,(,n,+1),=,A,n+1,f,(0),f,(1),f,(2),f,(,n,+1),若把,A,(,x,y,),固定，而把函数,f,(,x,),看作为被改造函数，则称,g,(,n,),是由旧函数,f,(,x,),利用,迭函算子,A,而得。,第18页,迭函算子,g(0)=f(0),g(n+1)=A g(n)f(n+1),A,g(n),g(n+1),f(n+1),第19页,迭加算子、迭乘算子,迭加算子,：取,A,为加法，将,A,n+1,记为,迭乘算子：取,A,为乘法，,将,A,n+1,记为,第20页,二、原始递归式,例,(,递归式,),阶乘函数,标准形式,:,(1),不含参数原始递归式标准形式,(2),含参数原始递归式标准形式,第21页,(1),不含参数原始递归式,其中，,a,为一常数，,B,(,x,，,y,),为已知函数。,第22页,阶乘函数,n!,不含参数原始递归式,表示,：,其中，函数,B,(,x,，,y,),为,(,S,I,21,，,I,22,),，是,已知函数,。,书上少,S,，这里假定乘法,已定义,第23页,(2),含参数原始递归式,其中，,A(u,1,u,2,u,k,),、,B(u,1,u,2,u,k,x,y),为,已知函数,。,第24页,第五章 递归函数论,5.1,数论函数和数论谓词,5.2,函数结构,5.2.1,迭置法,5.2.2,算子法,5.2.3,原始递归函数,第25页,一、原始递归函数结构方法,原始递归函数,由本原函数出发，利用迭置和原始递归式而得函数。,(1),本原函数为原始递归函数；,(2),对已建立原始递归函数使用迭置而得函数仍为原始递归函数；,(3),对已建立原始递归函数使用原始递归式而得函数仍为原始递归函数。,第26页,二、原始递归函数结构过程,原始递归函数例子,:,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,第27页,例,(p60),f,(,x,y,)=,x,+,y,f(x,y),可用,含参数,x,原始递归表示以下：,其中，,B=,SI,33,为函数迭置,。,第28页,例,f(x,y)=xy,可用原始递归表示以下：,其中，,B,为,+(I,33,，,I,31,),，它为函数迭置。,第29页,例,(p60),可用原始递归表示以下：,其中，,B,为,+(I,22,，,g,(SI,21,),，它为函数迭置。,书上错,f(x,n),第30页,例,(p60),可用原始递归表示以下：,其中，,B,=,N,I,22,。,书上错,f(x+1,2),第31页,例,f(x)=Nx,可用原始递归表示以下：,其中，,B,=OI,21,为函数迭置。,第32页,例,f(x,y)=,x,y,可用原始递归表示以下：,其中，,B,=DI,33,为函数迭置。,书上没有证实,第33页,例,(p60),min(,x,，,y,),因为,min(,x,，,y,)=,x,(,x,y,),，,又因为,x,y,是原始递归函数，,由它迭置所得函数仍为原始递归函数。,故,min(,x,，,y,),为原始递归函数。,第34页,例,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),为原始递归函数。,第35页,例,(p61),x,y,证实,:,因为,x,y,=(x,y),+(y,x),且,x+y,和,x,y,为原始递归函数，所以,x,y,是由原始递归函数,x+y,和,x,y,利用迭置而得。,依据原始递归函数定义知，,x,y,为原始递归函数,.,第36页,例,(p61),试证实以下函数为原始递归函数,证实,:,其中,B=,(f(SI,21,),I,22,),，,也就是说 可用原始递归式表示，,所以 为原始递归函数。,第37页,例,C,a,(x),解：显然，,Ca(x),能够写成迭置形式以下：,C,a,(x)=S,a,O(x),故,C,a,(x),为原始递归函数。,另解：,C,a,(x),可用原始递归表示以下：,其中，,B,=I,22,为已知函数。,第38页,本原,函数,原始递归函数,+,原始递归式,I(x),I,mn,(x,1,，,x,m,),O(x),S(x),D(x),D(0)=0,D(x+1)=I,21,(x,D(x),Nx,F(0)=1,f(x+1)=OI,21,(x,f(x),x+y,f(x,0)=x,f(x,y+1)=SI,33,(x,y,f(x,y),xy,f(x,0)=0,f(x,y+1)=(I,33,+I,31,)(x,y,f(x,y),f(0)=g(0),f(n+1)=,+,(f(SI,21,),I,22,)(,n,f(n),f(0)=g(0),f(n+1)=,(f(SI,21,),I,22,)(,n,f(n),第39页,本原,函数,原始递归函数,+,迭置,原始递归函数,+,原始递归式,x,y,f(x,y+1)=D(f(x,y),?,(x,y),+(y,x,),max(x,y),x,(,x,y),min(x,y),x+(y,x,),C,a,(x),C,a,(x)=S,a,O(x),C,a,(x+1)=I,22,(x,C,a,(x),x/y,rs(x,y),rs(x,2),dv(x,y),lm(x,y),x,.,y,第40页,第五章 递归函数论,5.1,数论函数和数论谓词,5.2,函数结构,5.2.1,迭置法,5.2.2,算子法,5.2.3,原始递归函数,第六章 集合,第41页,