↖  电脑前传(3):逻辑-2..


-loading- -loading- -loading-

2020-07-01 , 864 , 0 , 138

听音频 🔊 . 看视频 🎦

逻辑主义

布尔把普通代数作为出发点,用代数符号表示逻辑关系。

弗里德里希·弗雷格(Friedrich Frege, 1848—1925)反其道而用之,主张从逻辑学推导出全部数学,开创了逻辑主义。

1879年,弗雷格出版《概念文字——一种模仿算术语言构造的纯思维的形式语言》[4],明确规定了命题符号中的规范形式,明确了所有的演算推理规则,创造了自己的特殊符号来表示逻辑关系,并把这些关系作为逻辑的基础,后来这一思想也为现代逻辑继承[5]。


在这个体系中,命题变元通常使用字母表示,常用逻辑关系如下:


其中,~和→为基本关系,可以推导出其他逻辑关系。

也因此,逻辑电路只要有非门(对应~),加上电路连接(对应→),就可以实现各种逻辑关系,1938年克劳德·艾尔伍德·香农提出开关电路理论,利用开关这一种物理装置(实际上还有连线)就能组合出与、或、非以及更复杂的逻辑,在数理逻辑和物理实现之间架起了桥梁。


相对于布尔逻辑,弗雷格最重要的变化是引进了对变元进行限定的量词,最基本的是全称量词∀,另外一个常用量词是存在量词∃。

基于这套符号体系,弗雷格提出了把普通数学中的一切演绎推理都包含在内的第一个完备的逻辑体系,后来称为一阶逻辑,因为量词控制的只是变元的个体,而不是变元的集合以及变元之间的关系,否则就是后来的二阶或高阶逻辑了。


弗雷格的符号逻辑体系为所有计算机程序设计语言奠定了基础,但当初弗雷格的雄心是为整个数学奠定可靠基础。

19世纪末,数学家们采用公理化方法,已经把几何和微积分建构在实数理论基础上,进而又把实数理论建构在自然数基础上。

因此,从逻辑推导出数学的问题,就转换成如何从逻辑推导出自然数系统。


1889年,意大利数学家朱塞佩·皮亚诺(Giuseppe Peano, 1858—1932)提出关于自然数的五条公理,建立起了关于自然数的皮亚诺算术系统(PA)。

为了用《概念文字》提出的逻辑发展出自然数系统,弗雷格找到了集合论:基数相同的所有集合组成的集合定义了基数对应的那个自然数。

基于这一定义,1893年,弗雷格出版《算术的基本规律》第一卷,阐述了推导出自然数的方法,并继续撰写第二卷,争取为数学奠定可靠的逻辑基础。


1900年国际数学家大会上,法国数学家庞加莱兴高采烈地宣称:“借助集合论的概念,我们可以建造起整个数学大厦……今天,我们可以说,绝对的严格性已经达到了。”

数学领袖戴维·希尔伯特(David Hilbert,1862—1943)谨慎乐观,他在会上提出23个问题,2号问题就是算术公理系统的无矛盾性(即一致性):

“在这些无数个问题之上,我倾向于确定下面这个问题才是最重要的:这些公理经过有限步骤推演后不会导致相互矛盾的结论……也就是说,我们需要一个关于算术公理一致性的证明。”

-loading- -loading--loading-



很快希尔伯特的担心变为现实。1902年6月,在《算术的基本规律》第二卷付梓之际,弗雷格收到了伯特兰·罗素(Bertrand Arthur William Russell, 1872—1970)的来信。

UfqiLong

罗素表示“我在您的著作中找到了在其他逻辑学家的著作中不曾有过的探讨、区分和定义”,但是,“我只在一个地方碰到了困难。”


弗雷格的算术使用了集合的集合,罗素从中发现了悖论。如果一个集合是它自身的一个元素,则称之为异常的,否则是正常的。

