2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Мажоритарная функция
Сообщение12.03.2009, 22:41 
Аватара пользователя
Мажоритарная функция длины $n$ имеет $C_n^{\lceil \frac{n}{2}  \rceil}$ дизъюнкций в СДНФ.

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

 
 
 
 
Сообщение12.03.2009, 23:19 
Аватара пользователя
Ну сходу придумывается, например, такая конструкция:
$\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

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group