数学机械化自动推理计算机代数-上海海事大学课件_第1页
数学机械化自动推理计算机代数-上海海事大学课件_第2页
数学机械化自动推理计算机代数-上海海事大学课件_第3页
数学机械化自动推理计算机代数-上海海事大学课件_第4页
数学机械化自动推理计算机代数-上海海事大学课件_第5页
已阅读5页,还剩66页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

如何实现自动推理--简明介绍数学机械化与吴方法讲座2008-11-?朝鲁上海海事大学数学系如何实现自动推理讲座2008-11-?朝鲁上海讲座一、吴文俊简介讲座一、吴文俊简介

吴文俊院士是中国科学院数学与系统科学研究院的研究员,我国著名的数学家。他于上世纪50年代对数学的主要领域—拓扑学做出了杰出贡献。70年代后期,吴文俊开创了崭新的数学机械化领域。他建立了用计算机证明几何定理的“吴方法”。实现了高效几何定理自动证明;吴方法应用于计算机图形学、机器人、机构设计、全局优化、化学平衡、天体运行……等领域。87岁≠不能创新

吴文俊院士获得过很多奖项:1956年获得国家自然科学一等奖1979年获得中国科学院自然科学一等奖1990年获得第三世界科学院数学奖1993年获得陈嘉庚数理科学奖1994年获得首届香港求是科技基金会杰出科学家奖1998年度国际自动推理界的最高奖“Herbrand奖”

2000年获得首届国家最高科技奖2006年获邵逸夫数学科学奖87岁≠不能创新吴文俊院士获得过很多奖项:/detail2.asp?project_id=122&type_id=22看一段视频报道/detail2吴文俊的虚拟轴机床——数学机械化方法及其在并联机构中的应用

吴文俊院士开创了数学机械化研究领域。他所建立的“吴方法”,“吴消元法”及“吴有限核定理”已成为该领域的奠基性成果。运用数学机械化方法,本项研究解决了广义Stewart平台正解问题,这是对机器人运动学领域的一个主要贡献。以此为基础,研制成功我国第一台大型虚拟轴机床样机与集成电路制造装备关键子系统。吴文俊的虚拟轴机床——数学机械化方法及其在并联机构中的应用数学机械化自动推理计算机代数-上海海事大学课件数学机械化自动推理计算机代数-上海海事大学课件二、脑力劳动能机械化吗?二、脑力劳动能机械化吗?劳动=体力劳动+脑力劳动;

17世纪以来,工业革命使人们逐渐实现了体力劳动的机械化,大大地促进了社会生产力的发展。?!劳动=体力劳动+脑力劳动;17世纪以来,工业革命使人们逐渐

脑力劳动的彻底机械化是不可能,但部分机械化是完全可能,并且随着人类智慧的提高这个机械化程度越来越高。意义深远!脑力劳动的机械化是人类的追求,梦想脑力劳动的彻底机械化是不可能,但部分机械化是完全可能,并且

作为科学基础的数学研究是典型的脑力劳动,具有论证严谨、表述明确等优点,理应率先实现机械化。成为其他学科机械化的基础。如今,人类社会正步入信息革命时代,计算机的功能不断增强,为人类实现脑力劳动的机械化创造了物质条件。对脑力劳动的机械化,作为其灵魂或核心技术,数学的参与是不可缺少。作为科学基础的数学研究是典型的脑力劳动,具有论证三、数学机械化

与自动推理三、数学机械化

吴文俊:所谓机械化,无非是刻板化和规格化。数学问题的机械化,就要求在运算或证明过程中,每前进一步之后,都有一个确定的、必须选择的下一步,这样沿着一条有规律的、刻板的道路,一直达到结论。数学机械化吴文俊:所谓机械化,无非是刻板化和规格化。数学机械自动推理机械化算法的计算机实现。对某一个思维问题(脑力劳动)要设计机械化算法;算法是构造化的,能转化为计算机指令;计算机能接受并能按设计逻辑处理这些指令,推理出结论.这里要知道两个关键点:计算机能处理什么?算法是构造性(机械化)?自动推理机械化算法的计算机实现。实现机械化和自动推理需要两个发展:

构造性数学的发展(脑子);计算机的发展(肢体)。出现了“数学机械化”、“自动推理”、“计算机代数”,“理论计算机”,……等学科。实现机械化和自动推理需要两个发展:出现了“数学机四、数学机械化的艰难历程

