几何定理可读证明的自动生成

用计算机能生成几何定理的易为人们理解的证明吗？这个几十年来进展很小的难题,自１９９２年以来有了突破性进展,对于一大类欧几何命题－构造几何例题,已有了相当有效的算法,基于此算法所编制的程序,已证明了５００多非平凡的几何例题,对其中大多数例题,机器自动生的证明是简明而易于理解的,本文是对这一领域近三年来取得的进展的综述,包括了在非欧几何可读证明方面的最新成果。     

多项式等式型几何定理的可读证明

目前的智能几何软件都使用基于搜索法的定理证明器作为推理引擎,其主要缺点是不能可读地证明涉及到几何量代数运算的几何定理,这极大地限制了智能几何软件的实际应用.对一类结论为几何量多项式等式的几何定理,文中提出了一种能给出可读证明的启发式搜索算法.该算法通过引入多项式的变形操作算子——标准项代换,把证明结论为多项式等式g=0的几何定理转化为寻找从g到0的标准项代换序列的搜索问题.采用Lisp语言实现了该算法,并做了30个结论为几何量等式的几何定理的推理实验.实验结果表明算法具有较高的推理效率.     

几何定理机器证明的强正常升列分解算法

自上个世纪70年代吴文俊的开创性工作以来，几何定理机器证明这个曾被深人研究而停滞不前的分支在自动推理领域变得异常活跃，大量学术论著相继出现。国内外众多学者，如Chou，Koand Hussain，Wangand Gao，Wang，Zhang，Yangand Hou等提出了各种成功的有效的几何定理机器证明算法。这些方法及其变形已由多位学者实施，使用不同的证明器已经获得了大量几何定理的机器证明。这些定理包括(广义)：史坦纳定理；摩勒三分角线定理以及最近确认的泰博猜想。     

几何定理自动证明的一种数值测试辅助算法

基于数据挖掘中的聚类分析思想提出一种借助数值测试判断几何图形之间关系，以简化定理自动证明中搜索过程的新方法，该方法已成功地应用于作者参与开发的平面几何教育软件中，达到了加速推理引擎的目的。     

基于面向对象的几何定理自动证明系统设计与实现

针对几何定理自动证明的前推法实现方式,结合面向对象编程工具的特点,实现了一个原型系统。该系统结构简单、清晰,可扩展性强,并能产生可读证明过程。实例分析说明了该原型的有效性。     

基于复数法的几何定理可读机器证明

已有的机器证明方法在处理一些涉及大规模符号运算的几何问题时,常因算法复杂度过高或机器能力的限制,有时并不能在合理时间内实现可读机器证明. 故提出了复数法这一新的几何定理机器证明算法,并选用符号计算功能较为强大的软件Mathematica创建了新证明器CNMP(complex number method prover).新提出的复数法能有效地解决构造型几何命题,对用于测试与评价几何定理证明器性能的综合性平台TGTP(thousands of geometric problems for geometric theorem provers)上的180个几何问题的实验结果表明,CNMP的解题能力与运行效率均令人满意.尤其是对于一些具有相当难度的几何定理,如五圆定理、Morley定理、Lemoine圆定理、Thebault定理、Brocard圆定理等,CNMP均能在短时间内给出可读机器证明.     

基于前推法的几何信息搜索系统

我们提出并实现了几何信息搜索系统，它可用于找出所给几何图形的“所有”性质，记ＧＰ为一给定的几何谓词之集，ＬＭ为涉及ＧＰ中谓词的某些几何引理之集。若ＬＭ中的引理不引入新的几何元素，则用ＧＩＳＳ能找出所有能由ＬＭ中引理推出的身体性质。     

本体推理在几何定理机器证明中的应用

文中阐述了平面几何定理机器证明的基本原理及方法,针对几何定理机器证明过程中可读证明的产生,及推理信息快速增长的问题,提出了一种基于本体推理的几何定理机器证明方法。通过具体案例,描述了以Protégér软件为工具,基于WordNet重用的领域本体半自动构建方法,构建几何本体模型的过程,并结合Prolog规则进行双向推理。结果表明将本体引入几何定理机器证明是可行的,且本体推理脱离了代数形式,使得推理过程更接近自然语言的描述,同时推理效率更高。     

质点法机器证明视角下的近世几何研究

优化并发展了质点法机器证明算法的核心程序,用Mathematica创建了新的几何定理证明器。拓展了机器证明的研究范畴,首次实现了近世几何的机器证明,且可读性令人满意。在该证明器的帮助下,发现了一些新的近世几何性质,深化了近世几何的研究成果,并对已有的近世几何研究成果提出一些意见。     

应用本体和AllegroGraph实现几何定理证明

由于传统的定理机器证明方法是基于规则的,使得定理证明出现几何信息增长迅猛,推理和计算效率低以及过程可读性差等问题。针对以上情况,提出了基于本体和AllegroGraph的几何定理证明方法。该方法通过本体构建几何定理命题模型,然后采用Prolog规则描述语言对几何定理性质进行描述,同时通过分析本体模型和规则描述的对应关系,提出定理规则半自动生成方法。最后以AllegroGraph（ AG）图形数据库的推理机制为基础,完成几何定理证明。实验结果表明,将本体和AllegroGraph推理机应用于几何定理证明领域可以摆脱以往几何定理证明代数化问题,几何证明过程容易理解,同时合理地控制了信息的增长,支持定理可持续证明。     

