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


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


   и 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, така че отново получаваме



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





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