1. Úvod

  Quine-McCluskeyho (QM) algoritmus sa využíva pri určovaní skrátenej disjunktnej normálnej formy (SDNF) ako i pri určovaní irredundatnej disjunktnej normálnej formy (IDNF), ktorým sa zaoberá tento program. INDF je súčet prostých implikantov, ktoré tvoria úplný súbor implikantov, pričom žiadna vlastná časť tochto súboru už nepredstavuje úplný súbor. Môže existovať viac alternatív tejto formy, z ktorých najjednoduchšia sa nazýva minimálnou disjunktnou formou (MDNF).

  QM algoritmus pre určovanie IDNF používa tzv. mriežku prostých implikantov. Vstupmi pre jej vytvorenie sú : súbor prostých implikantov z SDNF, počet funkcií, ktorých INDF hľadáme a a ich jednotkové body. Neurčité body pri určovaní IDNF nesmieme použiť ! Pomocou vstupov vytvoríme tabuľku, ako je to uvedené na nasledujúcom obrázku.

Obr. 1. Mriežka prostých implikantov pre jednu funkciu

Do jednotlivých riadkov zapíšeme krížiky, ktorými vyznačíme, ktoré jednotkové body implikant v danom riadku pokrýva.

Potom môžeme použiť samotný QM algoritmus, ktorý má tri kroky. Jednotlivé kroky algoritmu aplikujeme dovtedy, kým z mriežky nie sú vyškrtnuté všetky stĺpce. Výsledkom je IDNF tvorená implikantmi, ktoré sme v priebehu algoritmu označili jednou alebo viacerými hviezdičkami.