A New Approach for Automatic Theorem Proving in Real Geometry

We present a new method for proving geometric theorems in the real plane or higher dimension. The method is derived from elimination set ideas for quantifier elimination in linear and quadratic formulas over the reals. In contrast to other approaches, our method can also prove theorems whose complex analogues fail. Moreover, the problem formulation may involve order inequalities. After specification of independent variables, nondegeneracy conditions are generated automatically. Moreover, when trying to prove conjectures that – apart from nondegeneracy conditions – do not hold in the claimed generality, missing premises are found automatically. We demonstrate the applicability of our method to nontrivial examples.     

Vectorial Equations Solving for Mechanical Geometry Theorem Proving

In this paper a new method is proposed for mechanical geometry theorem proving. It combines vectorial equations solving in Clifford algebra formalism with Wu"s method. The proofs produced have significantly enhanced geometric meaning and fewer nongeometric nondegeneracy conditions.     

A Deductive Database Approach to Automated Geometry Theorem Proving and Discovering

We report our effort to build a geometry deductive database, which can be used to find the fixpoint for a geometric configuration. The system can find all the properties of the configuration that can be deduced using a fixed set of geometric rules. To control the size of the database, we propose the idea of a structured deductive database. Our experiments show that this technique could reduce the size of the database by one hundred times. We propose the data-based search strategy to improve the efficiency of forward chaining. We also make clear progress in the problems of how to select good geometric rules, how to add auxiliary points, and how to construct numerical diagrams as models automatically. The program is tested with 160 nontrivial geometry configurations. For these geometric configurations, the program not only finds most of their well-known properties but also often gives unexpected results, some of which are possibly new. Also, the proofs generated by the program are generally short and totally geometric.     

半扩展规则下分解的定理证明方法

基于扩展规则的定理证明方法在一定意义上是与归结原理对偶的方法,通过子句集能否推导出所有极大项来判定可满足性.IER(improved extension rule)算法是不完备的算法,在判定子句集子空间不可满足时,并不能判定子句集的满足性,算法还需重新调用ER(extension rule)算法,降低了算法的求解效率.通过对子句集的极大项空间的研究,给出了子句集的极大项空间分解后子空间的求解方法.通过对扩展规则的研究,给出了极大项部分空间可满足性判定方法PSER(partial semi-extension rule).在IER算法判定子空间不可满足时,可以调用PSER算法判定子空间对应的补空间的可满足性,从而得到子句集的可满足性,避免了不能判定极大项子空间可满足性时需重新调用ER算法的缺点,使得IER算法更完备.在此基础上,还提出DPSER(degree partial semi-extension rule)定理证明方法.实验结果表明:所提出的DPSER和IPSER的执行效率较基于归结的有向归结算法DR、IER及NER算法有明显的提高.     

支持用户自定义谓词的自动定理证明的研究

在先前设计的一个出具证明编译器原型基础上,增加了可用来描述数据结构性质的自定义谓词,对断言语言表达能力方面做了提升.在出具证明编译器的框架内,借助自动定理证明技术,针对自定义谓词的特点,设计了专门的推理规则,由此实现自定义谓词专用的自动定理证明器原型,并将它并入系统原来的自动定理证明器中.该原型可以用来证明操作单链表、二叉树等共享数据结构的程序的性质,其程序规范中可以使用自定义谓词描述数据有序性、链表长度等性质.     

一种新的基于扩展规则的定理证明算法

基于扩展规则的定理证明方法是一种与归结方法互补的新的定理证明方法,首先通过对扩展规则的深入研究,给出了扩展规则的一个重要性质,设计并实现了该性质的判定算法.此外,从理论上分析及证明了该判定算法的时问和空间复杂性.基于此,提出了一种新的基于扩展规则的定理证明算法NER,将判定子句集可满足性问题转化为一系列文字集合的包含问题,而非计数问题.实验结果表明,算法NER的执行效率较原有扩展规则算法IER和基于归结的有向归结算法DR有明显提高,有些问题可以提高两个数量级.     

Theorem Proving Based on the Extension Rule

Methods based on resolution have been widely used for theorem proving since it was proposed. This paper presents a new method for theorem proving that uses the inverse of resolution and employs the inclusion-exclusion principle to circumvent the problem of space complexity. We prove its soundness and completeness. The concept of complementary factor is introduced to estimate its complexity. We also show that our method outperforms resolution-based methods in some cases. Thus it is potentially a complementary method to resolution-based methods. This revised version was published online in August 2006 with corrections to the Cover Date.     

GRAMY: A Geometry Theorem Prover Capable of Construction

This study investigates a procedure for proving arithmetic-free Euclidean geometry theorems that involve construction. Construction means drawing additional geometric elements in the problem figure. Some geometry theorems require construction as a part of the proof. The basic idea of our construction procedure is to add only elements required for applying a postulate that has a consequence that unifies with a goal to be proven. In other words, construction is made only if it supports backward application of a postulate. Our major finding is that our proof procedure is semi-complete and useful in practice. In particular, an empirical evaluation showed that our theorem prover, GRAMY, solves all arithmetic-free construction problems from a sample of school textbooks and 86% of the arithmetic-free construction problems solved by preceding studies of automated geometry theorem proving.