Chapitre 914 minDébutant
Tableau de Karnaugh : simplifier pas à pas
Par Josselyn C., prof de BTS SIO. Mis à jour le .
À la fin de ce chapitre, tu sauras
- construire un tableau de Karnaugh à deux ou trois variables ;
- le remplir à partir d'une table de vérité ou d'une expression ;
- faire les bons regroupements, y compris par les bords ;
- lire l'expression simplifiée et la vérifier.
6 exercices corrigés2 schémas
Un tableau de Karnaugh est une table de vérité rangée en grille, où deux cases voisines ne diffèrent que par la valeur d'une seule variable. Regrouper les 1 voisins par blocs de 2, 4 ou 8 cases fait apparaître directement l'expression simplifiée, sans calcul algébrique. Ce chapitre explique la construction du tableau à 2 et 3 variables (la limite du programme du BTS), les règles de regroupement et leur lecture, avec des exemples corrigés, puis le tableau à 4 variables en complément.
Le principe : des cases voisines
Toute la méthode repose sur la règle vue au chapitre 7 : xy + xy̅ = x. Deux mintermes qui ne diffèrent que par une variable se réunissent en un seul produit, sans cette variable. Par exemple, abc + abc̅ = ab.
Dans une table de vérité, ces paires de lignes sont éparpillées. Le tableau de Karnaugh (du nom de l'ingénieur américain Maurice Karnaugh, 1953) les place côte à côte : deux cases qui se touchent ne diffèrent que d'un bit. Pour cela, les en-têtes ne suivent pas l'ordre binaire 00, 01, 10, 11, mais l'ordre 00, 01, 11, 10, appelé code de Gray (ou code binaire réfléchi) : d'un en-tête au suivant, un seul bit change.
Le tableau à 2 variables
Quatre cases : a en ligne, b en colonne. Chaque case correspond à une ligne de la table de vérité.
| a \ b | 0 | 1 |
|---|---|---|
| 0 | a̅b̅ | a̅b |
| 1 | ab̅ | ab |
Exemple. F = a̅b + ab̅ + ab. On place un 1 dans les cases a̅b, ab̅ et ab :
| a \ b | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 1 |
- La ligne a = 1 (deux cases) donne le regroupement a : dans cette ligne, b prend les deux valeurs et disparaît.
- La colonne b = 1 donne le regroupement b.
- La case ab appartient aux deux groupes : c'est permis.
Donc F = a + b. Le calcul confirme : a̅b + ab̅ + ab = (a̅b + ab) + (ab̅ + ab) = b + a.
Le tableau à 3 variables
Huit cases sur deux lignes et quatre colonnes : a en ligne, le couple bc en colonne, dans l'ordre de Gray.
| a \ bc | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | a̅b̅c̅ | a̅b̅c | a̅bc | a̅bc̅ |
| 1 | ab̅c̅ | ab̅c | abc | abc̅ |
Les colonnes extrêmes 00 et 10 ne diffèrent que par b : elles sont voisines elles aussi. Imagine le tableau enroulé en cylindre, le bord droit collé au bord gauche.
Remplir le tableau
À partir d'une table de vérité : chaque ligne où la fonction vaut 1 donne un 1 dans la case correspondante. Attention à l'ordre des colonnes : la ligne a = 0, b = 1, c = 0 va dans la case (ligne 0, colonne 10), qui est la quatrième colonne.
À partir d'une somme de produits : chaque produit remplit toutes les cases où il vaut 1.
- un produit de 3 variables (ab̅c) remplit 1 case ;
- un produit de 2 variables (ab̅) remplit 2 cases voisines (ab̅c̅ et ab̅c) ;
- une variable seule (c) remplit 4 cases (les colonnes 01 et 11).
Les cases restées vides valent 0. On peut ne pas écrire les 0, mais les écrire évite les oublis.
Les règles de regroupement
Lire un regroupement
Un groupe donne un produit formé des variables qui gardent la même valeur dans toutes ses cases : une variable qui vaut 1 partout s'écrit telle quelle, une variable qui vaut 0 partout s'écrit barrée, une variable qui change disparaît.
| Taille du groupe | Variables éliminées (sur 3) | Produit obtenu |
|---|---|---|
| 1 case | 0 | 3 variables, comme abc̅ |
| 2 cases | 1 | 2 variables, comme ab |
| 4 cases | 2 | 1 variable, comme c |
| 8 cases | 3 | 1 : la fonction vaut toujours 1 |
L'expression simplifiée est la somme des produits de tous les groupes.
Méthode complète sur un exemple
Simplifions F = a̅b̅c̅ + a̅b̅c + a̅bc̅ + ab̅c̅ + abc̅.
1. Remplir le tableau. Les cinq mintermes donnent cinq 1.
| a \ bc | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
2. Chercher les plus grands groupes. Les colonnes 00 et 10 sont voisines (bords du cylindre) et contiennent quatre 1 : c'est un groupe de 4. Il reste le 1 de la case a̅b̅c (ligne 0, colonne 01). Son plus grand groupe possible est la paire qu'il forme avec sa voisine a̅b̅c̅ (ligne 0, colonne 00), déjà couverte : c'est permis.
3. Lire chaque groupe.
- Groupe des colonnes 00 et 10 : a prend les deux valeurs, b aussi ; c vaut 0 partout. Produit : c̅.
- Paire de la ligne 0, colonnes 00 et 01 : a vaut 0, b vaut 0, c change. Produit : a̅b̅.
4. Écrire le résultat : F = c̅ + a̅b̅.
5. Vérifier sur une case : pour a = 1, b = 1, c = 1 (case abc), F vaut 0 dans le tableau, et c̅ + a̅b̅ = 0 + 0 = 0. Juste.
Le piège du groupe en trop
Une fonction vaut 1 sur les cases a̅b̅c, a̅bc, abc et abc̅.
| a \ bc | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
Trois paires sont possibles : a̅c (ligne 0, colonnes 01-11), bc (colonne 11) et ab (ligne 1, colonnes 11-10). Mais la paire bc est inutile : ses deux cases sont déjà couvertes par les deux autres groupes. Le résultat minimal est F = a̅c + ab, pas a̅c + bc + ab (qui est juste, mais pas simplifié).
Cases indifférentes
Parfois certaines combinaisons ne peuvent pas se produire (par exemple un capteur qui ne peut pas signaler à la fois « porte ouverte » et « porte fermée »). La valeur de la fonction dans ces cas est indifférente : on note la case par un tiret (–) ou un X. On peut alors compter une case indifférente comme un 1 si cela agrandit un groupe, et l'ignorer sinon. Cette notion est hors programme du BTS, mais elle explique certaines corrections de sujets où l'énoncé précise qu'une situation est impossible.
Pour aller plus loin : le tableau à 4 variables
Le programme du BTS limite les tableaux de Karnaugh à trois variables. À quatre variables, le principe est le même avec une grille de 4 × 4 : ab en ligne et cd en colonne, toutes deux dans l'ordre de Gray. Les bords haut et bas sont voisins, comme les bords gauche et droit, et les quatre coins forment un groupe.
| ab \ cd | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 0 | 0 | 1 |
| 01 | 0 | 1 | 1 | 0 |
| 11 | 0 | 1 | 1 | 0 |
| 10 | 1 | 0 | 0 | 1 |
- Les quatre coins (b = 0 et d = 0 partout) donnent b̅d̅.
- Le carré central (b = 1 et d = 1 partout) donne bd.
Donc F = b̅d̅ + bd : F vaut 1 quand b et d sont égaux, quelles que soient a et c. Un groupe de 8 cases élimine trois variables, un groupe de 16 cases donne F = 1.
Exercices
Exercice 1 sur 6 Deux variables Réussi À revoir
Simplifie à l'aide d'un tableau de Karnaugh :
- F₁ = a̅b̅ + a̅b
- F₂ = a̅b̅ + ab̅ + ab
- F₃ = a̅b + ab̅
Voir la réponseMasquer la réponse de l'exercice 1
- Les deux 1 occupent la ligne a = 0 : F₁ = a̅.
- Trois 1 : la colonne b = 0 (a̅b̅ et ab̅) donne b̅, la ligne a = 1 (ab̅ et ab) donne a. F₂ = a + b̅.
- Les deux 1 sont en diagonale, pas voisins : aucun regroupement possible. F₃ = a̅b + ab̅ ne se simplifie pas : c'est le ou exclusif a ⊕ b.
Tu avais trouvé ?
Exercice 2 sur 6 Depuis une table de vérité Réussi À revoir
La fonction g de trois variables vaut 1 sur les lignes 000, 001, 101 et 111 de la table de vérité, et 0 ailleurs.
- Dresse le tableau de Karnaugh de g.
- Simplifie g.
Voir la réponseMasquer la réponse de l'exercice 2
1. Le tableau :
| a \ bc | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 |
2. Le 1 de a̅b̅c̅ ne peut se regrouper qu'avec a̅b̅c : paire a̅b̅. Le 1 de abc ne peut se regrouper qu'avec ab̅c : paire ac. Ces deux paires couvrent aussi la case ab̅c. La paire b̅c (colonne 01) serait en trop. g = a̅b̅ + ac.
Tu avais trouvé ?
Exercice 3 sur 6 Depuis une expression Réussi À revoir
Simplifie h = abc + ab̅c + a̅bc + a̅b̅c + abc̅ à l'aide d'un tableau de Karnaugh.
Voir la réponseMasquer la réponse de l'exercice 3
| a \ bc | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
- Les colonnes 01 et 11 forment un carré de quatre 1, où c vaut 1 partout : c.
- Il reste abc̅ (ligne 1, colonne 10). Son plus grand groupe est la paire avec abc : ab.
h = c + ab.
Tu avais trouvé ?
Exercice 4 sur 6 Un groupe à cheval Réussi À revoir
Simplifie k = a̅b̅c̅ + a̅bc̅ + abc̅.
Voir la réponseMasquer la réponse de l'exercice 4
| a \ bc | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
- Les cases a̅b̅c̅ (colonne 00) et a̅bc̅ (colonne 10) sont voisines par les bords : paire a̅c̅.
- Les cases a̅bc̅ et abc̅ (colonne 10) : paire bc̅.
k = a̅c̅ + bc̅ = c̅(a̅ + b). Erreur classique : oublier que les colonnes 00 et 10 se touchent, et laisser a̅b̅c̅ seul.
Tu avais trouvé ?
Exercice 5 sur 6 Un contrôle d'accès Réussi À revoir
La porte d'une salle serveur s'ouvre (O = 1) selon trois variables : b = 1 si le badge est reconnu, c = 1 si le code saisi est juste, n = 1 la nuit (n = 0 en journée). La porte s'ouvre dans les trois cas suivants, et seulement dans ces cas : (b, c, n) = (1, 1, 0), (1, 1, 1) et (1, 0, 0).
- Écris O sous forme canonique (dans l'ordre b, c, n).
- Simplifie O avec un tableau de Karnaugh (b en ligne, cn en colonne).
- Traduis le résultat par une phrase.
Voir la réponseMasquer la réponse de l'exercice 5
1. O = bcn̅ + bcn + bc̅n̅.
2. Le tableau :
| b \ cn | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
- Les cases bcn et bcn̅ (colonnes 11 et 10) : paire bc.
- Les cases bc̅n̅ (colonne 00) et bcn̅ (colonne 10), voisines par les bords : paire bn̅.
O = bc + bn̅ = b(c + n̅).
3. La porte s'ouvre si le badge est reconnu et que le code est juste ou que l'on est en journée. Autrement dit : en journée, le badge suffit ; la nuit, il faut le badge et le code.
Tu avais trouvé ?
Exercice 6 sur 6 Pour aller plus loin : quatre variables Réussi À revoir
Simplifie la fonction de quatre variables qui vaut 1 sur les cases suivantes (ab en ligne, cd en colonne) : a̅b̅c̅d̅, a̅b̅cd̅, ab̅c̅d̅, ab̅cd̅, a̅bc̅d, abc̅d.
Voir la réponseMasquer la réponse de l'exercice 6
| ab \ cd | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 0 | 0 | 1 |
| 01 | 0 | 1 | 0 | 0 |
| 11 | 0 | 1 | 0 | 0 |
| 10 | 1 | 0 | 0 | 1 |
- Les quatre coins (lignes 00 et 10, colonnes 00 et 10, toutes voisines par les bords) : b = 0 et d = 0 partout, groupe b̅d̅.
- Les cases a̅bc̅d et abc̅d (colonne 01, lignes 01 et 11, voisines) : b = 1, c = 0, d = 1, paire bc̅d.
F = b̅d̅ + bc̅d.
Tu avais trouvé ?