Сколько монотонных функций от 3 переменных

Булевы функции. Интересная задачка.

Напомните определение "антицепи", тогда, возможно я смогу помочь.
Пока могу высказать следующие соображения, которые могут натолкнуть на верное решение(или не помогут):
1) Подсчитывать в отдельности Число всех немонотонных функций от n переменных и число всех антицепей на множестве булева куба размерности n. — путь неверный, ибо подсчет числа монотонных функций — очень неблагодарное и сложное дело.
2) Существует критерий немонотонности б.ф. на булевом кубе:
б.ф. немонотонна <=> при движении "вверх", "вправо", "влево" от точки (0,0. 0) к (1,1. 1) найдется ребро типа (1,0).

Р.S. По виду вашей формулы не могу проследить за логикой составления, но, похоже, она не верна:
n=2.
Число всех фунций: 2^(2^2)=16;
Число монотонных функций: 2!*(2+2)*2^((2^2)-(2+1))=2*4*2^(4-3)=16. В то время как монотонных функций (n=2) равно 6.

Пусть в множестве А задано отношение порядка.
Антицепь — это подмножество А, в котором все элементы попарно несравнимы.

Для n=2 подсчёт монотонных функций не верный. там 10 функций!
x1 x2 f.
0 0 0001000110
0 1 0011001101
1 0 0000111110
1 1 0111011110

Пусть задано множество E=<0,1>.
E^n — множество векторов длины n, состоящее из нулей и единиц.
An принадлежит E^n => An=(a_1,a_2. a_n);
Bn принадлежит E^n => Bn=(b_1,b_2. b_n);
Введем бинарное отношение порядка An<=Bn <=> a_i<=b_i для всех i=1..n.
Определение: Функция f(x_1,x_2. x_n) называется монотонной, если для любого набора An и Bn из An<=Bn следует f(An)<=f(Bn)

Таких функций для n=2 все же 6:
0000,1000,1100,1010,1110,1111.

Например ваша функция(N4) не обладает таким свойством: f(x_1,x_2)=1011.
(00)<=(10), но f(00)=1 => f(10)=0.

Что касается антицепей, я так не совсем понял, как их применить относительно булева куба. Опишите для наглядности все антицепи булева куба размерности n=2, а дальше посмотрим.

вот блин я дурак. 🙂 Да, при n=2 там 6 монотонных функций.

У меня правильно только то, что число возможных цепей в булевом кубе n!. Длина какждой цепи n+1.
Для последовательности элементов каждой цепи имеем варианты значений функций 000. 0, 000. 1, . 011. 1, 111. 1.
Но ведь для каждой функции нужно учитывать и то, что элементам, не входящим в цепь могут соответствовать 0 или 1.
Но вот например, для цепи 000-001-011-111 не нужно учитывать возможные варианты возможных функций для 000 и 111, чтобы не повторяться.

Каждой монотонной булевой функции f поставим в соответствие множество M — максимальных элементов множества нулей f. Очевидно, M образует антицепь, причем эта антицепь максимальна во множестве нулей f.

Наоборот, по данной антицепи M определим функцию f следующим образом. Если n-мерный булевый вектор v сравним с каким-то элементом M и не больше его, то положим f(v)=0; если же v не сравним ни с одним из элементов M или сравним и больше какого-то элемента, то положим f(v)=1.

Нетрудно проверить, что определенное соответствие f <—> M взаимно-однозначно.

Да, конечно 🙂 Трудности остались (экзамен).
Что такое множество нулей f? Это те наборы, при которых f = 0? А! Понял.
Я считаю, что лучше не использовать понятия "Очевидно" и "Нетрудно". Т.к. очевидно — это когда очами видно :)) Ну да ладно, разберусь.

В булевом кубе размерности n=2 я насчитал только 5 антицепей почему-то: <00>, <01>, <10>, <11>, <01, 10>. А монотонных функций там 6:

x1 x2 f
0 0 0 0 0 0 0 1
0 1 0 0 1 0 1 1
1 0 0 0 0 1 1 1
1 1 0 1 1 1 1 1

Если учитывать пустое множество в качестве антицепи, то всё получается (проверял для n=2).

Вот я копал в сторону численного решения: найти число этих функций и антицепей. Что-то там было много запутано и пока нормально не додумался.

Построение у вас верное, насколько до меня дошло 🙂
Меня интересуют методы догадки до таких построений. Очень интересно.

