《数学机械化的观点课件》由会员分享,可在线阅读,更多相关《数学机械化的观点课件(35页珍藏版)》请在金锄头文库上搜索。
1、从吴文俊和吴方法谈起从吴文俊和吴方法谈起 数学机械化的观点数学机械化的观点 数学文化课程组 李军1 吴文俊吴文俊吴文俊吴文俊 中国科学院院士中国科学院院士 第三世界科学院院士第三世界科学院院士 首届国家最高科技奖首届国家最高科技奖 国家第一届自然科学奖国家第一届自然科学奖 最高奖一等奖最高奖一等奖 自动推理的最高奖自动推理的最高奖Herbrand奖奖 2006邵逸夫数学奖邵逸夫数学奖 2 最近,著名数学家吴文俊荣获邵逸夫数最近,著名数学家吴文俊荣获邵逸夫数学科学奖。邵逸夫数学科学奖是一项国际性学科学奖。邵逸夫数学科学奖是一项国际性大奖,它的评委是来自国际数学界的知名权大奖,它的评委是来自国际数
2、学界的知名权威。吴文俊说:这次邵逸夫奖的评委都是国威。吴文俊说:这次邵逸夫奖的评委都是国际上有影响的大家,他们宣布际上有影响的大家,他们宣布我获得邵逸夫我获得邵逸夫奖,是因为我的数学机械化问题的研究,这奖,是因为我的数学机械化问题的研究,这实际上是国际数学界对数学机械化研究的承实际上是国际数学界对数学机械化研究的承认与肯定,它比奖金重要得多。认与肯定,它比奖金重要得多。 数学机械化得到国际数学界承认数学机械化得到国际数学界承认 3中央电视台中央电视台大家大家栏目:栏目:吴文俊吴文俊我的不等式我的不等式片断片断 4什么是数学机械化什么是数学机械化 所谓机械化,无非是刻板化和规格化。所谓机械化,无
3、非是刻板化和规格化。数学数学问题的机械化,就要求在运算或证明过程中,问题的机械化,就要求在运算或证明过程中,每前进一步之后,都有一个确定的、必须选每前进一步之后,都有一个确定的、必须选择的下一步,这样沿着一条有规律的、刻板择的下一步,这样沿着一条有规律的、刻板的道路,一直达到结论。的道路,一直达到结论。 使用一种机械化方法证明一类定理,才真正使用一种机械化方法证明一类定理,才真正体现了机械化定理证明。体现了机械化定理证明。1977年,吴文俊给年,吴文俊给出了初等几何一类主要定理的机械化证明方出了初等几何一类主要定理的机械化证明方法法“吴方法吴方法”。5数学机械化:从设想到实现数学机械化:从设想
4、到实现 笛卡尔笛卡尔 莱布尼茨莱布尼茨 希尔伯特希尔伯特 6数学机械化:从设想到实现数学机械化:从设想到实现 哥德尔哥德尔 塔斯基塔斯基 王浩王浩 吴文俊吴文俊7笛卡尔的设想笛卡尔的设想 17 世纪法国的数学家世纪法国的数学家 Descartes 曾有过一个伟大曾有过一个伟大的设想:的设想:“一切问题化为数学问题,一切数学问题一切问题化为数学问题,一切数学问题化为代数问题,一切代数问题化为代数方程求解问化为代数问题,一切代数问题化为代数方程求解问题。题。” Descartes 把问题想得太简单了,如果他的设想真把问题想得太简单了,如果他的设想真能实现,那就不仅是数学的机械化,而是全部科学能实现
5、,那就不仅是数学的机械化,而是全部科学的机械化。因为代数方程求解是可以机械化的。的机械化。因为代数方程求解是可以机械化的。 但但 Descartes 没有停留在空想,他所创立的解析几没有停留在空想,他所创立的解析几何,在空间形式和数量关系之间架起了一座桥梁,何,在空间形式和数量关系之间架起了一座桥梁,实现了初等几何问题的代数化实现了初等几何问题的代数化。8莱布尼兹之梦莱布尼兹之梦 德国数学家德国数学家 Leibniz 曾有过曾有过“推理机器推理机器”的的设想。他研究过逻辑,设计并制造出能做乘设想。他研究过逻辑,设计并制造出能做乘法的计算机,进而萌发了法的计算机,进而萌发了设计万能语言和造设计万
6、能语言和造一台通用机器的构想。一台通用机器的构想。 他的努力促进了他的努力促进了 Boole 代数、数理逻辑以及代数、数理逻辑以及计算机科学的研究,正是沿着这一方向,经计算机科学的研究,正是沿着这一方向,经后人的努力,形成了机器定理证明的逻辑方后人的努力,形成了机器定理证明的逻辑方法。法。 9希尔伯特的构想希尔伯特的构想 Hilbert在在几何基础几何基础中提出了从公理化走向机械中提出了从公理化走向机械化的数学构想。化的数学构想。Hilbert计划将数学知识纳入严格的计划将数学知识纳入严格的公理体系中,并着力在公理化基础上寻找机械化的公理体系中,并着力在公理化基础上寻找机械化的方法判定命题是否
7、成立。方法判定命题是否成立。Hilbert同时指出,定理的同时指出,定理的判定问题应当是分类解决的,解决方法要同时强调判定问题应当是分类解决的,解决方法要同时强调简单性和严格性。简单性和严格性。 在在 Hilbert 的名著的名著几何基础几何基础一书中就提供了一一书中就提供了一条可以对一类几何命题进行判定的定理条可以对一类几何命题进行判定的定理 当然,当然,在那个时代,不仅在那个时代,不仅 Hilbert 本人,整个数学界都没本人,整个数学界都没有意识到这一点。有意识到这一点。 10哥德尔的著名结果哥德尔的著名结果 Gdel著名的不完全性定理指出一个不弱于初等数论的形式系统如果是无矛盾的,则是
8、不完全的 ,即存在形式系统的一个命题,它和它的否定都不能由形式系统证明。 因此, Hilbert 的要求太高了。上述的Gdel不完全性定理断言:即使在初等数论的范围内,对所有命题进行判定的机械化方法也是不存在的! 11塔斯基的判定法塔斯基的判定法 波兰数学家波兰数学家 Tarski 在在 1950 年推广了关于代年推广了关于代数方程实根数目的数方程实根数目的 Sturm 法则,由此证明了法则,由此证明了一个引人注目的定理:一个引人注目的定理:“一切初等几何和初一切初等几何和初等代数范围的命题,都可以用机械方法判定等代数范围的命题,都可以用机械方法判定。” Tarski得出的结论给定理证明机械化
9、的研究得出的结论给定理证明机械化的研究带来了曙光。可惜他的方法太复杂,即使用带来了曙光。可惜他的方法太复杂,即使用高速计算机也证明不了稍难的几何定理。高速计算机也证明不了稍难的几何定理。 12王浩:迈向数学机械化王浩:迈向数学机械化 1959 年,王浩设计了一个程序,用计算机证年,王浩设计了一个程序,用计算机证明了明了 Russell 、 Whitehead 的巨著的巨著数学原数学原理理中的几百条有关命题逻辑的定理,仅用中的几百条有关命题逻辑的定理,仅用了了 9 分钟。分钟。王浩工作的意义在于宣告了用计王浩工作的意义在于宣告了用计算机进行定理证明的可能性算机进行定理证明的可能性。 在在1960
10、年的年的IBM研究与发展年报研究与发展年报(IBM Journal),王浩发表了),王浩发表了迈向数学机械化迈向数学机械化(Toward Mechanical Mathematics),),“数学机械化数学机械化”一词即出自此处。一词即出自此处。13吴文俊:吴文俊:机器证明领域的新的一页机器证明领域的新的一页 1977 年,吴文俊在年,吴文俊在中国科学中国科学上发表论文上发表论文初初 等几何判定问题与机械化问题等几何判定问题与机械化问题。 1984 年,吴文年,吴文俊的学术专著俊的学术专著几何定理机器证明的基本原理几何定理机器证明的基本原理由由科学出版社出版,这部专著着重阐明几何定理机械科学出
11、版社出版,这部专著着重阐明几何定理机械化证明的基本原理。化证明的基本原理。 1985 年,吴文俊的论文年,吴文俊的论文关关于代数方程组的零点于代数方程组的零点发表,具体讨论了多项式方发表,具体讨论了多项式方程组所确定的零点集。与国际上流行的代数理想论程组所确定的零点集。与国际上流行的代数理想论不同,明确提出了具有中国自己特色的、以多项式不同,明确提出了具有中国自己特色的、以多项式零点集为基本点的机械化方法。自此,零点集为基本点的机械化方法。自此,“吴方法吴方法”宣告诞生,数学机械化研究揭开了新的一幕。宣告诞生,数学机械化研究揭开了新的一幕。 14 吴文俊吴文俊我的不等式我的不等式片断片断 15
12、三角形三条高线交于一点的代数证明三角形三条高线交于一点的代数证明 D是是BC和和CA上高线交点上高线交点16 定理的假定理的假设部分是部分是,由吴方法,可得非退化条件是由吴方法,可得非退化条件是.定理的定理的结论是是CO经过D点点.显然在非退化条件下定理成立。然在非退化条件下定理成立。17Morley定理定理 任意三角形中,一个角的三等分线,与和任意三角形中,一个角的三等分线,与和它相邻的角的三等分线相交,交点组成正它相邻的角的三等分线相交,交点组成正三角形。三角形。18机器方法容易证明机器方法容易证明Morley定理定理 任意三角形中,一个角的三等分线,与和任意三角形中,一个角的三等分线,与
13、和它相邻的角的三等分线相交,按一定的规它相邻的角的三等分线相交,按一定的规则选取交点,共可组成则选取交点,共可组成27个三角形,在这个三角形,在这27个三角形中,一定有个三角形中,一定有18个是正三角形。个是正三角形。用机器方法容易证明这个更一般的用机器方法容易证明这个更一般的Morley定理。在证明过程中,多次出现关于定理。在证明过程中,多次出现关于12个个变量的含有一千多项的多项式。变量的含有一千多项的多项式。19吴方法概要定理的假设相当于一组多项式方程定理的结论相当于一个多项式方程上面的诸Fi称为假设多项式,G称为终结多项式。20吴方法概要(续) 吴方法是给出了一个机械化方法,在有限步内
14、给出一组非退化条件多项式D1, , Dr 又根据这一机械化方法足以在有限步内,判定在非退化条件 D10, , Dr 0 下,G=0是否可从F1=0, , Fs=0推出。 21对吴方法的评价吴方法遵循中国传统数学中几何代数化的思想,与通常基于数理逻辑的方法根本不同,首次实现了高效的几何定理自动证明,显现了无比的优越性。他的工作被称为自动推理领域的先驱性工作,并于1997年获得“Herbrand自动推理杰出成就奖”。在授奖辞中对他的工作给了这样的介绍与评价: “几何定理自动证明首先由赫伯特格兰特(Herbert Gerlenter)于50年代开始研究。虽然得到一些有意义的结果,但在吴方法出现之前的
15、20年里,这一领域进展甚微。在不多的自动推理领域中,这种被动局面是由一个人完全扭转的。吴文俊很明显是这样一个人。他将几何定理证明从一个不太成功的领域变为最成功的领域之一。”22中国古代数学的贡献 70 年代初,吴文俊开始研读中国数学史。1975 年,他撰写了中国古代数学对世界文化的伟大贡献,文中详细列举在代数、几何、三角、解析几何和微积分等学科的发现和创立过程中,中国传统数学所起的重大作用。 吴文俊指出,中国传统数学注意解方程,在代数学、几何学、极限概念等方面既有丰硕的成果,又有系统的理论。23中国古代数学的特色 中国传统数学强调构造性和算法化,注意解决科学实验和生产实践中提出的各类问题,往往
16、把所得到的结论以各种原理的形式予以表述。 中国传统数学在从问题出发以解决问题为主旨的发展过程中建立了以构造性与机械化为其特色的算法体系, 九章算术与刘徽的九章算术注是这一机械化体系的代表作,这与西方数学以欧几里得几何原本为代表的所谓公理化演绎体系正好遥遥相对。 24机械化思想是中国古代数学的精髓 吴文俊把中国传统数学的思想概括为机械化思想,指出它是贯穿于中国古代数学的精髓。他列举大量事实说明,中国传统数学的机械化思想为近代数学的建立和发展做出了不可磨灭的贡献。 这种机械化思想,不仅曾深刻影响了数学的历史进程,而且对数学的现状也正在发扬它日益显著的影响。 25数学机械化的广泛应用 吴文俊特别重视
17、数学机械化方法的应用,明确提出“数学机械化方法的成功应用,是数学机械化研究的生命线”。他不断开拓新的应用领域,如控制论、曲面拼接问题、机构设计、化学平衡问题、平面天体运行的中心构形等,还建立了解决全局优化问题的新方法。 吴方法还被用于若干高科技领域,得到一系列国际领先的成果,包括曲面造型、机器人结构的位置分析、智能计算机辅助设计(CAD)、信息传输中的图像压缩等。26从开普勒定律到牛顿定律 开普勒定律为(1)行星绕太阳以椭圆轨道运行,太阳为一焦点(2)太阳到行星的向量在相同的时间扫过相同的 面积 牛顿定律为(3)行星的加速度与太阳到行星的距离的平方成反比 利用吴方法在微分域上的推广,可以从开普
18、勒经验公式自动推导出牛顿定律。27微分几何定理机器证明 微分几何离不开函数和微分,从表面上看似乎不能使用计算机进行证明,但事实上并非如此。在微分几何中出现的那种函数与导数完全可以形式地来对待,因此,存在着通过有限次的构造步骤借助于计算机来进行微分几何定理证明的可能性。 微分多项式组的整序算法已经应用于微分几何的一些定理的机器证明与一些几何关系或公式的自动发现和推导。28机器人与连杆机构的运动分析 如图,绿色的平台是活动平台,下面的平台是固定的,六根连杆长度可变,求连杆长度变化时平台上一点的 轨迹。29机器人与连杆机构的运动分析 已知连杆机构的构成,求该机构上某一点的轨迹及该点的位置与连杆机构的
19、关系,这类问题称为机械设计中的正解问题。前面的例子就是一个正解问题。 反过来,求解连杆机构的参数使得连杆机构上一点恰好位于空间指定位置的问题称为机械设计中的逆解问题。 这两类问题都可以看成方程求解问题。 吴文俊用特征集方法解决了一般PUMA型机器人的逆解问题,研究了四连杆的设计问题。30曲面连接问题 在几何设计中,有一大类问题要确定一给定次数的 代数曲面按一定要求连接已给的若干代数曲面。 这类问题可以用吴方法解决。左图是一个连接左图是一个连接三根管道的例子。三根管道的例子。31杨-Baxter方程与量子群 应用吴方法,采用人机对话的方式,运用多种技巧,成功地求出二维杨-Baxter方程的全部解
20、。在二维情形下,这组方程有16个未知数,由64个三次多项式方程组成。 相应于杨-Baxter方程的解,可得到量子群。但具体计算对应的量子群并不容易。从吴方法出发,可给出依据杨-Baxter方程的解直接计算相应量子群的机械化方法。32脑力劳动的机械化 在在新的正在到来的工业革命新的正在到来的工业革命中,可以认为是以某中,可以认为是以某种设备代替人脑。这将使人类艰苦思考的价值为种设备代替人脑。这将使人类艰苦思考的价值为之降低,之降低,是一种脑力劳动的机械化是一种脑力劳动的机械化。这种机械化。这种机械化由于上世纪中叶计算机的发明而有某种可能。由于上世纪中叶计算机的发明而有某种可能。数学是一种典型的脑
21、力劳动。由于数学思维具有数学是一种典型的脑力劳动。由于数学思维具有其它思维方式所没有的简洁、明确、严密、清晰其它思维方式所没有的简洁、明确、严密、清晰等优点,因而数学的机械化比之其它思维的机械等优点,因而数学的机械化比之其它思维的机械化,应有它的优越性与优先性,而且应更为容易。化,应有它的优越性与优先性,而且应更为容易。吴方法在几何定理证明方面机械化的成功,正好吴方法在几何定理证明方面机械化的成功,正好说明确是如此。说明确是如此。 33机械化思想促进数学发展 线性方程组求解中的消去法是机械化思想的杰作。线性方程组求解中的消去法是机械化思想的杰作。即使是现代纯粹数学研究中,机械化思想也一直即使是
22、现代纯粹数学研究中,机械化思想也一直发挥重大的作用。例如,希尔伯特倡导的数理逻发挥重大的作用。例如,希尔伯特倡导的数理逻辑为计算机的设计原理作了准备。辑为计算机的设计原理作了准备。H. Cartan关于关于代数拓扑学同调群计算的工作可以看作是机械化代数拓扑学同调群计算的工作可以看作是机械化思想的成功范例。思想的成功范例。运用机械化思想考察数学,将会发现数学的不同运用机械化思想考察数学,将会发现数学的不同侧面,建立新的模式,活跃和启迪数学家的思维,侧面,建立新的模式,活跃和启迪数学家的思维,从而产生大量的原始创新。从而产生大量的原始创新。机械化可以使得大量繁复的事情交给计算机去做,机械化可以使得
23、大量繁复的事情交给计算机去做,而数学家将从事富有创造性的劳动。而数学家将从事富有创造性的劳动。34展望数学机械化的未来 1981 年吴文俊在年吴文俊在数学的机械化与机械化的数学数学的机械化与机械化的数学一文中指出:一文中指出:“我们的研究工作还只是一个开端。我们的研究工作还只是一个开端。如何继续发扬中国古代传统数学的机械特色,如何继续发扬中国古代传统数学的机械特色,对数对数学各个不同领域探索实现机械化的数学,则是本世学各个不同领域探索实现机械化的数学,则是本世纪以致可能绵亘整个纪以致可能绵亘整个 21 世纪才能大体趋于完善的世纪才能大体趋于完善的事事。” 近近 20多年来多年来 , 在吴文俊的积极倡导下,中国的数在吴文俊的积极倡导下,中国的数学机械化研究已初现丰富多彩之势。展望学机械化研究已初现丰富多彩之势。展望 21 世纪,世纪,我们有理由相信,机械化数学和数学机械化必将为我们有理由相信,机械化数学和数学机械化必将为数学以致整个科学注入新的活力。数学以致整个科学注入新的活力。 35