Skip to main content

Calcul booléen et table de Karnaugh

Tableau de Karnaugh

Une première manière de représenter une fonction logique avec des opérateurs booléens est d'utiliser les formes normales tel que vue au cours d'architecture des ordinateurs.

Mais pour des fonctions plus complexes, les formes normales ne sont pas très efficace pour représenter de manière concise la fonction.

Former le tableau (code binaire réfléchit)

Tout d'abord on liste les différents paramètres de la fonction. Imaginons $a,b,c$. On va donc avoir par exemple $a$ et $b$ horizontalement et $c$ verticalement :

c/ab????
?
?

Ensiute pour chaque groupe, on va les écrire côte à côte

 a   b
--- ---
     0
     1

Ensuite pour ajouter le chiffre suivant on va faire un "mirroir" de ce que l'on a écrit

 a   b
--- ---
     0
     1
-------
     1
     0

Et sur la colonne d'a côté on va écrire des 0 sur la première partie, et des 1 sur la deuxième

 a   b
--- ---
 0   0
 0   1
-------
 1   1
 1   0

Ce qui nous donne donc le code binaire réfléchit, et ainsi les intitulé de notre colonne → 00, 01, 11, 10

c/ab00011110
0
1

On peut donc écrire dans chaque case les valeurs de la fonction correspondante. Par exemple la deuxième case signifie que a est à 0, b est à 1 et c est à 0. On peut ainsi compléter le tableau.

Comment transformer une forme normale en tableau de karnaugh

1er forme (disjonctive)

Pour la première forme on va dire que chaque groupe (produit) correspond à un 1

$$ F(a,b,c) = \overline{a} * \overline{b} * c + \overline{a} * b * c + a * \overline{b} * \overline{c} + a * \overline{b} * c + a * b * c $$

On peut ensuite construire le tableau de karnaugh :

c/ab00011110
00
01

Pour chaque groupe on peut indiquer un 1 dans le tableau, par exemple $\overline{a} * \overline{b} * c$ c'est l'équivalent de dire a=0, b=0 et c=1 on peut donc l'indiquer dans la case correspondante du tableau :

c/ab00011110
0
11

Et ainsi de suite pour le reste du tableau, ce qui nous donne :

c/ab00011110
01
11111

On complète ensuite les cases restantes par des 0

c/ab00011110
00001
11111

2e forme (conjonctive)

Pour la deuxième forme normale c'est un peu plus bizarre. Disons que l'on part de la forme suivante :

$$ F(a,b,c) = (a+b+c) * (\overline{a}+b+c) * (\overline{a}+b+\overline{c}) * (\overline{a}+\overline{b}+c) $$

Ensuite on inverse tous les paramètres

$$ F(a,b,c) = (\overline{a}+\overline{b}+\overline{c}) * (a+\overline{b}+\overline{c}) * (a+\overline{b}+c) * (a+b+\overline{c}) $$

Ensuite on procède exactement comme avant sauf qu'a la place d'écrire des 1 on écrit des 0.

c/ab00011110
00000
010

Enfin on complète le reste avec des 1 :

c/ab00011110
000100
011110

Simplifier un tableau de Karnaugh

Maintenant que l'on sait comment créer un tableau de Karnaugh, on va maintenant l'utiliser pour obtenir une forme plus abrégée des fonctions.

cd/ab00011110
001011
011010
111001
101001

On peut ensuite grouper les différents éléments par puissance de 2 (donc par 1, 2, 4, 8, etc). ATTENTION, il faut imaginer le tableau comme une boule, les 1 sur les extrémités peuvent être reliées entre elles. Donc si par exemple il y a un 1 dans chaque coin, ils peuvent être connecté comme un seul groupe.

Par exemple voici un groupe (un peu complexe) de 1 dans tous les coins :

cd/ab00011110
001011
011010
111001
101001

Ensuite on peut regarder quels sont les paramètres qui ne varient pas :

cd/ab00011110
001011
011010
111001
101001

On remarque donc que dans tous les cas du groupe, a et b sont à 0. Donc l'expression en produit de notre groupe est $\overline{b} * \overline{d}$

On peut ensuite faire la même chose pour tous les groupes ce qui nous donne :

Il faut donc essayer de toujours prendre les plus grand groupes (pour avoir les plus petits produits) et d'en prendre le moins possibles (pour avoir le moins de produits possibles).

Cela va donc nous donner l'expression simplifiée suivante :

$$ F(a,b,c) = \overline{b} * \overline{d} + \overline{a} * \overline{b} + \overline{c} * a * b + \overline{b} * c $$

Back to top