Дәріс 3 Бульдік функцияларды аналитикалық көрсету. Бульдік функцияларды ықшамдау

ЛАФ аналитикалық жолмен көрсету. Кез келген логикалық алгебра функциясын базис құратын кейбір элементар функциялардың суперпозициясы арқылы көрсетуге болады. Бұл жерде ЛАФ минималь логикалық өрнек түрінде болуы мүмкін. ЛАФ аналитикалық жолмен өрнектеуге мүмкіндік беретін ең көп таралған дизьюнкция, коньюнкция, логикалық терістеу сияқты элементар функциялардан тұратын базис болып табылады. Бұл базисті бульдік базис (,&,Х) деп те атайды.

Логикалық функциялардың ішінен аргументтердің тек бір жиынтығында ғана бірге айналатын, ал барлық қалған (2ⁿ-1) жиынтықтарда нольге айналатын функцияларды жеке (бөліп) атауға болады. Мұндай функциялар бірдің конституенті деген атқа ие болады. Элементар функциялар ішінен бұған дизьюнкция функциясы, Пирс (Вебба) функциясы және терістеу функциялары жатады.

Бірдің констуенті анықтамасынан бірдің констуенті ретінде аргументтің логикалық функциясын беру үшін функцияны бірге айналдыратын бір ғана аргументтер жиынтығын берсе жеткілікті. Ол үшін коьюнкция белгісімен байланыстырылған тура немесе терістелген х₁, х₂,..., х_n айнымалыларынан коньюнктивтік терм (минтерм) құрастырылған. Терм бірге тек бір ғана жиынтықта айналуға тиіс, ал басқа жиынтықтарда ноль мәнін алуға тиіс. Ол үшін көрсетілген жиынтықта нольге тең болатын айнымалылар терістеу белгісімен алынады. Егер a_i жиынтықтағы x_i айнымалысының мәні болса, онда функцияның жалпы түрі былай жазылады: f мұнда

Логикалық функциялары бірге айналатын бірнеше жиынтықтар бар болса,онда олардың әрқайсысы бірдің конституентін (минтерм) түзеді де олар дизьюнкция белгісімен біріктіріледі. Мұның нәтижесінде логикалық өрнек ЛАФ аналитикалық өрнек түрінде алынады: f

Бұл формулада -дизьюнкция функция тек бірлік мән қабылдайтын жиынтықтар бойынша алынатынын көрсетеді. ЛАФ бірдің конституенті (минтерм) түрінде өрнектеу қалыпты дизьюнктивтік форма (ҚДФ) деп аталады. Егер сонда термдердің әрбірі n айналымдардан құрылса, онда ЛАФ аналитикалық өрнектелуі жетілген ҚДФ деп аталады (ЖҚДФ).

Егер логика функциясын нольдің конституенті түрінде беру керек болса, онда дизьюнктивтік термді (макстермді) пайдаланады. Бұл жерде х_1, х_2,..., х_n айнымалыларын тура немесе теріс формада алып, дизьюнкция белгісімен байланыстырады. Терм бір жиынтықта нольге, ал барлық қалған жиынтықтарда бірге айналуы керек. Ол үшін көрсетілген жиынтықтарда бірге тең айнымалылар терістеу белгісімен алынады. Функция жалпы түрде былай жазылады: f , бұл жерде

Бірнеше жиынтықта ноль мәнін алатын ЛАФ өрнектеу үшін бұл жиынтықтарды нольдің конституенттері (макстермдер) түрінде бере отырып, оларды коньюнкция белгісімен біріктіру қажет. Бұл жағдайда ЛАФ мына түрде жазылады: f , формулада -коньюнкция функция ноль мәнін алатын жиынтықтардан құрылатындығын көрсететін белгі. Логика алгебрасы функциясын нольдің конституенттері коньюнкциясы түрінде өрнектеу қалыпты коньюктивті форма (ҚКФ) деп аталады. Егер барлық макстермдерде n айнымалылардың бәрі бар болса, онда ҚКФ жетілген (ЖҚКФ) деп аталады. Кез келген ЛАФ ЖҚКФ немесе ЖҚДФ түрінде жазылады. Кесте түрінде берілген логикалық алгебра функциясының ЖҚДФ алу үшін:

