数理逻辑与集合论发展

数理逻辑与集合论发展

本节通过数理逻辑发展史,了解有关的背景，加深对计算机学科的全面了解，特别是理论方面的了解，而不限于将计算机看成是一门技术或工程性的学科。通过重要的历史事件，了解计算机科学中的一些基本思维方式和一些基本问题。

数理逻辑的发展前期

• 前史时期——古典形式逻辑时期：亚里斯多德的直言三段论理论
• 初创时期——逻辑代数时期（17世纪末）
• • 资本主义生产力大发展，自然科学取得了长足的进步，数学在认识自然、发展技术方面起到了相当重要的作用。
  • 人们希望使用数学的方法来研究思维，把思维过程转换为数学的计算。
  • 莱布尼兹(Leibniz, 1646~1716)完善三段论，提出了建立数理逻辑或者说理性演算的思想：
  • • 提出将推理的正确性化归于计算，这种演算能使人们的推理不依赖于对推理过程中的命题的含义内容的思考，将推理的规则变为演算的规则。
    • 使用一种符号语言来代替自然语言对演算进行描述，将符号的形式和其含义分开。使得演算从很大程度上取决与符号的组合规律，而与其含义无关。
  • 布尔(G. Boole, 1815~1864)代数：将有关数学运算的研究的代数系统推广到逻辑领域，布尔代数既是一种代数系统，也是一种逻辑演算。

数理逻辑的奠基时期

• 弗雷格(G. Frege, 1848~1925)：《概念语言——一种按算术的公式语言构成的纯思维公式语言》(1879)的出版标志着数理逻辑的基础部分——命题演算和谓词演算的正式建立。
• 皮亚诺(Giuseppe Peano, 1858~1932)：《用一种新的方法陈述的算术原理》(1889)提出了自然数算术的一个公理系统。
• 罗素(Bertrand Russell,1872~1970)：《数学原理》(与怀特黑合著，1910, 1912, 1913)从命题演算和谓词演算开始，然后通过一元和二元命题函项定义了类和关系的概念，建立了抽象的类演算和关系演算。由此出发，在类型论的基础上用连续定义和证明的方式引出了数学（主要是算术）中的主要概念和定理。
• 逻辑演算的发展：甘岑(G. Gentzen)的自然推理系统(Natural Deduction System)，逻辑演算的元理论：公理的独立性、一致性、完全性等。
• 各种各样的非经典逻辑的发展：路易斯(Lewis,1883~1964)的模态逻辑，实质蕴涵怪论和严格蕴涵、相干逻辑等，卢卡西维茨的多值逻辑等。

集合论的发展

• 看待无穷集合的两种观点：实无穷与潜无穷

• 康托尔(G. Cantor, 1845~1918)：以实无穷的思想为指导，建立了朴素集合论

• • 外延原则（集合由它的元素决定）和概括原则（每一性质产生一集合）。

  • 可数集和不可数集，确定无穷集合的本质在于集合本身能与其子集一一对应。能与正整数集合对应的集合是可数的，否则是不可数的。证明了有理数集是可数的，使用对角线法证明了实数集合是不可数的。

• 超穷基数和超穷序数

• 朴素集合论的悖论：罗素悖论

• 公理集合论的建立：ZFC系统

第三次数学危机与逻辑主义、直觉主义与形式主义

• 集合论的悖论使得人们觉得数学产生了第三次危机，提出了数学的基础到底是什么这样的问题。
• 罗素等的逻辑主义：数学的基础是逻辑，倡导一切数学可从逻辑符号推出，《数学原理》一书是他们这一思想的体现。为解决悖论产生了逻辑类型论。
• 布劳维尔(Brouwer, 1881~1966)的直觉主义：数学是心灵的构造，只承认可构造的数学，强调构造的能行性，与计算机科学有重要的联系。坚持潜无穷，强调排中律不能用于无穷集合。海丁(Heyting)的直觉主义逻辑。
• 希尔伯特(D. Hilbert)的形式主义：公理化方法与形式化方法，元数学和证明论，提倡将逻辑演算和数学证明本身形式化，把用普通的语言传达的内容上的数学科学变为用数学符号和逻辑符号按一定法则排列的一堆公式。为了消除悖论，要数学建立在公理化基础上，将各门数学形式化，构成形式系统，并证明其一致性，这是希尔伯特的数学纲领。

数理逻辑的发展初期

• 哥德尔(Godel, 1906~1978)不完全性定理：一个足够强大的形式系统，如果是一致的则不是完全的，即有的判断在其中是不可证的，既不能断定其为假，也不能证明其为真。
• 各种计算模型：哥德尔的递归函数理论，邱吉尔的l演算，图灵机模型
• 这些计算模型是计算机科学的理论基础，是计算机的理论模型。

参考资料

[1] Discrete mathematics From Wikipedia, the free encyclopedia

[2] Discrete mathematics at the utk.edu Mathematics Archives, providiing links to syllabi, tutorials, programs, etc.

[3] Weisstein, Eric W., "Discrete mathematics", MathWorld.
[4]  Biggs, Norman L. (2002), Discrete mathematics, Oxford Science Publications (2nd ed.), New York: The Clarendon Press Oxford University Press, p. 89, ISBN 9780198507178, MR 1078626, Discrete Mathematics is the branch of Mathematics in which we deal with questions involving finite or countably infinite sets.

[5]ANew Kind of Science. Wolfram, S. Champaign, IL: Wolfram Media, 2002.

6] Weisstein, E. W. "Books about Discrete Mathematics." .html.

关于Discrete Mathematics更多讨论与交流，敬请关注本博客和新浪微博songzi_tea.