1.5. Quine-McCluskeyho algoritmus na určovanie skrátenej DNF

Q-M algoritmus vychádza z ÚDNF B-funkcie a jeho aplikáciou získame SDNF danej B-funkcie. Algoritmus pozostáva z nasledujúcich krokov :

  1. Ak funkcia f obsahuje neurčené body "x", tieto sa spolu s jednotkovými bodmi takisto zahrnú do určovania SDNF.
  2. Určenie binárnych vyjadrení elementárnych súčinov
  3. Usporiadanie elementárnych súčinov podľa počtu jednotiek v binárnom vyjadrení
  4. Aplikácia modifikovaného pravidla spojovania (MPS) len na susedné skupiny súčinov, ktorých p.j.(počet jednotiek) sa líši o jednu "1" a súčastne na susedné dvojice súčinov, ktoré sa líšia v hodnote iba jednej premennej.
  5. Aplikácia pravidla pohltenia len na spájané súčiny (bolo na ne aplikované MPS)

Skrátenú DNF predstavuje súčet tých elementárnych súčinov, ktoré neboli spájané zo žiadnym iným a v tabuľke nie označené .

Kontrolu správnosti určenia skrátenej DNF urobíme spätne v mape, v ktorej vyznačíme jednotlivé prosté implikanty a zistíme, či sú skutočne prosté a či pokrývajú všetky body. (príklad)