и f () > f ().
Доказателство: Тъй като f M, то съществуват , ,
такива че f () > f (), т.е. f () = 1, f () = 0. От горната лема съществуват 1, …, k J2n, такива че 1 … k .
Да означим 0 = , k+1 = . Да допуснем, че за всяко
i { 0, 1, …, k } имаме f (i) f (i+1).
Тогава 1 = f (0) f (1) … f (k) f (k+1) = 0 – противоречие.
Така съществува индекс i, такъв че f (i) > f (i+1) и i i+1.
Теорема: Множеството M е затворено множество от булеви функции.
Доказателство: Прилагаме критерия за затвореност.
Всяка функция f (x1, …, xn) F с полином на Жегалкин
от вида a0 a1x1 … anxn, наричаме линейна функция.
С L означаваме множеството от всички линейни функции,
с Ln тези от тях, които са на n променливи.
Например x, = x L, но xy L, x y = x y xy L.
Така L F2.
Очевидно |Ln| = 2n+1, тъй като в общия вид линейните полиноми на Жегалкин имат n+1 свободни коефициенти.
Теорема: Множеството L е затворено множество от булеви функции.
Доказателство: Използваме критерия за затвореност.
Теорема (Пост-Яблонски): Нека F F2. Тогава F е пълно F не е подмножество на нито едно от множествата T0, T1, S, M, L.
Доказателство:
Нека F е пълно и K { T0, T1, S, M, L }. Да допуснем, че F K.
Тогава [F] [K]. От пълнотата на F имаме [F] = F2 [K] = F2.
От друга страна за множеството K вече показахме, че [K] = K F2 – противоречие. Tака F не е подмножество на нито едно от
множествата T0, T1, S, M, L.
Нека F не е подмножество на нито едно от множествата
T0, T1, S, M, L. Тогава съществуват функции f0, f1, fs, fm, fl F,
не непременно различни, такива че f0 T0, f1 T1, fs S,
fm M, fl L. Да означим F = { f0, f1, fs, fm, fl}, F F.
Ще покажем, че xy, [F].
Функцията g0 (x) = f0 (x, x, …, x) [F], тъй като във функцията
f0 сме заместили променливи. Имаме g0 (0) = f0 (0, 0, …, 0) = 1, тъй като f0 T0. Функцията g1 (x) = f1 (x, x, …, x) [F], тъй като във функцията f1 сме заместили променливи.
Имаме g1 (1) = f1 (1, 1, …, 1) = 0, тъй като f1 T1.
За g0 (1) и g1 (0) имаме четири възможности:
1. g0 (1) = 0 и g1 (0) = 0 – тогава g0 (x) = , g1 (x) =
и така [F] и g0 (g1 (x)) = [F];
2. g0 (1) = 0 и g1 (0) = 1 – тогава g0 (x) = и g1 (x) =
и така [F];
3. g0 (1) = 1 и g1 (0) = 0 – тогава g0 (x) = и g1 (x) =
и така [F], [F];
4. g0 (1) = 1 и g1 (0) = 1 – тогава g0 (x) = и g1 (x) =
и така g1 (g0 (x)) = [F] и [F].
Така в три от случаите получихме двете константи.
Да разгледаме втория случай, при който получихме само отрицанието.
Функцията fs S съществува = a1a2…an J2n, така че
fs () = fs (). Функцията gs (x) = fs () [F]:
ако ai = 1, то = x и заместваме само променлива,
ако ai = 0, то = , но в този случай [F] и заместваме променлива с формула над F, така че отново получаваме
Редактор: Снежина Стоянова
