Kapitola2
Minimalizace pomocí algoritmu Quine-McCluskey
Minimalizace logických funkcí pomocí algoritmu Quine-McCluskey patří do kategorie algebraických metod minimalizace [2]. Algoritmus se opírá o aplikaci zákonů Booleovy algebry, zejména distributivního zákona a zákona o vyloučení třetího [5]. Algoritmus porovnává všechny možné dvojice mintermů a vyhledává v nich dvojice lišící se navzájem hodnotou jen jedné proměnné. Z takové dvojice lze pak tuto proměnnou vyloučit, a snížit tak počet proměnných obsažených v daných implikantech.
Výhody
Jak již z označení „algoritmus“ vyplývá, postup minimalizace uvedenou metodou lze zapsat pomocí jednoznačných kroků a aplikací Booleových zákonů, lze ji tedy snadno převést na algebraický algoritmus. Velkou výhodou této metody je tudíž fakt, že algoritmus lze zapsat (realizovat) pomocí programovacích jazyků, a vytvořit tak počítačově prováděnou minimalizaci logických funkcí. Využití výpočetní techniky je samozřejmě žádoucí s ohledem na mnohonásobně vyšší výkon v porovnání s ručními výpočty. Grafické metody minimalizace, Karnaughovými mapami a tělesy, lze v zásadě používat pouze při ručním zpracování a minimalizacích funkcí. Díky počítačovému způsobu realizace algoritmu není problém provést minimalizaci funkcí s mnohonásobně vyšším počtem nezávisle proměnných v porovnání s předchozími popsanými metodami.
Jinou výhodou algoritmu Quine-McCluskey je fakt, že pomocí něho lze vždy nalézt všechna minimální řešení, pokud jich je pro zadanou funkci více. Při minimalizaci pomocí Karnaughových map či těles není zaručeno, že budou v mapě či tělese odhalena všechna minimální řešení, při použití postupu dle algoritmu Quine-McCluskey však ano.
Zajímavost
K uvedené výhodě počítačové realizace algoritmu Quine-McCluskey a z toho vyplývajícím výpočetním možnostem algoritmu lze pro zajímavost uvést, že s rostoucím počtem nezávisle proměnných n zadané logické funkce f roste výpočetní náročnost algoritmu exponenciálně. Obecně lze určit, že pro n nezávislých proměnných lze maximálně nalézt až 3n · ln(n) prostých implikantů, například pro funkci obsahující 32 nezávisle proměnných můžeme nalézt maximálně až 534 · 1012 prostých implikantů. Záleží samozřejmě na výpočetní kapacitě daného počítače a složitosti zadané funkce, jak dlouho bude výpočet v takovém případě trvat.
Pro úpravy a minimalizace funkcí s více než 32 nezávisle proměnnými se proto používají zcela odlišné metody, založené například na heuristickém zpracování. Nejznámější z nich je tzv. Espresso.
Postup minimalizace algoritmem Quine-McCluskey lze zapsat pomocí následujících kroků:
  1. Nalezení množiny všech implikantů zadané funkce. V případě hledání MNDF (součtové formy) vyjdeme z úplné normální disjunktní formy funkce (ÚNDF), každému mintermu (jednotkovému bodu) funkce odpovídá jeden implikant a neurčité stavy považujeme též za jednotkové body, ačkoliv je od jednotkových bodů odlišíme. Pro určení MNKF (součinové formy) obdobně vycházíme z úplné normální konjunktní formy funkce (ÚNKF), ve které každému maxtermu (nulovému bodu) funkce odpovídá jeden implikant, a neurčité stavy opět považujeme za nulové body (avšak rozlišíme je značením).
    Podle toho, v jakém tvaru či jakým způsobem je výchozí funkce zadaná (algebraicky, seznamem indexů, tabulkou, mapou, atd.), sestavíme výchozí množinu implikantů dané funkce.
  1. Seznam implikantů procházíme systematicky tak, že hledáme všechny dvojice implikantů, v nichž se obsažené implikanty navzájem liší v hodnotě právě jedné nezávisle proměnné – v jednom implikantu je obsažena přímo proměnná, ve druhém její negace. Z této dvojice tuto proměnnou vyloučíme, zbylé opíšeme, a snížíme tak počet proměnných o jednu v nově vytvořeném implikantu (aplikace zákona o vyloučení třetího). Tímto způsobem postupujeme i s nově vytvořenými implikanty a dále i z nich vytvořenými atd., dokud lze dle tohoto klíče nalézt jakoukoliv dvojici. Pokud k určitému implikantu nelze nalézt žádnou dvojici, jedná se o prostý implikant, který vhodně vyznačíme (např. podtržením). Pokud tímto postupem vzniknou dva zcela shodné implikanty, jeden libovolný můžeme zcela vyškrtnout. Na konci tohoto kroku tedy zbydou jen prosté implikanty.
  1. Sestavíme tzv. tabulku pokrytí. Do řádků tabulky postupně vyplníme všechny nalezené prosté implikanty, do sloupečků pak zadané mintermy body a neurčité stavy, či maxtermy body a neurčité stavy. Vyplníme tabulku vhodně tak, abychom vyznačili (čárkou, jedničkou…), který prostý implikant pokrývá který bod funkce. Poslední řádek je tzv. výška pokrytí – ta udává, kolikrát je daný bod funkce pokryt, resp. kolik existuje různých prostých implikantů pokrývajících tento bod funkce.
  1. Po vyplnění tabulky provádíme výběr prostých implikantů do výsledné formy MNDF či MNKF funkce opět podle několika pravidel (kroků), viz dále. Při tomto výběru může dojít k nalezení více možných adekvátně minimálních řešení zadané funkce.
    Výslednou MNDF obdržíme jako logický součet vybraných prostých implikantů (v součinovém tvaru), MNKF pak jako negaci logického součtu vybraných prostých implikantů.
    Pro výběr prostých implikantů funkce z tabulky pokrytí se řídíme postupně těmito pravidly (kroky):
    1. Pokud daný prostý implikant pokrývá bod, jehož výška pokrytí je rovna 1, je tento implikant nutně obsažen vždy v každém daném minimálním řešení funkce (neexistuje jiný prostý implikant, který by daný bod pokrýval). Výjimku tvoří neurčité stavy funkce, ty pokryté být vůbec nemusejí.
    1. V případě, že daný prostý implikant pokrývá bod funkce, který je doposud nepokrytý, je daný implikant obsažen v alespoň jednom řešení dané minimální formy funkce (zde mohou vznikat další řešení).
    1. Každý jednotkový bod v případě MNDF funkce a každý nulový bod v případě MNKF funkce musí být na konci procesu výběru implikantů z tabulky pokrytí pokryt alespoň jedním implikantem. Neurčité stavy do tabulky obvykle nezahrnujeme, protože je lze ponechat nepokryté.
