Распознавание алгебраического тождества

До сих пор исходными данными для рассматриваемых нами алгоритмов были числа или группы чисел. Рассмот­рим теперь другие алгоритмы, исходными данными ко­торых являются алгебраические выражения. Ограничим­ся простейшим случаем целых рациональных алгебраи­ческих выражений, т. е. таких, в которых предусмотрены только действия сложения, вычитания, умножения и воз­ведения в целую положительную степень.

Прежде всего строго определим, что мы понимаем под целым рациональным алгебраическим выражением (бу­дем его в данном параграфе для краткости называть про­сто выражением). Для этого приведем следующее рекур­сивное определение:

1) буквой будем называть строчную букву латинского алфавита; числами будем называть общепринятые деся­тичные дроби (в частности, целые числа) и обыкновенные дроби, как положительные, так и отрицательные;

2) элементарным выражением называется либо буква, либо число, записанное без знака (значит, положитель­ное), либо произвольное выражение, заключенное в скоб­ки (круглые);

3) множителем называется либо элементарное выра­жение, либо элементарное выражение, возведенное в це­лую положительную степень;

4) одночленом называется либо множитель, либо одно­член, за которым стоит знак умножения и множитель;

5) многочленом, или выражением называется либо од­ночлен, либо одночлен, перед которым поставлен знак +, либо одночлен, перед которым поставлен знак –. либо многочлен, после которого приписан знак + или знак —, а затем приписан одночлен.

Это рекурсивное определение устанавливает нам со­вершенно точно структуру записи, которая называется выражением.

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

Подобными называются уже упрощенные одночлены, отличающиеся, может быть, только коэффициентами. Их приведение заключается в том, что вычисляют алгебраи­ческую сумму коэффициентов и заменяют их одночле­ном, перед которым стоит знак этой суммы, коэффици­ент равен ее абсолютному значению, а буквенная часть такая же, как буквенная часть любого из приводимых одночленов. Если алгебраическая сумма окажется равной нулю, то результатом приведения будем считать +0.

Операция раскрытия скобок не требует пояснения.

Алгоритм распознавания тождества двух выражений очень прост.

1. Второе из выражений заключить в скобки, перед открывающей скобкой поставить знак — и все это при­писать к первому выражению. Полученное выражение будем называть W. Перейти к п. 2.

2. Просматривать W слева направо и искать такую па­ру скобок, внутри которой больше нет скобок. Если такая пара найдется, перейти к п. 3, если не найдется, то перей­ти к п. 6.

3. Проверить, стоит ли вверху справа от закрывающей скобки показатель степени больше 1. Если стоит, перейти к п. 4, иначе перейти к п. 5.

4. Возвести выражение, стоящее в скобках, в соот­ветствующую степень, пользуясь правилом умножения многочленов. Зачеркнуть после этого показатель степени, который стоит после закрывающей скобки. Перейти к п. 5.

5. Раскрыть рассматриваемую пару скобок. Именем W впредь называть получившееся при этом новое выра­жение. Вернуться к п. 2.

6. Просматривая W слева направо, последовательно упростить все входящие в него одночлены. Перейти к п. 7.

7. Первый одночлен, входящий в W, будем в дальней­шем называть U. Перейти к п. 8.

8. Просматривая W, начиная с одночлена, следующего за U, искать одночлены, подобные U. Отмечать их. После конца просмотра привести их вместе с U, полученный результат записать вместо U и считать обозначенным этой буквой. Помеченные одночлены вместе с принадлежащими им знаками зачеркнуть. Выражение, которое после этого получится, впредь именовать W. Перейти к п. 9.

9. Если U не является предпоследним или последним в W, то перейти к п. 10, иначе к п. 11.

10. Найти в W многочлен, непосредственно следующий за U, и в дальнейшем называть его именем U. Вернуться к п. 8.

11. Если W состоит из нуля или является алгебраиче­ской суммой нулей, то перейти к п. 12, иначе к п. 13.

12. Сравниваемые многочлены между собой тождест­венны. Конец процесса.

13. Сравниваемые многочлены между собой не тож­дественны. Конец процесса.

Интересной особенностью данного алгоритма является наличие в нем двух «концевых» пунктов.

Рассмотренный алгоритм решает задачу распознавания тождества алгебраических целых рациональных выраже­ний. О задачах, для решения которых существует алгоритм, говорят, что они разрешимы. До сих пор мы рассматри­вали только разрешимые задачи (так как каждый раз нам удавалось найти решающий алгоритм).

Корректность алгоритма вытекает из того, что дейст­вия, которые выполнялись над выражением W, не изме­няли ни для каких возможных значений букв значения выражения W.