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/ab	00	01	11	10
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}\ast \overline{b}\ast c+\overline{a}\ast b\ast c+a\ast \overline{b}\ast \overline{c}+a\ast \overline{b}\ast c+a\ast b\ast c$$

On peut ensuite construire le tableau de karnaugh :

c/ab	00	01	11	10
00
01

Pour chaque groupe on peut indiquer un 1 dans le tableau, par exemple $\overline{a}\ast \overline{b}\ast 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/ab	00	01	11	10
0
1	1

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

c/ab	00	01	11	10
0				1
1	1	1	1	1

On complète ensuite les cases restantes par des 0

c/ab	00	01	11	10
0	0	0	0	1
1	1	1	1	1

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)\ast (\overline{a}+b+c)\ast (\overline{a}+b+\overline{c})\ast (\overline{a}+\overline{b}+c)$$

Ensuite on inverse tous les paramètres

$$F(a,b,c)=(\overline{a}+\overline{b}+\overline{c})\ast (a+\overline{b}+\overline{c})\ast (a+\overline{b}+c)\ast (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/ab	00	01	11	10
00	0		0	0
01				0

Enfin on complète le reste avec des 1 :

c/ab	00	01	11	10
00	0	1	0	0
01	1	1	1	0

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/ab	00	01	11	10
00	1	0	1	1
01	1	0	1	0
11	1	0	0	1
10	1	0	0	1

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/ab	00	01	11	10
00	1	0	1	1
01	1	0	1	0
11	1	0	0	1
10	1	0	0	1

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

cd/ab	00	01	11	10
00	1	0	1	1
01	1	0	1	0
11	1	0	0	1
10	1	0	0	1

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}\ast \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}\ast \overline{d}+\overline{a}\ast \overline{b}+\overline{c}\ast a\ast b+\overline{b}\ast c$$