离散数学第五章--递归函数论-数论函数和数论谓词.ppt

《离散数学第五章--递归函数论-数论函数和数论谓词.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、目录（数理逻辑）第一章命题演算基础（6学时）第二章命题演算的推理理论（4学时）第三章谓词演算基础（5学时）第四章谓词演算的推理理论（5学时）第五章递归函数论（4学时）递归函数——可计算性理论递归函数——数论函数，是以自然数为研究对象，定义域和值域均为自然数。它为可计算函数找出各种理论上的、严密的类比物，因此，递归函数又称为可计算性理论。可计算性理论的研究对象判定问题——判定方程是否有解可计算函数——讨论一个函数是否可计算，建立了原始递归函数、图灵机等许多数学模型判定一个函数是否属于可计算函数计算复杂性——讨论NP=P?问题，即非确定型多项式（NondeterministicPolynom

2、ial）可解问题是否存在时间和空间复杂度是多项式的有效算法可计算性理论的计算模型Turing机递归函数λ演算POST系统正则算法可计算函数、不可计算函数例1表示取自然数n的平方根的整数部分。将n依次与12，22，…作比较总可求得g(n)的值，所以g(n)是可计算的。因为π的展式是一个无穷序列，要计算上述函数可能是一个无限过程。故函数为不可计算函数。例2第五章递归函数论5.1数论函数和数论谓词5.1.1数论函数5.1.2数论谓词和特征函数5.2函数的构造数论函数定义：数论函数是指以自然数集为定义域及值域的函数。常用的数论函数（其中x，y均为自然数域中的变元）：x+y指x与y的和.xy指x与

3、y的积.指x与y的算术差,即xy时,其值为x减y,否则为0.指x与y的绝对差,即大数减小数.x.yx..y常用的数论函数[][x/y]rs(x,y)dv(x,y)lm(x,y)指x的平方根的整数部分。指x与y的算术商。指y除x的余数，约定y=0时，rs(x,0)=x。指x与y的最大公约数,约定xy=0时,其值为x+y。指x与y的最小公倍数,约定xy=0时,其值为0。常用的数论函数I(x)函数值与自变量的值相同，称为幺函数。Imn(x1，…,xn，…，xm)=xn,即函数值与第n个自变元的值相同，此函数称为广义幺函数。O(x)=0即函数值永为0，称为零函数。S(x)=x+1，此函数为后继

4、函数。特别地，把广义幺函数、零函数和后继函数称为本原函数，它们是构造函数的最基本单位。常用的数论函数D(x)指x的前驱，称为前驱函数。当x=0时，其值为0，x>0时，其值为x-1。Ca(x)=a，即函数值永为a，这个函数称为常值函数。常用的数论函数N(Ny)=N2yN3y=NyNy+N2y=1第五章递归函数论5.1数论函数和数论谓词5.1.1数论函数5.1.2数论谓词和特征函数5.2函数的构造一、数论谓词和特征函数定义：数论谓词是指以自然数集为定义域以真假为值域的谓词。定义：由数论谓词利用联结词和量词构成的式子称为数论语句。数论语句例子2为质数8>7且9为平方数x为质数x>7且y为平方数

5、特征函数定义：设A(x1，x2，…，xn)是一个含有n个变量的语句，f(x1，x2，…，xn)是一个数论函数，若对于任何变元组均有：A(x1，…，xn)为真时，f(x1，…，xn)=0；A(x1，…，xn)为假时，f(x1，…，xn)=1。则f(x1，…，xn)是语句A(x1，…，xn)的特征函数，记为ctA(x1，x2，…，xn)。定理1(p55)任何一个语句A均有唯一的特征函数证明：(1)存在性：对于任何一个语句A，恒可以如上定义一个函数f(x1，…，xn)，此函数必为语句A的特征函数，故存在性得证。(2)唯一性：设f和g为语句A的两个特征函数，由上定义知：当A(x1，…，xn)为真

6、时,f(x1，…，xn)=g(x1，…，xn)=0当A(x1，…，xn)为假时,f(x1，…，xn)=g(x1，…，xn)=1再由函数的相等性知，f(x1,…,xn)=g(x1,…,xn)，即语句A特征函数是唯一的。定理2(p55)如果有一函数f(x1，…，xn)满足下列条件：A(x1，…，xn)为真当且仅当f(x1，…，xn)=0则N2f(x1，…，xn)为语句A的特征函数。此时,把函数f(x1，…，xn)称为准特征函数。定理2(p55)如果有一函数f(x1，…，xn)满足下列条件：A(x1，…，xn)为真当且仅当f(x1，…，xn)=0则,N2f(x1，…，xn)为语句A的特征函数。

7、证明：当A(x1，…，xn)真时，由于f(x1，…，xn)=0，所以N2f(x1，…，xn)=0；当A(x1，…，xn)假时，由已知条件知：f(x1，…，xn)0，所以N2f(x1，…，xn)=1由特征函数的定义知：N2f(x1，…，xn)为语句A(x1，…，xn)的特征函数。二、简单语句的特征函数语句特征函数x≠0Nxx=0N2xx为y的倍数N2rs(x，y)x≤yx＜yN2(x.y)N2((x+1).y)二、简单语句的特征函数