Нет, мне ничего неизвестно об этой формуле(но это не значит, что ее нет). Вопрос очень интересный, но просто подсчитывать комбинаторно это число — это достаточно кропотливая работа. Смотрите сами:
F_i — число монотонных функций, для которой не существует набора A веса (n-i-1), при котором f(A)=1 (и существует такой набор веса (n-i)).
Для примера: F_1 — не существует набора А веса (n-1), в котором f(А)=1. С терминологией разобрались.

F_1: Такая функция всего одна: f(11. 1)=1, f(все остальные)=0, F_1=1;

F_2: C(n,1)+C(n,2)+. +C(n,n)=2^n-1. (таких наборов может быть 1, 2, . n).

F_3: Здесь по порядку:
C(n,2) * ( C(n-2,0)+C(n-2,1)+C(n-2,2)+. C(n-2,n-2)) + (выбрали 1 один набор на уровне F_3, так как ф-ция монотонна, на уровне F_2 обязательно существуют два набора А1 и А2 таких что f(A1)=f(A2)=1. Кроме них могут быть 0, 1, 2, (n-2) дополнительных набора, значение функции в которых будет равны 1) +
С(n,2)*C(n-2,2)*(C(n-4,0)+C(n-4,1)+C(n-4,2)+. C(n-4,n-4))/2! +
C(n,2)*(2*C(n-2,1))*(C(n-3,0)+C(n-3,1)+C(n-3,2)+. C(n-3,n-4))/2!+ (здесь мы выбирали два набора) +
С(n,2)*C(n-2,2)*С(n-4,2)*(C(n-6,0)+C(n-6,1)+C(n-6,2)+. C(n-6,n-6))/3!+С(n,2)*C(n-2,2)*С(n-4,1)*(C(n-5,0)+C(n-5,1)+C(n-5,2)+. C(n-5,n-5))/3!+С(n,2)*C(n-2,1)*С(n-3,1)*(C(n-4,0)+C(n-4,1)+C(n-4,2)+. C(n-4,n-4))/3!(здесь мы вибирали три набора) + .
Дальше продолжать как-то неохота, но уже видно, какое громадное выражение тут получается. И это только начало. Конечно, суммы эти можно будет потом свернуть, но времени все это просчитать у меня просто нету. Возможно существует такое взаимнооднозначное отображение, при котором число таких функций будет просто подсчитать, не знаю.

> Я считаю, что лучше не использовать понятия "Очевидно" и "Нетрудно".

Расписывать в деталях каждый шаг у меня нет ни времени, ни желания. Раз разобрались — значит, все действительно было "очевидно" и "нетрудно".

> Если учитывать пустое множество в качестве антицепи, то всё получается (проверял для n=2).

Правильно. Пустая антицепь соответствует тождественной 1 в моем построении.

> Если учитывать пустое множество в качестве антицепи, то всё получается (проверял для n=2).

Ничего сложного нет. Надо просто хорошо понимать, что стоит за словами "монотонная функция" и "антицепь" и искать связь между ними. Кроме того, редко когда доказательство равенства количест тех или иных объектов требует прямого подсчета этих количества. Чаще гораздо проще найти взаимно-однозначное соответствие между объектами.

Нашел ссылочку: http://www.allmath.ru/highermath/algebra/algebra7/algebra.htm
В частности там есть статья: "А. Д. Коршунов. О числе и строении монотонных булевых функций"

Формула там есть, но она по сути — запись алгоритма перебора по всем булевым функциям. ЖУТЬ! 🙂

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

Высказыванием считается повествовательное предложение, являющееся либо истинным, либо ложным. Мы не станем рассматривать высказывания с точки зрения их содержания и фактически будем отождествлять высказывание с его истинностностным значением. Произвольные высказывания будем обозначать буквами а, b, с, . . Значение "истина" обозначается через 1 или true, a значение "ложь" — через 0 или false.

Определение 1. Высказывания а и 6 называются равносильными, обозначается, а = b, если они оба истинны, либо оба ложны.

Свойство 2. Если a=b, то b = a.

Свойство 3. Если a =b и b = с, то, а = с.

Определение 2. Конъюнкцией высказываний а и b называется высказывание "а и b", которое является истинным лишь, когда каждое из высказываний а, 6 является истинным. Обозначается конъюнкция так: a*b, а /\ b, a&b,

Свойство 4. а • 0 = 0.

