bpc-los_01 - Hradla, Boolova algebra, minimalizace funkcí
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
•
Metody minimalizace:
–
Algebraické úpravy.
–
Pomocí mapy.
–
Speciální metody. Např. Quineova-McCluskeyova
metoda.
•
Lze je algoritmizovat a použít počítač.
48
Princip algebraické minimalizace funkce
zapsané v součtovém tvaru
•
Snažíme se spojovat mintermy tak, aby se vyloučily
proměnné:
•
Vyloučením proměnných vznikají tzv.
implikanty.
•
Implikant považujeme za větší, když pokrývá větší počet
bodů funkce, tj. když je tvořen menším počtem
proměnných.
•
Výsledkem je minimální disjunktní normální forma
(MDNF).
•
Někdy nastane situace, že jedna a tatáž funkce může
mít i více různých MDNF.
a . b + a . b = a . (b + b) = a
49
Princip algebraické minimalizace funkce
zapsané v součinovém tvaru
•
Snažíme se spojovat maxtermy tak, aby se
vyloučily proměnné:
•
Výsledkem je minimální konjunktní normální forma
(MKNF).
•
Někdy nastane situace, že jedna a tatáž funkce
může mít i více různých MKNF.
(a + b) . (a + b) = a
50
Minimální úplné soubory log. funkcí
•
Pomocí logického součinu, součtu a negace lze
realizovat libovolnou logickou funkci => tvoří úplný
soubor logických funkcí.
•
Existují však i jiné úplné soubory logických funkcí.
•
Pro technickou praxi je výhodné, aby počet funkcí,
které tvoří úplný soubor logických funkcí byl
minimální.
•
Existují dva minimální úplné soubory funkcí:
–
Funkce NAND.
–
Funkce NOR.
51
Úprava na členy NAND
•
Při úpravách na NAND vyjdeme ze
součtové formy a použijeme DeMorganův
zákon:
•
Např.:
a + b = a . b
x1 . x0 + x1 . x0 = x1 . x0 + x1 . x0 = x1 . x0 . x1 . x0
52
Úprava na členy NOR
•
Při úpravách na NOR vyjdeme ze
součinové formy a použijeme DeMorganův
zákon:
•
Např.:
a . b = a + b
(x1 + x0) . (x1 + x0) = (x1 + x0) . (x1 + x0) = (x1 + x0) + (x1 + x0)
53
Karnaughovy mapy
•
Uspořádány do čtverce nebo obdélníka.
•
Každému poli jednoznačně odpovídá jedna kombinace
vstupních proměnných.
•
Dovnitř pole zapisujeme hodnotu výstupní proměnné
odpovídající příslušné kombinaci vstupních proměnných.
•
Sousední pole:
–
Pole, která se dotýkají.
–
Pole na okrajích mapy: konce řádků a sloupců, rohy mapy.
–
U mapy pro 5 a 6 proměnných pole symetrická podle os (vodorovné,
svislé).
• Sousední pole odpovídají mintermům/maxtermů lišícím se jen v