时间：2022-11-22 22:30:01 | 来源：信息时代
时间：2022-11-22 22:30:01 来源：信息时代
数理逻辑 : 一门研究数学基础性问题的数学,它为历史悠久的宏伟的数学大厦起奠基与支撑作用。
数理逻辑发展于19世纪,在其出现的初期,它的主要目标是研究数学推理的形式化,这形成了经典数理逻辑时代(或称传统数理逻辑时代),并在以后出现了命题逻辑,一阶谓词逻辑,以及高阶逻辑等多种分支。
到20世纪初由于数学发展而引发的众多基础性问题而促进了数理逻辑的发展并形成了四个分支,它们是: 公理集合论、模型论、证明论及递归论。
到了近期,在20世纪70年代后由于应用的促进,非经典逻辑得到了发展,它包括多值逻辑、模态逻辑、时态逻辑、非单调逻辑及模糊逻辑等。
由于数学基础问题也是其他众多学科的基础性问题,特别是新近兴起的计算机科学,迫切需要解决其发展中的基础问题。因此,数理逻辑同样作为计算机科学中的基础问题的研究工具而与其发生了紧密的关系,并且对计算机科学的发展起到了有力的奠基与推动作用。
在数据库的发展中,数理逻辑同样也起到了重要的作用。E.F.codd在1970年创立关系数据库时,首先利用了关系代数与关系演算作为数学模型以建立起关系数据库的基础理论,为关系数据库发展奠定了坚实的基础。在此中即应用了数理逻辑中的一阶谓词逻辑与集合论理论,在关系数据库标准语言SQL中还大量应用了谓词、量词、布尔表达式、集合运算等数理逻辑中的方法与理论。数理逻辑在数据模型研究中,除了在关系模型外,还在其他模型研究中,如谓词模型,函数模型中发挥作用。在此后的演绎数据库(deductive database)及知识库(knowledge base)研究中大量地采用了数据逻辑中的公理化思想与推理理论,并引入了证明论与模型论理论,为研究演绎数据库及知识库起到了强有力的推进作用。在时态数据库、模糊数据库等特种数据库研究中也采用非经典逻辑作为其理论工具。在目前,有关数据仓库、OLAP及数据挖掘中,均应用了归纳逻辑,模糊逻辑等多种逻辑思想与方法。
在早期的数理逻辑中是采用数学的方法研究演绎推理的规则,所谓数学方法主要指的是引入一套符号体系进而建立一种形式系统,因此,数理逻辑又称为符号逻辑。具体地说,形式系统的建立,包括符号、公式、有效公式、公理、推理规则、证明及定理等若干个过程与步骤,这种形式系统也可称为公理化系统。
(1)符号: 一个形式系统的基础是一组确定的,有限个数的符号。
(2)公式:根据一定的形成规则由符号所组成的有限长度的符号串称公式,也称形式语言。
(3)有效公式:形式系统中具有肯定性论断的公式称有效公式。
(4)公理: 形式系统中部分有效公式称为公理。
(5)推理规则:形式系统中具推理功能的规则称推理规则,推理规则是由某些公式作为前提而获得另一个公式作为结果的过程。
(6)公理系统: 由公理及推理规则组成公理系统。
(7)证明及定理:证明是有限个公式的序列,这种公式由下面几部分组成: ①公理是证明中公式;② 由序列前面公式中的若干个为前提,通过推理规则所得到的结果是证明中公式;③公式序列中的最后一个公式是定理。
(8)形式系统: 由公理系统、证明及定理构成一个形式系统,形式系统是一种纯语法的系统,它具有高度抽象性与理论性。
(9)形式系统的不矛盾性、独立性与完全性:形式系统是需要研究的,研究包括所建系统是否会出现矛盾,是否是最小的以及是否包含所有有效公式,这就是形式系统的不矛盾性、独立性与完全性。
形式系统的不矛盾性即表示在该系统中若A为定理,则A必不为定理,或者说在该系统中不可能存在A与A均为定理。
形式系统的独立性即表示在系统中没有多余的公理与推理规则,亦即是说只要去掉系统中任一公理或推理规则系统中的定理即会减少。
形式系统的完全性即表示系统的定理都是有效公式。
一般而言,形式系统的不矛盾性是极端重要的,因为一个矛盾的系统任何公式均可证明为有效,因此,也是无用的系统,而形式系统的完全性表示系统是否存在缺陷; 最后形式系统的独立性,追求的是形式上的完美,一个不具独立性的系统对整个系统的推理与完全性不受任何影响,因此,一个形式系统必须是不矛盾的同时希望是完全的但并不一定需要是独立的。
20世纪初数理逻辑形成了几种新的分支:
(1)公理集合论(axiom set theory): 在数学的各分支中其研究对象的概念、定义、定理与证明等均可用集合论形式表示,因此,集合论是数学研究中的公共基础; 而集合论的基础则是有关集合论的公理系统,称为公理集合论,因此,公理集合论是整个数学基础中的核心。G.Contor于19世纪末创立了集合论,B.Russell发现了集合论中的悖论,从而引发了对公理集合论的研究。E.Zermelo与A.Fraenkel建立了第一个集合论公理系统ZF系统,此后尚有P.Baruags和K.Godel所提出的著名的GB系统,这些公理系统都为排除集合论中悖论作出了贡献。
(2)模型论(model thoery):是研究形式系统与对它解释之间关系的一种理论。我们知道,形式系统是一种语法系统,它可以有多种语意上解释,研究它们之间的关系是模型论的研究目标。模型论研究起源于20世纪20年代,由T.Skolem等人奠定基础,并于50年代正式形成理论,其代表人物是A.Tarski及A.Robinson等人。
模型论的基本思想是: 一个形式语言的解释称为此语言的结构(也称模型),在模型论中形式语言一般采用一阶逻辑语言(或简称一阶语言),因此,也称一阶模型论。
一阶谓词模型论(以下简称为模型论)由三元组(L,∑,M)组成,三元组中L,∑,M的含义分别如下: L表示语言,即指定模型所采用的数学语言,亦即是一种基于一阶谓词的逻辑语言。它由一些常量、变量、函数、谓词等按一阶谓词逻辑公式定义的要求所构成。它的基本组成单元是句子。句子即是一阶谓词逻辑中的公式。如一句子中变量均呈约束状态,则称该句子为语句。L-语言为模型论理论提供了书写的语言。∑是用L-语言所写的一个句子集。一般讲,该句子呈语句状,∑刻画了所研究对象的普遍性规律。M是一个解释,称为结构或L-结构。在L中常量、函数、谓词均可赋值,变量可确定值域。因此,对L中常量、函数、谓词的一组赋值,变量的一种定义域指定叫L的一个解释,或叫一个结构。
L中可以有多个解释,但是人们最感兴趣的解释是使∑为真的那些解释。设∑={σ1,σ2,…,σn},其中σi为L的句子,如有解释M使σi为真,则该M是σi的一个模型,如有解释M使所有σi(i=1,2,…,n)为真,则该M是∑的一个模型,并可记为:M|=∑。模型论即是研究满足M|=∑的三元组(L,∑,M)的数学理论。
(3)证明论(proof theory): 是以数学证明作为研究对象的一种数学理论,它特别研究数学系统的不矛盾性及完全性。证明论出现于20世纪20年代,由D.Hilbert等人在研究了数论、集合论及数学分析等数学系统的不矛盾性而开始。30年代,K.Godel研究了数学系统的完全性而得到了著名的哥德尔不完全性定理,此后又得到了哥德尔第二不完全性定理。
众多的证明论研究表明: 虽然形式化方法是一种有效的方法,但是它过于抽象的语法化倾向,从而存在着严重的局限性与片面性。
(4)递归论(recurse theory): 是研究算法理论的一种数学,它主要研究算法的一般性规律以及数学中一类问题是存在算法介的问题,可称为判定问题,其详细介绍可参见算法、可计算性理论。
在线咨询
