新書推薦：
《
微观经济学（第三版）【2024诺贝尔经济学奖获奖者作品】
》
售價：NT$
709.0
《
Python贝叶斯深度学习
》
售價：NT$
407.0
《
文本的密码：社会语境中的宋代文学
》
售價：NT$
306.0
《
启微·狂骉年代：西洋赛马在中国
》
售價：NT$
357.0
《
有趣的中国古建筑
》
售價：NT$
305.0
《
十一年夏至
》
售價：NT$
347.0
《
如何打造成功的商业赛事
》
售價：NT$
407.0
《
万千教育学前·透视学前儿童的发展：解析幼儿教师常问的那些问题
》
售價：NT$
265.0
|
| 編輯推薦： |
几何定理机器证明的完整算法由张景中、高小山、周咸青在20 世纪90 年代初提出并取得极大成功. 对于大部分几何定理， 这一方法可以生成的简短可读证明， 在一定意义下具有基于坐标的吴方法与基于搜索的人工智能方法两者的优点， 且避免了其缺点.本书是作者多年科研成果的结晶
《几何定理机器证明的几何不变量方法》可以作为数学、计算机科学以及相关工程领域的科研人员、教师以及研究生了解几何定理机器证明几何不变量方法的参考书， 也可以作为高等院校与中学教师进行几何教育改革的参考书。
|
| 內容簡介： |
|
《几何定理机器证明的几何不变量方法》系统介绍了几何定理机器证明的几何不变量方法. 主要包括：基于面积与勾股差等几何不变量的面积法、基于体积与勾股差等几何不变量的体积法以及基于向量计算的向量方法.
|
| 關於作者： |
|
张景中，中国科学院院士。现任广州大学计算机教育软件研究所所长。主要从事机器证明、教育数学、距离几何及动力系统等领域的研究。
|
| 目錄：
|
第1章几何定理机器证明概述1
1.1模拟人的思维——人工智能的开始1
1.2Gelernter的几何定理证明机4
1.3几何定理机器证明的吴方法6
1.4几何定理自动发现的吴方法12
第1章小结13
第2章15
2.1传统的证明方法和机器证明的比较15
2.2有向三角形的带号面积18
2.2.1定理18
2.2.2基本命题20
2.3Hilbert交点命题24
2.3.1命题的描述25
2.3.2几何命题的谓词形式27
2.4面积法29
2.4.1从面积中消去点29
2.4.2从比例中消去点31
2.4.3自由点和面积坐标34
2.4.4几何定理证明举例38
2.4.5其他的消元技术44
2.5面积法和仿射几何50
2.5.1平面仿射几何51
2.5.2面积法和仿射几何52
2.6应用55
2.6.1公式推导55
2.6.2n3构型的存在性61
2.6.3Ceva与Menelus定理的推广65
第2章小结73
第3章平面几何机器证明75
3.1勾股差75
3.1.1勾股差和垂直75
3.1.2勾股差和平行78
3.1.3勾股差和面积80
3.2构造型几何命题82
3.2.1线性构造型几何命题82
3.2.2最小构造集合84
3.2.3谓词形式85
3.3线性可构型几何命题的机器证明87
3.3.1算法87
3.3.2优化的消去技巧93
3.4比率构造96
3.4.1更多的比率构造96
3.4.2全角法的机械化104
3.5面积坐标111
3.5.1面积坐标系111
3.5.2面积坐标和三角形的特殊点113
3.6三角函数和共圆点120
3.6.1共圆定理120
3.6.2共圆点的消去123
3.7可构型几何命题的机器证明130
3.7.1从几何量中消点130
3.7.2伪除法和三角形式133
3.7.3可构型几何命题的机器证明136
3.8基于演绎数据库的全角方法140
3.8.1建立几何信息库141
3.8.2基于几何信息库的机器证明145
第3章小结153
第4章演绎数据库方法155
4.1结构化的演绎数据库和推理策略155
4.1.1基于结构化数据的推理155
4.1.2有关的工作156
4.2几何推理规则157
4.2.1几何推理规则158
4.2.2非退化条件160
4.2.3准确的数值图形的构造161
4.3结构化数据库161
4.3.1数据库的结构161
4.3.2证明的生成163
4.4搜索和控制的策略164
4.4.1基于数据的搜索164
4.4.2避免冗余推理166
4.5构造辅助点和Skolem化168
4.6算法的实现与例题169
4.6.1算法的实现169
4.6.2应用170
4.6.3测试结果和例子171
附录175
第4章小结178
第5章立体几何中的定理自动证明179
5.1带号体积179
5.1.1共面定理181
5.1.2体积和平行183
5.1.3体积与三维仿射几何185
5.2构造型几何命题190
5.2.1构造型几何命题190
5.2.2构造型几何图形193
5.3线性构造型几何命题的机器证明196
5.3.1关于体积的消点法196
5.3.2由面积比中消点199
5.3.3由长度比中消点202
5.3.4自由点和体积坐标206
5.3.5例子208
5.4空间中的勾股差215
5.4.1勾股差与垂直215
5.4.2勾股差与体积218
5.5体积法220
5.5.1算法221
5.5.2例子223
5.6体积坐标系230
第5章小结234
第6章非欧几何定理的机器证明236
6.1Cayley-Klein九种平面几何236
6.1.1直线上的三种度量236
6.1.2角度的三种度量238
6.1.3九种平面几何238
6.2Cayley-Klein几何的转化定理245
6.3双曲几何面积法252
6.4双曲几何的消元法256
6.4.1基本几何命题256
6.4.2从比率中消去点258
6.4.3从线性的几何量中消去点259
6.4.4从二次几何量中消去点260
6.4.5消去自由点261
6.4.6消去共圆的点262
6.5算法的实现与例子263
第6章小结269
第7章向量和机器证明270
7.1三维度量空间几何270
7.1.1内积和度量向量空间271
7.1.2度量向量空间的外积275
7.2立体度量几何277
7.2.1内积和外积279
7.2.2构造型几何语句281
7.3基于向量计算的机器证明283
7.3.1向量消点法283
7.3.2从内积和外积中消点287
7.3.3算法289
7.4度量平面几何中的机器证明291
7.4.1欧氏平面几何的向量方法292
7.4.2Minkowsky平面几何中的机器证明296
7.5使用复数的机器证明300
第7章小结308
参考文献310
索引317
|
| 內容試閱：
|
第1章几何定理机器证明概述
1.1模拟人的思维——人工智能的开始
现代意义上的计算机产生于20世纪40年代中期.最初的计算机基本上是用来从事数值计算的，例如计算炮弹的飞行轨迹.能有机会接触计算机的人无不为其巨大而神奇的计算能力所折服.很自然人们就开始对计算机提出新的更高的要求:计算机能否借助其巨大的计算能力产生只有人才能具有的某些智能行为呢？对这一问题的研究在20世纪50年代中期导致了人工智能这一领域的诞生.
要让计算机产生智能行为首先要问：什么是智能行为呢？人们马上想到数学定理证明.数学定理证明不仅被认为是高层次的智力活动，也被认为是人类一般问题求解能力最典型的代表与最好的训练方法.因此，美国学者Newell，Show与Simon便开始研究用计算机证明数学定理，开发了用于命题逻辑的定理证明器“逻辑理论机”LT.
Newell等采用的证明定理的基本方法是：模拟人证明定理的想法.这实际上是一种“搜索法最基本的搜索证明方法有两种：前推法与后推法.
1前推法与大英博物馆算法.
定理证明的前推法即由一个命题的假设A开始，使用一组公理R由假设D0推出新的结论，这些新的结论和Do在一起组成DU再用同样方法从Dl推出更新的结论，这些更新的结论和D，一起组成D2，周而复始，直到得出所要证明的命题结论或得不出更新的结论为止.这一过程可表示如下：
一个有趣的问题是：如果不论是否已经获得要证的结论总是继续推理，是否在某一步必有Dk=Dk+1?果真如此，也就是说，我们已经不能由Dk推导出新的结论.换句话讲，我们达到了“推理不动点”：
这一不动点应该包含能由假设A推导出的所有可能的结论.由此我们不仅可以证明所给定理，实际上还能发现所有能够用E从A推导出的定理.
若果能如此，何其妙哉！实际情况并非如此.主要问题是随着推理步骤的增加，所得到的结论可能非常之多，以致于用很快且容量很大的计算机也不足以在合理的时间内解决问题.这就是所谓的“搜索空间爆炸”现象.
由此也不难理解前推法的一个别名“大英博物馆方法其意是讲如果由英文26个字母和几个标点符号出发，使用前推法写出字母与标点符号的所有可能组合，这里会有所有的单词、所有的句子，以致可以自动生成大英博物馆内的所有著作.显而易见，此路是不通的.
2后推法.
所谓后推法，就是由定理的结论开始寻找使其成立的条件，直至定理的假设.严格定义如下：设G0为某个定理的结论，我们不妨将其称为要证明的目标.如果命题Gi可以由Gi直接推得，则称Gi是原问题的i阶子目标.我们可以将这些推理过程用一“推理树”形象表示，此树以G0为根，以子目标为节点.推理树有两种节点：“与”节点和“或”节点.假设一个节点G向下（远离根节点）与节点F1，F2，…….，Fm相连，这时可能有两种情形：
A.节点G是“与节点”，如果有
其中“A”代表“与”；
B.节点G是“或节点”，如果有
其中“V”代表“或’，.
图1-1表示后推法产生的一个推理树，其中用圆弧标示出“与节点”，并将“与节点”填充为灰色以便区别.
定理的一个证明是推理树的一棵满足下面条件的连通子树：
1该树以定理的结论为根，且所有叶子都是定理的假设或公理.
2如果该树包含推理树的一个“与节点”，那么包含该节点在推理树中的所有后代.
3如果该树包含推理树的一个“或节点”，那么包含该节点在证明树中的一个后代.
所以，定理的证明过程就是在推理树中寻找满足上述条件的一棵子树.与前推法相似，后推法也会出现“搜索空间爆炸”问题.
我们看到，用前推法与后推法证明定理的过程都可以表示为一棵推理树.而一个定理的证明实际上就是通过“搜索”这棵树而生成一棵子树.对于树的搜索方法主要有以下两种：
A.宽度优先法是先搜索层次为1的子目标，再搜索层次为2的子目标，依次类推.以图中的证明树为例，搜索次序是
Go，Gii，G12，G13，G21，G22，G23，G24，G25，G26，…
B.深度优先法是先搜索证明树最左侧的树枝直到不能前进为止.如果定理还没有证明，则需要“回溯”到下一个目标.回溯过程是一个递归过程，具体描述如下：首先回到当前节点的上一个节点，再由这个节点出发搜索没有搜索过的最左侧的后代.以图1-1中的证明树为例，搜索次序是
Go，G11，G21，G31，G41，G42，G22，G32，G33，G43…
宽度优先法搜索是完备的，即如果存在一个子树可以证明定理，则宽度优先法总能够找到这一子树.这是因为宽度优先法是以层为单位自上而下搜索的，深度优先法则无这一完备性.如果推理树的左侧分支是无限的且没有要寻找的子树，则这一搜索过程将无限进行下去.即使别的分支存在要寻找的子树，这一搜索过程也不能找到这一目标.另一方面，如果运气比较好，一般说来深度优先法找到证明的速度较快?
因此，基于搜索的证明方法大体上有三种形式：
1前推法；
2后推法+宽度优先搜索；
3后推法+深度优先搜索.
现在具体介绍一下Newell等的命题逻辑定理证明器LT.所谓命题逻辑公式可以严格定义如下：
单独的命题P是一个公式；
如果P是公式，则也是公式；
如果P和Q都是公式，则PVQ，PAQ也是公式.
通过V与八运算，还可以定义如下运算：
P—Q-TV--PVQ.
定理证明器LT就是要判断一个命题逻辑公式是否正确.
证明器LT采用的是后推法+深度优先搜索的方法.LT的贡献主要有两点:首先，这一工作首次在计算机上实现了定理自动证明，并进一步指出这一方法不仅可以证明定理，还可以用来解决诸如由数据自动发现科学规律、计算机下棋、自然语言理解等问题，在一定意义上为人工智能的发展指出了方向.
证明器LT的另一贡献是“启发式方法”的引入Newell等认为所有严格的证明方法都会遇到搜索空间爆炸问题，因而是不可行的.而出路在于模拟人类证明定理的方式，引入某种规则，对计算机给予“启发”，得以在较快的时间产生证明.
LT作为一个定理证明器的成功，与其作为导致人工智能产生的成功相比要逊色得多.LT只能证明一些简单的命题，它证明的最困难的定理是
真正用计算机成功证明命题逻辑的是华人学者王浩.他通过引入某种判定算法成功地证明了A.N.Whitehead与B.Russell的《数学原理》中所有命题逻辑定理.
相关的一个有趣现象是：除王浩外，早期从事定理证明的学者强调他们的工作目的主要不是证明定理，而是试图充分理解数学发现中人类是怎样理解与组织有关信息的.这一提法虽然宏大，却也包含着一些无奈.借助计算机证明困难的甚至是新的数学定理这一重要问题，始于王浩50年代末的工作，于80年代初经L.Wos，W.Bledsoe等的努力形成一门独立的学科——自动推理Wos，1985.
1.2Gelernter的几何定理证明机
数学定理证明是典型的智力活动，而几何定理证明则是典型的数学定理证明.古希腊Euclid的《几何原本》不仅是几何定理证明的典范，也为以后西方数学的主要活动——推理提供了一个范本.因此毫不奇怪，几何定理机器证明被选作为定理机器证明最早研究的问题之一.
Newell等的工作是证明逻辑公式.人们很自然想到是否可以用同样的方法解决其他数学问题呢？由于欧氏几何历来被认为是典型的推理问题，能否用计算机证明几何定理自然被提上议事日程.20世纪50年代末IBM公司的Gelernter小组开发了“几何定理证明机”GTPM，成为人工智能的经典工作之一Gelernter，etal.，I960；Koedinger，1990.GTPM基本上采用了Newell等LT的模式，采用后推法+深度优先的证明方法.GTPM的主要贡献是引入了基于几何图形推理的概念，产生了广泛影响.
为了克服搜索空间爆炸问题，Gelernter使用的最主要的启发规则或搜索策略是参照几何命题的图形.从一个（数值）图形，我们可以在如下两方面受益：
A.几何命题的图形可以用作“过滤器对于每一个子目标，我们可以检查该目标在这一数值图形上是否正确.如果正确则继续我们的推理；否则该目标肯定是错误的，我们无需再对它继续推理.这一措施将大大减少搜索空间，因为在基于后推法的证明过程中生成的大多数子目标实际上都是不正确的.但是为了在逻辑上严格证明这一点，可能需要很多层次的推理.这就是产生“搜索空间爆炸”的主要原因.使用图形过滤器，我们就可以把这些错误的子目标及早剔除，使得所有的推理对于所给的具体图形至少是正确的.如果所用的图形不是非常特殊，这一措施可以基本上将多余的推理避免掉.
B.几何命题的图形可以用作方向辨别器在几何定理证明中，我们经常要用到一些方向的概念，比如“内错角”“在某直线同侧”等.涉及这些概念的推导实际上是相当困难的.人们在证明几何定理时往往不严格证明这些方向概念，而是根据一幅图形来得到所需结论.这样做是有一定的理论根据的，但并不十分严格.在Gelernter的证明机中，点、线之间的方向同样由图形提供.
总体讲GTPM效率并不髙，只能证明一些较简单的几何定理.下面的定理是Gelernter证明机解决的最困难的问题.
例1.2.1设ABCD是一个梯形，ABCD，M与N分别是AC与的中点，设E是MN与BC的交点，证明E是BC的中点（图1-2.
图1-2
证明机GTPM不能发现证明.如果增加一个辅助点K=CNnAB，则证明机可以找到一个证明.该证明的基本想法是证明ANBK与ANDC全等.很多事实，如=ZCDB，是由该问题的图形中得到的，而没有严格证明.我们以后还要讨论这一问题.
1.3几何定理机器证明的吴方法
用模拟人的思维方法的方式证明几何定理的主要困难在于：我们并不确切知道几何学家们是怎么样发现这些证明的.实际上，几何定理证明自古被认为需要髙度智慧.一个好的证明往往需要神奇添线、巧妙推理、迂回曲折而达到，而且这一推理过程从根本上讲是无法可循的.Euclid曾对想寻找学习几何捷径的Ptolemy托勒密）国王说：“几何无王者之路始于Gelernter工作的几何定理机器证明虽经很大的改进，一直未能在证明效率方面取得突破，几何定理机器证明的研究逐渐趋于沉寂.
20世纪70年代末，吴文俊教授另辟蹊径，基于与Gelernter方法完全不同的原理提出了“吴方法”，使得几何定理的“机器证明”真正成为可能.吴方法是基于代数计算的证明方法，其基本想法是首先将几何问题转化为代数问题，然后再用符号计算的办法处理相应的代数问题.代数方法的实质在于把通常数学证明中所固有的质的困难性，代之以量的计算复杂性.实验结果证明吴方法效率极髙.吴文俊自己在很简单的计算机上用FORTRAN语言编程证明了诸如Feuerbach定理和Morley定理等初等几何中被认为最困难的定理.大量实验表明，使用吴方法可以快速地证明几乎所有的几何定理.在文献（Chou，1988中收集了用基于吴方法的程序证明的512个几何定理.在文献Wu，1984中收集了用吴方法的程序证明的近百个几何定理.大部分问题的求解时间只有数秒.
吴方法的基本思想可以归结为如下形式：
将几何问题代数化的选择，在一定意义下也是自然的.与几何定理证明的技巧性相反，代数则基本上是算法化的.从数的计算到简单方程的求解，只要遵从某种法则，最终就可以得到结论.因此，早在17世纪，Descartes就已经引进坐标，以便用方程来描述和处理几何问题.
本节将介绍吴方法的一个特殊情形.这种特殊方法可以用来证明构造型几何命题（参看3.2节.这一特殊情形虽然描述简单，却能够证明大量几何定理，且具有下列优点：
1可以自动生成几何形式的非退化条件，而且这些非退化条件是使几何命题为真的充分条件Chouetal.，1992-1.也就是说，如果一个几何定理在这些条件下不正确，则这一几何命题再进一步添加非退化条件也不会正确.对于线性构造型几何命题，这一方法给出一种判定欧氏几何中的几何命题是否为真的充要条件.
2这一特殊方法比吴方法的一般形式有更髙的效率，作为吴方法所能证明的
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