1) функция 1 мәнін қабылдайтын аргументтер жиынтықтарының бәрін белгілейді;

2) әрбір белгіленген жиынтық үшін аргументтер коньюнкциясын жазып алады; егер белгіленген жиынтықта аргумент 1 болса, онда алынған коньюнкция терістелмейді, ал қарсы жағдайда аргумент терістеледі;

3) алынған коньюнкциялар дизьюнкция белгісімен қосылады.

Мысал. 2.6-кестеде ЛАФ үш аргументпен берілген. Осы ЛАФ ЖҚДФ алу үшін: 1) f(х₁ х₂ х₃)=1 мәнін қабылдайтын аргументтер жиынтығын белгілейміз; 2) коньюнкцияларын жазып аламыз;

3) алынған коньюнкцияларды дизьюнкция белгісімен қосамыз;

f()= .

Алынған аналитикалық өрнек f(х_1, х_2, х₃) қалыпты деп аталады, өйткені терістеу белгілері аргументтердің функцияларына емес олардың өздеріне оның әрбір коньюнктивтік мүшелері n аргументтерден тұрады.

2.6 – кесте

Аналитикалық жолмен берілген ЛАФ өрнегінен кестелік өрнекке көшу былай орындалады:

1) аргументтердің барлық мүмкін болатын жиынтықтарының кестесі құрылады;

2) әр жиынтықтағы аргументтер мәнді ЛАФ аналитикалық жазылуына тікелей қойылады да элементар ЛАФ анықтамасы негізінде әрбір жиынтықта оның мәні есептеледі;

3) есептелген мән қаралған жиынтықта сәйкес келетін кесте жолына жазылады.

Аналитикалық жолмен көрсетілген ЛАФ элементар фнкциялардың қасиеттерін пайдалана отырып түрлендіруге болады. Түрлендіру мақсаты-терм сандарын және термдегі айнымалыларды азайту, басқаша айтқанда минималь қалыпты форма алу.

Әрбір айнымалысы бір реттен артық кездеспейтін терм элементар терм деп аталады. Термді құратын айнымалылар саны оның рангі (r) деп аталады. Бірдей айнымалылардан құрылған екі элементар терм бір-бірінентек бір айнымалы терістелуімен өзгеше болса, онда оларды көрші термдер деп атайды. Көрші термге мысал: .

Рангі r екі көрші терм дизьюнкциясын берілген термдердің ортақ бөлігі болатын рангі r-1 элементар ықшамдалған терммен ауыстыруға болады: . Біреуі екіншісінің бөлігі болатын, рангтері әр түрлі екі элементар минтермдердің дизьюнкциясын кіші рангті минтерммен ауыстыруға болады: =

Дизьюнктивтік термдерді жапсыру арқылы көрші тұрған екі (рангі) макстермдер коньюнкциясын бастапқы термдердің жалпы бөлігі болып келетін рангі r-1 элементар термдермен алмастыруға болады: y=

Біреуі екіншісінің бөлігі болатын әр түрлі рангті екі элементар макстермдер коньюнкциясын рангі кіші макстерммен ауыстыруға болады:

y=

ЛАФ ықшамды түрін алу үшін оны жетілген қалыпты формада (коньюнктивтік немесе дизьюнктивтік) кескіндеп, оған жапсыру не сіңіру ережелерін қолдану керек.

Мысал. 2.6-кестемен берілген функция үшін МҚДФ табу керек.

Шешуі. Функцияның ЖҚДФ формасын жазып оны түрлендіреміз:

f ()=

Түрлендіруде жапсыру ережесі тек бірдей сызықтармен сызылған термдерге қолдану арқылы жасалады.

