Жұмыс бағдарламасы (силлабус) осы мамандықттардың Қр мжмбс 08. 329-2006, Қр мжмбс 08. 33-2006 Мемлекеттік стандартына сәйкес құрылған
-дәріс тақырыбы: Буль функцияларының толық жүйелері
жүктеу/скачать 21,8 Mb.
|
| 8-дәріс тақырыбы: Буль функцияларының толық жүйелері. Пост теоремасы (2-сағ)
Дәріс конспекті: Буль функцияларының толық жүйелері. Кез келген логикалық функция өрнектелетін логикалық операциялардың жиынтықтары болады. Мұндай операциялар жиыны функционалды толық жүйелер немесе базис деп аталады. Функционапды толық жүйелерге немесе базистерге мысалдар. {, , }; {, }; {,}; {}; {}; {,,1}; {,}; {,,}; {, , }; т.б Бұлардың ішінде көбірек зерттелгені {, , }-базис; Бұлар буль формулалары деп аталады.
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) нөлдер мен бірлер жиынтығында 1  1,...,nn шарттың орындалуынан
f(1,…,n) f(1,…,n) орындалса f(х1,х2,…,хп) функциясы монотонды деп аталады. М{f f–монотонды функциялар}.
5. L-сызықты функциялар класы. Егер буль сақинасында <{0,1}, , > f-функциясы f(х1,х2,…,хп)=c0c1x1c2x2…cnxn түрінде өрнектелетін болса, мұндағы с1,с2,...,сn  {0,1} онда Буль функция сызықты деп аталады. c0с1с2,...,сn коэфициенттері төмендегідей анықталады.
с0=f(0,0,…,0), c0c1=f(1,0,…,0), c0c2=f(0,1,…,0),...,c0cn=f(0,0,…,1) яғни с0 =f(0,0,…,0), c1=c0f(1,…,0),…,сn=c0f(0,0,…,1) Сонымен f–функциясының сызықтығын тексеру деген сi коэфициенттерінің тауып, берілген формуланың ақиқаттық кестесімен табылған c0с1х1...cпхп формуланың ақиқат кестесін салыстыру болып табылады. Мысалы. xy функциясы сызықты ма ? Тексеру: c0=oo=o; c1=c0f(1,0)=0(10)=1; c2=0(f(0,1))=0(01)=1; Сонымен c0c1хc2yxy; x v y пен xy ақиқат кестесі бірдей емес. Ендеше x v y–cызықты емес. Егер функцияның МДҚФ тұріндегі V–операциясының орнына қойылса онда сызықты функцияның мүлтіксіз полиномды қалыпты түрін аламыз. (МПҚФ) (дизъюнкция белгісінің орнына ). Бұл Жегалкин полиномы деп аталады. Мысалы. F(x1,x2,x3)=(x2x3)(x1x2) функциясын 2 модулі бойынша қосу полиномы түрінде жазу керек. f(x1, x2, x3)=(  x3)(x1x2)(x2, x3, 1)(x1x2, x1x2)(x2, x3, 1) (x1x2x1x21)(x2, x3,1)x1x2x1x21(x2, x3,1)(x1x2x1x21)= x1x3x1x2x1x2x2x1x2x2x1x3x2x3x1x2x3x3x1x2x1x21=x2x1x3x2x3x1x2x31
(P2, , , 1)–Жегалкин алгебрасы деп аталады. ={ ,,1} болып белгіленеді: сигнатура деп аталады.
Буль функциясының сызықтылығы Жегалкин көп мүшелігінің сызықтылығымен эквивалентті яғни Жегалкин көпмүшелігі сызықты болса оған сәйкес буль функкциясы да сызықты болады. Мысал. f(x1y)=xy функциясы Пост класстарының қайсысына жататынын анықтау керек. 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= 
 =(x1)(y1)сызықты емес. Мынадай кесте құруға болады: Пост теоремасы Буль функциялар жүйесі Ғ толық жүйе болады тек сонда ғана, егер әрбір P0, P,S,M,L кластары үшін Ғ жүйесінен осы класқа жатпайтын функция табылса.
Бұл теоремадан жоғарыдағы  функция толық жүйе құрады, яғни Шеффер функциясы арқылы кез келген буль функциясын алуға болады:
хxx, xy  (xy)(xy)
Буль функциялар жүйесі толық болса базис деп аталады, ал жүйеден кез келген функция алынып тасталса жүйе толық емес болады. жүктеу/скачать 21,8 Mb. Достарыңызбен бөлісу:
|