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

Мультипликативной (или конъюнктивной) сложностью функции алгебры логики $f(x_1, \dots, x_n)$ (соответственно, системы функций алгебры логики $F = \{f_1, \dots, f_m\}$) называется минимальное число элементов конъюнкции в схемах из функциональных элементов в базисе $\{x\& y, x \oplus y, 1\}$, каждая из которых реализует функцию $f$ (соответственно, все функции из системы $F$). Мультипликативную сложность функции $f$ (системы функций $F$) будем обозначать через $\mu(f)$ (через $\mu(F)$). В работе доказано, что $\mu(f) = n-1$, если функция $f(x_1, \dots, x_n)$ представима в виде $x_1x_2\dots x_n \oplus q(x_1, \dots, x_n)$, где $q$ – функция степени два ($n \ge 3$). В работе также доказано, что $\mu(f) \le n-1$, если функция $f(x_1, \dots, x_n)$ представима в виде суммы по модулю $2$ двух мультиаффинных функций. Кроме того, в работе показано, что $\mu(F) = n-1$, если $F = \{x_1x_2\dots x_n, f(x_1, \dots, x_n)\}$, где $f$ – или функция степени два, или мультиаффинная функция. Работа поддержана РФФИ, гранты 13-01-00684-а и 13-01-00958-а.