1. Булеви функции. Теорема на Пост-Яблонски за пълнота. Нека J2 = { 0, 1}. Всяка функция f : J2n  J

Всяка функция f : J₂ⁿ  J₂ можем да разглеждаме като функция на n независими променливи x₁, x₂, …, x_n.

С F₂ⁿ ще означаваме множеството на всички двоични функции на n променливи. Очевидно е, че |F₂ⁿ| = .

Означаваме F₂ = - множеството на всички двоични функции.

Въвеждаме стандартна (лексикографска) наредба на J₂ⁿ:

 = a₁a₂…a_n предшества  = b₁b₂…b_n, ако съществува

i  { 1, 2, .., n}, такова че a₁ = b₁, a₂ = b₂, …, a_i-1 = b_i-1,

a_i < b_i (a_i = 0, b_i = 1). При стандартно подредени вектори от J₂ⁿ всяка булева функция се задава еднозначно с двоичен

вектор-стълб с размерност 2ⁿ. Това означава, че i-тата компонента на вектора-стълб е стойността на функцията за i-тия вектор от J₂ⁿ в стандартната наредба.
Нека f (x₁, x₂, …, x_n)  F₂ⁿ, g_i (y₁, y₂, …, y_m)  F₂^m, i = 1, 2, ..., n.

Функцията h (y₁, y₂, …, y_m) = f (g₁ (y₁, …, y_m), g₂ (y₁, …, y_m), …,

g_n (y₁, …, y_m)) наричаме суперпозиция на g₁, g₂, …, g_n във f.
Казваме, че функцията f : J₂ⁿ  J₂ не зависи съществено от променливата x_i, ако f (x₁, …, x_i-1, 0, x_i+1, …, x_n) = f (x₁, …, x_i-1, 1, x_i+1, …, x_n). Още казваме, че x_i е фиктивна променлива.

Ясно е, че към всяка двоична функция на n променливи можем да добавим колкото искаме фиктивни променливи. Така можем да считаме, че суперпозицията на g₁, g₂, …, g_n във f е дефинирана дори когато g₁, g₂, …, g_n са функции на различен брой променливи.

По-нататък ще записваме думите f, x, където ,   { 0, 1}⁺ като

f_i, x_j, където  е двоичното представяне на числото i,  е двоичното представяне на числото j. Дефинираме индуктивно понятието формула над множеството от функции F:

База: За всяка функция f_i  F на n променливи думата

f_i (x₁, x₂, …, x_n)  X* е формула над F.

Предположение: Нека f_i  F е функция на n променливи и

₁, ₂, …, _n  X* са формули над F или променливи, т.е. от вида x_k.

Стъпка: Тогава думата f_i (₁, ₂, …, _n)  X* е формула над F.

Нека F = { f₀, f₁, …}  F₂. На всяка формула  над F съпоставяме функция f  F₂ по следния начин:

База: Ако  = f_i (x₁, …, x_n), то определяме f = f_i  F.

Предположение: Нека f_i  F е функция на n променливи и

₁, ₂, …, _n са формули или променливи и съответните им функции са g₁, g₂, …, g_n  F₂. Aко _j е променливата x_k, то съответната функция g_j е идентитетът x_k.

Стъпка: Тогава на формулата  = f_i (₁, …, _n) съпоставяме суперпозицията f = f_i (g₁, …, g_n).

Очевидно е, че [ F₂ ] = F₂, но съществуването на пълни множества, различни от F₂ не е очевидно.

1. 
   F е пълно, т.е. [F] = F₂.
   
2. 
   F е минимално по включване с това свойство, т.е.
   

x^ = x, ако  = 1 и x^ = , ако  = 0.

Доказателство: Ако f =, можем да представим f = x и тогава

f  [{ x  y, xy, } ].

Нека f . Тогава f (x₁, x₂, …, x_n) = , което е формула над { x  y, xy, }.

{ , , xy, x  y } е пълно.

Доказателство: От теоремата на Бул и законите на Де Морган , и от = x  .
Да се спрем на последното пълно множество от следствието.

