Simplification des expressions logiques

Exemple de table de vérité

Nous l’avons vu, une table de vérité nous donne une équation logique sous sa forme canonique disjonctive. Celle-ci peut donc avoir de nombreux termes et il conviendra alors de la simplifier.

• C’est d’ailleurs ce que nous avons fait pour retrouver l’équation simplifiée de la fonction $\text{OU}$ à partir de sa table de vérité.

Pour montrer le principe, nous allons nous appuyer sur la table de vérité suivante :

Simplification algébrique

Utilisons, d’abord, la technique que nous connaissons tous, celle algébrique, en nous appuyant sur les propriétés vues dans le cours précédent.

• Écrivons l’équation à partir de la table de vérité :

$$S=\bar a\cdot b\cdot c+a\cdot \bar b\cdot c+a\cdot b\cdot \bar c+a\cdot b\cdot c$$

• Elle est sous sa forme canonique disjonctive.
• Nous cherchons donc à la simplifier.

Dans le tableau suivant, nous indiquons chaque étape de la simplification et nous précisons la propriété appliquée.

• L’expression simplifiée est donc : $S=a\cdot b + a\cdot c+b\cdot c$.

Simplification par la méthode de Karnaugh

Pour simplifier par la méthode algébrique, il faut parfois de nombreuses étapes, procéder à tâtons, sans parler du fait qu’il faut connaître toutes les propriétés (même si ce dernier point, bien sûr, ne nous pose aucun problème…).

• Rassurez-vous, il existe une méthode visuelle et plus rapide : la méthode de Karnaugh !

De la table de vérité au tableau de Karnaugh

La méthode repose sur la propriété vue et démontrée dans le cours précédent :

$$a\cdot \red b+a\cdot \red {\bar b}=a$$

Et elle consiste à identifier tous les mintermes qui ne diffèrent que par l’état d’une seule variable (appelés adjacents) : nous pourrons alors « éliminer » la variable qui change d’état.

Exemple

Dans la propriété citée, seul l’état de $b$ change, nous supprimons donc la variable $b$ pour ne conserver que $a$.

Nous l’avons dit, si une fonction dépend de $n$ variables, il y aura au maximum $2^n$ mintermes.

• Nous les représentons dans un tableau de Karnaugh.

Définition

Tableau de Karnaugh :

Il s’agit d’une table de vérité particulière, à double entrée, qui présente tous les produits possibles entre les variables et leurs compléments.

• Un tel tableau comptera $2^n$ cellules.

Astuce

Le lien entre le nombre de cases d’un tableau de Karnaugh et le nombre de lignes de la table de vérité associée est direct : il y a autant de produits possibles que de lignes dans la table de vérité et de cases dans le tableau de Karnaugh.

• Pour $n$ variables d’entrée, il y a $2^n$ lignes dans la table de vérité, il y a donc $2^n$ cellules à compléter dans le tableau de Karnaugh.

À retenir

Si le nombre de variables $n$ est pair, les lignes représenteront les valeurs des $\frac n2$ premières variables et les colonnes les $\frac n2$ variables restantes.
Si le nombre de variables $n$ est impair, les lignes représenteront les valeurs des $\frac {n-1}2$ premières variables et les colonnes les $\frac {n+1}2$ variables restantes.

Puisqu’il s’agit d’identifier les termes où une seule variable change d’état, il est important, pour les lignes et les colonnes, de donner les valeurs des variables selon l’ordre du code de Gray, et non selon celui du code binaire naturel (comme dans une table de vérité classique).

Voici les tableaux de Karnaugh pour $2$, $3$ et $4$ variables.

À retenir

Pour passer d’une table de vérité à un tableau de Karnaugh, il suffit d’écrire $1$ dans les cellules qui correspondent aux combinaisons ayant pour sortie $1$, et $0$ dans les cellules restantes.

Appliquons ce principe à la table de vérité donnée en début de cours :

• Nous obtenons le tableau de Karnaugh suivant :

Par exemple :

• la cellule en orange ($0\ 01$, soit $\bar a\cdot \bar b\cdot c$) correspond à la deuxième ligne de la table de vérité ;
• la cellule en jaune ($1\ 11$, soit $a\cdot b \cdot c$) correspond à la dernière ligne de la table de vérité.

Simplification à partir du tableau de Karnaugh

Voyons maintenant à quoi ce tableau sert.
Par exemple, intéressons-nous aux deux cellules correspondant à $0\ 11$ et $1\ 11$. Nous le savons, l’équation de vérité contiendra les termes : $\bar a\cdot b\cdot c + a\cdot b \cdot c$.

• Et selon la propriété d’absorption mentionnée :

$$\begin{aligned} \bar a\cdot b\cdot c + a\cdot b \cdot c&=\bar a\cdot (b\cdot c) + a\cdot (b \cdot c) \\ &= (b\cdot c)\cdot(\bar a + a) \\ &= (b\cdot c)\cdot 1 \\ &= b\cdot c \end{aligned}$$

• Nous pouvons simplifier en éliminant la variable $a$, qui est la seule changeant de valeur !

À retenir

La simplification par la méthode de Karnaugh repose sur ce principe.

• Dans le tableau, nous regroupons les valeurs égales adjacentes par une puissance de $2$ ($1$, $2$, $4$, $8$, $16$, etc.).
• La dernière ligne est adjacente à la première, la dernière colonne est adjacente à la première colonne (nous le voyons : une seule variable change d’état).
• Nous veillons à ce que toutes les valeurs égales appartiennent à un groupe.
• Un terme peut participer à plusieurs groupes (car $a + a = a$).
• Dans chaque groupe, nous supprimons la ou les variables qui changent d’état.
• Si un groupe contient un seul terme, nous ne pouvons évidemment supprimer aucune variable.
• Nous écrivons le produit des variables restantes, avec leurs valeurs (qui donc ne changent pas) dans le tableau.
• Nous faisons la somme de l’ensemble des termes ainsi obtenus.

Attention

Insistons sur ce point : les termes doivent être groupés par une puissance de $2$.

• Il ne faut donc pas faire des groupes de $3$, $5$, $7$, $10$… termes !

Regardons deux tableaux de Karnaugh avec $4$ variables.

Pour terminer, reprenons le tableau de Karnaugh constitué à partir de la table de vérité prise en exemple :

Nous constituons $3$ groupes de $2$ termes.

• Pour celui encadré en bleu, seul $a$ change de valeur : $b\cdot c$.
• Pour celui encadré en rouge, seul $b$ change de valeur : $a\cdot c$.
• Pour celui encadré en vert, seul $c$ change de valeur : $a\cdot b$.
• D’où l’équation logique : $S=a\cdot b+a\cdot c+b\cdot c$.
• Ce qui correspond bien à ce que nous trouvions avec la simplification algébrique, mais nous y sommes parvenus de manière plus visuelle !