Булеви функции. Теорема на Пост-Яблонски за пълнота


Категория на документа: Информатика


Нека 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, такива че



Сподели линка с приятел:





Яндекс.Метрика
Булеви функции. Теорема на Пост-Яблонски за пълнота 9 out of 10 based on 2 ratings. 2 user reviews.