Uvedený postup a jednotlivé kroky minimalizace pomocí algoritmu Quine-McCluskey si představíme na příkladu.
Příklad
Příklad:
Minimalizujte zadanou funkci f čtyř nezávisle proměnných a nalezněte její formu MNDF i MNKF pomocí algoritmu Quine-McCluskey. Obě formy realizujte (MNDF pomocí NAND, MNKF pomocí NOR).
f = 2, 3, (8), 11, 12, 13, (14), 15.
Zobrazit řešení
Řešení
Řešení:
1. Určení MNDF funkce a její realizace pomocí hradel NAND
  1. Nejprve převedeme zadaný seznam stavových indexů (jednotkových bodů a neurčitých stavů) funkce na jejich vyjádření pomocí součinových termů (implikantů) pomocí úplné pravdivostní tabulky funkce.
N
d
c
b
a
f
implikant
0
0
0
0
0
0
d¯⋅c¯⋅b¯⋅a¯
1
0
0
0
1
0
d¯⋅c¯⋅b¯⋅a
2
0
0
1
0
1
d¯⋅c¯⋅b⋅a¯
3
0
0
1
1
1
d¯⋅c¯⋅b⋅a
4
0
1
0
0
0
d¯⋅c⋅b¯⋅a¯
5
0
1
0
1
0
d¯⋅c⋅b¯⋅a
6
0
1
1
0
0
d¯⋅c⋅b⋅a¯
7
0
1
1
1
0
d¯⋅c⋅b⋅a
8
1
0
0
0
X
d⋅c¯⋅b¯⋅a¯
9
1
0
0
1
0
d⋅c¯⋅b¯⋅a
10
1
0
1
0
0
d⋅c¯⋅b⋅a¯
11
1
0
1
1
1
d⋅c¯⋅b⋅a
12
1
1
0
0
1
d⋅c⋅b¯⋅a¯
13
1
1
0
1
1
d⋅c⋅b¯⋅a
14
1
1
1
0
X
d⋅c⋅b⋅a¯
15
1
1
1
1
1
d⋅c⋅b⋅a
Nyní při hledání MNDF budeme vycházet z implikantů: d¯⋅c¯⋅b⋅a¯  – 2, d¯⋅c¯⋅b⋅a  – (3), d⋅c¯⋅b¯⋅a¯ , – (8), d⋅c¯⋅b⋅a  – 11, d⋅c⋅b¯⋅a¯  – 12, d⋅c⋅b¯⋅a  – 13, d⋅c⋅b⋅a¯  – (14), d⋅c⋅b⋅a  – 15. Za každým algebraicky vyjádřeným implikantem je uveden index, ze kterého vychází. Neurčité stavy jsou odlišeny pomocí závorek ().
Pořadí nezávisle proměnných v pravdivostní tabulce volíme obvykle tak, aby proměnná a byla umístěna na nejnižším řádovém místě. Jedná se však pouze o doporučení a volba pořadí proměnných je zcela libovolně na nás.
V předchozím textu „Úvod do logických funkcí a logických obvodů“ jsme si uvedli jednoduchou pomůcku pro rychlé vyplnění hodnot do tabulky – proměnnou na nejnižším řádovém místě střídáme mezi 0 a 1 každý řádek a každou vyšší proměnnou pak střídáme o dvojnásobný počet řádků než předchozí proměnnou.
Stavový index N představuje dekadicky vyjádřené číslo odpovídající binárnímu zápisu jednotlivých proměnných na daném řádku tabulky.
  1. Nyní zapíšeme pod sebe jednotlivé získané implikanty, s výhodou si k nim (před každý implikant) poznamenáme, ze kterého bodu zadané funkce f vznikl, jak ukazuje krok 1 v obrázku 11.
    Následně začneme v seznamu odshora dolů vyhledávat systematicky dvojice implikantů a porovnáváme každý implikant s každým, zda se navzájem liší v hodnotě právě jedné proměnné. Pokud ano, dvojicí čar je označíme jako pár a dle postupu uvedeného výše vyloučíme proměnnou, ve které se navzájem liší, a jako výsledek dané dvojice opíšeme zbylé proměnné (zákon o vyloučení třetího). Také je výhodné si k danému implikantu do závorky poznamenat, ze kterých bodů zadané funkce jsme jej vytvořili. Tímto způsobem projdeme celý původní seznam implikantů a vedle něho získáme seznam nový, jak představuje krok 2 na obrázku 11. Pokud bychom k určitému implikantu nenašli žádnou dvojici, podtržením jej označíme jako prostý implikant. V případě dvou zcela totožných implikantů můžeme jeden libovolný zcela vyškrtnout.
    Stejně tak budeme postupovat s nově vzniklým sloupečkem implikantů a opět dle stejného klíče vytvářet dvojice, podtrhávat prosté implikanty a případně vyškrtávat již se opakující, jak ukazuje obrázek 11 a krok 3. V tomto příkladu se jedná o poslední krok, po kterém již získáme všechny možné prosté implikanty funkce.
