Нека f (x1, …, xn) F2. Функцията f *(x1, …, xn), определена по следния начин: за всеки вектор a1…an J2n,
f *(a1, …, an) = наричаме двойнствена на f.
Векторите = a1a2…an J2n и = … J2n наричаме противоположни вектори.
Лема: В стандартната наредба на J2n, противоположните вектори са симетрично разположени относно средата на таблицата.
От тази лема получаваме следният алгоритъм за намиране на двойнствена функция, зададена със своя вектор-стълб:
1. инвертираме всяка стойност в стълба;
2. завъртаме симетрично стълба около средата.
Като непосредствено следствие от алгоритъма получаваме:
за всяка функция f F2, (f *)* = f.
С прилагане на алгоритъма можем да установим следните двойнствености: ()* = , (x)* = x, ()* = , (xy)* = x y.
Лема (двойнственост на сложна функция):
Ако h = f (g1, …, gn), то h* = f *(g1*, …, gn*).
Функцията f (x1, …, xn) F2 наричаме самодвойнствена,
ако f * = f. Със S означаваме множеството от всички самодвойнствени функции, със Sn тези от тях, които са на n променливи.
Например x, са самодвойнствени, xy не е самодвойнствена.
Така S F2.
Лема: Функцията f на n променливи е самодвойнствена
за всеки вектор J2n е в сила f () f ().
Вече е ясно, че |Sn| = , тъй като всяка самодвойнствена функция на n променливи се дефинира свободно точно върху един от всяка двойка противоположни вектори.
Теорема: Множеството S е затворено множество от булеви функции.
Доказателство: Прилагаме критерия за затвореност, като използваме лемата за двойнственост на сложна функция.
Въвеждаме нова релация в J2n:
ако = a1a2…an и = b1b2…bn, то a1 b1, …, an bn. Релацията очевидно е частична наредба, която не е линейна.
Въвеждаме релация в J2n:
ако = a1a2…an и = b1b2…bn, съществува
i { 1, 2, …, n }, такова че ai < bi (ai = 0, bi = 1) и aj = bj при j i.
Лема: Ако и , то съществуват 1, …, k J2n,
такива че 1 … k (допускаме k = 0).
Казваме, че функцията f (x1, …, xn) F2 е монотонна, ако за всеки
, J2n, такива че имаме f () f ().
С M означаваме множеството от всички монотонни функции,
с Mn тези от тях, които са на n променливи.
Функциите x, xy, x y, , са монотонни, докато не е монотонна, тъй като 0 1, но 1 = > = 0.
Така M F2.
Задачата за намиране на явна формула за броя на монотонните функции на n променливи не е решена.
Лема: Нека f M. Тогава съществуват , J2n, такива че
Редактор: Снежина Стоянова
