ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ

— построение по заданным объектам эквивалентных объектов в том или ином смысле. Типичными примерами объектов, к которым применяются Э. п., являются алгебраические выражения, алгоритмы, автоматы, схемы контактные, алгоритмов схемы и др. Э. п. играют важную роль в задаче минимизации; полные системы Э. п. являются одной из форм аксиоматизации алгебр, и других систем.

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

Пусть для объектов определено понятие подобъекта, т. е. такой части объекта, которая сама является объектом рассматриваемого вида. Операцией замены с помощью пары операция, дающая по объекту у объект

, получающийся из у заменой к.-л. вхождения подобъекта а объектом (если а не входит в у, то считается, что у совпадает с ). Замыканием относительно замен мн-ва Н пар объектов наз. наименьшее мн-во R такое, - что:

где получается из операцией замены с помощью пары .

Полная система правил для контактных схем.

Наряду с операцией замены обычно рассматривают еще операцию подстановки (над парами объектов), которая состоит в том, что все вхождения некоторого элементарного подобъекта в оба элемента пары заменяются одним и тем же объектом у. Подмножество наз. полным для Е или полной системой правил Э. п., если его замыкание относительно замен и подстановок совпадает с Е. Э. о., замкнутое относительно замен, наз. конгруэнцией. Очевидно, что полное подмножество существует только для конгруэнций, причем подмножество является полным для конгруэнций Е тогда и только тогда, когда любой объект у можно перевести в любой эквивалентный ему объект только операциями замены с помощью пар из R, где R — замыкание R относительно подстановок. В связи с этим пары из конгруэнции Е наз. правилами Э. п., а операция замены с помощью пары применением правила .

Характерным примером описанной подстановки являются Э. п. в алгебрах. Для алгебры произвольной сигнатуры проблема Э. п. совпадает с задачей алгебр, аксиоматизации и состоит в следующем. На мн-ве всех термов сигнатуры Ф рассматривается естественная конгруэнция, т. е. такое э. о. Е, что тогда и только тогда, когда термы представляют одну и ту же ф-цию алгебры . Пары из Е наз. равенствами или тождествами и вместо обычно пишут Операция подстановки состоит в замене всех вхождений некоторой переменной произвольным термом. Требуется найти конечное полное для Е мн-во равенств.

Напр, для булевой алгебры конечную полную систему образуют следующие 10 равенств:

В такой постановке проблема Э. п. имеет положительное решение далеко не для всех алгебр. Известно, что она решается положительно для всех двухэлементных алгебр, а также для всех конечных групп. В то же время для любого существуют алгебры (группоиды) с элементами, для которых эта задача не имеет положительного решения. Существуют также бесконечные группы и конечные полугруппы, для которых указанная задача решается отрицательно. Она решается отрицательно и для алгебры регулярных событий (см. Алгебры событий), возникающей в связи с изучением автоматов конечных. В последнем случае рассмотрены некоторые модификации описанной постановки проблемы Э. п., допускающие положительное решение.

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

Правила , принадлежащие конгруэнции Е, наз. локальными, поскольку их применение сохраняет Е (т. е. переводит объекты в эквивалентные им) независимо от объекта, в котором производится замена подобъекта а объектом . Иногда отсутствие полной системы таких правил вынуждает расширять допустимые средства Э. п. за счет нелокальных правил , применимость которых (т. е. сохранение э. о.) может зависеть от окрестности подобъекта а и, в частности, от объекта в целом. Содержательные примеры нелокальных правил возникают при Э. п. схем алгоритмов. Не существует

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

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

Лит.: Мурский В. Л. Об эквивалентных преобразованиях контактных схем. «Проблемы кибернетики», 1961, в. 5; Янов Ю. И. О системах тождеств для алгебр. «Проблемы кибернетики», 1962, в. 8; Мурский В. Л. О преобразованиях конечных автоматов. «Проблемы кибернетики», 1965, в. 15; Янов Ю. И. О локальных преобразованиях схем алгоритмов. «Проблемы кибернетики», 1968, в. 20; Янов Ю. И. О направленных преобразованиях формул. «Математические заметки», 1969, т. 6, № 6.

Ю. И. Яков.