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

[Uta]

то есть к 2 в тепени n добавляется ещё ф-ия, переменные кот. 0 - т.е как бы добавляется ещё одна строчка, да?

[juna]

Фунция из одних нулей на выходе также монотонная, но мы ее в количестве $2^n$ не посчитали. А в этом количестве ставим единицы, начиная снизу. Сколько единиц можно поставить?

[maxal]

AD писал(а):

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

все верно, вопрос открытый: A000372

[id]

Uta
Если говорить о порядке, описанном juna, то надо представить себе таблицу истинности, состоящую из $2^n$ строк, в которую нужно поставить одну единичку так, что все следующие значения будут определены. Но есть еще одна монотонная функция,в которую ставить как раз не надо.

[Uta]

2 в степени n что ли?

[juna]

Uta писал(а):

2 в степени n что ли?

Естественно, исходя из нашего определения монотонных функций.

[Uta]

juna, спасибо большое! и всем остальным тоже)

[Коровьев]

Видимо, алгоритм есть. Я его не знаю.Да и булевку тож.
Из задачника Г.П.Гаврилова.
Задача 5.24.
$m(n)$ - число монотонных функций от $n$ переменных
$m(1)=3$
$m(2)=6$
$m(3)=20$
$m(4)=186$

[maxal]

Коровьев, их число известно вплоть до $n=8$, а дальше - увы.
Я уже давал ссылку, повторю еще раз:
A000372

[luitzen]

Помню, что $2^ {C^{[n/2]}_{\;\;\;n}}<\psi(n) < 3^ {C^{[n/2]}_{\;\;\;n}}$, где $[\alpha]$ — целая часть числа $\alpha$. Проблема нерешённая, довольно престижная и носит имя Дедекинда.

В седьмом «Кибернетическом сборнике» нашёл статью Клейтмена.

Предлагаю гнать вопрошающего в шею. Сам он интересоваться таким вопросом не может, преподаватель ему его тоже задать не мог. Следовательно, издевается.

[Коровьев]

luitzen писал(а):

Обозначим число монотонных функций от n переменных через $\psi(n)$. Помню, что

$$2^ {C^{[n/2]}_{\;\;\;n}}<\psi(n) < 3^ {C^{[n/2]}_{\;\;\;n}}$$

, где $[\alpha]$ — целая часть числа $\alpha$. Проблема нерешённая, довольно престижная и носит имя Дедекинда.

Вроде бы в каком-то из «Кибернетических сборников» много боролись за улучшение верхней оценки.

Завтра постараюсь подыскать ссылки или вспомнить побольше

Предлагаю гнать вопрошающего в шею. Сам он интересоваться таким вопросом не может, преподаватель ему его тоже задать не мог. Следовательно, издевается.

Да, именно эта оценка сверху и с низу приведена у Гаврилова в "Сборнике задач по дискретной математике"
Жаль только, что решение не приведено, дескать, докажите, а как - не знаю. Решения-то не приведено.

[Профессор Снэйп]

maxal писал(а):

AD писал(а):

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

все верно, вопрос открытый
http://www.research.att.com/~njas/sequences/A000372

+1

У меня друг на четвёртом курсе считал $F(8)$ в дипломной работе, для чего писал какую-то прогу, которая целых два часа эти вычисления и производила.

$F(n) =$ количество монотонных $n$-местных булевых функций $=$ количество порядковых идеалов в $n$-мерном кубе $=$ количество элементов свободной дистрибутивной решётки с $n$ образующими $=$ количество различных днф от $n$ переменных (без операции отрицания).

Задача точного вычисления $F(n)$ вроде бы даже имеет важное практическое значение для каких-то там сетей. Проблема нахождения формулы для $F(n)$ известна как "проблема Дедекинда", ей более ста лет

[Uta]

Не надо меня гнать в шею!
Я ж просто за пормощью обратилась и никому не парю мозг! Преподавательпросто спонтанно придумал задачку и задал нам. Вот.

[RIP]

Он, наверное, так пошутил.

[maxal]

luitzen писал(а):

Сам он интересоваться таким вопросом не может, преподаватель ему его тоже задать не мог.

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

// переношу в корень форума