文档介绍：目录(数理逻辑)第一章命题演算基础(6学时)第二章命题演算的推理理论(4学时)第三章谓词演算基础(5学时)第四章谓词演算的推理理论(5学时)第五章递归函数论(4学时)递归函数——可计算性理论递归函数——数论函数,是以自然数为研究对象,定义域和值域均为自然数。它为可计算函数找出各种理论上的、严密的类比物,因此,递归函数又称为可计算性理论。可计算性理论的研究对象判定问题——判定方程是否有解可计算函数——讨论一个函数是否可计算,建立了原始递归函数、图灵机等许多数学模型判定一个函数是否属于可计算函数计算复杂性——讨论NP=P?问题,即非确定型多项式(NondeterministicPolynomial)可解问题是否存在时间和空间复杂度是多项式的有效算法可计算性理论的计算模型Turing机递归函数λ演算POST系统正则算法可计算函数、不可计算函数例1表示取自然数n的平方根的整数部分。将n依次与12,22,…作比较总可求得g(n)的值,所以g(n)是可计算的。因为π的展式是一个无穷序列,要计算上述函数可能是一个无限过程。故函数为不可计算函数。:数论函数是指以自然数集为定义域及值域的函数。常用的数论函数(其中x,y均为自然数域中的变元):x+,即xy时,其值为x减y,,..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,此函数为后继函数。特别地,把广义幺函数、零函数和后继函数称为本原函数,它们是构造函数的最基本单位。常用的数论函数D(x)指x的前驱,称为前驱函数。当x=0时,其值为0,x>0时,其值为x-1。Ca(x)=a,即函数值永为a,这个函数称为常值函数。