+
11. Postup hledání prostých implikantů funkce f při určování její formy MNDF.
Obr. 11. Postup hledání prostých implikantů funkce f při určování její formy MNDF.
  1. Po nalezení všech prostých implikantů sestavíme tabulku pokrytí. Do jejích řádků zapíšeme jednotlivé nalezené prosté implikanty: d¯⋅c¯⋅b , c¯⋅b⋅a , d⋅b¯⋅a¯ , d⋅b⋅a , d⋅c a do sloupečků zadané jednotkové body (neurčité stavy funkce lze vynechat): 2, 3, (8), 11, 12, 13, (14), 15. V tabulce pak čárkami vyznačíme pokrytí bodů danými prostými implikanty a výšku pokrytí sečteme pro každý bod. Pokud jsme si v průběhu hledání a vytváření dvojic ke každému implikantu poznamenali, ze kterých bodů funkce jsme jej vytvořili, snadněji nyní vyplníme tabulku pokrytí. Vyplněnou tabulku představuje obrázek 12.
+
12. Vyplněná tabulka pokrytí v příkladu zadané funkce f při hledání její formy MNDF.
Obr. 12. Vyplněná tabulka pokrytí v příkladu zadané funkce f při hledání její formy MNDF.
  1. Nyní můžeme provést postupně výběr prostých implikantů z tabulky pokrytí dle kroků (postupu) uvedených výše. Výšku pokrytí 1 mají jednotkové body 2 a 13 (neurčitých stavů si zatím nevšímáme). Tyto body pokrývají prosté implikanty: d¯⋅c¯⋅b , d⋅c . Ty musíme vždy vybrat, neboť neexistuje jiná možnost, jak dané body pokrýt jiným prostým implikantem. Z tabulky pokrytí vyškrtneme řádky s těmito implikanty a vyškrtneme také všechny sloupečky (body), které tyto implikanty pokrývají: 2, 3, 12, 13, (14), 15, jak ukazuje obrázek 13.
