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) нөлдер мен бірлер жиынтығында 1  1,..., n n шарттың орындалуынан
f (1,…,n) f (1,…,n) орындалса f (х1,х2,…,хп) функциясы монотонды деп аталады. М { f f – монотонды функциялар }.
5. L- сызықты функциялар класы.
Егер буль сақинасында < {0,1}, , > f- функциясы f (х1,х2,…,хп) = c0 c1x1 c2x2 … cnxn түрінде өрнектелетін болса, мұндағы с1,с2,...,сn  {0,1} онда Буль функция сызықты деп аталады. c0 с1с2,...,сп коефициенттері төмендегідей анықталады.
с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 = o (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 x1x2 x3 x3 x1 x2 x1x2 1= x2 x1x3 x2x3 x1x2 x3 1
(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 = 
 = (x 1) (y 1) = сызықты емес. Мынадай кесте қүруға болады:
Пост теоремасы Буль функциялар жүйесі Ғ толық жүйе болады тек сонда ғана, егер әрбір P0, P,S,M,L кластары үшін Ғ жүйесінен осы класқа жатпайтын функция табылса.
|
функция
|
кластар
|
|
Po
|
P1
|
S
|
M
|
L
|
 
|
жоқ
|
жоқ
|
жоқ
|
жоқ
|
жоқ
|
|
Бұл теоремадан жоғарыдағы функция толық жүйе құрады, яғни Шеффер функциясы арқылы кез келген буль функциясын алуға болады:
х x x, x y  (x y) (x y)
Буль функциялар жүйесі толық болса базис деп аталады, ал жүйеден кез келген функция алынып тасталса жүйе толық емес болады.
Теорема. Әрбір базис 4-тен артық емес буль функциясынан тұрады. Мысалы,
{, }, {, }, {, }, { }, { }, { , v, 0 },{ , , , } базистер.
1-мысал. (P2, ,,1) – Жегалкин алгебрасындағы = { ,,1}сигнатурасы функционалды толық жүйе. Бұл кез келген логикалық функция сигнатурамен кескінделетіндігін,яғни кез келген логикалық функция айнымалылар мен { ,,1} операция символдары арқылы өрнектелетіндігін көрсетеді.. { ,,1} – функцияналдың толықтығын дәлелдеу үшін.
а)  = x 1
б) x 0 = 1
|
в) x1(x2 x3) = x1x2 x1x3
г) x1 x2 = x1x2 x1 x2
|
е) x = 1
|
қатынастары қолданылады. Формулалардың эквиваленттігін дәлелдеудің стандартты әдісін қолданып,бұл қатынастардың дұрыстығына көз жеткізуге болады.
х
|
|
1
|
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
|
|
|
*
|
|
|
  *
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
|
Бірінші теоремадан Буль функцияларының жиыны * { , , }-функционалды толық. 2-теорема бойынша = { ,,1} жүйесінің толықтығын дәлелдеу үшін * { , , }-базистің операцияларын = { ,,1}-базистің операциялары арқылы өрнектеуге болатындығын көрсету жеткілікті. Конъюнкция () операциясы екі жүйеге де ортақ . Енді қалған операциялардың (дизъюнкция (), терістеу( ) ) { ,,1}-символдары арқылы өрнектелетіндігін көрсетсек жеткілікті. Бұл жоғарыдағы а),г) қатынастарынан көрініп тұр.
Негізгі әдебиет: 1[49-54]; 2[192-197].
Қосымша әдебиет: 7[50-80] .
Бақылау сұрақтары:
2. Пост кластарының әрқайсысына анықтама беріңіз.
3. Логикалық функциялардың қандай жүйелері толық деп аталады?
4. Функционалдық толықтығы туралы Пост теоремасы қандай?
5. Қандай логикалық функциялар сызықты деп аталады ?
6. Жегалкин алгебрасына қандай логикалық функциялар кіреді?
Достарыңызбен бөлісу: |
