Минимизация дегеніміз - логикалық функцияларды қарапайым түрге келтіру арқылы, оны аппараттық жолмен қолдануға немесе есептеуіш құралдың модуліне қолдануға даярлық жасауды айтады. Минимизацияның аналитикалық және графикалық әдістері бар. Аналитикалық әдіске машиналық минимизациялау алгоритмдерін жатқызуға болады.
Аналитикалық минимизацияны - жобалаушы өз интуициясына сүйене отырып жасайды, әрі бұл минимизация қарапайым функиялар үшін (аз аргументтермен) қолданылады. Күрделі функцияларды қысқарту үшін машиналық алгоритмдер жасалған. Кей жағдайларда минимизацияны Квайн теоремасы арқылы жүзеге асыруға болады.
Графикалық минимизация - Карно картасын қолдануға негізделген. Карно картасы – бұл торларға бөлінген тік төртбұрыш. Ондағы торлардың саны функция жинтығының максималды санына яғни 2n, (мұндағы n-аргументтер саны), тең. әрбір тор бір жиынға сәйкестендірілген және онда жиынның мәні жазылады: 1 немесе 0. Функция анықталмаған жағдайда Карно картасы белгісіз жиындар үшін (-) таңбасымен) таңбасымен толтырылуы мүмкін., тыйым салынған жиындар үшін ( ) таңбасымен толтырылуы мүмкін.
Логикалық функцияларды азайту схемалық технологияны оқыту процесінде типтік міндеттердің бірі болып табылады.
Кез-келген логикалық функцияны аксиомалар мен логикалық теоремалар арқылы тікелей жеңілдетуге болады, бірақ, әдетте, мұндай түрлендірулер күрделі есептеулерді қажет етеді.
SDNF немесе SCNF түрінде ұсынылған логикалық функцияларды азайтудың негізгі әдісі-жұптық толық емес желімдеу және элементар сіңіру операциясы. Жұптық желімдеу операциясы бірдей айнымалылары бар екі термин (терминдер) арасында жүзеге асырылады, олардың пайда болуы (түзу және кері) бір айнымалыдан басқа барлық айнымалыларға сәйкес келеді. Бұл жағдайда бір айнымалыдан басқа барлық айнымалыларды жақшадан шығаруға болады, ал жақшада қалған бір айнымалының тікелей және инверсиялық пайда болуы желімделеді. Мысалы:
Сіңіру мүмкіндігі айқын теңдіктерден туындайды
Осылайша, SDNF және SCNF-ті азайтудың негізгі міндеті-желімдеуге жарамды терминдерді іздеу, содан кейін сіңіру, бұл үлкен формалар үшін өте қиын міндет болуы мүмкін. Карно карталары мұндай терминдерді табудың көрнекі әдісін ұсынады.
Суретте осы кестеге сәйкес келетін екі айнымалы функцияның қарапайым ақиқат кестесі көрсетілген 2 өлшемді текше (шаршы), сондай-ақ SDNF мүшелерін белгілейтін 2 өлшемді текше және терминдерді топтастыруға арналған баламалы кесте:
Үш айнымалы функция жағдайында үш өлшемді текшемен күресу керек. Бұл күрделірек және көрнекі емес, бірақ техникалық тұрғыдан мүмкін. Суретте мысал ретінде үш айнымалының логикалық функциясы үшін ақиқат кестесі және оған сәйкес текше көрсетілген.
Суреттен көріп отырғаныңыздай, үш өлшемді жағдай үшін терминдердің күрделі конфигурациялары мүмкін. Мысалы, текшенің бір бетіне жататын төрт термин екі айнымалының жұтылуымен бір терминге біріктіріледі:
Жалпы алғанда, гиперкубтың бір k–өлшемді бетіне жататын 2K терминдер бір терминде бір-біріне жабысып, k айнымалыларын сіңіреді деп айтуға болады.
Сабақтың соңы
(15 минут)
|
1) Минимизация дегеніміз не?
2) Аналитикалық әдіске қандай минимизациялау алгоритмдерін жатқызуға болады?
3) Логикалық функциялырды аналитикалық минимизациялау ерекшеліктеріне нақты мысал келтіріңіз?
4) Логикалық функциялырды графикалық минимизациялау ерекшеліктеріне нақты мысал келтіріңіз?
|
Қорытынды
(5 минут)
|
Цифрлық жүйелер оқулық.
21. 147 бет.
|
Достарыңызбен бөлісу: |
