La méthode de Quine-McCluskey systématise la sélection des impliquants en se basant sur des relations qui s’expriment en fonction d’un tableau de couverture.
Un tableau de couverture comporte une ligne pour chaque i.p. et une colonne pour chaque minterm de la fonction à minimiser \(z\). Un ✓ est inscrit à l’intersection de la ligne \(i\) et de la colonne \(j\) si l’i.p. \(P_i\) de la ligne \(i\) couvre le minterm \(m_j\) de la colonne \(j\).
Le problème de minimisation devient alors: trouver une couverture pour la fonction \(z\) qui
contient le nombre minimum de lignes
est telle qu’aucune autre couverture à nombre de lignes minimum comprend moins d’entrées 1 et 0 dans ses codes d’impliquants de ligne.
Dans le tableau de couverture, on identifie facilement les i.p.e. par les colonnes qui ne contiennent qu’un ✓. L’i.p. qui couvre une colonne qui ne contient qu’un ✓ est un i.p.e.
Puisque les i.p.e. doivent faire partie de la solution finale, toutes les colonnes couvertes par des i.p.e. seront couvertes dans n’importe quelle solution. On peut donc éliminer ces colonnes de la suite de la recherche de la solution, de même que les lignes correspondant aux i.p.e. On obtient ainsi un tableau de couverture réduit.
Il ne faut cependant pas oublier de mettre les i.p.e. dans la solution finale.
Le tableau de couverture réduit permet de se concentrer sur la sélection des i.p. dont la sélection n’est pas évidente a priori. Pour illustrer la discussion, considérons le tableau de couverture réduit suivant. \(m_c\) est sans doute couvert par un i.p.e. qui n’est pas montré ici.
| $$m_a$$ | $$m_b$$ | $$m_c$$ | $$m_d$$ | $$m_e$$ | $$m_f$$ | $$m_g$$ | $$m_h$$ | |
|---|---|---|---|---|---|---|---|---|
| $$P_A$$ | ✓ | ✓ | ✓ | ✓ | ||||
| $$P_B$$ | ✓ | ✓ | ✓ | ✓ | ||||
| $$P_C$$ | ✓ | ✓ | ✓ | ✓ | ||||
| $$P_D$$ | ✓ | ✓ | ||||||
| $$P_E$$ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
Une ligne \(P_i\) domine une ligne \(P_j\) (ce qui est noté \(P_i \supseteq P_j\)) si la ligne \(P_i\) contient un x dans toutes les colonnes où la ligne \(P_j\) contient un x. Ici, on a \(P_B \supseteq P_D\) mais \(P_B\) ne domine pas \(P_A\). On peut voir aussi que \(P_E\) domine plusieurs lignes.
En général, une \(P_i\) dominante contient plus de x que \(P_j\). Si elles ont le même nombre de x (dans les mêmes colonnes), on a \(P_i = P_j\). Il n’y a pas de cas d’égalité ici.
Une ligne dominée par une autre peut être éliminée du tableau de couverture à condition que son nombre de littéraux soit supérieur ou égal à celui de la ligne dominante.
Une colonne \(m_i\) domine une colonne \(m_j\) (ce qui est noté \(m_i \supseteq m_j\)) si la colonne \(m_i\) contient un x dans toutes les lignes où la colonne \(m_j\) contient un x. Ici, la colonne \(m_h \supseteq m_g\) mais \(m_b\) ne domine pas \(m_a\).
Une colonne dominant une autre colonne peut être éliminée du tableau de couverture, car le fait que la solution finale couvre la colonne dominée assure que la colonne dominante sera couverte aussi. Donc ici, la colonne \(m_h\) peut être éliminée.
En cas d’égalité, comme on a ici pour \(m_e = m_g\), on peut librement choisir quelle colonne éliminer.