罗素指出,所有正常集合组成的集合是正常的还是异常的?很容易检查发现,无论哪种选择都自相矛盾。弗雷格马上明白了,他匆忙在第二卷增加了一个补遗:“正当工作就要完成之时,发现那大厦的基础已经动摇。

对于一个科学工作者来说,没有什么比这更为不幸的了。伯特兰·罗素的一封信使我置身于这样的境地”。


数学大厦将倾,“捅出娄子”的罗素试图重新奠基,这就是他和怀特海合著的《数学原理》[6],三卷相继于1910年、1912年和1913年出版。

这部2000多页的巨著引言只陈述了一个目标,那就是“完整地列出数学推理的所有方法和步骤”,这就是逻辑主义的纲领。


《数学原理》继承了弗雷格的思想和逻辑符号,为了规避悖论,采用了一种精心设计的、使用起来很不方便的分层结构(类型论)。

第一步是推出“数”来,过程极其繁琐费力,直到第一卷363页,才成功地用类推演出“1”,第二卷费了很大力气证明了乘法交换律。

《数学原理》前三卷覆盖了集合、基数、序数和实数的相关内容,虽然对第四卷几何的基础做了筹划,但整个体系实在太过复杂,十年辛苦不寻常,两位作者再也写不下去了。

罗素曾回忆,痛苦在1903和1904年夏天达到高峰,那段日子里,除午饭外,整天就对着白纸枯坐,往往一个字也写不出,这让罗素甚至产生悲观厌世的想法。


图书出版后,罗素迎来了更大的打击,特别是作为前提的可化归性公理遭到了猛烈批评,罗素自己也认为有问题,但是放弃这条公理,很多部分——比如有关实数的部分——就会失去依托。

更大的问题在于这种机械式的罗列背离了数学的根本之美。1958年,王浩在IBM 704 计算机上仅用几分钟时间就证明了《数学原理》的数百条定理。

1954年至1963年,赫伯特·西蒙(司马贺)等的启发式程序“逻辑理论家”证明了《数学原理》第二章全部52个定理。

他们把这个结果通知罗素,据说罗素回复说:“得知《数学原理》现在可以采用机械方式完成,我很高兴。要是我和怀特海早知道能这么做,就不用浪费10年的时间来手工完成了。”当然,这已经是半个世纪以后的劫后余波了。


希尔伯特纲领

为数学奠定牢固的基础,没有谁比数学界领袖希尔伯特更上心。希尔伯特关于数学基础的思考统称为希尔伯特纲领,经历了20年左右的时间逐步成熟[7],

主要体现在1904年海德堡第三届国际数学家大会上的“论逻辑和算术的基础”报告,1917年发表的《公理化思维》,1922年在汉堡的“数学的新基础”讲演和在莱比锡德国自然科学家大会上的《数学的基础》演讲。


-loading- -loading--loading-


UfqiLong

希尔伯特提出,为了消除对数学可靠性的怀疑,避免出现悖论,就要设法绝对地证明数学的一致性,使数学奠定在严格的公理化基础上。

由此,希尔伯特想到,彻底抛弃公理体系中的含义,构造一个纯粹形式化的公理体系,这个体系内的各种表达式仅仅具有符号意义。

如果能证明这种公理体系的一致性,那么把任何含义赋予这个公理体系时,都必然是无矛盾的、一致的。


希尔伯特认为,有三种数学理论[1, 8]:

(1) 直观的非形式化的数学理论;

(2) 把第一种数学理论形式化,构成形式系统。形式系统包含逻辑演算,直观数学理论中的基本概念转换为形式系统中的初始符号,命题转换为符号公式,推演规则转换为符合公式之间的形式变换,证明转换为符号公式的有穷序列;

(3) 描述和研究第二种数学理论的数学,称为元数学或证明论。希尔伯特希望,一致性证明将在元数学内部完成,数学和逻辑则将以一种纯形式的符号语言被发展出来。


