1、目录（数理逻辑）数理逻辑）第一章第一章 命题演算基础命题演算基础（6学时）学时）第二章第二章 命题演算的推理理论（命题演算的推理理论（4学时学时）第三章第三章 谓词演算基础（谓词演算基础（5学时）学时）第四章第四章 谓词演算的推理理论（谓词演算的推理理论（5学时）学时）第五章第五章 递归函数论（递归函数论（4学时）学时）递归函数递归函数可计算性理论可计算性理论递归函数递归函数数论函数数论函数，是以自然数为研究对，是以自然数为研究对象，定义域和值域均为自然数。象，定义域和值域均为自然数。它为可计算函数找出各种理论上的、严密的类它为可计算函数找出各种理论上的、严密的类比物，因此，递归函数又称为比物
2、，因此，递归函数又称为可计算性理论可计算性理论。可计算性理论的研究对象u判定问题判定问题判定方程是否有解判定方程是否有解u可计算函数可计算函数讨论一个函数是否可计算，建讨论一个函数是否可计算，建立了原始递归函数、图灵机等许多数学模型判立了原始递归函数、图灵机等许多数学模型判定一个函数是否属于可计算函数定一个函数是否属于可计算函数u计算复杂性计算复杂性讨论讨论NP=P?问题，即非确定型问题，即非确定型多项式（多项式（Nondeterministic Polynomial）可解问）可解问题是否存在时间和空间复杂度是多项式的有效题是否存在时间和空间复杂度是多项式的有效算法算法可计算性理论的计算模型1
3、)Turing机2)递归函数3)演算4)POST系统5)正则算法可计算函数、不可计算函数可计算函数、不可计算函数例例1nng)(否则个连续的的展式中有 18 0)(nng表示取自然数表示取自然数n的平方根的整数部分。的平方根的整数部分。将将n依次与依次与12，22，作比较总可求得作比较总可求得g(n)的值，所的值，所以以g(n)是是可计算可计算的。的。因为因为的展式是一个无穷序列，要计算上述函数可的展式是一个无穷序列，要计算上述函数可能是一个无限过程。故函数能是一个无限过程。故函数为为不可计算不可计算函数。函数。例例2第五章 递归函数论5.1 数论函数和数论谓词数论函数和数论谓词 5.1.1
4、数论函数数论函数 5.1.2 数论谓词和特征函数数论谓词和特征函数5.2 函数的构造函数的构造 数论函数数论函数定义：数论函数是指以自然数集为定义域及值域的定义：数论函数是指以自然数集为定义域及值域的函数。函数。常用的数论函数（其中常用的数论函数（其中x，y均为自然数域中的变元）：均为自然数域中的变元）：x+y 指指x与与y的和的和.xy 指指x与与y的积的积.指指x与与y的算术差的算术差,即即x y时时,其值为其值为x减减y,否则为否则为0.指指x与与y的绝对差的绝对差,即大数减小数即大数减小数.x .yx .y常用的数论函数常用的数论函数 x/yx/y rs(x,yrs(x,y)dv(x,
5、ydv(x,y)lm(x,ylm(x,y)x指指x的平方根的整数部分。的平方根的整数部分。指指x与与y的算术商。的算术商。指指y 除除x的余数，约定的余数，约定y=0时，时，rs(x,0)=x。指指x与与y的最大公约数的最大公约数,约定约定xy=0时时,其值为其值为x+y。指指x与与y的最小公倍数的最小公倍数,约定约定xy=0时时,其值为其值为0。常用的数论函数常用的数论函数 I(xI(x)函数值与自变量的值相同，称为幺函数。函数值与自变量的值相同，称为幺函数。I Imnmn(x(x1 1，,x xn n，x xm m)=)=x xn n,即函数值与第即函数值与第n n个自变个自变元的值相同，
6、此函数称为元的值相同，此函数称为广义幺函数广义幺函数。O(xO(x)=0)=0即函数值永为即函数值永为0 0，称为，称为零函数零函数。S(xS(x)=x+1)=x+1，此函数为，此函数为后继函数后继函数。特别地，把广义幺函数、零函数和后继函数称特别地，把广义幺函数、零函数和后继函数称为为本原函数本原函数，它们是构造函数的最基本单位。，它们是构造函数的最基本单位。常用的数论函数常用的数论函数 D(x)指指x的前驱，称为前驱函数。的前驱，称为前驱函数。当当x=0时，其值为时，其值为0，x0 时，其值为时，其值为 x-1。Ca(x)=a，即函数值永为，即函数值永为a，这个函数称为常值，这个函数称为常
7、值函数。函数。常用的数论函数常用的数论函数 0001yyNy当当01002yyyN当当N(Ny)=N2y N3y=NyNy+N2y=1第五章 递归函数论5.1 数论函数和数论谓词数论函数和数论谓词 5.1.1 数论函数数论函数 5.1.2 数论谓词和特征函数数论谓词和特征函数5.2 函数的构造函数的构造一、数论谓词和特征函数一、数论谓词和特征函数定义：定义：数论谓词数论谓词是指以自然数集为定义域以真假为是指以自然数集为定义域以真假为值域的谓词。值域的谓词。定义：定义：由数论谓词利用联结词和量词构成的式子称由数论谓词利用联结词和量词构成的式子称为为数论语句数论语句。数论语句例子数论语句例子u2为
8、质数为质数u87且且9为平方数为平方数u x为质数为质数ux7且且y为平方数为平方数特征函数定义：设定义：设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)的的特征特征函数函数，记为记为 ct A(x1，x2，xn)。定理1(p55)任何一个语句任何一个语句A 均有唯一的特征函数均有唯一的特征函数证明：证明：(1)
9、存在性存在性：对于任何一个语句：对于任何一个语句A，恒可以如上定义一个函数，恒可以如上定义一个函数f(x1，xn)，此函数必为语句，此函数必为语句A的特征函数，故的特征函数，故存在性得证。存在性得证。(2)唯一性唯一性：设：设f 和和g为语句为语句A的两个特征函数，由上定义知：的两个特征函数，由上定义知：当当A(x1，xn)为真时为真时,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)如果有一
10、函数如果有一函数f(x1，xn)满足下列条件：满足下列条件：A(x1，xn)为真当且仅当为真当且仅当f(x1，xn)=0则则N2 f(x1，xn)为语句为语句A 的特征函数。的特征函数。此时此时,把函数把函数f(x1，xn)称为称为准特征函数准特征函数。定理2(p55)如果有一函数如果有一函数f(x1，xn)满足下列条件：满足下列条件：A(x1，xn)为真当且仅当为真当且仅当f(x1，xn)=0 则则,N2 f(x1，xn)为语句为语句A 的特征函数。的特征函数。证明：证明：当当A(x1，xn)真时，由于真时，由于f(x1，xn)=0，所以所以 N2 f(x1，xn)=0；当当A(x1，xn)
11、假时，由已知条件知：假时，由已知条件知：f(x1，xn)0，所以，所以N2 f(x1，xn)=1由特征函数的定义知：由特征函数的定义知：N2 f(x1，xn)为语句为语句A(x1，xn)的特征函数。的特征函数。二、简单语句的特征函数 语句语句 特征函数特征函数 x 0 N x x=0 N2 x x为为y的倍数的倍数 N2 rs(x，y)x y x y N2(x .y)N2(x+1).y)二、简单语句的特征函数 语句语句 特征函数特征函数 x=0 N2 x x0 N x x=a xa x与与y互质互质N2(dv(x,y).1)N2(x.a)N(x.a)三、复合语句的特征函数定理定理1：设：设A，
12、B为任意两个语句，则有为任意两个语句，则有u ct A=1 ctA=NctAu ct(A B)=ctA ctB=min(ctA，ctB)u ct(A B)=N2(ctA+ctB)=max(ctA，ctB)u ct(AB)=ctB NctAu ct(AB)=ctA ctB例1(p56)x异于异于0且且x为平方数为平方数解：记解：记A:x异于异于0.A的特征函数为的特征函数为 Nx.记记B:x为平方数为平方数,并记并记 B为真时为真时,y=0,B的特征函数为的特征函数为 N2y.由定理由定理1知知,A B 的特征函数为：的特征函数为：max(Nx,N2y)=N2(Nx+N2y)y=x .x 2例2
13、(p56)x 2且由且由a除尽除尽x可推出可推出a=1或或a=x 解：令解：令A表示表示“x 2”，其特征函数为，其特征函数为N2(2 x)B表示表示“a除尽除尽x”，其特征函数为，其特征函数为N2rs(x，a)C表示表示“a=1”，其特征函数为，其特征函数为N2(a 1)D表示表示“a=x”，其特征函数为，其特征函数为N2(a x)原句翻译为公式：原句翻译为公式：A(B(C D)其特征函数为：其特征函数为：ct(A(B(C D)=N2(ctA+ctC ctD NctB)于是原句的特征函数为：于是原句的特征函数为：N2(N2(2 x)+N2(a 1)N2(a x)Nrs(x，a)即即 max(
14、N2(2 x),N2(a 1)N2(a x)Nrs(x，a)受限全称量词、受限存在量词)(xAnx)(xAnx表示对于任何表示对于任何0到到n之间的一切之间的一切x均使得均使得A(x)成立。成立。此量词称为此量词称为受限全称量词受限全称量词。表示对于任何表示对于任何0到到n之间至少有一个之间至少有一个x使得使得A(x)成成立。此量词称为立。此量词称为受限存在量词受限存在量词。)()1()0()(,),1(),0(max)(2nctActActANnctActActAxActnx定理：设定理：设A(x)为任意一个含有为任意一个含有x的语句，则有的语句，则有)()1()0()(,),1(),0(min)(nctActActAnctActActAxActnx第五章 递归函数论5.1 数论函数和数论谓词数论函数和数论谓词 5.1.1 数论函数数论函数 5.1.2 数论谓词和特征函数数论谓词和特征函数5.2 函数的构造函数的构造
