Ақиқаттық кесте бойынша МКҚФ құрудың алгоритмі.

Алгоритмді f (x1 ,x2,x3 ) = (0,3,7) функциясына МКҚФ құруға қолданайық.

1. Кестеден функцияны 0-ге айналдыратын аргументтерге сәйкес құрамалар алынады(асты сызылады).

2. Осы құрамаларға сәйкес дизъюнкция жазамыз. Егер хі аргументінің құрамадағы мәні 0-ге тең болса ол конъюнкцияға өзгеріссіз енеді, ал хі=1, болса конъюнкцияға оның терістеуі алынады.

3. Алынған барлық дизъюнкциялар конъюнкциямен жалғастырылады.

Анықтама. Егер f*(x1,x2,…,xn)= онда f*(x1,x2,…,xn) функциясы f(x1,x2,…,xn) функциясына түйіндес функция деп аталады. f(x1,x2,…,xn) функциясына түйіндес функцияны анықтау үшін, барлық айнымалылар және функцияның өзін оның қарама-қарсы мәндеріне ауыстыру керек.

Мысал. Үш айнымалыдан тәуелді функциясын буль формуласы яғни МДҚФ-түрінде өрнектеу керек.

Іздеп отырған МДҚФ

=

Түйіндестік принципі: Егер f функциясын өрнектейтін F формуласындағы барлық операция белгілерін түйіндес функцияның операция белгілеріне алмастырғаннан алынған F* формуласы берілген f функциясының түйіндес функциясын өрнектейтін болады.

Тек &, Ú, а, ж символдарымен ғана байланысқан формулаларды қарастырамыз. &, Ú, а, ж символдары бір біріне түйіндес деп аталады.

Мысалдар: ақиқат–формуласының түйіндесі - жалған;

Егер f1, f2 функциялары тең болса, онда оларға сәйкес түйіндес формулалар да тең болады. онда . Түйіндестік принцип дизъюнкция, конъюнкция, терістеу арқылы байланысқан формулалармен берілген функциялардың түйіндестерін табу үшін ыңғайлы. Бұл жағдайда берілген формулада конъюнкция дизъюнкцияға, дизюнкция конъюнкцияға ауысады. Сөйтіп ДҚФ–КҚФ, КҚФ-ДҚФ, МДҚФ–МКҚФ немесе керісінше.

Мысалы: (

Егер j формуласы m-ге эквивалент болса:j~m онда оларға сәйкес түйіндес формулалар да эквивалентті болады ,яғни j* ~m* болады.

Егер f* (x1,x2,…,xn)=f(x1,x2,…,xn) онда f(x1,x2,…,xn) функциясы өзіне-өзі түйіндес функция деп аталады. Мысалы, j =xyÚxzÚyz функциясы өзіне өзі түйіндес функцияны кескіндейді. Оған (б123) және (1-б1, 1-б2 , 1-б3) жиынтықтарының қарама-қарсы мәндерінде функция да қарама-қарсы мән қабылдайтындығына көз жеткізуге болады. Ол үшін ақиқаттық кесте құрып:

екендігін көреміз.

Мысал: Түйідестік принципіне сүйене отыра, буль алгебрасындағы түйідестік принципінің дұрыстығын дәлелдеу керек. Буль алгебрасында үш амал бар: ;

Буль алгебрасының әр бір амалына түйіндес амалдарды анықтайық.

а) Айталық, болсын.

Олай болса ;

б) Айталық, ;Олай болса ;

в) Айталық, ; Олай болса ;

Сонымен конъюнкция дизъюнкцияға, дизъюнкция конъюнкцияға түйіндес, ал терістеу өзіне өзі түйіндес.

Негізгі әдебиет: 1[49-54]; 2[192-197].

Қосымша әдебиет: 7[50-80] .

Бақылау сұрақтары:

1. Қандай функциялар бір-біріне түйіндес деп аталады? Мысал келтіріңіз.

2. Ақикаттық кесте бойынша формула құру ережелері

 

8-дәріс тақырыбы: Буль функцияларының толық жүйелері. Пост теоремасы (2-сағ)

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

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

{&, Ú, ù}; {&, ù}; {Ú,ù}; {|}; {¯}; {&,Å,1}; {®,ù}; {Ú,~,Å}; {&, ~, Å}; т.б

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

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

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

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

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

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

Р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-өзіне-өзі түйіндес функция}

М–монотонды функциялар класы. Кез-келген (a1, ...,an) және (b1, b2,...,bn) нөлдер мен бірлер жиынтығында a1 b1,...,an bn шарттың орындалуынан

f(a1,…,an) f(b1,…,bn) орындалса 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)

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

Теорема. Әрбір базис 4-тен артық емес буль функциясынан тұрады.

Мысалы.

{Ù,ù }, {Ú,ù }, {®,ù }, {¯ }, {| }, { «, v, 0 },{ Å, Ù, «} базистер.

1-мысал. (P2, &, Å, 1)–Жегалкин алгебрасындағы å={&, Å, 1} сигнатурасы функционалды толық жүйе. Бұл кез келген логикалық функция å сигнатурамен кескінделетіндігін,яғни кез келген логикалық функция айнымалылар мен {&,Å,1} операция символдары арқылы өрнектелетіндігін көрсетеді. {&, Å,1} –функцияналдың толықтығын дәлелдеу үшін.

қатынастары қолданылады. Формулалардың эквиваленттігін дәлелдеудің стандартты әдісін қолданып,бұл қатынастардың дұрыстығына көз жеткізуге болады.

Бірінші теоремадан Буль функцияларының жиыны S*={&, Ú, ù}-функционалды толық. 2-теорема бойынша å={&,Å,1} жүйесінің толықтығын дәлелдеу үшін S*={&, Ú, ù}-базистің операцияларын å={&, Å,1}-базистің операциялары арқылы өрнектеуге болатындығын көрсету жеткілікті. Конъюнкция (&) операциясы екі жүйеге де ортақ. Енді қалған операциялардың (дизъюнкция (Ú), терістеу(ù )) {& ,Å,1}-символдары арқылы өрнектелетіндігін көрсетсек жеткілікті. Бұл жоғарыдағы а),г) қатынастарынан көрініп тұр.

Негізгі әдебиет: 1[49-54]; 2[192-197].

Қосымша әдебиет: 7[50-80] .

Бақылау сұрақтары:

2. Пост кластарының әрқайсысына анықтама беріңіз.

3. Логикалық функциялардың қандай жүйелері толық деп аталады?

4. Функционалдық толықтығы туралы Пост теоремасы қандай?

5. Қандай логикалық функциялар сызықты деп аталады ?

6. Жегалкин алгебрасына қандай логикалық функциялар кіреді?

 









Дата добавления: 2015-08-14; просмотров: 3347; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию, введите в поисковое поле ключевые слова и изучайте нужную вам информацию.

Поделитесь с друзьями:

Если вам понравился данный ресурс вы можете рассказать о нем друзьям. Сделать это можно через соц. кнопки выше.
helpiks.org - Хелпикс.Орг - 2014-2020 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.015 сек.