Бульдік функцияларды ықшамдау. Квайн-Мак-Класки әдісі. Жетілген қалыпты формалардан (ЖҚДФ және ЖҚКФ) тікелей минималь қалыпты формаларды (МҚДФ және МҚМФ) жапсыру және сіңіру ережелерін қайта-қайта қолдану арқылы алуға болады. Бұл ережелерді қолданғанда термдерді жүйесіз салыстыру кезінде минималь қалыпты формалар қажетті төменгі рангті термдер толық алынбауы мүмкін. Квайн әдісі 1952 жылы термдерді қос-қостан салыстыру операциясын ретке келтіріп, минималь қалыпты форманы алу алгоритмін анықтайды. Квайн әдісімен минимальдау үшін бастапқы функция ЖҚДФ берілген деп ұйғарылады. Оған кіретін барлық термдер қос-қостан салыстырылып, оларға қайсыбір айнымалы бойынша жапсыру операциясын қолданамыз: . Мұнда F-r=(n-1) рангті терм. Сонымен терм рангін r=n -нен r=n-1 -ге дейін төмендетіледі. Бұл операция қажетінше қайталанады. Жапсыру операциясына қатыспайтын термдерді бастапқы импликанттар деп атайды. Дизъюнкция белгісімен байланысқа бастапқы импликанттар жиыны МҚДФ түрінде бола бермейді. Сондықтан алынған импликанттар жиыны кейбір бастапқы импликанттарды алып тастау жолымен ықшамдалады. Алып тасталған имплианттар функцияның тепе-теңдігін бұзбауы керек. Квайн әдісінің елеулі кемістігі жапсыру амалын қолдану үшін барлық термдерді қос-қостан салыстыру керектігінде.

1956 жылы Мак-Класки конъюнктивтік термдерді () екілік айнымалылар жиынтығы түрінде жазуды ұсынды. Мұнда термге t -куб сәйекстендіріледі. Бұл термдердің епетейсіз жазылуынан айырып, жапсыру операциясын қолдану үстінде термдерді қос-қосап салыстыру санын қысқартуға мүмкіндік береді. Өйкені барлық айнымалылар жиынтықтарын олардағы бірліктер санымен қиылыспайтын топтарға бөлуге болады, і-топқа і-бірліктері бар барлық жиынтықтар кіреді. Бұл жағдайда тек көршілес топтағы жиынтықтар бір-бірімен салыстырылады. (i-1) топ пен і топ; і топпен і+1 топ және т.с.с. көршілес емес топтарға кіретін жиынтықтар бір-бірімен кем дегенде екі бірліктермен өзгеше болады.

Сондықтан олардың жапсырылу ықтималдығы 0-ге тең. Төменде Квайнның Мак-Класки жетілдірген (Квайн-Мак-Класки әдісі) кезеңдерге бөлінген формальді алгоритмі баяндалады.

1-кезең. Бастапқы импликантты табу. ЖҚДФ-ға кіретін барлық {m} термдерді екілік айнымалылар жиынтығы түрінде (0-кубтар К⁰ кешені) топтап олардағы бірліктер санына қарай жазып алады. Көршілес екі жиынтыққа жапсыру амалы қолданылады. Нәтижелерді топтап 1-кубтар К¹ кешені түрінде жазылады. Көршілес топтарға (К¹) кіретін 1-кубтар бір-бірімен салыстырып 2-кубтар түзіледі. Бұл салыстыру және жапсыру амалдары t кубтардың K^t кешентерін алғанша орындалады. Олар бір-бірімен жапсырылуы тиісті емес. Жапсыру амалдарына қатыспаған кубтар бастапқы импликанттар {l} жиынтығын құрады.

2-кезең. Импликанттық матрица құру. Матрицаның жолдарын бастапқы импликанттармен, ал бағандарын алғашқы (негізгі) импликанттармен (0-кубтармен) белгілейді. Егер бастапқы импликантта терміне енсе онда і жолымен j баған қиылысқан жеріне белгі қойылады.