Свойство 5. а • 1 = а.

Свойство 6. a • а = а —идемпотентность.

Свойство 7. a•b = b•а — коммутативность.

Свойство 8. а(bс) = (аb)с — ассоциативность.

Доказательство этого свойства непосредственно следует из определения эквиваленции и суммы по модулю 2 (см. табл. 5).

Определение 3. Дизъюнкцией высказываний о и b называется высказывание "а или b я , которое истинно, если хотя бы одно из высказываний а, b является истинным, что и отражено в табл. 1. Обозначается значение дизъюнкции так : а V b,

Свойство 9. а V 0 = а.

Свойство 10. а V 1 = 1.

Свойство 11. a V a = a — идемпотентность.

Свойство 12. а V b = b V а — коммутативность.

Свойство 13. a V (b V с) = (a V b) V с — ассоциативность.

Доказательство. Сделаем разбор случаев по переменной 6; для этого найдем значения левой части (LP) и правой части (АР) для b = 0 и для b=1.

Пусть b = 0, тогда LP = a V (0 V c) = a V c,

RP=(a V 0) V c = — aVс; отсюда следует, что LP = RP.

Пусть b = 1, тогда LP = a V(l V c) = a V l =1,

RP= (a V l) V c = = l V c = l; отсюда следует, что LP = RP.

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

Свойство 14. а (b V с) = ab V ас.

Свойство 15. a V bc = (a V b)(a V с).

Докажем свойство 15.

В табл. 2 для всех возможных значений а, b, с приводятся результаты выполнения операций V и /\ в левой и правой частях данной формулы. Столбцы, выделенные жирным шрифтом, являются итоговыми значениями левой и правой частей и поскольку эти столбцы одинаковы, то свойство 15 доказано.

§ 3. Пропозициональные формулы, булевы функции и их количество

Определение 1. Пропозициональной формулой (ПФ) называется формула, составленная из логических констант 0 и 1, логических переменных, принимающих эти значения 0 и 1, с помощью скобок и знаков логических операций.

Для уменьшения количества скобок устанавливают следующие приоритеты для логических связок:

Для пропозициональной формулы A(x₁,x₂. х_п) можно составить истинностную таблицу ее значений для всех наборов значений логических переменных x₁,x₂. х_п Эта таблица имеет 2 n строчек. Значения переменных x₁,x₂. х_п записывают переводя числа 0,1,2. , 2 n — 1 в двоичную систему счисления в порядке их возрастания (см. табл. 1 ,5).

Определение 2. Функция у = f(x₁,x₂. х_п) называется булевой (БФ), если x_i € <0; 1>при i = 1,2. ,n, у € <0; 1>.

Булевы функции можно задавать истинностными таблицами, а также указывать правило их вычисления с помощью пропозициональных формул.

Определение 1. Дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ). Дизъюнкция полных элементарных конъюнкций называется совершенной ДНФ.

Теорема о реализации булевой функции в ДНФ. Для любой булевой функции f(x₁,x₂. , х_п) имеет место формула

Доказательство. При фиксированных значениях x₁,x₂. , х_п конъюнкция x q 1 ₁,x q 2 ₂. , х qn _п истинна лишь тогда, когда q_i = x_i для всех значений i = 1,2. , п. Следовательно, в правой части формулы (1) может быть отличной от 0 только одна элементарная конъюнкция f(x₁,x₂. , х_п,x₂. , х_п)x x 1 ₁,x x 2 ₂. , х xn _п равная f(x₁,x₂. , х_п,x₂. , х_п). Теорема доказана.

Теорема о количестве булевых функций.

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

Доказательство. Если функция имеет n переменных, то в ее истинностной таблице имеется 2 n строчек. Поскольку в каждой строчке булева функция может принимать два значения 0 и 1, то всего имеется различных булевых функций от n переменных. В табл. 6 приведены все 16 булевых функций от двух переменных а и b.

Если булева функция от n переменных задана стандартной таблицей, строчки которой являются двоичными числами, расположенными в порядке возрастания от 0 до 2 n — 1, то достаточно указать столбец значений функции. Этот столбец можно написать целиком, однако часто указывают только номера строчек, на которых функция истинна.

Определение 3. Переменная Х_i называется существенной для функции у = f(x₁,x₂,— ,x_n), если можно указать такие значения

Теорема Анселя о числе монотонных функций