+
13. Krok 1 při výběru prostých implikantů z tabulky pokrytí při řešení MNDF.
Obr. 13. Krok 1 při výběru prostých implikantů z tabulky pokrytí při řešení MNDF.
  1. V tabulce nám zbyly tři prosté implikanty a jeden nepokrytý jednotkový bod 11 (bod (8) je neurčitý stav a do tabulky jej nemusíme ani uvádět). Bod 11 je jednotkový bod a musí být pokryt. Výška jeho pokrytí je 2 a pokrývají jej prosté implikanty: c¯⋅b⋅a , d⋅b⋅a . Každý z implikantů kromě bodu 11 pokrývá ještě jeden další bod, který však již máme pokrytý z předchozího kroku a je vyškrtnutý v tabulce (bod 3 a bod 15). Z tohoto důvodu jsou oba tyto implikanty pro pokrytí bodu 11 stejně výhodné a hledaná forma MNDF má tedy dvě rovnocenná minimální řešení, každé obsahující dvojici prostých implikantů z předchozího kroku a jeden ze zbývajících implikantů pokrývajících bod 11.
    fD1=d⋅c∨d¯⋅c¯⋅b∨c¯⋅b⋅a ,
    fD2=d⋅c∨d¯⋅c¯⋅b∨d⋅b⋅a .
    Zbývající bod v tabulce (8) je neurčitý stav, který nemusí být pokryt.
    Z tabulky je také patrné, že poslední prostý implikant, d⋅b¯⋅a¯ , zůstal nepoužit, neboť kromě neurčitého stavu (8) pokrývá již pokrytý bod 12. Tento implikant tedy není do MNDF potřeba. V tabulce jej proto přeškrtneme. Konečné řešení tabulky pokrytí uvádí obrázek 14, dvě rovnocenné MNDF funkce jsou uvedeny výše.
+
14. Výsledek vyškrtání a výběru prostých implikantů z tabulky při hledání MNDF funkce f.
Obr. 14. Výsledek vyškrtání a výběru prostých implikantů z tabulky při hledání MNDF funkce f.
  1. Nyní již jen zbývá realizovat obě řešení MNDF funkce f pomocí hradel NAND. Stejně jako v předchozích příkladech, nejprve pomocí zákona dvojité negace a zákona o negaci logického součtu upravíme výrazy MNDF:
    fD1=d⋅c∨d¯⋅c¯⋅b∨c¯⋅b⋅a=d⋅c¯⋅d¯⋅c¯⋅b¯⋅c¯⋅b⋅a¯¯ ,
    fD2=d⋅c∨d¯⋅c¯⋅b∨d⋅b⋅a=d⋅c¯⋅d¯⋅c¯⋅b¯⋅d⋅b⋅a¯¯ .
    A ty již můžeme realizovat pomocí součinových hradel NAND, jak ukazuje obrázek 15.