——从设想到实现四、数学机械化的艰难历程数学机械化:从设想到实现笛卡尔莱布尼茨希尔伯特数学机械化:从设想到实现笛卡尔莱布尼茨希尔伯特数学机械化:从设想到实现哥德尔塔斯基王浩吴文俊数学机械化:从设想到实现哥德尔塔斯基王浩吴文俊笛卡尔的设想

17

世纪法国的数学家Descartes曾有过一个伟大的设想:“一切问题化为数学问题,一切数学问题化为代数问题,一切代数问题化为代数方程求解问题。”

并,Descartes

没有停留在空想,他所创立的解析几何,在空间形式和数量关系之间架起了一座桥梁,实现了初等几何问题的代数化。但,Descartes把问题想得太简单了,如果他的设想真能实现,那就不仅是数学的机械化,而是全部科学的机械化。笛卡尔的设想莱布尼兹之梦德国数学家Leibniz

曾有过“推理机器”的设想。他研究过逻辑,设计并制造出能做乘法的计算机,进而萌发了设计万能语言和造一台通用机器的构想。他认为,他的方案一旦实现,人们之间的一切争论都可以被心平气和的机器体力劳动所代替。他的努力促进了Boole代数、数理逻辑以及计算机科学的研究,正是沿着这一方向,经后人的努力,形成了机器定理证明的逻辑方法。

莱布尼兹之梦德国数学家Leibniz曾有过“推理机器”的希尔伯特的构想

Hilbert在《几何基础》中提出了从公理化走向机械化的数学构想。Hilbert计划将数学知识纳入严格的公理体系中,并着力在公理化基础上寻找机械化的方法判定命题是否成立。Hilbert同时指出,定理的判定问题应当是分类解决的,解决方法要同时强调简单性和严格性。在Hilbert

的名著《几何基础》一书中就提供了一条可以对一类几何命题进行机械化判定的定理—当然,在那个时代,不仅Hilbert

本人,整个数学界都没有意识到这一点。

希尔伯特的构想Hilbert在《几何基础》哥德尔的著名结果

Gödel著名的不完全性定理指出一个不弱于初等数论的形式系统如果是无矛盾的,则是不完全的,即存在形式系统的一个命题,它和它的否定都不能由形式系统证明。因此,Hilbert的要求太高了。上述的Gödel不完全性定理断言:即使在初等数论的范围内,对所有命题进行判定的机械化方法也是不存在的!哥德尔的著名结果Gödel著名的不完全性定理塔斯基的判定法

波兰数学家Tarski

在1950年推广了关于代数方程实根数目的Sturm法则,由此证明了一个引人注目的定理:“一切初等几何和初等代数范围的命题,都可以用机械方法判定。”

Tarski得出的结论给定理证明机械化的研究带来了曙光。可惜他的方法太复杂,即使用高速计算机也证明不了稍难的几何定理。

塔斯基的判定法波兰数学家Tarski在1950王浩:迈向数学机械化1959年,王浩设计了一个程序,用计算机证明了Russell、Whitehead的巨著《数学原理》中的几百条有关命题逻辑的定理,仅用了9分钟。王浩工作的意义在于宣告了用计算机进行定理证明的可能性。在1960年的《IBM研究与发展年报》(IBMJournal)上,王浩发表了《迈向数学机械化》(TowardMechanicalMathematics)的文章。“数学机械化”一词即出自此处。王浩:迈向数学机械化1959年,王浩设计了一个程序,

其他人与王浩同一时期,A.Newell和H.A.Simon也做了与王浩类似的工作。1965年Robinson归结原理的提出是用逻辑方法进行机器证明的又一重要进展。1976年K.I.Appel和W.Haken在高速电子计算机上用1200小时的计算时间,证明了著名的四色定理,使数学家们100多年来未能解决的这个难题得到了肯定的回答(机械化证明)。数学机械化自动推理计算机代数-上海海事大学课件数学大师们的坚持不懈地追求,表明数学机械化思想重要而深刻。但数学机械化历程漫长而艰难,发展缓慢。70年代末,在中国得到突破!数学大师们的坚持不懈地追求,表明数学机械化思想重要而深刻。

五、数学机械化的突破

