目录数理逻辑.ppt

《目录数理逻辑.ppt》由会员分享，可在线阅读，更多相关《目录数理逻辑.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目录数理逻辑 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望什么是计算什么是计算？l首先指的就是数的加减乘除；首先指的就是数的加减乘除；l其次则为方程的求解、函数的微分积分等；其次则为方程的求解、函数的微分积分等；l计算在本质上还包括定理的证明推导。计算在本质上还包括定理的证明推导。l可以说，可以说，“计算计算”是一个无人不知无人不晓是一个无人不知无人不晓的数学概念的数学概念。什么是计算什么是计算？从符号串从符号串12+3变换成变换成15就是一个加法计算。就是一个

2、加法计算。如果符号串如果符号串f是是x2，而符号串，而符号串g是是2x,从从f到到g的计算就的计算就是微分。是微分。令令f表示一组公理和推导规则，令表示一组公理和推导规则，令g是一个定理是一个定理,那么那么从从f到到g的一系列变换就是定理的一系列变换就是定理g的证明。的证明。如如f代表一个英文句子，而代表一个英文句子，而g为含意相同的中文句子，为含意相同的中文句子，那么从那么从f到到g就是把英文翻译成中文。就是把英文翻译成中文。从己知符号从己知符号(串串)开始，一步一步地改变符开始，一步一步地改变符号号(串串)，经过有限步骤，最后得到一个，经过有限步骤，最后得到一个满足预先规定的符号满足预先规

3、定的符号(串串)的变换。的变换。可计算函数？可计算函数？例例1例例2可计算性理论的计算模型1)递归函数递归函数2)Turing机机3)演算演算4)POST系统系统丘奇丘奇-图灵论点：图灵论点：凡是可计算的函数都是一般递凡是可计算的函数都是一般递归函数归函数(或是图灵机可计算函数等或是图灵机可计算函数等)20世纪世纪30-40年代年代递归函数论递归函数论可计算性理论可计算性理论递归函数递归函数数论函数，定义域和值域均为自数论函数，定义域和值域均为自然数。然数。递归函数论递归函数论为为能行能行可计算函数可计算函数找出各种理找出各种理论上的、严密的类比物。论上的、严密的类比物。有效？有效？可计算性理

4、论的研究对象u可计算函数可计算函数讨论一个函数是否可计算，讨论一个函数是否可计算，建立了原始递归函数、图灵机等许多数学模建立了原始递归函数、图灵机等许多数学模型，判定一个函数是否属于可计算函数。型，判定一个函数是否属于可计算函数。u判定问题判定问题判定方程是否有解。判定方程是否有解。u计算复杂性计算复杂性讨论讨论NP=P?问题，即非确定问题，即非确定型多项式（型多项式（Nondeterministic Polynomial）可解问题：是否存在时间和空间复杂度是多可解问题：是否存在时间和空间复杂度是多项式的有效算法。项式的有效算法。第五章 递归函数论5.1 数论函数和数论谓词数论函数和数论谓词

5、5.1.1 数论函数数论函数 5.1.2 数论谓词和特征函数数论谓词和特征函数5.2 函数的构造函数的构造 数论函数数论函数定义：数论函数是指以自然数集为定义域及定义：数论函数是指以自然数集为定义域及值域的函数。值域的函数。x+y 指指x与与y的和的和.xy 指指x与与y的积的积.指指x与与y的算术差的算术差,即即x y时时,其值为其值为x减减y,否则为否则为0.指指x与与y的绝对差的绝对差,即大数减小数即大数减小数.常用的数论函数常用的数论函数其中其中x，y均为自然数域中的变元。均为自然数域中的变元。x .yx .y常用的数论函数常用的数论函数 x/y x/y rs(x,y)rs(x,y)d

6、v(x,y)dv(x,y)lm(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)I(x)函数值与自变量的值相同，称为函数值与自变量的值相同，称为幺函数幺函数。I Imnmn(x(x1 1，,x,xn n，x xm m)=x)=xn n,即函数值与第即函数值与第n n个自变元个自变元的值相同，称为

7、的值相同，称为广义幺函数，广义幺函数，也称为也称为投影函数投影函数。O(x)=0O(x)=0即函数值永为即函数值永为0 0，称为，称为零函数零函数。S(x)=x+1S(x)=x+1，此函数为，此函数为后继函数后继函数。特别地，把广义幺函数、零函数和后继函数称特别地，把广义幺函数、零函数和后继函数称为为本原函数本原函数，它们是构造函数的最基本单位。，它们是构造函数的最基本单位。常用的数论函数常用的数论函数D(x)指指x的前驱，称为前驱函数。的前驱，称为前驱函数。当当x=0时，其值为时，其值为0，x0 时，其值为时，其值为 x-1。Ca(x)=a，即函数值永为，即函数值永为a，这个函数称为常值，这

