Жұмыс бағдарламасы (силлабус) осы мамандықттардың Қр мжмбс 08. 329-2006, Қр мжмбс 08. 33-2006 Мемлекеттік стандартына сәйкес құрылған


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



бет74/214
Дата13.02.2017
өлшемі21,8 Mb.
#9109
түріМазмұндама
1   ...   70   71   72   73   74   75   76   77   ...   214
8-дәріс тақырыбы: Буль функцияларының толық жүйелері. Пост теоремасы (2-сағ)

Дәріс конспекті:

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

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

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

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

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

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

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



Пост кластарының анықтамасы.

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

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

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



М–монотонды функциялар класы. Кез-келген (1, ...,n) және (1, 2,...,n) нөлдер мен бірлер жиынтығында 11,...,nn шарттың орындалуынан

f(1,…,n)f(1,…,n) орындалса f(х12,…,хп) функциясы монотонды деп аталады. М{f  f–монотонды функциялар}.

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



Егер буль сақинасында <{0,1}, , > f-функциясы f(х12,…,хп)=c0c1x1c2x2…cnxn түрінде өрнектелетін болса, мұндағы с12,...,сn{0,1} онда Буль функция сызықты деп аталады. c0с1с2,...,сn коэфициенттері төмендегідей анықталады.

с0=f(0,0,…,0), c0c1=f(1,0,…,0), c0c2=f(0,1,…,0),...,c0cn=f(0,0,…,1) яғни с0 =f(0,0,…,0), c1=c0f(1,…,0),…,сn=c0f(0,0,…,1)

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

Тексеру: c0=oo=o; c1=c0f(1,0)=0(10)=1; c2=0(f(0,1))=0(01)=1;

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

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



f(x1, x2, x3)=(x3)(x1x2)(x2, x3, 1)(x1x2, x1x2)(x2, x3, 1) (x1x2x1x21)(x2, x3,1)x1x2x1x21(x2, x3,1)(x1x2x1x21)= x1x3x1x2x1x2x2x1x2x2x1x3x2x3x1x2x3x3x1x2x1x21=x2x1x3x2x3x1x2x31

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

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

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

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



Мысал. f(x1y)=xy функциясы Пост класстарының қайсысына жататынын анықтау керек.

f(0,0)=1; f(1,1)=0, f(x1y)Po және f(x1y)P1

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

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



f(x, y) функциясы үшін Жегалкин көпмүшелігі f(x, y)=x y=

=(x1)(y1)сызықты емес. Мынадай кесте құруға болады: Пост теоремасы Буль функциялар жүйесі Ғ толық жүйе болады тек сонда ғана, егер әрбір P0, P,S,M,L кластары үшін Ғ жүйесінен осы класқа жатпайтын функция табылса.



Бұл теоремадан жоғарыдағы функция толық жүйе құрады, яғни Шеффер функциясы арқылы кез келген буль функциясын алуға болады:

хxx, xy(xy)(xy)

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




Достарыңызбен бөлісу:
1   ...   70   71   72   73   74   75   76   77   ...   214




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет