-дәріс тақырыбы: Буль функцияларының толық жүйелері

{, , }; {, }; {,}; {}; {}; {,,1}; {,}; {,,}; {, , }; т.б

Бұлардың ішінде көбірек зерттелгені {, , }-базис; Бұлар буль формулалары деп аталады.

Анықтама. Логикалық функциялар жиыны Р₂-негізгі жиыны, ал операциялары-дизъюнкция, конъюнкция, терістеу болатын {Р₂; , , } алгебрасы логикалық функциялардың бульдік алгебрасы деп аталады.

1-Теорема. Кез келген логикалық функция буль формуласы түрінде кескінделеді яғни дизъюнкция, конъюнкция, терістеудің суперпозициясы. Бұдан буль формулаларының жүйесі {, , }; функциональды толық жүйе. Бұл кесте түрінде берілген кез келген функцияны буль алгебрасының формуласы түрінде кескіндеуге болатындығын көрсетеді.

2-Теорема. Егер функционалды толық * жүйенің барлық функциялары -жүйенің формулалары арқылы өрнектелетін болса,онда -жүйе де функционалды толық жүйе болады.

Кез келген жүйенің толықтығы туралы сұраққа Пост теоремасы жауап береді:

Р₀–класы. Бұл 0-ді сақтайтын буль функциялары класы, яғни f(0,0,…,0)=0 болатын функциялар. Р₀ f  f (0,0,…,0) = 0}.

Р₁–класы. 1-ді сақтайтын функциялар класы, яғни f (1,1,…,1) =1 болатын функциялар. Р₁ f  f (1,1,…,1) = 1}

S-өзіне-өзі түйіндес функциялар класы. S={f  f-өзіне-өзі түйіндес функция}

5. L-сызықты функциялар класы.

с₀=f(0,0,…,0), c₀c₁=f(1,0,…,0), c₀c₂=f(0,1,…,0),...,c₀c_n=f(0,0,…,1) яғни с₀ =f(0,0,…,0), c₁=c₀f(1,…,0),…,с_n=c₀f(0,0,…,1)

Сонымен f–функциясының сызықтығын тексеру деген с_i коэфициенттерінің тауып, берілген формуланың ақиқаттық кестесімен табылған c₀с₁х₁...c_пх_п формуланың ақиқат кестесін салыстыру болып табылады. Мысалы. xy функциясы сызықты ма ?

Тексеру: c₀=oo=o; c₁=c₀f(1,0)=0(10)=1; c₂=0(f(0,1))=0(01)=1;

Сонымен c₀c₁хc₂yxy; x v y пен xy ақиқат кестесі бірдей емес. Ендеше x v y–cызықты емес. Егер функцияның МДҚФ тұріндегі V–операциясының орнына  қойылса онда сызықты функцияның мүлтіксіз полиномды қалыпты түрін аламыз. (МПҚФ) (дизъюнкция белгісінің орнына ). Бұл Жегалкин полиномы деп аталады.

Мысалы. F(x₁,x₂,x₃)=(x₂x₃)(x₁x₂) функциясын 2 модулі бойынша қосу полиномы түрінде жазу керек.

(P₂, , , 1)–Жегалкин алгебрасы деп аталады. ={ ,,1} болып белгіленеді:

сигнатура деп аталады.

Анықтама. Егер Жегалкин көпмүшелігінің құрамында айнымалылардың көбейтіндісі бар болса, онда көпмүшелік сызықты емес деп аталады, жоқ болса сызықты деп аталады.

Буль функциясының сызықтылығы Жегалкин көп мүшелігінің сызықтылығымен эквивалентті яғни Жегалкин көпмүшелігі сызықты болса оған сәйкес буль функкциясы да сызықты болады.

f(0,0)=1; f(1,1)=0, f(x₁y)P_o және f(x₁y)P₁

f(1,0)f(0,1) болғандықтан f(x, y)S;

f(0,0)f(1,1) болғандықтан f(x, y)M;

Буль функциялар жүйесі толық болса базис деп аталады, ал жүйеден кез келген функция алынып тасталса жүйе толық емес болады.