3-кезең. Мәнді импликанттарды табу. Егер импликанттық матрицаның қайсыбір бағынында тек бір ғана белгі болса, онда осы белгіге сәйкес келетін алғашқы импликантта мәнді болып табылады, өйткені онсыз берілген термдердің барлық жиынтығын {m} алуға болмайды. Мәнді импликанттар міндетті түрде МҚДФ құрамына кіруі керек. Мәнді импликанттармен жабылатын термдерге сәйкес келетін бағандар және мәнді импликантты жолдар матрицадан сызылып тасталады.

4-кезең. Басы артық бастапқы импликанттарды сызып тастау. Алдыңғы кезеңдер орындалған соң, импликанттық матрицада бірде-бір белгісі жоқ жолдар пайда болуы мүмкін. Мұндай жолдарға сәйкес келетін бастапқы импликанттар әрі қарай қаралмайды, өйткені олар матрицадағы қалған алғашқы термдерді жаба алмайды.

5-кезең. Минималь жабын алу. Импликанттық матрицаның жолдары мен бағандарын сызып тастағанмен алынған матрица зерттеледі. Қалған жолдар ішінен қалған алғашқы термдерді тегіс жабатын бастапқы импликанттар жиынтығы іріктелініп алынады. Мұндай импликанттардан әріп сандарын аз жиынтық таңдалынып алынады. Оларға мәнді импликанттарды қосып, мөлшері әр-түрлі куб түрінде жазылған бастапқы импликанттардан рангі әр түрлі конъюнктивтік термдерге көшіріледі. Соңғыларды дизъюнкция белгісімен біріктіріп МҚДФ алынады.

Мысал. Квайн-Мак-Класки әдісімен f(x₁,x₂,x₃,x₄) логикалық функциясының МҚДФ табу керек: f(x₁,x₂,x₃ x₄)=

=

Шешуі. К⁰ кешені бірнеше топқа бөлінеді:

мұнда кешентердің төменгі индекстері топқа енетін кубтардағы бірліктер санын көрсетеді.

1-кезең. Бастапқы импликанттарды табу (* белгісімен жапсыру амалына қатысатын термдер белгіленеді).

а) ,

салыстырылады, жапсыру нәтижесінде алынады:

салыстырылады, жапсыру амалынан кейін мынадай нәтижеге ие боламыз:

салыстырылады, жапсыру амалын орындай отырып мынадай нәтиже аламыз:

Барлық 0-кубтар 1-кубтарды алуға қатысады, сондықтан олардың ешқайсысы бастапқы импликант болмайды.

ә) Әрі қарай және салыстырылады да, нәтижесі алынады:

мен салыстырып, нәтижесі алынады:

кубында , кубында

кубында термдер бірде –бір * символымен белгіленбеген. Сондықтан олар 3 рангті бастапқы импликанттар болып табылады:

б) мен кешентерін салыстыра отырып оларды құратын 2-кубтар үлкен кубтар құрамайтынын байқауға болады (жапсырылмайды). Сондықтан барлықалынған 2-кубтар бастапқы импликанттар болып табылады:

2-кезең. Импликанттық матрица құру. Импликанттық матрица 7 жолдан және 10 бағанадан тұрады. 2.7-кесте белгілері бар матрица келтірілген.

2.7 – кесте

mj
010X	*	*
X100	*							*
01X1		*	*
X111			*							*
10XX				*	*	*	*
1XX0				*		*		*	*
1X1X						*	*		*	*

3-кезең. Мәнді импликанттарды табу. Импликанттық матрицада бір белгілі тек бір ғана баған бар. Бұл белгіге 10ХХ мәнді импликантта сәйкес келеді. 2.7-кестеден мәнді 10ХХ импликантпен жабылатын баған –термдер және ол импликантқа сәйкес келетін жол сызылып тасталады. Соның нәтижесінде 2.8-кесте алынады.

4-кезең. Басы артық бастапқы импликанттарды сызып тастау.

2.8 – кесте

mj
010X	*	*
X100	*			*
01X1		*	*
X111			*			*
1XX0				*	*
1X1X					*	*

2.8-кестеде мұндай импликанттар жоқ.

5-кезең. Минималь жабу алу. 2.8-кестеден 4-рангті алты термдерді жабатын бастапқы импликанттар жиынтығы таңдалынып алынады: 1Х1Х,01Х1,Х100. Бұл жинақты мәнді импликантпен қоса конъюнктивтік термдерге өтіп МҚДФ алынады:

f(x₁,x₂,x₃,x₄)=

Ең соңғы бесінші кезеңде бастапқы импликанттардың басқа жиынтығын таңдауға болады: 1ХХ0,Х111,010Х. Мұндай жиынтықта

f(x₁,x₂,x₃,x₄)=

Табылған бірінші және екінші жазылуларда сан жағынан бірдей әріптер қолданылып отырғандықтан олардың екеуі де МҚДФ болып табылады. Қаралған әдісті МҚКФ үшін де қолдануға болады. Ол үшін мәні және осы мәнге сәйкес термдер қаралады.

Минимумдаушы карталар әдісі. Аса көрнекі және қарапайым әдіс – Вейч-Карно картасын пайдаланып минимумдау әдісі. Сонда ЛАФ-ты көрсету үшін графиктік өрнектеу әдісі қолданылады. Жапсыру және сіңіру операциясы графиктік (көзбен шолу) жолмен орындалады. Сонда 0-кубтарға сәйкес келетін барынша көп “1” мәндерін жабыстыруға тырысады. Екі көрші “1” өз мәнін өзгертетін айнымалылары жоқ айнымалылар конъюнкциялармен белгіленетін 1-куб құрайды. Төрт көрші “1” белгіленуінде екі айнымалы жоқ болатын 2-куб құрайды. Сегіз көрші “1” 3-куб құрады. Оның айнымалылар конъюнкицясында үш айнымалы болмайды. Мысалы, 4 айнымалыдан тәуелді ЛАФ ЖҚДФ түрінде берілсін: f(x₁,x₂,x₃,x₄)

2.3-суретте берілген ЛАФ графиктік түрде көрсетілген. Көрші төрт “1” 2-куб құрайды. Демек, f .

Жалпы түрде Вейч-Карно картасын пайдалана минимумдау ережесін мына түрде тұжырымдауға болады: саны болатын көршілес “1” (0-кубтар) біріктіріліп, алғашқы 0-кубтарда әртүрлі мән қабылдайтын айнымалылар орнына t бос компоненттері бар бір t- куб құрады. ЛАФ минималь өрнектеу үшін барлық 0-кубтар (біліктер) неғұрлым көп көлемді, бірақ аз мөлшерлі кубтармен жабылуы керек. Сонда бір ғана 0-куб бірнеше кубтар құрғанда пайдаланылуы мүмкін. Алынған кубтар дизъюнкция белгісімен біріктіріледі.

Вейч-Карно картасы әдетте айнымалылар аз (n-1,2,3,4,5) болатын Бульдік функцияларды минимумдауға қолданылады. Егер n>4 болса Вейч-Карно картасы қарапайым карталардан (n-4) құрастырылады; мысалы n-5 болса, төрт айнымалы екі карта пайдаланылады. Ал n-6 болса, онда мұндай төрт карта пайдаланылады және т.с.с. Минимудау алдымен осы қарапайым карталардың ішінде жүргізіледі, одан барып қарапайым карталар арасындағы көрші торлар іздестіреді. Көрші торлар деп қарапайым карталарды бірінің үстіне бірін салғанда бір-біріне дәл келетін торларды айтады.

Мысал. ЛАФ 0 мәнін үшінші (011) және жетінші (111) жиынтықтарда қабылдайды. Функцияны Пирс базисінде минимумдау үшін ЛАФ-ты ЖҚПФ түрінде жазып, жапсыру операциясын қолдану керек.

Нәтиже бірмүшелік түрінде болғандықтан квадрат дәрежеге шығарылады.

Қарастырылған базистерде бульдік функцияларды минимумдау мәселесін, ҚДФ пен ҚКФ өрнектеріне өтудің белгілі қатыстарын пайдаланып сәйкес ҚДФ пен ҚКФ функцияларын минимумдау мәселесіне келтіруге болатынын атап өтейік.