——吴方法的出现五、数学机械化的突破吴文俊:

数学机械化(机器证明)领域的新的一页

1976年,我国数学家吴文俊教授为数学机械化(机器证明,自动推理)的发展翻开了新的一页。提出几何定理的机器证明机械化算法,并计算机实现。他当时既没有接触到Tarski的工作,也没有想到Hilbert的著作里那一条定理。中国古代构造性数学思想的启迪了他。吴文俊:

数学机械化(机器证明)领域的新的一页1971977年,吴文俊在《中国科学》上发表论文《初等几何判定问题与机械化问题》。1984年,吴文俊的学术专著《几何定理机器证明的基本原理》由科学出版社出版,这部专著着重阐明几何定理机械化证明的基本原理。1985年,吴文俊的论文《关于代数方程组的零点》发表,具体讨论了多项式方程组所确定的零点集。与国际上流行的代数理想论不同,明确提出了具有中国自己特色的、以多项式零点集为基本点的机械化方法。自此,“吴方法”宣告诞生,数学机械化研究揭开了新的一幕。

1977年,吴文俊在《中国科学》上发表论文《初等几何判定问

六、吴方法的介绍六、吴方法的介绍

所谓定理的机械化证明,就是对一类定理(这类定理可能成千上万)提供一种统一的方法,使得该类定理中每个定理,都可依此方法给出证明。在证明过程中,每前进一步,都有章可循地确定下一步该做什么和如何做。

