Karnaugh

Les tableaux de Karnaugh

Introduction

La simplification d'une expression booléenne consiste à réduire le nombre d'opérateurs et/ou de variables, permettant ainsi d'obtenir une version plus compacte de cette expression.

Plusieurs méthodes sont disponibles à cet effet, mais l'une des plus efficaces est l'utilisation du tableau de Karnaugh. Voici comment elle fonctionne :

On crée un tableau pour la fonction à simplifier.
On cherche les cellules adjacentes avec la valeur 1.
On regroupe ces cellules en blocs de 2^n (n étant un nombre entier), en visant à faire des blocs aussi grands que possible.

Construction du tableau de Karnaugh

Pour une fonction à 3 variables :

On met deux variables en haut du tableau (A et B).
On place la troisième variable sur le côté gauche (C).
La sortie (S) est le résultat de la fonction pour chaque combinaison de valeurs des variables.

Pour une fonction à 4 variables :

Deux variables en haut (A et B)
Deux variables à gauche (C et D)

Exemples

Considérons la simplification de l'équation logique suivante : $$ S = \overline a b \overline c \overline d + abcd + a \overline b c d + ab \overline c \overline d $$ En utilisant le tableau de Karnaugh, on peut regrouper les 1 adjacents. Dans le premier regroupement (en haut du tableau), la variable a change d'état et est donc éliminée. Il reste alors : $$ b \overline c \overline d $$ Dans le second regroupement (en bas du tableau), la variable b change d'état et est éliminée. Il reste alors : $$ acd $$ L'équation logique simplifiée est donc : $$ S = acd + b \overline c \overline d $$

En utilisant la même méthode, on peut simplifier d'autres équations logiques. Par exemple :

S	00	01	11	10
00	1	0	0	0
01	1	0	0	0
11	1	0	0	0
10	1	0	0	0

Est simplifiée en : $$ S = \overline a \overline b $$

Et de même pour :

S	00	10
00	1	1
01	1	1
11	1	1
10	1	1

Qui devient : $$ S = \overline b $$

Et encore une fois pour :

S	00	10
00	1	1
01	0	0
11	0	0
10	1	1

Qui devient : $$ S = \overline b \overline d $$

Exercices

Essayez de simplifier l'équation logique suivante à l'aide d'un tableau de Karnaugh : $$ T = \overline a b \overline c \overline d + ab \overline c \overline d + \overline a bc \overline d + abc\overline d + \overline a \overline b c \overline d + a \overline b c \overline d $$

Puis, en utilisant le tableau de Karnaugh ci-dessous, tentez de trouver l'équation logique réduite correspondante. Astuce : utilisez le théorème de DE MORGAN.

U	00	01	11	10
00	1	1	1	1
01	1	1	1	1
11	1	1	0	1
10	1	1	1	1

\[ \overline U = abcd \]

Auteur : Florian Mathieu

Licence CC BY NC

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.