1.2
Algebraická metoda minimalizace logických funkcí
Tento způsob minimalizace logických funkcí je založen na přímé aplikaci zákonů Booleovy algebry a na algebraických úpravách výrazů pomocí jednotlivých zákonů. Vlastní zákony Booleovy algebry byly představeny v minulém textu „Úvod do logických funkcí a logických obvodů“. Stručně je shrňme pomocí tabulky 3.
Tabulka 3. Zákony Booleovy algebry
asociativita logického součtu
a∨b∨c=a∨b∨c
asociativita logického součinu
a⋅b⋅c=a⋅b⋅c
komutativita logického součtu
a∨b=b∨a
komutativita logického součinu
a⋅b=b⋅a
distributivní zákon
a⋅b∨c=a⋅b∨a⋅c
a∨b⋅a∨c=a∨b⋅c
zákon o vyloučení třetího
a∨a¯=1
a⋅a¯=0
zákon agresivity nuly
a⋅0=0
zákon agresivity jedničky
a∨1=1
zákon neutrálnosti nuly
a∨0=a
zákon neutrálnosti jedničky
a⋅1=a
zákon o idempotenci prvků
a⋅a=a
a∨a=a
zákon absorpce negace
a∨a¯⋅b=a∨b
a¯∨a⋅b=a¯∨b
zákon absorpce
a⋅a∨b=a
a∨a⋅b=a
zákon dvojité negace
a¯¯=a
zákon o negaci logického součinu
a⋅b¯=a¯∨b¯
zákon o negaci logického součtu
a∨b¯=a¯⋅b¯
Zákon o negaci logického součinu a zákon o negaci logického součtu jsou často označovány jako tzv. De Morganovy zákony (De Morganova pravidla).
Uveďme si tento způsob a postup minimalizace na následujícím příkladu.
Příklad
Příklad:
Nalezněte minimální disjunktní formu fD funkce (MNDF) zadané jako:
f=a¯⋅b∨d∨c⋅b∨c⋅d⋅b⋅d∨a¯⋅b⋅c¯ .
Tuto minimální formu fD realizujte pomocí hradel NAND.
Zobrazit řešení
Řešení
Řešení:
  1. Nejprve odstraníme závorky pomocí distributivního zákona:
    f=a¯⋅b∨d∨c⋅b∨c⋅d⋅b⋅d∨a¯⋅b⋅c¯=a¯⋅b∨a¯⋅d∨a¯⋅b⋅c∨b⋅c⋅d∨a¯⋅b⋅c⋅c¯⋅d
  1. Na poslední součinový term můžeme aplikovat zákon o vyloučení třetího:
    a¯⋅b⋅c⋅c¯⋅d=0 .
  1. Na první a třetí součinový term můžeme použít distributivní zákon a upravit:
    f=a¯⋅b⋅1∨c∨a¯⋅d∨b⋅c⋅d .
  1. Výraz v závorce můžeme odstranit na základě zákona o agresivitě jedničky a získáme tak následující výsledek:
    fD=a¯⋅b∨a¯⋅d∨b⋅c⋅d .
Dále je naším úkolem funkci fD realizovat pomocí hradel NAND.
Jak vyplývá z pravdivostní tabulky 1, pro realizaci funkce pomocí hradel NAND je potřeba výraz upravit do tvaru součinů, respektive negovaných součinů. Ve vyjádření funkce fD ponechme tedy součinové termy, pouze logické součty mezi nimi převedeme rovněž na součiny. Použijeme proto zákon dvojité negace a posléze zákon o negaci logického součtu (De Morganův zákon). Úpravy můžeme opět provádět v jednotlivých krocích:
  1. Nejprve aplikujeme dvojí negaci:
    fD=a¯⋅b∨a¯⋅d∨b⋅c⋅d¯¯ .
  1. Dále provedeme úpravu, kdy jednu negaci ponecháme, druhou pak znegujeme logické součty na součiny dle zákona a o negaci logického součtu:
    fD=a¯⋅b¯⋅a¯⋅d¯⋅b⋅c⋅d¯¯ .
  1. Získáme tak výraz, který obsahuje pouze negované logické součiny a který s výhodou můžeme realizovat pomocí hradel NAND, jak ukazuje obrázek 3. Pro realizaci negace proměnné a využijeme hradla NAND dle postupu uvedeném v kapitole 1.1.
+
3. Realizace MNDF funkce fD pomocí hradel NAND
Obr. 3. Realizace MNDF funkce fD pomocí hradel NAND
Nevýhody
Z uvedeného příkladu je evidentní, že nevýhodou algebraického způsobu minimalizace a úprav výrazů za pomocí zákonů Booleovy algebry je značná pracnost a případná nepřehlednost, pokud termy obsahují víc proměnných, nebo je jejich počet vyšší. Při úpravách termů rovněž záleží na pořadí použití jednotlivých zákonů, respektive na pořadí jednotlivých úprav, např. v případě distributivního zákona může v určitých situacích záležet, na které termy jej aplikujeme a v jakém pořadí. Často totiž můžeme nevhodným použitím zákonů či jejich použitím v neoptimálním pořadí obdržet formu, která není minimální!