В работе исследуется вопрос сложности логических схем, реализующих функции алгебры логики. Реализация функций алгебры логики рассматривается в классе логических схем, называемых обратимыми. Для построения обратимых схем используются элементарные обратимые схемы, известные под названием элементов Тоффоли. За исключением двух функций одного аргумента, все функции алгебры логики не являются обратимыми. Однако их можно моделировать так называемыми многовыходными функциями, у которых число выходов совпадает с числом аргументов и которые являются перестановками на множестве наборов аргументов. В работе использовано представление функций алгебры логики многовыходными функциями. Многовыходные функции, в свою очередь, реализованы обратимыми схемами в базисе Тоффоли. Для функции схема, ее реализующая, неопределена однозначно. Это позволяет определить сложность функции, как сложность минимальной схемы, реализующей эту функцию. В представленных результатах решена задача нахождения сложности самой сложной функции или функции Шеннона для класса всех функций алгебры логики в классе обратимых схем в подмножестве базиса Тоффоли. Решение этой задачи сведено к решению задачи нахождения функции Шеннона для класса булевых функций в классе полиномиальных форм, называемых расширенными полиномами Жегалкина. Для решения задачи нахождения функции Шеннона для класса булевых функций в классе расширенных полиномов Жегалкина построены последовательности множеств функций по количеству аргументов. Для функций в этих множествах найдена сложность их полиномиальных представлений и доказано, что эти функции имеют максимальную сложность среди всех функций в классе расширенных полиномов Жегалкина.

MSC

94C10

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

2. Винокуров С. Ф. Сложность булевых функций в некоторых классах обратимых схем / С. Ф. Винокуров, А. С. Францева // Материалы XVIII междунар. школы-семинара «Синтез и сложность управляющих систем» им. акад. О. Б. Лyпанова, Пенза, 28 сент. – 3 окт. 2009 г. / под ред. О. М. Касим-Заде. – М. : Изд-во механ.-мат. фак. МГУ, 2009. – С. 20–22.

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

4. Toffoli T. Bicontinuous Extensions of Invetible Combinatorial Functions / T. Toffoli // Mathematical Systems Theory. – 1981. – Vol. 14. – P. 13–23.

5. Toffoli T. Reversible Computing / T. Toffoli // Automata, Languages and Programming (Series: Lecture Notes in Computer Science). – Springer Berlin Heidelberg, 1980. – Vol. 85. – P. 632–644.