布劳威尔(Luitzen Egbertus Jan Brouwer,1881—1966)对希尔伯特纲领嗤之以鼻,希尔伯特的得意门生赫尔曼·外尔也心存疑虑[1]。

布劳威尔认为,数学存在于数学家的直觉,最终根源是时间这个“数学的原初直观”,而不是什么形式化表达,为数学寻找一个僵化的形式基础,从根本上就是错误的。外尔认为康托和戴德金等人处理极限的过程“建立在沙滩之上”,对自己重建连续统的努力也不满意,对布劳威尔的直觉主义一见倾心,宣称“布劳威尔……这就是革命。”

无论如何,外尔最终还是继承了希尔伯特的衣钵,这是后话。


1928年,希尔伯特和学生阿克曼出版了一册120页的逻辑课本《数理逻辑原理》。

这是他1917年冬在哥廷根开设的课程基础上完成的,基本思路是从《数学原理》的逻辑系统开始,先分解成一个个扩展的子集,分别进行单独研究。

这本书提出了两个关于弗雷格逻辑(即一阶逻辑)的问题。

第一个问题是证明一阶逻辑的完备性,即任何一个从外部看来有效的公式都可以只用课本中提出的规则从系统内部导出。第二个问题就是著名的判定问题。

进而,如果一阶逻辑是完备的,希尔伯特还希望证明,把一阶逻辑应用于皮亚诺自然数公理系统算术(PA)也是完备的,即任何一个在PA中表达的命题,或者可以在PA中被证明为真,或者可以在PA中被证明为假。


1930年希尔伯特退休,应邀在柯尼斯堡发表主题为“自然科学与逻辑”的演讲,他再次重申了完备性证明和判定问题证明的梦想,并喊出了“我们必须知道,我们必将知道”的口号。

但就在前一天,同样在柯尼斯堡,在一场数学基础研讨会上,24岁的库尔特·哥德尔(Kurt Gödel, 1906—1978)对完备性问题给出了否定回答。6年后,24岁的图灵对判定问题给出了否定回答。



+逻辑 +数学 +公理 +证明 +基础

本页Url

↖回首页 +当前续 +尾续 +修订 +评论✍️


👍9 仁智互见 👎0
  • 还没有评论. → +评论
  • -loading- -loading- -loading-


    🔗 连载目录

    🤖 智能推荐

    我所了解的哈耶克思想

    人的行为 Human Action-12:先験和眞实

    市场的基础——浅谈米塞斯《人的行动》的意义

    理解计算:从根号2到AlphaGo -10:第5季 导数的前世今生

    人的行为 Human Action-81:逻辑的交换学对数学的交换学

    人的行为 Human Action-15:历史的范围和其特殊方法

    人的行为 Human Action-29:第5章 时间

    幸存者偏差——看不到的真相最致命-2 幸存者偏差——看不到的真相最致命-2

    美国OpenAi公司的人工智能聊天机器人ChatGPT能取代多少程序员?

    人的行为 Human Action-26:主张理知(reason)的理由

    -loading- -loading- -loading-


    🔥 相关精选

    人的行为 Human Action-10:第2章 行为科学的一些认识论的问题

    计算机机器能思考吗?——认知与真实

    极度聪明的天才人物-5:排名在前1%的高中生是靠天赋还是靠努力?-2 极度聪明的天才人物-5:排名在前1%的高中生是靠天赋还是靠努力?-2

    日常常見的論證逻辑陷阱-2

    编程随想:学习与人生:700篇博文之感悟-2

    一本线能上清华、无需高考读北大,大学招生逻辑在变化 23

    《美丽境界》爱情没有证据证明,只是相信而已 10

    院士专家追忆“一个时代的精神符号” 1

    靳东又惹争议了,这事也证明:5种乱象,正在谍战剧圈里野蛮生长 1

    数学家计划计算机证明费马大定理 0

    -loading- -loading- -loading-

     


    + 安安 安安
    AddToFav   
    新闻 经典 官宣