Мощность класса монотонных б.ф.

[Wynardtage]

В конспекте вижу:

Цитата:

Теорема (о мощности класса монотонных б.ф.)
$ 2^{n\choose \lfloor \frac{n}{2} \rfloor} \le |M| \le 3^{n\choose \lfloor \frac{n}{2} \rfloor} $
/ Без доказательства /

А разве мощность монотонных функций не равна $ 2^n + 1 $? Мои рассуждения: подсчитываем количество монотонных функций: $ (0,\ 0,\ 0, \dots,\ 0,\ 1) $, $ (0,\ 0,\ \dots,\ 0,\ 1,\ 1) $, ... — всего $ 2^n $, т.к. вектор значений у б.ф. состоит из $ 2^n $ координат (по количеству наборов для $ n $ переменных) и плюс нулевой вектор $ (0,\ 0,\ 0,\ \dots,\ 0,\ 0,\ 0) $, т.е. всего $ 2^n + 1 $. В чём моя ошибка?

P.S. В показателях стоит количество сочетаний из $ n $ по $ \lfloor \frac{n}{2} \rfloor $.

[Хорхе]

Нет, вы неправильно понимаете термин "монотонная булева функция". Почитайте определение.

-- Вт янв 25, 2011 11:28:56 --

Кстати, это не то же самое, что антицепи в булеане?

[Xaositect]

Хорхе в сообщении #404168 писал(а):

Кстати, это не то же самое, что антицепи в булеане?

Да, монотонная функция однозначно задается нижними единицами, а они образуют антицепь. Ну и обратно.

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

Ха-ха. Свободная дистрибутивная решётка с $n$ образующими. Подсчёт числа её элементов --- так называемая задача Дирихле.

Открытая проблема уже сто с лишним лет Численно точные значения найдены для довольно малого количества $n$, не помню точно, но где-то в пределах десятка. А асимптотические оценки, да, до сих пор ищут и улучшают. Задача вроде имеет важное прикладное значение в каких-то там сетях...

-- Вт янв 25, 2011 23:33:03 --

Хорхе в сообщении #404168 писал(а):

Кстати, это не то же самое, что антицепи в булеане?

Ага. И то же самое, что порядковые идеалы $n$-мерного куба, а также дизъюнктивные нормальные формы без отрицаний.

[Gortaur]

Профессор Снэйп
Вы все время говорите о решетках. Что это?

[Хорхе]

Gortaur в сообщении #404519 писал(а):

Профессор Снэйп
Вы все время говорите о решетках. Что это?

Второй результат в гугле.

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

Хорхе в сообщении #404528 писал(а):

Второй результат в гугле.

А также тут, первые три страницы файла.

Не могу удержаться от ссылки на себя С другой стороны, для кого-то же я это когда-то писал!!!

[Gortaur]

Хорхе
какой запрос?

Профессор Снэйп
спасибо. студенты не читают?

[Wynardtage]

Да, оказывается я не знал определение монотонной б.ф. функции. Я почему-то думал о лексикографическом порядке. Всем спасибо, экзамен-то сдан.

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

Gortaur в сообщении #404558 писал(а):

Профессор Снэйп
спасибо. студенты не читают?

Нэ знаю, но думаю, вряд ли. Это писалось как спецкурс для старшекурсников.

[Gortaur]

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

(Оффтоп)

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

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

(Оффтоп)

Gortaur в сообщении #404620 писал(а):

Я имею ввиду, есть ли прямая связь?

Не могу сказать, есть или нет, поскольку не знаю, что такое PCTL

Если же взять классическое исчисление предикатов (первого порядка), то связь есть, причём очень глубокая. Если взять полную теорию (не более чем счётной сигнатуры), то для неё естественным образом вводится алгебра Линденбаума, которая является булевой алгеброй. И тогда теория имеет простую модель (модель, реализующую лишь главные типы) в том и только в том случае, когда эта алгебра является атомной; кроме того, теория имеет счётно-насыщенную модель тогда и только тогда, когда алгебра Линденбаума является суператомной.

Вообще, булевы алгебры много где возникают, так что хороший математик обязан знать некий минимум по этой теме... Думаю, в обсуждаемом конспекте этот минимум заканчивается на критерии Воота, а всё, что до него, всем незнакомым с темой надо читать подряд и внимательно