Мажоритарная функция

[Trotil]

Мажоритарная функция длины $n$ имеет $C_n^{\lceil \frac{n}{2} \rceil}$ дизъюнкций в СДНФ.

Возник интересный вопрос: можно ли записать эту функцию покороче? Можно использовать только скобки, "И", "ИЛИ", "НЕ"

[Xaositect]

Ну сходу придумывается, например, такая конструкция:
$\bigvee\limits_{1\leq i_1<i_2<\dots<i_{\lceil\frac n 2\rceil-1}<n} x_{i_1}x_{i_2}\dots x_{i_{\lceil\frac n 2\rceil-1}}(x_{i_{\lceil\frac n 2\rceil-1}+1}\vee\dots\vee x_n)$
Можно попробовать побольше переменных в скобки засунуть, $\frac n 4$ например.
Интересный вопрос, могут ли здесь отрицания дать что-нибудь полезное для упрощения формулы.
Вообще, оптимизация конкретных функций - это очень интересная, но сложная область. Нижних оценок мало. По теореме Храпченко минимально возможный ранг этой функции $\approx \frac 1 4 n^2$. О теореме Храпченко можно прочитать здесь: http://mathcyb.ru/mediawiki/images/1/10/Dgk_text.pdf