+
15. Řešení realizace MNDF funkce f.
Obr. 15. Řešení realizace MNDF funkce f.
2. Určení MNKF funkce a její realizace pomocí hradel NOR
  1. Využijeme již vyplněnou úplnou pravdivostní tabulku zadané funkce f z předchozího hledání MNDF funkce. Pouze z ní naopak vybereme implikanty, které odpovídají nulovým bodům a neurčitým stavům, abychom získali MNKF zadané funkce. Pro hledání MNKF tedy použijeme implikanty: d¯⋅c¯⋅b¯⋅a¯  – 0, d¯⋅c¯⋅b¯⋅a  – 1, d¯⋅c⋅b¯⋅a¯  – 4, d¯⋅c⋅b¯⋅a  – 5, d¯⋅c⋅b⋅a¯  – 6, d¯⋅c⋅b⋅a  – 7, d⋅c¯⋅b¯⋅a¯ , – (8), d⋅c¯⋅b¯⋅a  – 9, d⋅c¯⋅b⋅a¯  – 10, d⋅c⋅b⋅a¯  – (14).
  1. Stejným způsobem jako při předchozím hledaní MNDF sepíšeme nyní seznam maxtermů, avšak pro nalezení MNKF vyjdeme z nulových bodů a neurčitých stavů, před každý z nich poznamenáme, který bod funkce pokrývá. Dále budeme stejným způsobem systematicky procházet seznam a podle stejného klíče hledat dvojice implikantů lišících se navzájem v hodnotě jedné proměnné. Takové implikanty opět spojíme, lišící se proměnnou vyloučíme dle zákona o vyloučení třetího a zbylé opíšeme. Do závorky za takto vzniklý implikant poznamenáme, ze kterých bodů jsme jej vytvořili. Stejný postup budeme opakovat i pro seznam nově vzniklých implikantů a opět pro nový seznam tak dlouho, dokud budeme moci nějaké dvojice najít. Prosté implikanty (pro které nelze najít žádnou dvojici) podtržením označíme, stejné implikanty vyškrtneme. Postup v jednotlivých krocích hledání dvojic implikantů a jejich řešení ukazuje obrázek 16.
+
16. Hledání dvojic implikantů a určení všech prostých implikantů při řešení MNKF funkce f.
Obr. 16. Hledání dvojic implikantů a určení všech prostých implikantů při řešení MNKF funkce f.
  1. Výsledkem předchozího kroku jsou prosté implikanty: d¯⋅b¯ , c¯⋅b¯ , d¯⋅c , c⋅b⋅a¯ , d⋅c¯⋅a¯ , d⋅b⋅a¯ . Prosté impikanty zapíšeme do tabulky pokrytí a vyplníme ji, výsledná tabulka je zachycena na obrázku 17.
+
17. Tabulka pokrytí pro řešení MNKF funkce f.
Obr. 17. Tabulka pokrytí pro řešení MNKF funkce f.
  1. Z tabulky začneme opět dle stejných pravidel jako výše vybírat postupně jednotlivé prosté implikanty pro určení řešení MNKF. Výšku pokrytí 1 a zároveň podmínku, že se nejedná o neurčité stavy, splňují body 7 a 9. Bod 7 je pokryt implikantem d¯⋅c a bod 9 c¯⋅b¯ . Tyto implikanty musíme vybrat do řešení MNKF, neboť jinak nelze body 7 a 9 pokrýt. Vyškrtneme proto tyto implikanty v tabulce a zároveň i všechny sloupce s indexy, které tyto dva prosté implikanty pokrývají. Dostaneme pak tabulku na obrázku 18.
+
18. Postup výběru prostých implikantů pro určení řešení MNKF funkce f.
Obr. 18. Postup výběru prostých implikantů pro určení řešení MNKF funkce f.
  1. V tabulce nám zbyl již jen jeden nepokrytý nulový bod 10, bod (14) je neurčitý stav, který pokrývat nemusíme. Bod 10 můžeme pokrýt dvěma různými implikanty: d⋅c¯⋅a¯ , d⋅b⋅a¯ . Implikant d⋅c¯⋅a¯ pokrývá kromě bodu 10 již pokrytý neurčitý stav (8), zatímco implikant d⋅b⋅a¯ prozatím nepokrytý neurčitý stav (14). Oba prosté implikanty pro pokrytí bodu 10 tedy nabízí rovnocenně minimální řešení a MNKF funkce f má tedy dvě možná řešení. Nesmíme rovněž zapomenout výsledný logický součet vybraných součinových termů (implikantů) znegovat, neboť se jedná o MNKF. Výsledek tedy je:
    fK1=d¯⋅c∨c¯⋅b¯∨ d⋅c¯⋅a¯¯=d∨c¯⋅c∨b⋅d¯∨c∨a ,
    fK2=d¯⋅c∨c¯⋅b¯∨ d⋅b⋅a¯¯=d∨c¯⋅c∨b⋅d¯∨b¯∨a .
    Z tabulky vyplývá, že implikanty d¯⋅b¯ a  c⋅b⋅a¯ jsme nepoužili, neboť jimi pokryté body jsme výhodněji pokryli jinými prostými implikanty. Tyto implikanty tedy můžeme zcela vyškrtnout. Výslednou tabulku pokrytí po výběru všech prostých implikantů a po nalezení obou řešení MNKF zadané funkce f ilustruje obrázek 19.