Нека f  F₂. Тогава f има формула над { , , xy, x  y }. Разкриваме скобите във формулата, като прилагаме дистрибутивния закон на конюнкцията спрямо събирането по модул 2, използваме идемпотентността на умножението (xx = x) и факта, че f  f = . Накрая получаваме многократна сума по

модул 2 от елементарни конюнкции без отрицания, като една елементарна конюнкция участва най-много веднъж. При това, от аналогията на конюнкцията с умножението по модул 2, получената формула може да разглеждаме като полином над полето GF (2) (полето с два елемента). Наричаме я полином на Жегалкин.
Теорема: Всяка булева функция има и то единствен полином на Жегалкин.

Доказателство: Всяка функция има полином, различните функции имат различни полиноми и броят на полиномите е = |F₂ⁿ|.

Например F₂ е затворено, тъй като [F₂] = F₂.

Множествата {}, {}, { x, } също са затворени.
Теорема (критерий за затвореност): Нека F  F₂ е такова, че

1. 
   f (x) = x  F;
   
2. 
   за всяка функция f (x₁, …, x_n)  F и g₁, …, g_n  F имаме
   

Тогава F е затворено множество.

f (0, …, 0) = 0. Kазваме, че функцията f (x₁, …, x_n)  F₂ запазва единицата, ако f (1, …, 1) = 1.

означаваме с T₀ⁿ. Oзначаваме с T₁ множеството от всички булеви функции, които запазват единицата и с T₁ⁿ тези от тях, които са на n променливи.

Например xy  T₀, x  y  T₀, xy  T₁, x  y  T₁, x  T₀, x  T₁,

 T₀,  T₁, x  y  T₀, x  y  T₁.

Така T₀  F₂ и T₁  F₂.

Очевидно, |T₀ⁿ| = = |T₁ⁿ|, тъй като всяка функция запазваща коя да е от константите се дефинира по произволен начин върху всички вектори освен един.
Теорема: Множествата T₀ и T₁ са затворени множества от булеви функции.

Доказателство: Директно от критерия за затвореност.

f *(a₁, …, a_n) = наричаме двойнствена на f.

1. 
   инвертираме всяка стойност в стълба;
   
2. 
   завъртаме симетрично стълба около средата.
   

за всяка функция f  F₂, (f *)* = f.

Ако h = f (g₁, …, g_n), то h* = f *(g₁*, …, g_n*).

ако f * = f. Със S означаваме множеството от всички самодвойнствени функции, със Sⁿ тези от тях, които са на n променливи.

Така S  F₂.

за всеки вектор   J₂ⁿ е в сила f ()  f ().

Доказателство: Прилагаме критерия за затвореност, като използваме лемата за двойнственост на сложна функция.

ако  = a₁a₂…a_n и  = b₁b₂…b_n, то    a₁  b₁, …, a_n  b_n. Релацията очевидно е частична наредба, която не е линейна.

Въвеждаме релация  в J₂ⁿ:

ако  = a₁a₂…a_n и  = b₁b₂…b_n,     съществува

i  { 1, 2, …, n }, такова че a_i < b_i (a_i = 0, b_i = 1) и a_j = b_j при j  i.
Лема: Ако   и   , то съществуват ₁, …, _k  J₂ⁿ,

такива че   ₁  … _k   (допускаме k = 0).

,   J₂ⁿ, такива че   имаме f ()  f ().

С M означаваме множеството от всички монотонни функции,

с M_n тези от тях, които са на n променливи.

Функциите x, xy, x  y, , са монотонни, докато не е монотонна, тъй като 0 1, но 1 = > = 0.

Така M  F₂.

   и f () > f ().

Доказателство: Тъй като f  M, то съществуват  ,   ,

такива че f () > f (), т.е. f () = 1, f () = 0. От горната лема съществуват ₁, …, _k  J₂ⁿ, такива че   ₁  … _k  .

Да означим ₀ = , _k+1 = . Да допуснем, че за всяко

i  { 0, 1, …, k } имаме f (_i)  f (_i+1).

Тогава 1 = f (₀)  f (₁)  … f (_k)  f (_k+1) = 0 – противоречие.

Така съществува индекс i, такъв че f (_i) > f (_i+1) и _i  _i+1.