Пусть Т = T(Ti,T2) — множество всех тестов для обучающей выборки 7,Т₂.

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

Сопоставим множеству Т его характеристическую функцию fr(t) • Е п —> Е такую, что

Из очевидного свойства, что если некоторое множество признаков есть тест, то любое множество, содержащее данное множество, также является тестом, следует, что функция /т(0 является монотонной функцией.

Напомним, что булева функция /(a?i. ,т_п) называется монотонной., если для любых наборов (сц. с*_п) и (Д. Д) таких, что а* )> такого, что (А. Р_п) п — множество верхних нулей функции /. Положим 7 = <а>, где а = (ах. а_п) =

(1. 1) — единичный набор, Т₂ = <<ц. ,6*>.

Рассмотрим произвольный набор ? = (tx. ?„), на котором f. ?„) = 1, и произвольный верхний ноль

Так как /(6ц. М = о, то наборы ? и bi либо несравнимы,

либо 6 bij, т.е. ?у = оу = 1, 6у = 0. Откуда в силу произвольности ^ следует, что ? — тест для Гх, Г₂ и /r(Ti,r₂)(0 = 1- Рассмотрим произвольный набор t = (?х. ,?„), на котором /(t 1. ,t„) = 0. Тогда существует верхний ноль

такой, что ? 1 = 0. Нижняя оценка в этих неравенствах была получена Э.Н.Гильбертом [13], а верхняя — Ж.Анселем [6]. Отметим, что Коршуновым А.Д. [31] получена асимптотика числа ф(п) при п —* оо.

Последовательность элементов из Е п называется цепью, если получается из (3^ заменой одного

нуля (в наборе координат) на единицу, i = 1,2. ,m — 1. Тем самым, 2 > п образуют цепь, то четвертый элемент /?, образующий вместе с ними квадрат (см. рис. 1.11), называют дополнением цепи 04,02,03 А° квадрата. Лемма 4 (Анселя). Единичный п-мерный куб Е п может быть покрыт множеством из попарно непересекающих—

ся цепей, обладающих следующими свойствами:

а) число цепей длины п —2р + 1 равно С? — С%

1 (0 п делится на два подмножества Е? и Е™ (минимальное и максимальное), изоморфные кубу Е п

1 и полученные соответственно присоединением 0 и 1 слева к координатам куба Е п

1 . В предположении, что лемма верна для куба Е п

Тогда цепи, покрывающие Е п _> не будут пересекаться и число цепей длины п — 2р + 1 будет равно

2) Свойство б) леммы является непосредственным следствием вышеприведенной конструкции.

В самом деле, цепи в Е п — двух сортов: «удлиненные», возникшие из цепей Е?

1 _> и «укороченные», возникшие из цепей Е^

. Рассмотрим возможные случаи для трех элементов ai, с*2, п (длины п — 2р + 1).

I. С — удлиненная цепь, и аз не есть ее максимальный элемент. В этом случае а, (*2, Eq

1 (длины п — 2р). Дополнение цепи ах,а2,аз до квадрата находится на некоторой цепи С’ (длины п — 2р — 2) в Eq

1 , которая будет продолжена при переходе к Е п до цепи длины п — 2р — 1.

И. С — удлиненная цепь, и аз — ее максимальный элемент. Пусть С = С[ (рис 1.12) возникла в результате удлинения цепи Ci из Eq

1 С2 — цепь в Ei“ l _t изоморфная СС₂ — укороченная цепь, возникшая из С2 (С₂ имеет длину п — 2р — 1). Тогда дополнение цепи а_ь а₂, аз до квадрата есть максимальный элемент цепи С₂.

III. С — укороченная цепь. Пусть С = С‘₂ возникла из цепи Сг (длины и — 2р + 2) в Е%

г . Тогда, во-первых, а₃ — не максимальный элемент цепи С2 и, во-вторых, в силу второй части свойства а) максимальный а элемент цепи С2 имеет р — 1 нулей. В силу свойства б) дополнение /3 цепи ai, аг, аз до квадрата принадлежит некоторой цепи С длины п — 2р в Е^

; максимальный элемент этой цепи имеет р нулей. Так как @ п _> т.е. S — множество всех наборов, содержащих ровно [п/2] единиц. Понятно, что любая пара наборов из S попарно несравнима. Следовательно, любое подмножество S может быть использовано в качестве множества нижних единиц некоторой монотонной функции. Откуда сразу следует, что