8、个函数称为常值函数。函数。常用的数论函数常用的数论函数N(Ny)=N2y N3y=NyNy+N2y=1数论谓词、数论谓词、数论语句数论语句数论谓词数论谓词以自然数集为定义域以真假为以自然数集为定义域以真假为值域的谓词。值域的谓词。数论语句数论语句由数论谓词利用联结词和量词由数论谓词利用联结词和量词构成的公式。构成的公式。数论语句例子数论语句例子u2为质数为质数u87且且9为平方数为平方数u x为质数为质数ux7且且y为平方数为平方数特征函数设设A(x1，x2，xn)是一个含有是一个含有n个变量的语句，个变量的语句，f(x1，x2，xn)是一个数论函数，是一个数论函数，若对于任何变元组均有：若对

9、于任何变元组均有：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)任何一个语句均有唯一的特征函数。任何一个语句均有唯一的特征函数。证明：证明：(1)存在性存在性(略略)(2)唯一性唯一性(略略)定理2(p55)如果有一函数如果有一函数f(x1，xn)满足下列条件：满足下列条件：A(x1，xn)为真当且仅当为真当且仅当f(x1，xn)=0则则 N2 f(x1，xn)为语句为语句A 的特征函数。的特征函数。准

10、特征函数准特征函数二、简单语句的特征函数 语句语句 特征函数特征函数 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，B为任意两个语句，则有为任意两个语句，则有u ct A=1 ctA=NctAu ct(A B)=ctA ctB=min(ctA，ctB)u ct(A B)=N2(ctA+ctB)=max(ct

11、A，ctB)u ct(AB)=ctB NctAu ct(AB)=ctA ctB例1(p56)x异于异于0且且x为平方数为平方数解：记解：记A:x异于异于0.A的特征函数为的特征函数为:Nx 记记B:x为平方数为平方数,B的特征函数为的特征函数为:于是，于是，A B 的特征函数为：的特征函数为：例 a=1或或a=x 解：令解：令C表示表示“a=1”，D表示表示“a=x”，则则C的特征函数为的特征函数为N2(a 1)D的特征函数为的特征函数为N2(a x)于是于是C D的特征函数为：的特征函数为：ct(C D)=ctC ctD =N2(a 1)N2(a x)例 由由a除尽除尽x可推出可推出a=1或

12、或a=x 解：令解：令B表示表示“a除尽除尽x”，C表示表示“a=1”，D表示表示“a=x”，则则B的特征函数为的特征函数为N2rs(x，a)C的特征函数为的特征函数为N2(a 1)D的特征函数为的特征函数为N2(a x)于是于是B(C D)的特征函数为：的特征函数为：ct(B(C D)=ctC ctD NctB =N2(a 1)N2(a x)Nrs(x，a)例2(p56)x 2且且解：令解：令A表示表示“x 2”，其特征函数为，其特征函数为 N2(2 x)F表示表示“由由a除尽除尽x可推出可推出a=1或或a=x”其特征函数为：其特征函数为：ct(F)=N2(a 1)N2(a x)Nrs(x，

13、a)于是原句于是原句A F的的特征函数为：特征函数为：ct(A F)=max(ctA+ctF)=max(N2(2 x),N2(a 1)N2(a x)Nrs(x，a)N2(N2(2 x)+N2(a 1)N2(a x)Nrs(x，a)即即 例2 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)则原句的特征函数为：则原句的特征

14、函数为：ct(A(B(C D)=N2(ctA+ctC ctD NctB)=N2(N2(2 x)+N2(a 1)N2(a x)Nrs(x，a)=max(N2(2 x),N2(a 1)N2(a x)Nrs(x，a)受限全称量词、受限存在量词 表示对于任何表示对于任何0到到n之间的一切之间的一切x均使得均使得A(x)成立。成立。此量词称为此量词称为受限全称量词受限全称量词。表示对于任何表示对于任何0到到n之间至少有一个之间至少有一个x使得使得A(x)成成立。此量词称为立。此量词称为受限存在量词受限存在量词。定理定理2：设设A(x)为为任意一个含有任意一个含有x的的语语句，句，则则有有第五章 递归函数论5.1 数论函数和数论谓词数论函数和数论谓词 5.1.1 数论函数数论函数 5.1.2 数论谓词和特征函数数论谓词和特征函数5.2 函数的构造函数的构造