Tableaux de Karnaugh

📦 Le cours : lire une grille de Karnaugh

Une table de vérité à n variables a 2ⁿ lignes, difficiles à simplifier « à l'œil ». Le tableau de Karnaugh range ces mêmes lignes dans une grille où deux cases côte à côte ne changent que d'une variable (ordre de Gray) : un groupe de cases à 1 correspond alors à un terme simplifié.

Exemple à 2 variables

Table de vérité de a XOR b (voir fiche Formes normales), placée en grille :

        b=0   b=1
       ┌─────┬─────┐
  a=0  │  0  │  1  │
       ├─────┼─────┤
  a=1  │  1  │  0  │
       └─────┴─────┘

Les deux 1 ne sont pas adjacents (diagonale) : aucun groupe possible, XOR ne se simplifie pas — c'est normal, c'est justement l'exemple classique qui reste sous forme DNF.

Exemple à 3 variables : retrouver f = b

Table de vérité où f vaut 1 dès que b vaut 1 (quels que soient a et c) :

           bc=00  bc=01  bc=11  bc=10
       ┌───────┬───────┬───────┬───────┐
  a=0  │   0   │   0   │   1   │   1   │
       ├───────┼───────┼───────┼───────┤
  a=1  │   0   │   0   │   1   │   1   │
       └───────┴───────┴───────┴───────┘
                          └───┬───┘
                       groupe de 4 cases

Les colonnes sont ordonnées en code Gray (00, 01, 11, 10 — pas l'ordre binaire naturel 00, 01, 10, 11) pour que les colonnes voisines ne diffèrent que d'un bit. Le groupe de 4 cases à 1 (colonnes bc=11 et bc=10, les deux lignes) reste toujours dans une zone où b = 1 ; a et c varient à l'intérieur du groupe, donc ils disparaissent de l'expression finale.

Résultat : f(a, b, c) = b, directement lu sur la grille — bien plus rapide qu'en manipulant l'algèbre de Boole terme à terme.

Règles des groupes

• Toujours une puissance de 2 de cases (1, 2, 4, 8…), en rectangle.
• Un groupe plus grand = un terme plus simple (moins de littéraux).
• La grille « boucle » : la dernière colonne est adjacente à la première (même principe que le code Gray qui revient à son point de départ).
• Une même case à 1 peut appartenir à plusieurs groupes si cela aide à simplifier.

💻 Vérifier une simplification en Python

def f_originale(a, b, c):
    return (not a and b and not c) or (not a and b and c) \
        or (a and b and not c) or (a and b and c)

def f_simplifiee(a, b, c):
    return b

for a in (False, True):
    for b in (False, True):
        for c in (False, True):
            assert f_originale(a, b, c) == f_simplifiee(a, b, c)
print("Simplification f(a,b,c) = b vérifiée sur les 8 combinaisons")

📋 Aide-mémoire

Lignes/colonnes en code Gray (00, 01, 11, 10) : deux cases voisines diffèrent d'un seul bit.

Groupes en puissance de 2 ; la variable qui varie dans le groupe disparaît de l'expression.