如何实现三角身份证明算法

Question

我如何实现一个接受三角方程两侧的程序（可以推广到任何东西，但现在我将只保留三角恒等式）并且该程序将输出转换一个方程的步骤一边到另一边（或将它们都转换）以表明它们实际上是相等的。该程序将假定它们首先是相等的。我对如何实现算法来执行此操作感到非常困惑。我的第一个想法是与图表有关，但我想不出除此之外的任何事情。从那里，我认为我应该首先将等式的两边解析为树。例如 (cot x * sin) / (sin x + cos x) 看起来像这样：

     division
     /    \
    *      +
  /  \    / \
cot sin sin cos

在此之后，我有两个类似的想法，都存在问题。第一个想法是选择叶子数量最少的一侧，并尝试通过使用由 "tree regexs." 表示的等效项将其操纵到另一侧，这些 "tree regexs" 的示例将是 csc = 1 / sin 或 cot = cos / sin（当然是树形），等等。我的第二个想法是选择叶子较多的一侧，并尝试找到一些表达式，当乘以该表达式时等于另一侧。使用倒数这不会太糟糕，但是，我必须证明我乘以等于 1 的结果。我又回到了这个 "tree regex" 事情。

这两者的主要缺陷在于 order/how 我可以应用这些替换。是只需要一堆 if 语句还是有更优雅的解决方案？实际上是否有我没有看到的基于图形的解决方案。 什么（如果有的话）可能是证明三角恒等式的好算法。

明确地说，我不是在谈论 "solve for x" 类型的问题，例如 tan(x)sin(x) = 5，找到 x 的所有值，而是证明 sqrt((1 + sin x) / (1 - sin x)) = sec x + tan x

Answer 1

这是一个用于确定三角恒等式的简单算法，可以采用 polynomial(sin x, cos x) = 0 :

的形式

通过明显的替换 (tan x -> (sin x)/(cos x), ..., sin 2x -> 2 (sin x) (cos x), ...)
通过对（孤立的）根求平方将恒等式转换为多项式（不过，去除恒等式中的多个根可能很棘手），乘以分母并将所有扩展项放在一边
将多项式（cos^3 x = (cos^2 x)(cos x)、cos^4 x = (cos^2 x)(cos^2 x)、...）中的所有项cos^2 x替换为1 - sin^2 x并展开多项式。
最后计算出一个没有cos^2 x的多项式。如果它与 0 相同，则身份被证明，否则身份不成立。

你的例子sqrt((1 + sin x)/(1 - sin x)) = sec x + tan x:

使用替换 sec x -> 1/(cos x) 和 tan x -> (sin x)/(cos x) 我们得到

sqrt((1 + sin x)/(1 - sin x)) = 1/(cos x) + (sin x)/(cos x).

为简洁起见，让我们写 s 而不是 sin x 和 c 而不是 cos x，这给我们：

sqrt((1 + s)/(1 - s)) = 1/c + s/c

对方程求平方并将两边乘以(1 - s)c^2我们得到

(1 + s)c^2 = (1 + s)^2(1 - s)。

展开括号并将所有内容都放在一边，我们得到

c^2 - sc^2 + s^3 + s^2 - s - 1 = 0

将c^2 = 1 - s^2代入我们得到的多项式

(1 - s^2) - s(1 - s^2) + s^3 + s^2 - s - 1 扩展为 0.

至此身份证明。

Answer 2

寻找有关计算机代数的课本（我没有），我相信你会在那里找到聪明的想法。

我的方法是基于图的搜索，因为我怀疑转换的线性应用能否可靠地得出解决方案。

按照您已经开始的方式将整个方程表示为表达式树，但包括上面的 "equals" 节点。

对于搜索图视图，将一棵表达式树作为一个搜索状态。搜索目标是一个可判定的表达式树，如 1=1 或 1=0。搜索时（扩展搜索状态），通过对表达式应用等价转换来创建子状态（对我来说，类似正则表达式的听起来很合理）。定义计算表达式整体复杂性的评估函数（例如表达式树中的节点数）。进行定向搜索，最小化求值函数（首先展开复杂度最低的表达式），从而简化表达式，直到达到可判定的形式。

根据表达式，不受限制的搜索很可能永远不会终止。我不知道你会如何处理，也许是通过将允许的表达式复杂性限制为原始表达式的某些倍数。这将无限期地降低运行的风险，但会给您留下悬而未决的案例。

如何实现三角身份证明算法

How to Implement a Trig Identity Proving Algorithm

algorithm

tree

graph

symbolic-math

data-structures