List of issues > Series «Mathematics». 2010. Vol. 4
On Complexity of a Particular Boolean Functions Class
This paper concerns complexity of polynomial forms (exor-sum-of-pro-ducts) representing Boolean functions. Complexity is defined as a minimal number of summands in exor-sum-of-products for a given function. A class of Boolean functions being the most complex among Boolean functions having 6 or less arguments is considered. The exact complexity for functions of described class having 7 agruments is obtained.
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.