AnalyseOutil · Glossaire
table de Karnaugh
Une table de Karnaugh est un outil graphique permettant de simplifier une fonction logique à partir de sa table de vérité. Elle organise les combinaisons de valeurs des variables d'entrée de manière à faire apparaître visuellement les regroupements de cases adjacentes, facilitant ainsi la minimisation des expressions booléennes sans recourir à des calculs algébriques complexes. Ces tables ont été introduites en 1953 par Maurice Karnaugh, ingénieur en télécommunications américain né à New York en 1924.
Sommaire
Ce que vous allez apprendre
- Reconnaître l'ordre en code de Gray et l'adjacence cyclique d'une carte.
- Former des groupes valides dont la taille est une puissance de 2.
- Traduire chaque groupe en terme booléen et contrôler l'expression obtenue.
- Refaire l'exemple à trois variables qui conduit à F = C + AB.
En clair
Imaginez trois entrées logiques, comme trois interrupteurs, qui valent chacune 0 ou 1. Elles donnent huit combinaisons : la table de vérité les énumère, tandis que la table de Karnaugh range les mêmes résultats dans une grille particulière. Deux cases voisines ne diffèrent que par une seule entrée.
On entoure alors les 1 par groupes rectangulaires de 1, 2, 4 ou 8 cases. Dans chaque groupe, les entrées qui changent disparaissent de l'expression : seules restent celles qui gardent la même valeur.
Définition
Une table de Karnaugh représente une fonction booléenne de plusieurs variables. Chaque case correspond à une combinaison de valeurs 0 ou 1 et reçoit la sortie de la fonction pour cette combinaison. Les lignes et colonnes sont ordonnées en code de Gray : deux cases partageant un côté diffèrent par une seule variable. Les bords opposés sont eux aussi adjacents ; la grille doit donc se lire comme si elle s'enroulait horizontalement et verticalement.
Pour obtenir une somme de produits, on couvre les cases contenant 1 par des rectangles de taille égale à une puissance de 2. Un groupe peut chevaucher un autre. Il fournit un terme où ne figurent que les variables constantes dans tout le rectangle ; réunir ces termes par l'opération OU donne une expression équivalente. Une grande table peut admettre plusieurs couvertures minimales, donc plusieurs expressions aussi courtes.
La méthode part ainsi de la table de vérité et applique visuellement les règles de l'algèbre de Boole. Maurice Karnaugh a introduit ces tables en 1953. Cet ingénieur en télécommunications américain était né à New York en 1924.
Où on le rencontre
On rencontre la table de Karnaugh à côté d'une table de vérité ou lors de la conception d'un circuit numérique. Elle se reconnaît à sa grille dont le nombre de cases est une puissance de 2 — par exemple 2, 4, 8 ou 16 —, aux valeurs 0 et 1 inscrites dans les cases et aux étiquettes binaires des lignes et colonnes.
L'ordre des étiquettes n'est pas l'ordre binaire usuel : la suite 00, 01, 11, 10 rend voisines les combinaisons qui ne changent qu'une variable. Des contours rectangulaires autour de certains 1 signalent les termes conservés dans l'expression simplifiée.
Le mode d'emploi
La grandeur lue est la valeur 0 ou 1 de la fonction pour chaque combinaison d'entrées. 1. Associez chaque case à ses étiquettes de ligne et de colonne. 2. Repérez des rectangles de 1, 2, 4, 8… cases contenant uniquement des 1. 3. Préférez les plus grands groupes nécessaires pour couvrir tous les 1. 4. Dans chaque groupe, conservez seulement les variables dont la valeur ne change pas.
La convention décisive est l'adjacence cyclique : la première et la dernière colonne sont voisines, tout comme la première et la dernière ligne. L'œil voit pourtant des bords séparés. Le bon réflexe consiste à vérifier les étiquettes binaires plutôt que la seule distance dessinée, puis à s'assurer que chaque rectangle contient un nombre de cases égal à une puissance de 2.
Un exemple, pas à pas
Considérons trois entrées A, B et C. La sortie F vaut 1 pour les combinaisons numérotées 1, 3, 5, 6 et 7, et 0 pour les combinaisons 0, 2 et 4. La numérotation lit ABC comme un nombre binaire.
Ces données s'écrivent : .
La carte place A sur les lignes et BC sur les colonnes dans l'ordre 00, 01, 11, 10. Les deux contours montrent les groupes à traduire en termes booléens.
1. Le groupe de quatre cases des colonnes 01 et 11 garde C = 1, tandis que A et B changent : il donne C.
2. Le groupe de deux cases de la ligne A = 1, colonnes 11 et 10, garde A = 1 et B = 1, tandis que C change : il donne AB.
3. Les deux groupes se recouvrent sur la combinaison 111 ; ce chevauchement est autorisé.
2. Le groupe de deux cases de la ligne A = 1, colonnes 11 et 10, garde A = 1 et B = 1, tandis que C change : il donne AB.
3. Les deux groupes se recouvrent sur la combinaison 111 ; ce chevauchement est autorisé.
L'expression simplifiée est donc : , où + signifie OU et la juxtaposition signifie ET.
Le contrôle consiste à reprendre les huit combinaisons. C rend la sortie égale à 1 pour 001, 011, 101 et 111 ; AB ajoute 110. On retrouve les numéros 1, 3, 5, 6 et 7, sans créer de 1 supplémentaire.
En pratique
Pour simplifier une fonction donnée par une table de vérité, la carte offre un contrôle visuel : on reporte les sorties, on forme les plus grands groupes possibles, puis on vérifie l'expression obtenue sur toutes les lignes. Une manipulation algébrique directe reste préférable si l'expression est déjà très courte.
Lors de la conception d'un circuit numérique, une expression comportant moins de termes ou moins de variables peut conduire à une réalisation plus simple. Le critère n'est toutefois pas le dessin le plus élégant : il faut conserver exactement la même sortie pour chaque combinaison d'entrées.
Pour vérifier le résultat, la table de vérité reste l'alternative de référence. Si la carte et l'expression simplifiée divergent sur une seule combinaison, le report d'une case, l'adjacence ou la traduction d'un groupe doit être repris.
À ne pas confondre
Une table de vérité énumère les sorties de la fonction ; une table de Karnaugh réordonne ces mêmes sorties pour faire apparaître les adjacences. Si aucun regroupement n'est tracé et que les combinaisons suivent simplement l'ordre binaire, il s'agit d'une table de vérité.
Une table de Karnaugh n'est pas l'expression booléenne simplifiée. La grille est le support de recherche ; l'expression est le résultat. Dans l'exemple, la carte contient huit cases, tandis que F = C + AB est la formule obtenue.
Limites et pièges
Un groupe de trois, six ou dix cases est invalide : sa taille doit être 1, 2, 4, 8… Si un contour contient trois 1, il faut le remplacer par des groupes de puissance de 2, qui peuvent se chevaucher.
Deux cases situées en diagonale ne sont pas adjacentes. Deux cases sur des bords opposés peuvent l'être si leurs étiquettes ne diffèrent que d'une variable. Il faut donc comparer les codes, pas la proximité apparente sur la feuille.
Couvrir tous les 1 ne garantit pas à lui seul une expression minimale : un petit groupe peut être absorbé dans un plus grand, et plusieurs couvertures minimales peuvent exister. Il faut rechercher les plus grands groupes utiles et comparer les termes obtenus.
Quand le nombre de variables augmente, la grille comporte rapidement beaucoup de cases et perd son avantage visuel. La méthode reste définie, mais le risque d'oublier une adjacence ou une couverture augmente ; une procédure systématique ou un outil de minimisation devient alors plus sûr.
Pour aller plus loin
La fiche table de vérité montre le support initial dont chaque sortie est reportée dans la carte de Karnaugh.
La fiche algèbre de Boole précise les opérations ET, OU et NON qui permettent d'écrire puis de vérifier l'expression simplifiée.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres