Co je to minimalizacia logickej funkcie?
Tento pojem krasne vysvetluje pani docentka Kubatova vo svojich skriptach. Pri minimalizacii sledujeme jediny ciel a tym je "najst co najjednoduchsie vyjadrenie logickej funkcie". Otazkou zostava, co znamena najjednoduchsie vyjadrenie. Aj na tuto otazku nam skripta poskytuju odpoved. Jedna sa o take vyjadrenie funkcie, ktore obsahuje
- minimalny pocet termov
- minimalny pocet nezavisle premennych v kazdom terme
- minimalny pocet negovanych premennych
Minimalna normalova disjunktivna forma, dalej MNDF je logicky sucet minimalneho poctu minimalnych P-termov
Minimalna normalova konjuktivna forma, dalej MNKF je logicky sucin minimalneho poctu minimalnych S-termov
Co je P-term a S-term sme pisali uz minule, ale mozno sa hodi to trosku zopakovat (kto by si to vsetko pamatal, ze?).
P-term, alebo sucinovy term, je vyraz (term) tvoreny len premennymi a operaciami logickeho sucinu
S-term, alebo suctovy term, je term tvoreny len premennymi a operaciami logickeho suctu
Minterm je taky P-term, ktory obsahuje vsetky nezavisle premenne
Maxterm je taky S-term, ktory obsahuje vsetky nezavisle premenne
Preklad definicie MNDF/MNKF je teda taky, ze sa jedna o sucet/sucin co najmensieho poctu P/S-termov, ktore obsahuju co najmensi pocet premennych a negovanych premennych. To vlastne aj pasuje k "definicii" jednoduchosti vyjadrenia fcie.
Ako minimalizovat?
Huraa :), mozme sa vrhnut na minimalizaciu :). Mame na vyber viacero sposobov (a vsetky je dobre vediet). Minimalizovat mozme pomocou:
- boolovej algebry
- mapy
- metody Quine-McCluskey
Ako nazov naznacuje, jedna sa o sposob minimalizacie pomocou zakladnych a odvodenych zakonov Boolovej algebry. Takze upravujeme funkciu, az kym ju nezminimalizujeme natolko, ze uz dalej to nejde :). K tomu sa jedine da dodat, ze sa pozrite na zakony boolovej algebry a skuste si vypocitat par prikladov. Lepsia cesta snad neexistuje. Inak, toto je celkom odbre opakovanie boolovej algebry, bez ktorej to proste nejde ;). Este jeden detail, v boolovej algebre ma bin. sucin aj bin. sucet rovnaku prioritu, takze bacha na zapis. Moj zapis bude vacsinou zodpovedat pravidlam z algebry realnych cisel (najprv nasobim, potom scitam ... )
Priklad (overit prebraty zo studentskeho servru):
¬(a + b) + a + ab
¬(a + b) + a . (1 + b) {distributivita}
¬(a + b) + a . 1 {agresivita 1 vzhledem ke sčítání}
¬(a + b) + a {neutralita 1 vzhledem k násobení}
¬a . ¬b + a {deMorganův zákon}
b + a {absorbce negace}
Minimalizacia pomocou map
Minimalizacia pomocou map je peknou nazornou metodou minimalizacie. Pouzivat budem Karnaughovu mapu, pretoze je vytvorena tak, aby susedne stavy boli topologicky vedla seba. Na obrazku znazorneny susedny stav pre s=10 pre Karnaughovu/Svobodovu mapu (v poradi).
Ako budeme postupovat:
- funkciu zapiseme do mapy
- budeme si vsimat susedne stavy a hladat vzdy najvacsiu skupinu (vzdy 2^n stavov)
- 1cky ak hladame MNDF
- 0ky ak hladame MNKF
- plati, ze cim vacsia skupina susendych stavov, tym mensi pocet nezavisle premennych potrebujeme k popisu
- vyberieme skupiny, ktore zodpovedaju kriteriu minimality
MNKF: (a' + b') . (a + b + c) . (a + c + d)
MNDF: ab' + a'c + a'bd
Este jeden pekny obrazok map s popisom fcii:
Quine-McCluskey
Tato metoda bola vyvinuta pre pouzitie na cislicovych pocitacoch a pre minimalizaciu logickych funkcii vacsieho poctu nezavislych premennych.
f(d,c,b,a) = SUM(1,4,7,8,9,10,11,12,14,15)
spravime pravdivostnu tabulku:
s d c b a | f(d,c,b,a)
0 0 0 0 0 0
1 0 0 0 1 1
2 0 0 1 0 0
3 0 0 1 1 0
4 0 1 0 0 1
5 0 1 0 1 0
6 0 1 1 0 0
7 0 1 1 1 1
8 1 0 0 0 1
9 1 0 0 1 1
10 1 0 1 0 1
11 1 0 1 1 1
12 1 1 0 0 1
13 1 1 0 1 0
14 1 1 1 0 1
15 1 1 1 1 1
vyberieme si len jednickove stavy, pretoze len s nimi budeme pracovat. V tychto stavoch musime vyhladat a "zgrupit" jednotkove stavy.
1. stavy zoradime podla poctu jedniciek
2. najdeme susedne dovjice medzi skupinami z bodu 1, ale popiseme ich len 3 premennymi. (susedne dvojice sa zhoduju v jednej jednicke a odlisne su v jednom stave)
3. najdeme susedne dvojice
4. najdeme stavy/skupiny, ktore nie su pokryte ziadnou vacsou skupinou stavov - oznacime velkym pismenom a tieto skupiny budu oznacovat priame implikanty funkcie f(d,c,b,a)
Povodne Podla n 1iek Susedne 2ice Susedne 4ice
d c b a | s | d c b a | s | d c b a | s | d c b a | s
0 0 0 1 1 | 0 0 0 1 | 1 | - 0 0 1 | 1,9 F |
0 1 0 0 4 | 0 1 0 0 | 4 | - 1 0 0 | 4,12 E | 1 - - 0 | 8,10,12,14
0 1 1 1 7 | 1 0 0 0 | 8 | 1 0 - 0 | 8,10 | 1 0 - - | 8,10,9,11
| 1 0 0 - | 8,9 | 1 0 - - | 8, 9, 10, 11 C
| 1 - 0 0 | 8,12 | 1 - - 0 | 8,12,10,14 B
1 0 0 0 8 | 1 0 0 1 | 9 | 1 0 - 1 | 9,11 |
1 0 0 1 9 | 1 0 1 0 | 10 | 1 0 1 - | 10,11 | 1 - 1 - | 10,11,14,15 A
| 1 - 1 0 | 10,14 | 1 - 1 - | 10,14,11,15
1 0 1 0 10 | 1 1 0 0 | 12 | 1 1 - 0 | 12,14 |
1 0 1 1 11 | 0 1 1 1 | 7 | - 1 1 1 | 7,15 D |
1 1 0 0 12 | 1 0 1 1 | 11 | 1 - 1 1 | 11,15 |
1 1 1 0 14 | 1 1 1 0 | 14 | 1 1 1 - | 14,15 |
1 1 1 1 15 | 1 1 1 1 | 15 | |
Z tohto pocinu vyssie musime najst MNDF. A aby to nebolo tak jednoduche, tak budeme potrebovat dalsiu tabulku a to tabulku pokrytia.Tabulka pokryva vsetky jednickove stavy a obsahuje minimalny pocet prvkov.
1 4 7 8 9 10 11 12 14 15
A bd * * * *
B a'd * * * *
C c'd * * * *
D abc * *
E a'b'c * *
F ab'c' * *
V tabulke pokrytia * oznacuje, z ktorych stavov je dany implikant tvoreny.
- Najdeme stlpce, ktore obsahuju len jednu hviezdicku. V tomto pripade to je 1,4,7 a nalezia implikantom D,E,F. Tieto implikanty nazyvame nesporne priame implikanty.
- V riadku, ktory patri k nespornemu implikantu, vyskrtneme stlpce, ktore obsahuju hviezdicku
8 10 11 14
A bd * * *
B a'd * * *
C c'd * * *
- S takto upravenou tabulkou zopakujeme bod 1 a 2
- Najdeme taky stav, ze ostatne stavy su jeho podmnozinou. V tomto pripade 10, pretoze pokryva stavy, ktore pokryvaju stavy 8, 11, 14. 10 teda mozme vyskrtnut. Budeme to volat dominancia stlpcov.
8 11 14
A bd * *
B a'd * *
C c'd * * - Dominancia riadkov. Hladame teda riadok taky, ze niektory z dalsich riadkov je jeho podmnozinou. Taky stlpec v tabulke nie je.
8 11 14
A bd * *
B a'd * *
C c'd * * - A konecne vyberieme termy. Nesmieme zabudnut pouzit nesporne priame implikanty z bodu 1!
f(d,c,b,a) = abc + a'b'c + ab'c' + bd + c'd alebo
f(d,c,b,a) = abc + a'b'c + ab'c' + bd + a'd
moznost a'd + c'd sme nepouzili, aby sme co najviac uspokojili kriterium minimality.
Uff, :). Good Luck! :)
Pouzita literatura
[1] Logicke obvody, Kubatova, FEL CVUT Praha - velmi pekne napisane skripta, doporucujem do nich mrknut, ak nieco nie je jasne.
