1сандық ҚҰрылғылардың математикалық негіздері 2 1 Санау жүйесі 2

1.7 Логикалық функцияларды кішірейту

Ақиқат кестесі бойынша ЖДНФ немесе ЖКНФ-те құралған логикалық функцияның аналитикалық өрнегі молдық болып табылады. Көп жағдайларда оны жеңілдетуге болады. Өйткені функцияның шығыс өрнегіне эквивалентті, бірақ айнымалылар санын немесе операцияларды аз қамтитын мұндай аналитикалық өрнек табуға болады. Логикалық функцияның аналитикалық өрнегінде айнымалылар санын немесе операцияларды кішірейту процедурасы минимизация деп аталады.

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

Минимизацияны әр түрлі тәсілдермен өткізуге болады. Айнымалылардың алты және одан кіші саны көзінше көбірек жіберу Карно картасын (Вейч диаграммалары) қолдану әдісін қамтиды.

1.8 сурет- Карно картасы

Карно картасы нақты ережелер бойынша құралған логикалық функцияның барлық мәндері енгізілген кестесін көрсетеді. Осымен, Карно картасы логикалық функцияның тапсыру тәсілдерінің бірі болып табылады. Карно картасының бейнелеу нұсқалары көп. Осы нұсқалардың бірі 1.8 суретінде көрсетілген екі айнымалы үшін а),үш айнымалы үшін б) төрт айнымалы үшін в). Карно картасының бейнелеуінің қай нұсқасымен қолдануының қағидалы мәні жоқ. Алдымызда 1.8 суретінде көрсетілген Карно карталары қолданылады, және студенттерге де оларды қолдану керек.

1.8 суретінде көрсетілген Карно картасында барлық айнымалылар (X_i) инверсиясыз аудандарда, сызықпен белгіленген. Сызықпен белгіленбеген аудандарда айнымалылар () инверсиясымен болады. Мысалы, Х ₃ айнымалы ауданына 4,5,6,7,12,13,14,15 клеткалар, ал ауданына 0,1,4,5,8,9,12,13 клеткалары жатады. Сонымен, 1.8 суретінде көрсетілген Карно картасында айнымалылар аудандары бар. Кіші айнымалы Х ₁ деп белгіленеді, ал қалған айнымалылардың үлкендері сызба түрде, индекс ұлғаюымен өседі.

Карно картасының әр бір клеткасына нақты және бір минтермге (макстермге) сай. Минтерм индексі Карно картасының клетканың нөмірі болып табылады.

Карно картасы ақиқат кестесі бойынша немесе функцияның аналитикалық өрнегі бойынша толтырылады, оны кішірейту керек.

Егер функция ақиқат кестесі бойынша берілсе, онда Карно картасын толтыру реті келесі.

Ақиқат кестесінің жолағы алынып, осы жолаққа сай клеткасы бар айнымалылар ауданы анықталады. Содан соң Карно картасында бұл аудандар белгіленеді. Бір уақытта барлық белгіленген айнымалылардың аудандарында болатын клетка искомды болады(бір уақытта барлық белгіленген аудандарға жатады, оларға ортақ болып табылады). Табылған клеткаға алынған жолақтың айнымалылар комбинациясына сай функция мәндері қойылады. Осы процедура ақиқат кестесінің барлық жолақтарына қайталанады Карно картасын толық толтырғанға дейін.

Мысалы, 1.6 ақиқат кестесінің 3 жолағына сай Карно картасында клетка табу керек делік. Бұл жолақта келесі айнымалылардың мәндері бар: Х₃ = 0, Х₂ = 1 Х₁ =1. Карно картасында (1.9сурет) аймақтары белгіленеді (инверсті мән өйткені Х₃ = 0) – қызыл түспен (1аудан), Х₂ - көк түспен (2 аудан), Х₁ – жасыл түспен (3 аудан).Барлық үш аудандарға ортақ сары түспен белгіленген клетка болады. Осы клеткаға функция мәні енгізіледі. Қарастырылатын айнымалылар комбинациялары үшін ол 1-ге тең.

Қалған бірлік орнатылмаған клеткаларға нөлдер орнатады.

Мысалы, Карно картасын ƒ(ν) = өрнегі үшін толтвру қажет. Осы өрнекке күрделі конъюнкция кіреді . Оған де Морган ережесін қолдана отырып = аламыз. Дизъюнктивті нормальді формада берілген функция мынандай түрде болады ƒ(ν) = және үш конъюнкциядан тұрады. Бірінші конъюнкция өзіне бір айнымалыны қосады, содан, бірліктер ауданына жататын клеткаларда орнатылады. Осы конъюнкция үшін Карно картасы 1 орнатылымымен 1.10 а) суретінде көрсетілген. Екінші конъюнкция өзіне екі айнымалы қосады: пен , содан, бірліктер бір уақытта пен аудандарына жататын (аудандар қиылысында жатады) клеткаларда орнатылады. Осы конъюнкция үшін Карно картасы 1 орнатылымымен 1.10 б) суретінде көрсетілген. Үшінші конъюнкция өзіне ш айнымалы қосады: , , , содан, бірліктер бір уақытта ,пен аудандарына жататын (аудандар қиылысында жатады) клеткаларда орнатылады. Осы конъюнкция үшін Карно картасы 1 орнатылымымен 1.10 в) суретінде көрсетілген.

1.10 сурет

Осы үш Карно карталарын бір біріне салғанда 1.11а) суретінде көрсетілген карта шығады. Қалған бос клеткаларға 0- ді қойғаннан соң, 1.11б) суретінде көрсетілген толық толтырылған Карно картасы шығады.

1.11 сурет
Карно картасын толтырғаннан кейін кішірейту басталады. Кішірейту процессінде 1 (немесе 0) қамитын барлық клеткалар топтарға біріктірілуі керек.

Топтарға 1 (немесе 0) қамтитын және тікбұрыш немесе квадрат құрайтын көрші клеткалар біріктіріледі. Топ 2 ⁿ клеткалар қамту керек (n = 0, 1, 2, 3 ж т.с.с), басқаша айтқанда 1, 2, 4, 8, 16 және т.с.с клеткалар. Топтар неғұрлым аз болуына тырысу керек, осыған жету үшін әр бір топқа клеткалардың максималды болымды санын қосу керек. Топтарды құру процессі барлық клеткалар топқа біріктірілмегенінше жалғасады.басқалармен біріктіруге болмайтын 1мен (немесе 0мен ) клеткалар, 1 клеткалар санымен топ құады. Сол бір клетка бірнеше топқа кіруі мүмкін.

Көрші клеткаларын анықтағанда Карно картасын көлденеңмен тігімен рулонға орауға болады. Карно картасында 1.8в) суретінде мысалы, көрші клеткалар 2 мен 10 болады; 1, 5, 9 бен 13; сондай ақ 0, 4, 8 бен 12!

Клеткаларды біріктіру теңмәнді нұсқалар бірнеше болуы мүмкін.

Кішірейтілген функцияны дизъюнктивті нормальді формада (ДНФ) немесе конъюнктивті нормальді формада (КНФ) жазады. Жиі ДНФ қолданылады. ДНФ- те клеткаларды бірліктермен біріктіргенде кішірейтілген функция түрі:

клеткаларды нөлдермен біріктіргенде:
,
мұнда С_i – i – ші топ үшін конъюнкция; m – топтар саны.

Конъюнкция өрнегіне инверсиямен инверсиясыз айнымалылар (бірақ бір уақытта емес) ауданында i – ші бүтін болатын топ кіреді.

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

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

Мысалы, 1.12суретінде көрсетілген 1 мен толық клетка топтары қай айнымалы аудандарында екенін анықтау керек.

1.12 сурет

Егер туынды (барлық емес айнымалыларға анықталған) функция ақиқат кестесімен берілсе, онда Карно картасын клеткаларға толтырғанда, оларға функция анықталмаған, функцияның минималды аяққы аналитикалық өрнегі мәндерін орнатады. Карно картасын толтырғанда мұндай клеткаларға жиі (Х) мәнін қояды.

Карно картасы көмегімен функцияны кішірейту реті келесі:

1 Ақиқат кестесін немесе фунцияның аналитикалық өрнегін қолдана отырып,Карно картасын толтырады;

2 Карно картасында 1 мен клеткаларды (немесе 0 мен) біріктіретін топтар жасалынады. 1 немесе 0 бойынша функцияны кішірейту арасындағы қағидалы әр түрлілігі жоқ. Функция минималды өрнегі бар нұсқа алынады;

3 Функцияның таңдалған формада кішірейтілген өрнегін жазады.

Мысалы, келесі ақиқат кестесімен берілген функцияны кішірейту керек

Х 4	Х 3	Х 2	Х 1	f (ν)
0	0	0	1	0
0	0	1	1	1
0	1	0	1	1
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1
1	0	1	1	0
1	0	1	0
1	1	0	1
1	1	1	1