1. Ce qu'est une table de Karnaugh
Une table de Karnaugh est une table de vérité redessinée sous forme de grille. Maurice Karnaugh l'a présentée aux Bell Labs en 1953 comme un moyen de simplifier les circuits de commutation à l'œil, et elle reste la façon la plus rapide de minimiser à la main une petite fonction booléenne : pas d'algèbre, pas de lois à retenir, seulement des rectangles.
Chaque case de la table contient une ligne de la table de vérité. Ce qui fait de la table plus qu'un réarrangement, c'est l'ordre dans lequel ces lignes sont placées : deux cases voisines ne diffèrent que d'une seule variable.
Cette seule propriété fait tout le travail. Si deux cases voisines sont toutes deux vraies, la variable qui change entre elles ne peut pas être ce qui rend l'expression vraie : elle disparaît, et un seul terme couvre les deux cases. Simplifier revient à tracer les plus grands rectangles possibles.
2. Pourquoi les colonnes semblent en désordre
Les colonnes d'une table de Karnaugh ne comptent pas 00, 01, 10, 11. Elles vont 00, 01, 11, 10 : le code Gray réfléchi, un ordre dans lequel chaque valeur ne diffère de la suivante que d'un bit. Compter en binaire placerait 01 à côté de 10, qui diffèrent de deux bits, et les cases voisines ne diraient plus rien.
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 3 | 2 |
| 1 | 4 | 5 | 7 | 6 |
Les bords aussi sont voisins. La première et la dernière colonne ne diffèrent que d'une variable, de même que la première et la dernière ligne, si bien qu'un groupe peut sortir par un bord et continuer de l'autre côté - c'est pourquoi les quatre coins d'une table à quatre variables forment un seul groupe. Une table de Karnaugh est en réalité tracée sur un tore ; la feuille plane n'est qu'une commodité.
3. Regrouper les uns
Pour lire sur la table une somme de produits minimale, couvrez chaque case contenant un 1 par des groupes rectangulaires, en suivant quatre règles :
- Un groupe est un rectangle de 1, 2, 4, 8 … cases - une puissance de deux sur chaque côté.
- Un groupe peut passer par-dessus les bords de la table, horizontalement, verticalement, ou les deux.
- Les groupes peuvent se recouvrir. Couvrir une case deux fois ne coûte rien ; en laisser une découverte change la fonction.
- Faites chaque groupe aussi grand que possible, puis utilisez le moins de groupes possible pour couvrir tous les uns.
Chaque groupe donne un terme. On le lit en cherchant quelles variables restent identiques dans tout le groupe : celles-là figurent dans le terme - telles quelles là où elles valent 1, niées là où elles valent 0 - et toutes celles qui changent disparaissent. Un groupe de deux cases perd une variable, un groupe de quatre en perd deux, un groupe de huit en perd trois. L'expression minimale est la disjonction des termes.
4. Un exemple traité
Prenons (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D). Sa table a quatre variables : A et B en lignes, C et D en colonnes.
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 1 | 1 |
| 01 | 0 | 0 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 0 | 0 |
Deux groupes couvrent tous les uns. Le premier est le bloc de quatre cases situé dans les deux lignes où A = 0 et les deux colonnes où C = 1 : B et D y changent tous deux, ils disparaissent donc et le terme est ¬A ∧ C. Le second est la ligne entière où A et B valent 1, sur les quatre colonnes : C et D y changent, il reste A ∧ B.
La forme minimale est donc (¬A ∧ C) ∨ (A ∧ B). Le troisième terme de départ, B ∧ C ∧ D, s'est évanoui : chacune des cases qu'il couvrait l'était déjà par l'un des deux groupes. Voilà à quoi ressemble l'absorption quand on peut la voir.
5. Impliquants premiers et essentiels
Un groupe qu'on ne peut plus agrandir s'appelle un impliquant premier. Énumérer les impliquants premiers est la moitié facile du problème ; choisir lesquels garder est la moitié qui tourne mal.
Si une case n'est couverte que par un seul impliquant premier, cet impliquant est essentiel : aucune forme minimale ne peut s'en passer, puisque rien d'autre ne couvre cette case. Prenez d'abord les impliquants essentiels, puis couvrez ce qui reste avec le moins possible des groupes restants.
La méthode gloutonne - prendre à chaque fois le plus grand groupe encore disponible - est tentante et ne marche pas toujours. Sur un tableau cyclique, où aucun impliquant n'est essentiel et où chaque case est couverte deux fois, le choix glouton peut finir avec un terme de plus que la meilleure réponse. La table de ce site explore au contraire toutes les possibilités restantes, ce qui, à quatre variables, ne coûte rien.
6. Regrouper les zéros à la place
Tout ce qui précède fonctionne aussi bien sur les zéros. Couvrez-les avec les mêmes rectangles, lisez chaque groupe avec ses littéraux niés - une variable qui vaut 1 sur tout le groupe apparaît niée, une qui vaut 0 apparaît telle quelle - et reliez les groupes par ∧ plutôt que par ∨.
Le résultat est un produit de sommes : une conjonction de disjonctions fausse exactement dans les cases où l'expression est fausse, donc vraie partout ailleurs. Laquelle des deux formes est la plus courte dépend de la fonction - une formule avec peu de uns a une somme de produits courte, une avec peu de zéros un produit de sommes court - il vaut donc la peine de lire les deux sur la table avant de choisir.
7. Tables plus grandes et cas indifférents
Cinq et six variables peuvent se dessiner comme deux ou quatre tables à quatre variables empilées, les cases occupant la même position sur des couches voisines comptant comme adjacentes. Cela marche, mais l'adjacence qui rendait la méthode visuelle devient quelque chose à retenir plutôt qu'à voir. Au-delà, l'algorithme de Quine-McCluskey fait le même travail sous forme de tableau : c'est la version mécanique de ce regroupement, et c'est lui qui tourne derrière les tables présentées ici.
La conception de circuits ajoute une idée de plus. Certaines combinaisons d'entrée ne se produisent jamais - un chiffre décimal codé en binaire n'est jamais 1010 - de sorte que le concepteur se moque de ce que le circuit en fait. Ces cases sont marquées d'un X et peuvent être lues avec l'une ou l'autre valeur, celle qui agrandit le plus les groupes. Les tables de cette calculatrice sont construites à partir d'une formule, qui donne une valeur à chaque affectation : aucune case n'y est indifférente.
8. Essayez vous-même
Tapez dans la calculatrice une expression de deux à quatre variables et sa table est tracée sous la table de vérité, chaque groupe entouré de sa propre couleur et la forme minimale écrite en dessous. Passez en produit de sommes pour voir les zéros regroupés à la place.