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


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


формула над F.
Имаме gs (0) = fs () = fs () = fs (),
gs (1) = fs () = fs () = fs ().
Tака gs (0) = gs (1).
Aко gs (0) = gs (1) = 0, то gs (x) =  [F] и g1 (gs (x)) =  [F].
Aко gs (0) = gs (1) = 1, то gs (x) =  [F] и g1 (gs (x)) =  [F].
Така с формули над { f0, f1, fs } построихме константите и във всички случаи.
Функцията fm  M и тогава от лемата по-горе съществуват вектори ,   J2n, такива че    и fm () = 1, fm () = 0.
Нека  = a1…ai-10ai+1…an,  = a1…ai-11ai+1…an.
Функцията gm (x) = fm (a1, …, ai-1, x, ai+1, …, an)  [F], тъй като заместваме променливи с вече получените формули , над F.
Имаме gm (0) = fm (a1, …, ai-1, 0, ai+1, …, an) = fm () = 1,
gm (1) = fm (a1, …, ai-1, 1, ai+1, …, an) = fm () = 0.
Така gm (x) =  [F].
Нека xyz1z2…zk (k  0) е най-късият нелинеен член в полинома на Жегалкин за функцията fl. Такъв има, тъй като fl  L. Във формулата за fl заместваме променливите z1, …, zk с вече получената формула над F и всички останали променливи без
x и y с вече получената формула над F. Така получаваме функция gl (x, y)  [F]. Полиномът на Жегалкин за gl (x, y) има вида gl (x, y) = xy  ax  by  c, тъй като всички останали нелинейни членове съдържат поне една променлива, различна от
x, y, z1, …, zk и се анулират. Да направим следната смяна на променливите: x = u  b, y = v  a. Тя е позволена:
ако b = 0, то u  b = u и заместваме само променлива,
ако b = 1, то u  b =  [F] и заместваме променлива с формула над F, така че отново получаваме формула над F.
Tака получаваме функция
hl (u, v) = (u  b)(v  a)  a(u  b)  b(v  a)  c = uv  d,
където d = ab  c.
Ако d = 0, то hl (u, v) = uv,
ако d = 1, то hl (u, v) = и gm (hl (u, v)) = uv.
Получихме, че конюнкцията е формула над F.
Така { xy, }  [F]  [F] и { xy, } е пълно множество и от една теорема за пълни множества  F е пълно множество.

Казваме, че функцията f  F2 е Шеферова, ако [ { f } ] = F2.
Съгласно теоремата на Пост-Яблонски f е Шеферова 
f  T0, f  T1, f  S, f  M, f  L. Ще покажем едно достатъчно условие за Шеферовост.

Теорема: Нека f  F2 и f  T0, f  T1, f  S. Тогава f е Шеферова.
Доказателство:
Ще покажем, че f  M и f  L и тогава от теоремата на Пост-Яблонски функцията f e Шеферова.
Тъй като f  T0, то f (0, 0, …, 0) = 1.
Също от f  T1  f (1, 1, …, 1) = 0.
Но (0, 0, …0) (1, 1, …, 1) и f (0, 0, …, 0) > f (1, 1, …, 1),
така че f  M.
Да допуснем, че f  L, т.е. f = a0    … .
От f  T0  f (0, …, 0) = 1, т.е. a0 = 1. От f  T1  f (1, 1, …, 1) = 0, т.е. = 0  k е нечетно. Сега
f * = 1  (  1)  … (  1)  1 =   … =
= 1   … = f  f  S – противоречие. Tака f  L.

2. Крайни автомати. Регулярни изрази. Теорема на Клини.

Краен детерминиран автомат наричаме петорката
A = < Q, X, q0, , F >, където
Q е крайно множество от вътрешни състояния,
X е крайна входна азбука,
q0  Q е начално състояние,
 : Q x X  Q е частична функция на преходите,
F  Q е множеството от заключителни състояния.



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





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