Tableaux de Karnaugh
Les tableaux de Karnaugh sont une forme particulière de table de vérité. En respectant certaines règles de présentation, ils permettent d'obtenir la forme la plus simple possible d'une fonction logique.
Chaque case du tableau correspond à une ligne de la table de vérité d'une fonction logique: une fonction à n variables est donc représentée par un tableau à 2n cases agencé de telle façon qu'une seule variable change de valeur quand on passe d'une case à une case adjacente.
Attention :
La dernière ligne et la première ligne sont aussi adjacentes. La dernière et la première colonne sont aussi adjacentes.
Dans l'idéal il faudrait donc représenter le tableau de Karnaugh sur un tore !
Remarque :
Si un tableau contient peu de \(0\), on peut regrouper les \(0\) plutôt que les \(1\) pour obtenir le complémentaire de la fonction logique.
Si certaines combinaisons d'entrées sont absurdes et ne peuvent pas absolument se réaliser ("pièce trop grande" ET "pièce trop petite"), on écrit une croix dans la case correspondante. Cette croix pourra être considérée comme valant \(1\) ou \(0\) suivant ce qui nous arrange dans les regroupements.
Méthode : Regroupement dans les tableaux de Karnaugh
Reporter d'abord dans le tableau les valeurs de la fonction pour chacune des combinaisons des entrées
Faire ensuite des groupes de \(2^i\) cases adjacentes (donc pas en diagonale !) valant \(1\) (cf. remarque précédente) :
on essaie de faire des groupes les plus "grands" possibles
on peut utiliser plusieurs fois si nécessaire une même case pour plusieurs groupes différents
cependant, si toutes les cases à regroupées font partie d'un groupe au moins, on "arrête"
Pour chaque groupe, on ne conserve pour l'équation logique que les variables qui ne changent pas d'état
On déduit l'équation de la sortie en sommant les différents "morceaux" d'équation logique obtenus précédemment.
n=2
\(f_4 = \color{blue}{a \bar b}\)
n=3
\(f_5 = \color{blue}{\bar a b \bar c} + \color{green}{a b \bar c} \color{black}{= b \bar c}\)
n=4
\(f_6 = \color{magenta}{a \bar b c d}+\color{blue}{abcd} + \color{red}{ab \bar c d} + \color{green}{a \bar b \bar c d} \color{black}{= ad}\)
Maurice Karnaugh (1924 - )
Complément :
Ingénieur américain, docteur en physique (1952). Chercheur aux laboratoires Bell de 1952 à 1966, il y développe sa méthode de simplification d'équations logiques.
Il travaille ensuite dans le monde informatique au sein d'IBM (entre 1966 et 1993) et participe activement aux évolutions des télécommunications (membre de l'IEEE, association fixant notamment de nombreux standards en informatique).