第 5 章 递归函数论 递归函数是数论函数,以自然数为研究对象,定义域和值域均为自然数。它 为能行可计算函数找出各种理论上的、严密的类比物,即某个函数能否用若干可 计算函数通过某种已有的算法(如迭置或算子)在有限步内递归产生,若能,说明 该函数为可计算函数,否则为不可计算函数,因此,递归函数论又称为可计算性 理论。下 面举几个例子说明函数的可计算性。 例5.1 g(n)= [ n ] 表示取自然数n 的平方根的整数部分。 将n 依次与12,22,32,…作比较,总可求得g(n)的值,所以g(n)是可计算的。 例5.2 g(n)= 0 π的展开式中有n 个连续的9 1 否则{ 因π的展开式是一个无穷序列,要计算上述函数可能是一个无限过程,故函 数g(n)为不可计算函数。 视频5.1 .. 5.1 数论函数和数论谓词 5.1.1 数论函数 5.1:数论函数是指以自然数集为定义域及值域的函数。 下面简单介绍常用的数论函数,其中x、y 均为自然数域中的变元。 x+y 指x 与y 的和。 xy 指x 与y 的积。 x·- y 指x 与y 的算术差,即x≥y 时,其值为x-y,否则为0。 x ·-·y 指x 与y 的绝对差,即大数减小数。 [ x ] 指x 的平方根的整数部分。 [x/y ] 指x 与y 的算术商。 rs(x,y)指y 除x 的余数,约定y=0时,rs(x,y)=x。 dv(x,y)指x 与y 的最大公约数,约定xy=0时,其值为x+y。 lm(x,y)指x 与y 的最小公倍数,约定xy=0时,其值为0。 I(x)=x 指函数值与自变量的值相同,称为幺函数。 Imn(x1,x2,…,xn ,…,xm )=xn ,即函数值与第n 个自变量的值相同,此函数 82 离散数学(微课版) 称为广义幺函数。 O(x)=0,即函数值永为0,称为零函数。 S(x)=x+1,称为后继函数。 D (x)指x 的前驱,称为前驱函数。当x=0时,其值为0;当x>1时,其值为x-1。 Ca(x)=a,即函数值永为a,这个函数称为常值函数。 函数xNy、xN2y 的定义如下: xNy = x 当y =0时 0 当y ≠0时{ xN2y = 0 当y =0时 x 当y ≠0时{ 特例,当x=1时有 Ny = 1 当y =0时 0 当y ≠0时{ N2y = 0 当y =0时 1 当y ≠0时{ eq(x,y)= 0 当x =y 时 1 当x ≠y 时{ 特别地,把广义幺函数、零函数和后继函数称为本原函数,它们是构造函数的最基本 单位。 5.1.2 数论谓词和特征函数 1.数论谓词和特征函数的定义 在第3章中提到的谓词是以个体为定义域,以真假为值域的函数,而含有变元的语句是 指含有个体变元的谓词填式或由它们利用真值联结词和量词组成的式子,即谓词演算公式。 5.2:数论谓词是指以自然数集为定义域,以真假为值域的谓词。由数论谓词利用 联结词和量词构成的式子称为数论语句。例如,“2为质数”“8>7且9为平方数”等均为数 论语句。 5.3:设A(x1,x2,…,xn)是一个含有n 个变量的语句,f(x1,x2,…,xn )是一个 数论函数,若对于任何变元组均有 A(x1,x2,…,xn)为真时,f(x1,x2,…,xn)=0; A(x1,x2,…,xn)为假时,f(x1,x2,…,xn)=1。 则称f(x1,x2,…,xn)是语句A(x1,x2,…,xn)的特征函数,记为ctA(x1,x2,…,xn)。 5.1:任何一个语句均有唯一的特征函数。 证明: (1)存在性。对于任何一个语句A ,恒可以按如上定义一个函数f(x1,x2,…,xn ),此 函数必为语句A 的特征函数,故存在性得证。 (2)唯一性。设f 和g 为语句A 的两个特征函数,由上定义知: 当A(x1,x2,…,xn)为真时, f(x1,x2,…,xn)=g(x1,x2,…,xn)=0 当A(x1,x2,…,xn)为假时, f(x1,x2,…,xn)=g(x1,x2,…,xn)=1 再由函数的相等性知,f(x1,x2,…,xn)=g(x1,x2,…,xn),即语句A (x1,x2,…,xn )的特 征函数是唯一的。 第5章递归函数论83 2:如果有一个函数f(x1,x2,…,)满足下列条件: x2,…,)为真当且仅当f(x2,…,) 5.xn A(x1,xn x1,xn = 0 x1,xn x1,xn 则N2f(x2,…,)为语句A(x2,…,)的特征函数。 x1,xn x1,xn =x1,xn = 证明:当A(x2,…,)为真时,由于f(x2,…,)0,所以N2f(x2,…,)0; x1,nx1,xn)≠0, x1,xn= 当A(x2,…,)为假时,由已知条件知f(x2,…,所以N2f(x2,…,)1。 由特征函数的(x) x1,) 句A(x2,…,的特征函数。定义知N2f(x2,…,xn 为语x1,xn ) x1,xn x1,xn此时把函数f(x2,…,)称为A(x2,…,)的准特征函数。 2.简单语句的特征函数 表5. 1是一些包含变量的语句的特征函数。 表5.一些包含变量的语句的特征函数 1 语句特征函数语句特征函数 x 为0 N2x x 小于 y N2((x+1)· -y) x 不等于0 Nx x 与 y 互质N2(dv(x,y)·· -1) x 为 y 的倍数N2rs(x,y) 3.复合语句的特征函数 5.3:设A、 B 为任意两个语句,则有 ct..A=1·ctA =NctA - ct(=tcB=mn(tcB) A ∨B)cA·ticA,tt(=N2(B)x(A,B) cA ∧B)ctA+ct=mactctct( A →B)=ctB·NctA - 例5.3 给出“ ct(A.B)=ctA · ctB 的特征函数。 a 为 b 的倍数且 a 为平方数” 解:“ 的特征函数为N2rs(“ 的特征函数为N2( a a 为 b 的倍数” b), a 为平方数”· a, [a] 由定理5. N2(N2rb)+N2(·[a]2)) 2)。 3知原句的特征函数为 s( a a, - 例5.4 给出“ x≥2且由 a 除尽 x 可推出a=1或a= x ”的特征函数 。 解: 令 A 表示“ x≥2其特征函数为N2(2 ”, · x) ; B 表示“, s(a) ; a 除尽x”其特征函数为N2rx, ”其特征函数为N2(· · C 表示“ a=1, a -1); D 表示“,其特征函数为N2(·-· x)。 a= x ” a 原句译为 84 离散数学(微课版) A ∧( B →( C ∨D)) 其特征函数为 ct( A ∧( B →( C ∨D)))=N2(ctA+ctC·ctD·NctB) 则原句的特征函数为 N2(N2(2· x)+N2( · ·N2( · a)) a 1)ax)·Nrs(x, 下面简单讨论用量词构成的语句的特征函数。 .A(x)表示对于任何0到 n 的一切 x 均使得A(x)成立。此量词称为受限全称量词。 x→ n .A(x)表示对于任何0到 n 至少有一个 x 使A(x)成立。此量词称为受限存在量词。 x→ n 5.x) 则有 4:设A(为任意一个含有 x 的语句, (1)t(. x))x(t0),t1),t2),…,tn)) cA(=macA(cA(cA(cA( x→ n 0)1)n)) (x))0),1),2),…,n)) =N2(ctA(+ctA(+ctA(2)+…+ctA( 2)ct(.A(=min(ctA(ctA(ctA(ctA( x→ n =cA(·cA(·cA(2)·…·cA( t0)t1)ttn) ..5.2 函数的构造 视频5. 2 前面介绍了一些常用的简单函数,这些简单函数均可采用直接定义的方法来产生。显 然直接定义的方法只能产生少量简单的函数,而对于绝大多函数来说,无法用直接定义的方 视频5. 法产生,为此,必须利用已定义的函数(称为旧函数)来构造新函数,这种方法称为派生法。 3 派生法有两类:一类是迭置法,另一类是算子法。 5.1 迭置法 2. 4:设新函数在某一变元处的值与诸旧函数的 n 个值有关,如果 n 不随新函数的 变元组的变化而变化,则称该新函数是由旧函数利用迭置而得的。 例如,设有函数S( a 为常数。现构造一元函数Sa (显然Sa (x)在x0 处的值与 5. x),x), S(x)在Sa-1(x0),Sa-2(x0),…,S(x0),x0 等 a 个值有关,而且 a 为常量与x0 无关,所以 Sa (x)可由S(x)利用迭置而得。 1.(m,标准迭置 x1,xm x1,xn g2(x1, n) 设有一个 m 元函数f(x2,…,), m 个 n 元函数g1(x2,…,)、x2,…, xn )、…、gm x1,xn 由 f 和gi(=2,…,构造如下的函数: (x2,…,), i1,n) x1,xn =f(g1(x1,xn g2(x1,xn h(x2,…,)x2,…,),x2,…,),…, (x2,…,)) 称为(m,n)标准迭置。称函数hg 是由 m xm 1, 个 g 对 xfn 作(m,n)标准迭置而得的,简记为 h(x1,)g2,…,x1,) x2,…,xn =f(g1,gm )(x2,…,xn 例5.5 注意,通常的迭置并不满足上述条件,但可以采用本原函数把它们化为(n)标准迭置。 利用本原函数把下面的迭置化为(m,n)标准迭置。 m, h(x1,x3,x6)g1(3),g2(x3),g3(x2)) x2,x5,=f(x1,4,x2,x5,x6, 第5章 递归函数论 85 解:h(x1,x2,x3,x5,x6)=f(h1,h2,h3,h4,h5)(x1,x2,x3,x5,x6) 其中: h1(x1,x2,x3,x5,x6)=g1(I51,S3OI51)(x1,x2,x3,x5,x6) h2(x1,x2,x3,x5,x6)=S4OI51(x1,x2,x3,x5,x6) h3(x1,x2,x3,x5,x6)=g2(I52,I53)(x1,x2,x3,x5,x6) h4(x1,x2,x3,x5,x6)=I54(x1,x2,x3,x5,x6) h5(x1,x2,x3,x5,x6)=g3(I55,I52)(x1,x2,x3,x5,x6) 故函数h(x1,x2,x3,x5,x6)是由函数h1、h2、h3、h4、h5 对f 作(5,5)标准迭置而得的。 2.凑合定义法 所谓凑合定义法是指如下构造函数的方法: h(x1,x2,…,xn)= f1(x1,x2,…,xn) 当A1(x1,x2,…,xn)为真时 f2(x1,x2,…,xn) 当A2(x1,x2,…,xn)为真时 . . fk(x1,x2,…,xn) 当Ak(x1,x2,…,xn)为真时 ì . í ... ... 称新函数h 由旧函数f1,f2,…,fk 及数论语句A1,A2,…,Ak 利用凑合定义而得。注 意,数论语句A1,A2,…,Ak 互相不可兼,即对任何一个变元组(x1,x2,…,xn),有且仅有一 个条件Ai 成立。 可以看出,此种定义方法不利于计算机的符号处理,为此,利用前面定义的一些简单函 数,如xNy 等函数,把新函数化归为迭置。即 h(x1,x2,…,xn)=f1(x1,x2,…,xn)·N ctA1(x1,x2,…,xn)+ f2(x1,x2,…,xn)·NctA2(x1,x2,…,xn)+ … + fk(x1,x2,…,xn)·NctAk(x1,x2,…,xn) 例5.6 试用凑合定义法定义函数lm(x,5),并把它化为迭置。 解: lm(x,5)= x 当x 为5的倍数时 5x 当x 不为5的倍数时{ 根据凑合定义法知 lm(x,5)=xNN2rs(x,5)+5xNNrs(x,5) =xNrs(x,5)+5xN2rs(x,5) =xNrs(x,5)+xN2rs(x,5)+4xN2rs(x,5) =x(Nrs(x,5)+N2rs(x,5))+4xN2rs(x,5) =x +4xN2rs(x,5) 5.2.2 算子法 5.5:设新函数在某一变元组处的值与诸旧函数的n 个值有关,如果n 随新函数的 变元组的变化而变化,则称该新函数是由旧函数利用算子而得的。 例如,设有函数S(x),现构造函数Sy (x),显然Sy (x)在(x0,y0)处的值与S(x)在 Sy0-1(x0),Sy0-2(x0),…,S(x0),x0 等y0 个值有关,而且y0 随着变元组(x0,y0)的变化 86 离散数学(微课版) 而变化,所以Sy (x)可由S(x)利用算子而得。 算子的类型很多,下面介绍迭函算子和原始递归式两种算子。 1.迭函算子 5.6:设有一个二元函数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(A(f(0),f(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(n)) 显然,g(n)的值依赖于函数A (x,y)和函数f (x)。若把A (x,y)固定,而把函数 f(x)看作被改造函数,则称g(n)是由旧函数f(x)利用迭函算子而得的。例如,把A 分别 固定为加法和乘法时可得不同的迭函算子。 (1)迭加算子:取A 为加法,记为Σx→n 。例如: Σx→n f(x)=f(0)+f(1)+ … +f(n) (2)迭乘算子:取A 为乘法,记为Πx→n 。例如: Πx→n f(x)=f(0)×f(1)× … ×f(n) 2.原始递归式 递归的概念在前面已经多次提到,如阶乘的函数 n!= 1 当n =0时 n(n -1)! 当n ≥1时{ 有了此例子,下面来定义原始递归式。 (1)不含参数的原始递归式: g(0)=a {g(n +1)=B(n,g(n)) 其中,a 为常数,B(x,y)为已知函数。此式称为不含参数的原始递归式的标准形式。 例如,g(n)=n!可用递归式表示如下: g(0)=1 {g(n +1)=(n +1)×g(n)=B(n,g(n)) 其中,函数B(x,y)为×(SI21,I22),它是已知函数。 (2)含参数的原始递归式: g(u1,u2,…,uk ,0)=A(u1,u2,…,uk) {g(u1,u2,…,uk ,n +1)=B(u1,u2,…,uk ,n,g(u1,u2,…,uk ,n)) 其中,A(u1,u2,…,uk)和B(u1,u2,…,uk ,x,y)为已知函数。此式称为含参数的原始递归 式的标准形式。 5.2.3 原始递归函数 1.原始递归函数的构造方法 根据上面介绍的内容,可知构造原始递归函数的方法如下: 第5章 递归函数论 87 (1)本原函数为原始递归函数。 (2)对已建立的原始递归函数利用迭置而得的函数仍为原始递归函数。 (3)对已建立的原始递归函数利用原始递归式而得的函数仍为原始递归函数。 所以,原始递归函数是由本原函数出发,利用迭置和原始递归式而得的函数。 2.原始递归函数的构造过程 下面是若干递归函数的例子,以便说明原始递归函数的构造过程,其他函数可以此类推。 (1)S(x)=x+1,为本原函数。 (2)Imn(x1,x2,…,xn ,…,xm )=xn ,为本原函数。 (3)f(x,y)=x+y。 可用原始递归式表示如下: f(x,0)=x {f(x,y +1)=x +y +1=B(x,y,f(x,y)) 其中,B 为SI33,它们为函数的迭置。 (4)f(x,y)=xy 。 可用原始递归式表示如下: f(x,0)=x0 =1 {f(x,y +1)=xy+1 =xy ×x =B(x,y,f(x,y)) 其中,B 为×(I33,I31),它们为函数的迭置。 (5)f(x)=ax 。 可用原始递归式表示如下: f(0)=a0 =1 {f(x +1)=ax+1 =ax ×a =B(x,f(x)) 其中,B 为×(I22,SaOI21),它们为函数的迭置。 (6)f(x)=D (x)。 可用原始递归式表示如下: f(0)=D (0)=0 {f(x +1)=D (x +1)=x =B(x,f(x)) 其中,B 为I21。 (7)max(x,y)。 因为max(x,y)=x+(y·-x),又因为x+y 和x·- y 是原始递归函数,由它们的迭置 所得的函数仍为原始递归函数。故max(x,y)为原始递归函数。 .. 5.3 典型例题 例5.7 给出“x 为质数”的特征函数。 解:“x 为质数”可理解为2至x-1都不是x 的因子。 其特征函数可表示为 N2 Σt→x ( Nrs(x,t)·-·2) 88 离散数学(微课版) 例5.8 把下面利用凑合定义法定义的函数化为迭置。 f(x)= x 当x ≤10时 2x 当1020时 ì . í .. .. 解:“x≤10”的特征函数为N2(x·- 10)。 “1020”的特征函数为N2(21·- x)。 将上述函数化为迭置: f(x)=x·N N2(x ·-10)+2x·N N2(N2(11·-x)+ N2(x ·-20))+3x·N N2(21·-x) =x·N (x ·-10)+2x·N (N2(11·-x)+ N2(x ·-20))+3x·N (21·-x) .. 习 题 5.1 写出下列函数的特征函数。 (1)a 大于或等于b。 (2)a 为b、c 的公倍数。 (3)x 异于0且x 为平方数。 (4)a 为非负数或a 为奇数。 (5)在a、b 间的一切x 均使得A(x)成立。 (6)在a、b 间有一个x 使得A(x)成立。 5.2 把下列函数化为标准迭置。 (1)h(x1,x2,x3,x5)=f(g1(x1,x3,3),a,g2(x2,x3),x5)(其中a 为正整数) (2)h(x1,x2,x3,x4)=f(x1,3,g1(x2,x3),g2(x4,2)) 5.3 用凑合定义法定义函数dv(x,5),并把它化为迭置。 5.4 证明下列函数为原始递归函数。 (1)xy (2)rs(x,2) (3)O(x) (4)min(x,y) (5)x ·-·y (6)Πx→n f(x)