математическая-логика — Сколько существует монотонных булевых функций от n переменных
Это известная проблема Дедекинда. Точные значения известны только для «малых» значений $%n$%. Для больших значений известна асимптотика. Конкретные факты приведены в Вики-статье по ссылке.
Можно добавить следующее простое соображение. Рассмотрим случай, когда $%n$% чётно. На всех наборах, где количество нулей превышает количество единиц, значение функции положим равным 0. Если количество единиц набора превышает количество нулей, значение функции положим равным 1. На оставшихся наборах, где нулей и единиц поровну, зададим значение функции произвольным образом. Все такие функции будут монотонными, и их количество равно $%2^>$%. Это даёт простую оценку снизу. Заметим, что таких функций «много», если сравнить с общим количеством (всего их $%2^$%, а здесь получается порядка $%2^>$%). Кроме того, верхняя оценка близка к нижней (см. двойное неравенство по ссылке). Для нечётного $%n$% возможна аналогичная конструкция.
отвечен 21 Сен ’15 14:54
falcao
300k ● 9 ● 38 ● 55
математическая-логика — Количество монотонных булевых функций
Сколько существует монотонных булевых функций от 3 переменных?
задан 14 Янв ’18 17:14
fodidu
59 ● 1 ● 7
66% принятых
1 ответ
В отличие от других предполных классов, для количества монотонных функций от n переменных, хорошей общей формулы не имеется. Поэтому считать придётся вручную. Способов можно предложить несколько. Один из них такой: сразу учтём 2 константы. Остальные монотонные функции представляются в виде дизъюнкции элементарных конъюнкций. При этом более «слабые» члены не учитываются, что гарантирует единственность. Это означает, что если одна конъюнкция «содержит» другую — в том смысле, как xz «содержит» и x, и z, то x V xz равно x. Поэтому наличие члена xz исключает наличие более «слабых» членов x и z.
Тогда, если есть xyz, то больше ничего нет. Предположим, что члена 3-й степени нет, а члены 2-й степени есть. Если их три, то получается функция голосования xy V xz V yz. Других членов нет. Если их два, то это функция xy V xz, или симметричная ей. Всего таких 3 штуки. Других членов снова нет. Если есть только один член — скажем, xy, то он идёт или сам по себе, или вместе с z, то есть функция равна xy V z. С учётом симметрии, это ещё 6 случаев. Наконец, если члены имеют только первую степень, то функций будет 2^3-1=7 по числу непустых подмножеств в .
Теперь аккуратно всё складываем: 2+1+1+3+6+7=20. Это ответ.
Вот ещё один способ. От двух переменных имеется ровно 6 монотонных функций: две константы, две переменные, конъюнкция и дизъюнкция. Это легко проверяется. В виде векторов их легко выписать (в лексикографическом порядке): 0000, 0001, 0011, 0101, 0111, 1111. Теперь заметим, что при фиксации значения одной переменной у монотонной функции, это свойство сохраняется. Если для функции f(x,y,z) мы фиксируем x=0, то получим один из этих 6 наборов. Если фиксируем x=1, то снова получается набор из списка, который покоординатно не меньше предыдущего. Поэтому остаётся для каждого набора списка подсчитать число покоординатно не меньших, и всё сложить. Это даёт 6+5+3+3+2+1=20. Ответ тот же.
отвечен 14 Янв ’18 17:52
falcao
300k ● 9 ● 38 ● 55
Научный форум dxdy
Попробуйте начать с оценок, например, оценить число несравнимых попарно наборов и отсюда посмотреть, что получится. Это будет оценка снизу.
Точной формулы от n, определяющей число таких функций, даже не встречал.
07.06.2008, 20:24
| ! |
cepesh: |
| Uta , если вы еще раз заведете дублирующую тему, Вы будете забанены. Читайте правила форума.
|
07.06.2008, 21:13
По-моему, где-то я слышал, что это открытый вопрос. Но, может быть, я и путаю — давно это было.
07.06.2008, 21:37
Oтнюдь, ничего открытого: .
07.06.2008, 21:39
А что же тогда открытое было?
дискретка
07.06.2008, 21:41
juna, скажи пожалуйста, а откуда эта формула? как её вывести?Очень важен сам процесс решения! Пожалуйста!
07.06.2008, 21:46
Начните c ответа на следующие вопросы:
1.Сколько строк в таблице истинности от переменных
2. Что такое монотонные булевы функции
07.06.2008, 22:05
juna
А относительно какого порядка? Ваш ответ описывает число функций, монотонных относительно порядка, в котором двоичный набор a меньше двоичного набора b тогда и только тогда, когда задаваемые ими десятичные числа находятся в данном соотношении.
А что если порядок другой?
Скажем, покомпонентный? ( Для которого и доказывается лемма о немонотонной ф-ии и т.п. )
07.06.2008, 22:11
Последний раз редактировалось RIP 07.06.2008, 23:01, всего редактировалось 2 раз(а).
Что-то я сомневаюсь, что это количество считается (разве что в виде какой-нибудь страшной суммы). Мы как-то на семинаре по дискре полпары доказывали оценку сверху вида 
07.06.2008, 22:12
строк в таблице — 2 в степени n, а монотонные — ф-ии, для которых определено отношение порядка. А почему 2 ^n +1? единица откуда берётся?
07.06.2008, 22:14
Uta
А Вы скажите, какой там порядок.
07.06.2008, 22:17
про порядок ничего не сказано. просто найти число n-местных функций для всех возможных n
07.06.2008, 22:21
Давайте все-таки начнем с определения монотонных булевых функций.
Я имею в виду следующее определение
Функция монотонна, если она не убывает при возрастании своих аргументов.
Т.е. если составлять таблицу истинности с нулевых значений переменных, и двигаться сверху вниз, то если встретили единицу на выходе, ниже должны быть единицы.
07.06.2008, 22:21
Uta
Так как найти это число, если не известно какой порядок? Порядок разный — число таких функций будет разным.
Как легко доказать, для естественного порядка на двоичных числах это будет ответ, данный juna .
А вот если порядок покомпонентный. то не знаю.
Причем привычные теоремы ( скажем, лемма о немонотонной ф-ии, используемая в док-ве теоремы Поста ) доказываются именно для него. И, что вполне может быть, число монотонных ф-ий для него найти не так просто.
Поэтому вопрос «Какой порядок?» весьма важен.
juna
Ну да, для такого порядка все просто. А если он другой?
| Страница 1 из 3 |
[ Сообщений: 31 ] |
На страницу 1 , 2 , 3 След. |
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения |
Полные системы функций. Теорема Поста о полной системе функций
Американский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:
- функции, сохраняющие константу [math]T_0[/math] и [math]T_1[/math] ,
- самодвойственныые функции [math]S[/math] ,
- монотонные функции [math]M[/math] ,
- линейные функции [math]L[/math] .
Замкнутые классы булевых функций
Класс функций сохраняющих ноль [math]T_0[/math] .
| Определение: |
| Говорят, что функция сохраняет ноль, если [math]f(0, 0, \ldots, 0) = 0[/math] . |
Класс функций сохраняющих единицу [math]T_1[/math] .
| Определение: |
| Говорят, что функция сохраняет единицу, если [math]f(1, 1, \ldots, 1) = 1[/math] . |
Класс самодвойственных функций [math]S[/math] .
| Определение: |
| Говорят, что функция самодвойственна (англ. self-dual), если [math]f(\overline,\ldots,\overline)=\overline[/math] . Иными словами, функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения. |
Класс монотонных функций [math]M[/math] .
| Определение: |
| Говорят, что функция монотонна (англ. monotonic function) , если [math]\forall i (a_i \leqslant b_i) \Rightarrow f(a_1,\ldots,a_n)\leqslant f(b_1,\ldots,b_n)[/math] . |
Класс линейных функций [math]L[/math] .
| Определение: |
| Говорят, что функция линейна (англ. linear function), если существуют такие [math]a_0, a_1, a_2, \ldots, a_n[/math] , где [math]a_i \in \, \forall i=\overline[/math] , что для любых [math]x_1, x_2, \ldots, x_n[/math] имеет место равенство: [math]f(x_1, x_2, \ldots, x_n) = a_0\oplus a_1\cdot x_1\oplus a_2\cdot x_2 \oplus\ldots\oplus a_n\cdot x_n[/math] . |
Количество линейных функций от [math]n[/math] переменных равно [math]~2^[/math] .
Функция является линейной тогда, и только тогда, когда в ее полиноме Жегалкина присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью преобразования Мебиуса.
Формулировка и доказательство критерия Поста
Набор булевых функций [math]K[/math] является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов [math] S,M,L,T_0,T_1 [/math] , иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
Необходимость.
Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора [math]K[/math] входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор [math]K[/math] не мог бы быть полным.
Достаточность.
Докажем, что если набор [math]K[/math] не содержится полностью ни в одном из данных классов, то он является полным.
- Рассмотрим функцию, не сохраняющую ноль — [math]f_0[/math] (то есть функцию, для которой [math]f_0(0) = 1[/math] ). Тогда [math] f_0(1)[/math] может принимать два значения:
- [math]f_0(1) = 1[/math] , тогда [math]f_0(x, x, x, \ldots, x) = 1[/math] .
- [math]f_0(1) = 0[/math] , тогда [math]f_0(x, x, x, \ldots, x) = \neg x[/math] .
- [math]f_1(0) = 0[/math] , тогда [math]f_1(x, x, x, \ldots, x) = 0[/math] .
- [math]f_1(0) = 1[/math] , тогда [math]f_1(x, x, x, \ldots, x) = \lnot x[/math] .
Таким образом, возможны четыре варианта:
- Мы получили функцию [math] \neg [/math] .
Используем несамодвойственную функцию [math]f_s[/math] . По определению, найдется такой вектор [math]x_0[/math] , что [math]f_s(x_0) = f_s(\lnot x_0)[/math] . Где [math]x_0 = (x_, x_, \ldots, x_)[/math] .
Рассмотрим [math]f_s(x^>, x^>, \ldots, x^>)[/math] , где либо [math]x^> = x[/math] , при [math]x_ = 1[/math] . Либо [math]x^> = \lnot x[/math] , при [math]x_ = 0 [/math] . Нетрудно заметить, что [math]f_s(0) = f_s(1) \Rightarrow f_s = \operatorname [/math] . Таким образом мы получили одну из констант.
- Мы получили [math] \neg [/math] и [math]0 \Rightarrow[/math] имеем константу, равную [math]1[/math] , поскольку [math]\lnot 0 = 1[/math] .
- Мы получили [math] \neg [/math] и [math]1 \Rightarrow[/math] имеем константу, равную [math]0[/math] , поскольку [math]\lnot 1 = 0[/math] .
- Мы получили [math]1[/math] и [math]0[/math] .
Рассмотрим немонотонную функцию [math]f_m[/math] . Существуют такие [math]x_1, x_2, \ldots, x_n[/math] , что [math]f_m(x_1, x_2, \ldots, x_, 0 , x_, \ldots, x_n) = 1[/math] , [math]f_m(x_1, x_2, \ldots, x_, 1 , x_, \ldots, x_n) = 0[/math] , зафиксируем все [math]x_1, x_2, \ldots, x_n[/math] , тогда [math]f_m(x_1, x_2, \ldots, x_, x, x_, \ldots, x_n)= \lnot x[/math] .
В итоге имеем три функции: [math] \neg [/math] , [math]0[/math] , [math]1[/math] .
Используем нелинейную функцию [math]f_l[/math] . Среди нелинейных членов [math]f_l[/math] (ее представления в виде полинома Жегалкина), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем [math]x_1[/math] и [math]x_2[/math] . Все элементы, не входящие в данный член, примем равными нулю. Тогда эта функция будет представима в виде [math]g_l = x_1 \land x_2 [ \oplus x_1] [\oplus x_2][ \oplus ~1][/math] , где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов).
Рассмотрим несколько вариантов:
- Присутствует член [math]\oplus ~1[/math] . Возьмем отрицание от [math]g_l[/math] и член [math]\oplus ~1[/math] исчезнет.
- Присутствуют три члена, без [math]\oplus ~1[/math] : [math]g_l= x_1 \land x_2 \oplus x_1 \oplus x_2[/math] . Составив таблицу истинности для этой функции нетрудно заметить, что она эквивалентна функции [math] \vee [/math] .
- Присутствуют два члена, без [math]\oplus ~1[/math] . Построив две таблицы истинности для двух различных вариантов, заметим, что в обоих случаях функция истинна только в одной точке, следовательно, СДНФ функции [math]g_l[/math] будет состоять только из одного члена. Если это так, то не составляет труда выразить [math] \wedge [/math] через [math] \neg [/math] и [math]g_l[/math] . Например, если функция [math]g_l(x_1, x_2, \ldots, x_n)[/math] принимает истинное значение, когда аргументы c номерами [math]i_1, i_2, \ldots, i_m[/math] ложны, а все остальные истины, то функцию [math] \wedge [/math] можно выразить как [math]g_l([\lnot]x_1, [\lnot]x_2, \ldots, [\lnot]x_n)[/math] , где [math]\lnot[/math] ставится перед аргументами с номерами [math]i_1, i_2, \ldots, i_m[/math] .
- Присутствует один член. Выразим [math] \wedge [/math] через [math] \neg [/math] и [math]g_l[/math] аналогично пункту 3.
В итоге получим функцию [math] \neg [/math] , а также либо функцию [math] \wedge [/math] , либо функцию [math] \vee [/math] . Поскольку функцию [math] \wedge [/math] можно выразить через [math] \vee [/math] и [math] \neg [/math] , а функцию [math] \vee [/math] через [math] \wedge [/math] и [math] \neg [/math] , то мы получили базис [math] \wedge [/math] , [math] \vee [/math] , [math] \neg [/math] . Любую булеву функцию, не равную тождественному нулю, можно представить в форме СДНФ, то есть выразить в данном базисе. Если же функция равна тождественному нулю, то ее можно представить в виде [math]x \land \lnot x[/math] .
Примеры
Согласно критерию Поста система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов [math]T_0[/math] , [math]T_1[/math] , [math]S[/math] , [math]M[/math] , [math]L[/math] .
В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера или стрелку Пирса.
Широко известны такие полные системы булевых функций:
- [math]\left\<\land,\lor,\neg\right\>[/math] (конъюнкция, дизъюнкция, отрицание);
- [math]\left\<\land,\oplus,1\right\>[/math] (конъюнкция, сложение по модулю два, константа один).
Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.
Первая из упоминавшихся выше полных систем безызбыточной не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является безызбыточной — все три её элемента необходимы для полноты системы.
Теорема о максимальном числе функций в базисе: максимально возможное число булевых функций в базисе — четыре.
Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему [math]\left\<\oplus,1\right\>[/math] можно назвать базисом класса линейных функций.
См. также
- Булевы функции
- Суперпозиции
- Полином Жегалкина
Источники информации
- Википедия — Критерий Поста
- Википедия — Замкнутые классы булевых функций
- Образовательный сайт MiniSoft
- Post’s lattice
- Лекции по дискретной математике