从“一理一证”到“-类一证”,是数学的认识和实践的飞跃。数学(脑力劳动)机械化的典范所谓定理的机械化证明,就是对一类定理(这类吴方法的基本思想是十分朴素的:把几何命题化成代数形式加以处理。化成什么形式?如何处理?整个过程是什么样?主要思想是什么?吴方法的基本思想是十分朴素的:

Simson定理的机器证明

Simson定理:在的外接圆上任取一点P。自P点向直线BC,CA,AB引垂线,垂足依次为R,S,T,那么R,S,T三点在一直线上(如图所示)。O

定理:

(1)A,B,C,P在同一圆上;

条件:(2)R,S,T分别在直线BC,CA,AB上;(3)PR⊥BC,PT⊥AB,PS⊥AC

结论:R,S,T共线。用一个例子来简单介绍吴方法Simson定理的机器证明Simson定理:在

为了简便,可以将△ABC的外接圆中心O取为Descartes坐标原点,将圆半径取为单位长,并设各点的坐标为

A(x1,y1),B(x2,y2),C(x3,y3),R(x4,y4),S(x5,y5),T(x6,y6),P(1,0)于是,定理的假设部分可以改写成代数等式的形式。

由假设,条件(1)可以写成:(A在圆O上);

(B在圆O上);(C在圆O上);O定理:

(1)A,B,C,P在同一圆上;

条件:(2)R,S,T分别在直线BC,CA,AB上;

(3)PR⊥BC,PT⊥AB,PS⊥AC

结论:

R,S,T共线。第一步几何问题的代数化为了简便,可以将△ABC的外接圆中心O取为De条件(2)可以写成:(R在BC上)

(S在AC上)(T在AB上)O

定理:

(1)A,B,C,P在同一圆上;

条件:(2)R,S,T分别在直线BC,CA,AB上;

(3)PR⊥BC,PT⊥AB,PS⊥AC

结论:

R,S,T共线。条件(2)可以写成:(R在BC上)(S在AC上)(T在条件(3)可以写成:要证明的结论可以表示为(R,S,T共线)O

定理:

(1)A,B,C,P在同一圆上;

条件:(2)R,S,T分别在直线BC,CA,AB上;

(3)PR⊥BC,PT⊥AB,PS⊥AC

结论:

R,S,T共线。条件(3)可以写成:要证明的结论可以表示为(R,S,T至此,我们已经完成了用吴方法证明几何定理的第一步:用解析几何方法将几何问题代数化。当然,也可以用其他方法,如三角方法。所得代数形式的问题就是,在假设一组多元多项式组为0的条件下,求证另一多项式为0。即,定理的等价代数表示为求证(R,S,T共线)设(A在圆O上)

(B在圆O上)(C在圆O上)(R在BC上)(S在AC上)(T在AB上)O至此,我们已经完成了用吴方法证明几何定理的第一步:用解析几何等价地,用多项式的零点集(集合论)描述上述定理:需要证明问题的进一步转换。O

定理:

(1)A,B,C,P在同一圆上;

条件:(2)R,S,T分别在直线BC,CA,AB上;

(3)PR⊥BC,PT⊥AB,PS⊥AC

结论:

R,S,T

共线。如何做?用记号问题的进一步转换。O定理:如何做?用记号由此,我们有零点关系有方程组的关系已经对约化。对任意两个一元多项式我们总有若带余除法的回忆由此,我们有零点关系有方程组的关系已经对约化。对对现在的问题,如果能实现就有定理就成立,遗憾的是(*)一般不成立!!什么条件下成立呢?对现在的问题,如果能实现就有定理就成立,遗憾的是(*)一般不第二步整序就本例而论,A,B,C三点在圆上的位置定了,其他点的位置也就定了。而A,B,C三点的位置可以由三个纵坐标来确定。因此,在这12个变元当中,只有3个是自由的,另外9个都是受约束的。我们取为自由变元,并用另外记号记

整序就是把约束变元排个序改变为另一族具有特殊结构的多项式组,并尽可能零点性质不变。然后通过让满足我们所要的结论。O第二步整序就本例而论,A,B,C三点在圆上的位置定了,其他无规律(A在圆O上)

(B在圆O上)(C在圆O上)(R在BC上)(S在AC上)(T在AB上)O已知无规律(A在圆O上)(B在圆O上)(C在圆O上)(R在BC把左边看作多元多项式,让等价地变为三角形形式其中如何得到的?有规律O把左边看作多元多项式,让等价地变为三角形形式其中如何得到的?的推导因为利用简化后得令(A在圆O上)

(B在圆O上)(C在圆O上)(R在BC上)(S在AC上)(T在AB上)O用消,令的推导因为利用简化后得令(A在圆O上)(类似地得到其它的使得类似地得到其它的使得故,要证明的问题变为证明的问题。因为=故,要证明的问题变为证明的问题。因为=吴方法的第二步至此完成。我们得到了一个三角化组(升列):第三步:伪除法

(其它变元暂看成扩域当中的常量)即对G进行带余除法(称伪除法);所得得余式称为G关于对变元的伪余式,并用*9F记作做这种伪除时,需要假定这叫做非退化条件。

这相当于从方程解出再将该解带入中。和G开始。将G和都看成最后一个约束变元的一元多项式伪除求余从吴方法的第二步至此完成。我们得到了一个三角化组(升列):第三现将看成的(一元)多项式,即写成

又将也看成的多项式,并用伪除得到的伪余式,即再将和都看成的多项式。用伪除求余式,并继续下去。现将看成的(一元)多项式,即写成又将也看成的多项式,并用从这个等式看出,当的条件下,有最后得到等式其中所要证明定理的结论成立。成立。这表明在非退化条件之下,从这个等式看出,当的条件下,有最后得到等式其中所要证明定理的伪除法求余式,若用手算则是繁琐的,甚至是不可行的。它有时要涉及上千项的多项式的运算和整理。如果我们有足够细心并有足够的耐心,也许可以用纸笔来完成这个例子中的计算,但可能要花上好几个小时。若要是算到最后余式不为零,根据吴方法:若升列不可约的,则命题不成立.对可约升列,总可以通过因子分解将其化为几个不可约升列,从而将问题完全解决。整个过程的基本思想是朴素的:尽可能地消去约束变元,或降低约束变元的次数,使定理的假设部分三角化,再用其将定理的结论约化为0。注:伪除法求余式,若用手算则是繁琐的,甚至是不可行的。它有时要涉第四步:退化条件的讨论从形式上看,非退化条件就是要求在整序后得到的升序中,每个多项式中新出现的约束变元最高次项的系数不等于零.在本例中,多项式不产生非退化条件。多项式中新出现的约束变元是,它的最高次项是1次的,系数是,因而产生了非退化条件

该条件的几何意义是“B与C两点不重合”.这当然是需要的:如果B与C重合,那么ABC就不成为三角形了。提出要对“非退化条件”进行研究是吴文俊教授对几何证明理论的又一贡献,也是定理机器证明研究的副产品.长期以来,人们认为Euclid几何中的论证推理过程是严密.即使有问题,也出在公理体系上。D.Hilbert重整了Euclid公理体系之后,总不会再有什么漏洞了吧?但吴文俊教授指出:传统的初等几何证明方法不但不严密,而且也不可能严密。问题就出在“退化”情形上。

O第四步:退化条件的讨论从形式上看,非退化条件就是要求在整序那么,在几何命题的假设中,排除了退化情形,是不是就万事大吉,完全严密了呢?问题没这么简单;因为用综合法证几何题,往往要作辅助线、辅助图,再对辅助图形运用一些已知定理。在辅助图形中有可能遇到退化的情形。怎样作辅助线,事先是不知道的,因而无法预先说明会出现哪些退化情形而使证明失效。证明中推理环节越多,出现退化情形而破坏证明的严密性的可能性就越大。吴方法使这个问题得到了圆满解决:在机器证明几何定理的过程中,该方法能够自然地一一给出退化情形的代数表示,指出保证命题成立的非退化条件。Euclid几何中的概念通常是排除了”退化’’情形.比如说“三角形’’,就要求三顶点不共线,若三顶点共线,三角形成了线段,就是退化了。有些几何定理,对退化情形也成立;但也有些几何定理,图形一退化,定理便不成立了。例如“△ABC中,若∠B=∠C,则“|AB|=IACI”,这条定理,当∠B=∠C=0时就不成立,而当∠B=∠C=时又成立了。由此可见,对退化条件要单独进行讨论。

O那么,在几何命题的假设中,排除了退化情形,是不是就万事大吉,七,总结七,总结为什么能机械化?算法是构造性的,可以程序化理论是严密的。数学原理是核心,计算机是辅助工具。为什么能机械化?算法是构造性的,可以程序化数学原理是核心,八、对吴方法的评价八、对吴方法的评价吴方法遵循中国传统数学中几何代数化的思想,与通常基于数理逻辑的方法根本不同,首次实现了高效的几何定理自动证明,显现了无比的优越性。他的工作被称为自动推理领域的先驱性工作,并于1997年获得“Herbrand自动推理杰出成就奖”。在授奖辞中对他的工作给了这样的介绍与评价:

“几何定理自动证明首先由赫伯特·格兰特(H.Gerlenter)于50年代开始研究。虽然得到一些有意义的结果,但在吴方法出现之前的20年里,这一领域进展甚微。在不多的自动推理领域中,这种被动局面是由一个人完全扭转的。吴文俊很明显是这样一个人。他将几何定理证明从一个不太成功的领域变为最成功的领域之一。”吴方法遵循中国传统数学中几何代数化的思想,与通常基于数理逻辑

公理化体系的几何定理证明非常不机械化。以中学课程中的几何为例,-个定理的证明,往往要经过冥思苦想,奇巧构思,无章可循地填加辅助线,迂回曲折地给出证明。如何利用计算机进行自动推理,特别是进行几何定理的自动证明,是学术界长期研究的课题。

公理化体系的几何定理证明非常不机械化。以中学课程中

吴先生创立的初等几何(泛指不具有微分运算的几何,如欧氏几何、非欧几何、仿射几何、投影几何、代数几何等等)定理证明的机械化方法(国际上称“吴方法”)打破了国际自动推理界在几何定理自动证明研究中长期徘徊不前的局面,也使我国在这一领域处于领先地位。吴先生创立的初等几何(泛指不具有微分运算的几何,

机器证明定理的研究的推动下,一门研究如何用计算机进行符号与代数计算的学科--计算机代数--应运而生了。计算机代数系统如Mathematica和Maple为定理机器证明的研究和发展提供了物质基础。吴方法的发现使具有数千年历史,手工式的初等几何研究真正跨入了机械化的阶段。今后,当人们在初等几何范围内提出新命题而不知其真假时,只要上机一试,便知分晓,把烦琐复杂计算交给计算机,而人把精力投入到更深刻创造发明当中。机器证明定理的研究的推动下,一门研究如何用计算机九、吴方法的广泛应用九、吴方法的广泛应用控制论、曲面拼接问题、机构设计、化学平衡问题、平面天体运行的中心构形等,还建立了解决全局优化问题的新方法。吴方法还被用于若干高科技领域,得到一系列国际领先的成果,包括曲面造型、机器人结构的位置分析、智能计算机辅助设计(CAD)、信息传输中

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论