«Математика» 2010 4

О сложности одного класса булевых функций

Авторы: С. Ф. Винокуров, А. С. Казимиров
Аннотация:

В работе исследуется сложность представления булевых функций в классе полиномиальных нормальных форм, которая определяется по числу слагаемых в минимальном полиноме. Рассматривается класс булевых функций, которые имеют наибольшую сложность среди всех функций от 6 переменных и менее. Получено точное значение сложности функций этого класса, зависящих от 7 переменных.
Ключевые слова: булевы функции, полиномиальные формы, операторные формы, минимизация, сложность
УДК: 519.716.322
Литература: 1. Балюк А. С. Нижняя оценка сложности одной последовательности булевых функций в классе полиномиальных нормальных форм / А. С. Балюк // Синтез и сложность управляющих систем : материалы XII междунар. шк.-семинара. – М. : Изд-во ЦПИ при мех.-мат. фак. МГУ, 2001. – Ч. 1. – С. 18–21.
2. Винокуров С. Ф. Перечисление операторных классов булевых функций / С. Ф. Винокуров, А. С. Казимиров// Изв. Иркут. гос. ун-та. Сер.: Математика. – 2009. – Т. 2, № 2. – С. 40–55.
3. Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций / К. Д. Кириченко // Синтез и сложность управляющих систем : материалы XII междунар. шк.-семинара. – М. : Изд-во ЦПИ при мех.-мат. фак. МГУ, 2001. – Ч. 1. – С. 115–120.
4. Рябец Л. В. Нахождение минимальных полиномов булевых функций с использованием специальной операторной формы / Л. В. Рябец // Технологии Microsoft в теории и практике программирования. – Новосибирск, 2006. – С. 215–217.
5. Even S. On minimal modulo 2 sums of products for switching function / S. Even, I. Kohavi, A. Paz // IEEE Trans. Elect. Comput. – 1967. – P. 671–674.
6. Gaidukov A. Algorithm to derive minimum ESOPs for 6-variable functions / A. Gaidukov // Proceedings of the 5th International Workshop on Boolean Problems 2002, Freiberg, Germany, Sept. 19–20, 2002. – P. 141–148.
7. Koda N. An Upper Bound on the Number of Products in Minimum ESOPs / N. Koda, T. Sasao // Workshop in Application of the Reed-Muller Expansion Apllication in Circuit Design. – Japan, 1995. – P. 94–101.