数学、逻辑与计算机科学的关系.doc

数学、逻辑与计算机科学的关系数学、逻辑是与计算机科学密不可分的。数学是基础材料，逻辑是支柱，计算机科学是大厦。首先，是数学与逻辑的关系。数学基础的讨论主要在19世纪末20世纪初，当时对数学的看法有许多流派，其中一派是逻辑主义学派，认为数学可以完全由逻辑得到。但后来数理逻辑中的一些深刻结果则否定了这种观点。事实上，数学不能完全由逻辑得到，即，如果要求数学是无矛盾的，那么，它就不可能是完备的。现在对数学看法的主流是源于Hilbert的形式主义数学的观点。粗略地说，就是公理化的观点。也就是说，人们可以从实际出发（也可以从空想出发），给出一组无矛盾、不多余的公理，这种公理系统下就形成一种数学。在建立公理以后的事情则属于逻辑。所以，逻辑是数学的重要方法和基础，但不是数学的全部。反过来，数学也不包括逻辑的全部。逻辑学主要是（至少曾经是）哲学的一支，它不仅研究逻辑命题的推演关系，也研究这种关系为什么是对的，等等。逻辑学中影响数学的主要是形式逻辑和数理逻辑，但涉及哲学思辨的部分就不在数学的范畴之中了。其次，是数学与计算机的关系。因为计算机是一种进行数值计算、逻辑推理、符号处理等方面信息加工的机器，有人就称它为数学的机器;近年由于计算机应用的拓广，其系统软件与应用软件发展很大，吸引了甚为巨大的社会人力与财力，形成了一种新兴的工业，人们认为这是继土木工程，机械工程、电子工程之后的一种新的工程软件工程。由于它具有数学的特征，即高度的精确性，广泛的应用性，与推理的严谨可靠性。因此，计算机科学被称程序为具有数学性质的学科。计算机科学是对计算机体系，软件和应用进行探索性、理论性研究的技术科学。由于计算机与数学有其特殊的关系，故计算机科学一直在不断地从数学的概念、方法和理论中吸取营养;反过来，计算机科学的发展也为数学研究提供新的问题、领域、方法和工具。近年来不少人讨论过数学与计算机科学的关系问题，都强调其间的密切联系。同时，人们也都承认，计算机科学仍有其自己的特性，它并非数学的一个分支，而有自身的独立性。正确说法应该是:由于计算机及程序的特殊性，计算机科学是与数学有特殊关系的一门新兴的技术科学。这种特殊关系使得计算机科学与数学之间有一公共的交界领域，它范围相当广，内容相当丰富，很富有生命力。这一领域既是理论计算机科学的一部分，也是应用数学的一部分。这里只准备若干主要方面说明一些基本事实，不讨论有关计算机的工程技术问题。再次，是逻辑与计算机科学的关系。计算机科学里的逻辑主要指的是数理逻辑。数理逻辑又称符号逻辑、理论逻辑。它既是数学的一个分支，也是逻辑学的一个分支。是用数学方法研究逻辑或形式逻辑的学科。其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。数理逻辑是数学基础的一个不可缺少的组成部分。虽然名称中有逻辑两字，但并不属于单纯逻辑学范畴。所谓数学方法就是指数学采用的一般方法，包括使用符号和公式，已有的数学成果和方法，特别是使用形式的公理方法。用数学的方法研究逻辑的系统思想一般追溯到莱布尼茨，他认为经典的传统逻辑必须数理逻辑改造和发展，是之更为精确和便于演算。后人基本是沿着莱布尼茨的思想进行工作的。简而言之，数理逻辑就是精确化、数学化的形式逻辑。它是现代计算机技术的基础。新的时代将是数学大发展的时代，而数理逻辑在其中将会起到很关键的作用。数理逻辑的主要分支包括：逻辑演算(包括命题演算和谓词演算)、模型论、证明论、递归论和公理化集合论。数理逻辑和计算机科学有许多重合之处，两者都属于模拟人类认知机理的科学。许多计算机科学的先驱者既是数学家、又是逻辑学家，如阿兰图灵、邱奇等。程序语言学、语义学的研究从模型论衍生而来，而程序验证则从模型论的模型检测衍生而来。柯里霍华德同构给出了“证明”和“程序”的等价性，这一结果与证明论有关，直觉逻辑和线性逻辑在此起了很大作用。演算和组合子逻辑这样的演算现在属于理想程序语言。计算机科学在自动验证和自动寻找证明等技巧方面的成果对逻辑研究做出了贡献，比如说自动定理证明和逻辑编程。当逻辑代数的逻辑状态多于2种时（如0、1、2或更多状态时），其通用模型的基本逻辑有2个。一个是从一种状态变为另一种状态的逻辑，是一个一元逻辑；另外一种是两种状态中按照某种规则（比如比较大小）有倾向性的选择出其中一种状态的逻辑，这是一个二元逻辑。依据这两种逻辑，可以表达任意多状态的任意逻辑关系，即最小表达式。即任意多状态的逻辑是完备的。当逻辑状态数扩展有理数量级甚至更多。任意数学运算都可以用两个运算关系来联合表达：