+
19. Výsledná tabulka pokrytí po určení obou řešení MNKF funkce f.
Obr. 19. Výsledná tabulka pokrytí po určení obou řešení MNKF funkce f.
  1. Posledním krokem zadání je realizace MNKF, respektive obou jejích řešení, pomocí hradel typu NOR. Provedeme opět úpravy vyjádření, abychom získali MNKF ve tvaru negovaných logických součtů:
    fK1=d∨c¯⋅c∨b⋅d¯∨c∨a¯¯=d∨c¯¯∨c∨b¯∨d¯∨c∨a¯¯ ,
    fK2=d∨c¯⋅c∨b⋅d¯∨b¯∨a=d∨c¯¯∨c∨b¯∨d¯∨b¯∨a¯¯ .
    Obě řešení MNKF realizovaná pomocí hradel NOR představuje obrázek 20.
+
20. Realizace MNKF (obě řešení) funkce f pomocí hradel NOR.
Obr. 20. Realizace MNKF (obě řešení) funkce f pomocí hradel NOR.
Abychom lépe procvičili postup a celou metodu minimalizace logických funkcí pomocí algoritmu Quine-McCluskey, spočítáme ještě jeden obdobný příklad.
Příklad
Příklad:
Pomocí algoritmu Quine-McCluskey nalezněte všechna řešení forem MNDF a MNKF funkce čtyř proměnných. Realizaci pomocí hradel neprovádějte. Funkce f je zadána pomocí zkráceného seznamu indexů:
f = (0), 1, (2), 4, (5), 6, (11), (13), 15.
Zobrazit řešení
Řešení
Řešení:
Řešení příkladu a celý postup opět rozdělíme na minimalizaci vedoucí k získání MNDF a zvlášť pak hledání MNKF funkce.
1. Nalezení MNDF funkce pomocí algoritmu Quine-McCluskey
Postup je stejný jako u předchozího řešeného příkladu. Nejprve pomocí úplné pravdivostní tabulky převedeme zadané jednotkové body a neurčité stavy funkce na vyjádření implikantů pomocí proměnných. Následně budeme vyhledávat dvojice implikantů a provádět vylučování proměnných, abychom získali prosté implikanty. Ty zapíšeme do tabulky pokrytí a z ní získáme výsledné řešení MNDF.
Celý postup a výsledek zachycuje následující animace 2.
Animace 2. Postup minimalizace a výsledného řešení MNDF zadané funkce f čtyř proměnných pomocí algoritmu Quine-McCluskey.
Výsledkem jsou dvě rovnocenná řešení MNDF:
fD1=d¯⋅b¯∨d¯⋅a¯∨d⋅b⋅a ,
fD2=d¯⋅b¯∨d¯⋅a¯∨d⋅c⋅a .
2. Určení MNKF funkce pomocí algoritmu Quine-McCluskey
Opět stejný postup provedeme při hledání MNKF zadané funkce, pouze s tím rozdílem, že z pravdivostní tabulky vybereme implikanty odpovídající nulovým bodům a neurčitým stavům funkce. Na konci pak nezapomeneme provést negaci logického součtu jednotlivých součinových implikantů, abychom obdrželi MNKF.
Opět si celý postup včetně řešení můžeme prohlédnout v animaci 3.
Animace 3. Postup minimalizace a výsledného řešení MNKF zadané funkce f čtyř proměnných pomocí algoritmu Quine-McCluskey.
I pro MNKF jsme tedy určili dvě minimální řešení:
fK1=d¯∨a⋅d∨b¯∨a¯⋅d¯∨c ,
fK2=d¯∨a⋅d∨b¯∨a¯⋅d¯∨b .
Poznámka
V rámci kontroly správnosti výpočtu a dalšího procvičování se pokuste všechny příklady řešené pomocí algoritmu Quine-McCluskey vyřešit za použití Karnaughových map. Měli byste dojít ke stejným výsledkům.
Nevýhody
Při řešení posledního příkladu a zejména jeho MNKF je zřejmě, že při ručním hledání dvojic implikantů lze při jejich velkém počtu snadno nějaký přehlédnout. I proto je vhodnější realizace algoritmu pomocí programovacího jazyka na počítači.