Рассматривается задача представления функций алгебры логики обратимыми схемами, построенными из элементов Тоффоли. Интерес к данной задаче связан с актуальными исследованиями возможности организовать «холодные» вычисления с помощью дискретных преобразователей информации, т. е. такие вычисления, при выполнении которых технические устройства, их реализующие, не выделяли бы тепла.

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

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

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

1. Винокуров С. Ф., Казимиров А. С. Перечисление операторных классов булевых функций // Изв. Иркут. гос. ун-та. Сер. Математика. 2009. Т. 2, № 2. С. 40–55.

2. Винокуров С. Ф., Францева А. С. Приближенный алгоритм вычисления сложности обратимой функции в базисе Тоффоли // Изв. Иркут. гос. ун-та. Сер. Математика. 2011. Т. 4, № 4. С. 12–26.

3. Винокуров С. Ф., Францева А. С. Сложность представлений многовыходных функций алгебры логики // Изв. Иркут. гос. ун-та. Сер. Математика. 2016. Т. 16. С. 30–42.

4. Избранные вопросы теории булевых функций : монография / под ред. С. Ф. Винокурова, Н. А. Перязева. М. : Физматлит, 2001. 192 с.

5. Иркутский суперкомпьютерный центр СО РАН [Электронный ресурс] : сайт. Иркутск : ИДСТУ СО РАН. URL: http://hpc.icc.ru (дата обращения: 05.05.2018).

6. Пат. № 2017619310 Российская Федерация. Программа построения минимального представления многовыходных булевых функций в классе обратимых схем / С. Ф. Винокуров, Л. В. Рябец, А. С. Францева ; опубл. 22.08.17. Бюл. № 9.

7. Рябец Л. В., Винокуров C. Ф. Алгоритм точной минимизации булевых функций в классе кронекеровых форм // Алгебра и теория моделей 4. Новосибирск, 2003. С. 148–159.

8. Knuth D. E. MMIXware: A RISC Computer for the Third Millennium // Springer Heidelberg New York Dordrecht London. 2003. LNCS Sublibrary: SL 2 – Programming and Software Engineering. 550 p. DOI: 10.1007/3-540-46611-8.

9. Fredkin Е., Toffoli T. Conservative Logic // International Journal of Theoretical Physics. 1982. Vol. 21, Iss. 3. P. 219–253. DOI: 10.1007/BF01857727.

10. Toffoli T. Reversible Computing // Automata, Languages and Programming (Series: Lecture Notes in Computer Science). 1980. Vol. 85. P. 632–644. DOI: 10.1007/3-540-10003-2_104.