Нормальная форма для чисел, определенных радикалами?

Question

Я пишу небольшую систему компьютерной алгебры, которая позволяет выполнять основные арифметические операции и радикалы. Таким образом, выражения представляют собой двоичные деревья, где внутренние узлы являются операторами + - * / ^ и листья рациональные числа. Теперь я хочу, как и другие CAS, упростить выражения, например,

(5+sqrt(2)+sqrt(8)) / (1+sqrt(2)) = 1 + sqrt(8)

Если вы начнете с левой стороны, не очевидно, что вы можете переписать его в RHS. Так как же это делают другие CAS? Существует ли нормальная форма этих выражений, так что каждое выражение может быть однозначно записано в нормальной форме? И есть ли детерминированный алгоритм, который переписывает любое выражение в нормальную форму?

Answer 1

Я не знаю, как создаются CAS, но я думаю, что процедура упрощения может быть выполнена с помощью поиска в пространстве состояний. У вас может быть набор правил, как транскрибировать одно выражение в другой эквивалент. Применения этих правил - ребра в графе поиска, а узлы - деревья выражений. Затем вы можете выполнить поиск в этом графике, чтобы найти наименьшее возможное дерево (или достаточно маленькое, или, возможно, такое, где никакое правило не может быть применено далее).

Более простой задачей может быть процедура дифференциации, которая на самом деле только применяет правила без (почти) необходимости фактически выполнять какой-либо поиск. Это может быть очень легко написано на прологе (хотя я никогда не делал этого, только наш преподаватель пролога в университете сказал нам).