收稿日期:20110917;修回日期:20111031
作者简介:陈世平(1970),男,四川遂宁人,讲师,博士,主要研究方向为计算机推理技术、智能教育软件(chinshiping@sina.com).
一类三角形几何不等式的自动证明
陈世平
1
,刘 忠
2
(1.四川省商贸学校—中国民航飞行学院德阳校区,四川 德阳 618000;2.四川建筑职业技术学院,四川 德阳
618000)
摘 要:讨论了一类只含三角函数的三角形几何不等式的自动证明问题。运用代数方法将其有理化,在不新增
加根式的条件下将问题转换为一个二元多项式不等式的证明,设计的基于胞腔分解和实根分离的算法实现了二
元多项式不等式的自动证明,输出的证明过程可以手工验证或借助一些数学软件进行理解。实验表明上述算法
对一大批具有相当难度,特别是关于三角函数的几何不等式十分高效,并且能够解决三角形内角的任意有理倍
数函数的不等式机器证明问题。
关键词:几何不等式;可读证明;有理化;实根分离;胞腔分解
中图分类号:TP3 文献标志码:A 文章编号:10013695(2012)05173205
doi
:10.3969/j.issn.10013695.2012.05.035
Automatedprovingforclassoftrianglegeometricinequalities
CHENShiping
1
,LIUZhong
2
(1.DeyangBranchofCivilAviationFlightUniversityofChina&SichuanTradeSchool,DeyangSichuan618000,China;2.SichuanCollegeof
ArchitecturalTechnology,DeyangSichuan618000,China)
Abstract:Thispaperdiscussedtheautomatedprovingforaclassoftrianglegeometricinequalitieswithonlytrigonometric
functions.Withoutnewradicals,itfirstlytransformedtheoriginalinequalitytoatwovariablepolynomialoneusingalgebraic
methodfirstly.Andthenitimplementedanalgorithmbasedoncelldecompositionandrealrootisolationtoprovethetwovaria
blepolynomialinequalities
,andtheoutputwasreadableorcouldbeunderstoodwiththehelpofmathematicsoftware.Experi
mentsshowthattheabovemethodscanproveanextensiveclassofgeometricinequalitieswithgreatdifficultyautomaticallyand
aremuchefficientespeciallyfortheinequalitieswithonlytrigonometricfunctions.Furthermore
,thealgorithmissuitfortrian
glegeometricinequalitieswitharbitraryrationalcoefficientsofinteriorangles.
Keywords:geometricinequalities;readableproof;rationalization;realrootisolation;celldecomposition
!
引言
三角形几何不等式是自动推理领域中一个十分困难的研
究课题,传统的方法是将每一个几何变量转换为等价的代数表
达式,但这些代数表达式一般都带有根式,对待根式一般是利
用一 些 消 去 手 段 (如 Grobner基 法
[1]
、Wu方 法
[2]
、结 式 方
法
[3]
)寻找其边界多项式,然后再对边界多项式进行胞腔分
解,对每一胞腔选择样本点,最后将样本点回带入根式检验,这
类方法是完备的
[1~5]
。对于根式不等式的处理,徐嘉等人在杨
路教授工作的基础上,提出了“去根号 +逐次差分代换”的方
案,解决了形如 u
1/m
1
+u
1/m
2
+… +u
1/m
n
≤
t
1/m
的不等式证明中的
去根号问题,将原不等式等价为若干个有理不等式组,再运用
杨路教授提出的逐次差分代换方法证明
[6~8]
。其中有一大类
三角形不等式等价的代数不等式具有
槡
u
+
槡
v
+
槡
w
≤
槡
t
的形式,
运用初等数学的方法将其有理化再与逐次差分代换方法结合
也可实现此类不等式的自动证明
[9]
。该类方法虽然不是完备
的,但能够证明大量具有相当难度的几何不等式。然而一般来
说,处理根式常常需要较大的复杂度,机器运行需要大量的时
间,并且有些几何变量直接转换为代数表达式还可能出现多重
根式,上述方案更难于处理。例如最近有学者提出三角形内角
的四分之一函数不等式的自动证明问题
[10~13]
,直接转换为代
数表达式就带有多重根号,目前的不等式证明软件暂时都还没
有涉及。同时目前的一些不等式证明软件对于一般的三角形
不等式还难以输出易于阅读的、有几 何 或 代 数 意 义 的 证 明
过程。
本文把目标限制在一类只含三角函数的三角形不等式
(当然几乎所有的三角形不等式都可以转换为此类不等式),
探讨如何解决其机器证明及其可读证明的自动生成问题。首
先运用三角公式将目标不等式转换为三角形的两个内角的正
切函数的函数,且同一内角出现在不同正切函数内的系数相同
(归一化),再利用变量代换将其转换有理式,这样就将问题转
换为一个二元多项式不等式的证明,且在处理过程中不会产生
新的根式。关于二元多项式不等式的证明利用杨路教授的胞
腔分解“初等化”的思想
[14]
,将问题转换为一组单变量多项式
的实数解的判定问题,产生的证明过程可以手工验证或借助一
些数学软件理解,是不等式一定程度上的“明证”。实验表明
算法对一大批具有相当难度,特别是关于只含三角函数的几何
不等式(如文献[
15]中第 2章的不等式和文献[16]中第 4章
的 1.2节中不等式)十分高效,同时能够解决三角形内角的任
意有理数倍数函数不等式机器证明问题,特别地,能够证明三
第 29卷第 5期
2012年 5月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol29No5
May2012