h_smlf_070.php

Vytvárame tabuľku pokrytia. Ako bolo spomenuté na predchádzajúcej strane, riadky tabuľky sú tvorené prostými a skupinovými jedinečnými implikantami systému zadaných funkcií, stĺpce tabuľky sú jednotlivé jednotkové body (nedefinované sa neuvádzajú) každej z funkcií.
<br>
Treba vybrať taký súbor prostých implikantov, ktorý spĺňa podmienku úplnosti pokrytia a vytvorť minimálnu DNF. Podmienka úplnosti pokrytia sa v tabuľke pokrytia prejavuje tak, že v každom stĺpci tabuľky má vybratý súbor prostých implikantov aspoň jednu jednotku. Systematický postup hľadania spočíva v hľadaní stĺpcov, ktoré obsahujú len jednu jednotku, v dominancii riadkov a dominancii stĺpcov.
<ul>
<li>Stĺpec s práve jednou jednotkou v každej irredundantnej DNF, a teda aj v MDNF funkcie f, sa musí nevyhnutne nachádzať taký prostý implikant, ktorý ako jediný pokrýva niektorý jednotkový bod funkcie f. Takýto implikant budem ďalej nazývať irredundantný implikant. V tabuľke pokrytia sa takýto implikant nájde tak, že sa hľadá stĺpec, ktorý obsahuje práve jednu jednotku. Implikant nachádzajúci sa v tom istom riadku, ako táto jednotka, je irredundantným implikantom. Keď sme našli irredundantný implikant, poznačíme si ho napr. hviezdičkou. Následne ho vyškrtneme z tabuľky pokrytia a tiež všetky stĺpce, v ktorých má tento implikant jednotku, lebo už nie je potrebné hľadať ďalšie implikanty, ktoré by pokrývali tieto body funkcie, keďže ich už pokryl tento irredundantný implikant. Pokračujeme v hľadaní ďalšieho irredundantného implikantu hľadaním iného stĺpca, ktorý má práve jednu jednotku. Ak sa nám už nepodarilo taký stĺpec nájsť, treba prejsť k nasledujúcim pravidlám.
<li>Dominancia riadkov - Hovoríme, že riadok i dominuje nad riadkom j tabuľky pokrytia vtedy, ak riadok j má v tabuľke pokrytia jednotky práve v tých stĺpcoch ako riadok i, avšak počet jednotiek v riadku i je väčší ako počet jednotiek v riadku j. Výber implikantu ai, ktorý zodpovedá dominantnému riadku i, môže byť vzhľadom na hľadanú MDNF významný, keďže pokrýva viac jednotkových bodov funkcie ako implikant aj, nad ktorým dominuje, a preto dominantný riadok zostáva v tabuľke pokrytia, zatiaľ čo riadok j z tabuľky pokrytia možno vyškrtnúť a ďalej nebrať do úvahy. Tým, že sa tento riadok vyškrtne, môže sa objaviť stĺpec, ktorý obsahuje práve jednu jednotku, a tak sa opäť vrátime k pravidlu 1. a hľadáme ďalší irredundantný implikant.
<li>Napokon môže nastať situácia, kedy ani jedno z vyššie uvedených pravidiel nie je možné použiť. Vtedy si obyčajne pomáhame voľbou alternatív. Vyberieme si napr. implikant a pred implikantom b, aj keď obidva pokrývajú spoločný jednotkový bod. Takto sa obyčajne dostaneme k jednému riešeniu, a teda aj jednej z MDNF. Treba však tiež preskúmať aj druhú cestu, teda keby sme si zvolili implikant b pred implikantom a.
</ul>
Napokon sa nájdené implikanty, ktoré boli po nájdení jednou z vyššie uvedených metód, zapísané do finálneho zoznamu irredundantných implikantov, rozdelia funkciám, ktorým prislúchajú. Tak dostaneme výsledok skupinovej minimalizácie logických funkcií, ktorý je zobrazený v spodnej èasti stránky.