Сложность представлений многовыходных функций алгебры логики

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