Число n-местных монотонных булевых функций

[Uta]

Помогите решить задачку по дискретке!!!
Сколько существует n-местных монотонных булевых функций?

[id]

Попробуйте начать с оценок, например, оценить число несравнимых попарно наборов и отсюда посмотреть, что получится. Это будет оценка снизу.

Точной формулы от n, определяющей число таких функций, даже не встречал.

[cepesh]

cepesh:

Uta, если вы еще раз заведете дублирующую тему, Вы будете забанены. Читайте правила форума.

Название темы изменено с "Пожалуйста, не проходите мимо) Помогите, пожалуйста!" на "Число n-местных монотонных булевых функций"

[AD]

По-моему, где-то я слышал, что это открытый вопрос. Но, может быть, я и путаю - давно это было.

[juna]

Oтнюдь, ничего открытого: $2^n+1$.

[AD]

А что же тогда открытое было?

[Uta]

juna, скажи пожалуйста, а откуда эта формула? как её вывести?Очень важен сам процесс решения! Пожалуйста!

[juna]

Начните c ответа на следующие вопросы:
1.Сколько строк в таблице истинности от $n$ переменных
2. Что такое монотонные булевы функции

[id]

juna
А относительно какого порядка? Ваш ответ описывает число функций, монотонных относительно порядка, в котором двоичный набор a меньше двоичного набора b тогда и только тогда, когда задаваемые ими десятичные числа находятся в данном соотношении.

А что если порядок другой?
Скажем, покомпонентный? ( Для которого и доказывается лемма о немонотонной ф-ии и т.п. )

[RIP]

Что-то я сомневаюсь, что это количество считается (разве что в виде какой-нибудь страшной суммы). Мы как-то на семинаре по дискре полпары доказывали оценку сверху вида $2^{c\binom n{\lfloor n/2\rfloor}}$ (оценка снизу $\geqslant2^{\binom n{\lfloor n/2\rfloor}}$ тривиальна).

[Uta]

строк в таблице - 2 в степени n, а монотонные - ф-ии, для которых определено отношение порядка... А почему 2 ^n +1? единица откуда берётся?

[id]

Uta
А Вы скажите, какой там порядок.

[Uta]

про порядок ничего не сказано. просто найти число n-местных функций для всех возможных n

[juna]

Давайте все-таки начнем с определения монотонных булевых функций.
Я имею в виду следующее определение
Функция монотонна, если она не убывает при возрастании своих аргументов.
Т.е. если составлять таблицу истинности с нулевых значений переменных, и двигаться сверху вниз, то если встретили единицу на выходе, ниже должны быть единицы.

[id]

Uta
Так как найти это число, если не известно какой порядок? Порядок разный - число таких функций будет разным...

Как легко доказать, для естественного порядка на двоичных числах это будет ответ, данный juna.

А вот если порядок покомпонентный... то не знаю.
Причем привычные теоремы ( скажем, лемма о немонотонной ф-ии, используемая в док-ве теоремы Поста ) доказываются именно для него. И, что вполне может быть, число монотонных ф-ий для него найти не так просто.

Поэтому вопрос "Какой порядок?" весьма важен.

juna
Ну да, для такого порядка все просто... А если он другой?