Médaille
N°1 pour apprendre & réviser du collège au lycée.

Simplification des expressions logiques

Déjà plus de

1 million

d'inscrits !

Introduction :

Ici, nous allons appliquer les propriétés apprises dans le cours précédent, afin de simplifier une équation logique.
Nous verrons aussi une autre méthode, plus visuelle et rapide, pour opérer une simplification à partir d’une table de vérité.

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 OU\text{OU} à partir de sa table de vérité.

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

aa bb cc S\red S
00 00 00 0\red 0
00 00 11 0\red 0
00 11 00 0\red 0
00 11 11 1\red1
11 00 00 0\red0
11 00 11 1\red1
11 11 00 1\red1
11 11 11 1\red1

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=aˉbc+abˉc+abcˉ+abcS=\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.

S=aˉbc+abˉc+abcˉ+abcS=\bar a\cdot b\cdot c+a\cdot \bar b\cdot c+a\cdot b\cdot \bar c+a\cdot b\cdot c Forme canonique disjonctive
S=aˉbc+a(bˉc+bcˉ+bc)S=\bar a\cdot b\cdot c+\red{a\cdot (\bar b\cdot c+ b\cdot \bar c+ b\cdot c)} Distributivité : factorisation par aa
S=aˉbc+a(bˉc+b(cˉ+c))S=\bar a\cdot b\cdot c+a\cdot \big(\bar b\cdot c+ \red{b\cdot (\bar c+ c)}\big) Distributivité : factorisation par bb
S=aˉbc+a(bˉc+b1)S=\bar a\cdot b\cdot c+a\cdot (\bar b\cdot c+ b\cdot \red 1) cˉ+c=1\bar c + c=1
S=aˉbc+a(b+bˉc)S=\bar a\cdot b\cdot c+a\cdot \red{(b + \bar b\cdot c)} 11 élément neutre de ET\text{ET}, puis commutativité
S=aˉbc+a(b+c)S=\bar a\cdot b\cdot c+a\cdot \red{(b + c)} Absorption : b+bˉc=b+cb + \bar b\cdot c = b+c
S=aˉbc+ab+acS=\bar a\cdot b\cdot c+\red{a\cdot b + a\cdot c} Distributivité : développement
S=c(aˉb+a)+abS=\red{c\cdot(\bar a\cdot b+a)}+a\cdot b Distributivité : factorisation par cc
S=c(a+aˉb)+abS=c\cdot\red{ (a+\bar a\cdot b)}+a\cdot b Commutativité
S=c(a+b)+abS=c\cdot\red{(a+ b)}+a\cdot b Absorption : a+aˉb=a+ba + \bar a\cdot b = a+b
S=ab+ac+bcS=a\cdot b + a\cdot c+b\cdot c Distributivité : développement, puis commutativité
  • L’expression simplifiée est donc : S=ab+ac+bcS=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 :

ab+abˉ=aa\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.

bannière exemple

Exemple

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

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

  • Nous les représentons dans un tableau de Karnaugh.
bannière definition

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 2n2^n cellules.
bannière astuce

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 nn variables d’entrée, il y a 2n2^n lignes dans la table de vérité, il y a donc 2n2^n cellules à compléter dans le tableau de Karnaugh.
bannière à retenir

À retenir

Si le nombre de variables nn est pair, les lignes représenteront les valeurs des n2\frac n2 premières variables et les colonnes les n2\frac n2 variables restantes.
Si le nombre de variables nn est impair, les lignes représenteront les valeurs des n12\frac {n-1}2 premières variables et les colonnes les n+12\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 22, 33 et 44 variables.

Tableau à 22 variables

bb\rightarrow

aa\downarrow

00 11
00 aˉbˉ\bar a\cdot \bar b aˉb\bar a\cdot b
11 abˉa\cdot \bar b aba\cdot b

Tableau à 33 variables

bcbc\rightarrow

aa\downarrow

0000 0101 1111 1010
00 aˉbˉcˉ\bar a\cdot \bar b \cdot \bar c aˉbˉc\bar a\cdot \bar b \cdot c aˉbc\bar a\cdot b \cdot c aˉbcˉ\bar a\cdot b \cdot \bar c
11 abˉcˉa\cdot \bar b \cdot \bar c abˉca\cdot \bar b \cdot c abca\cdot b \cdot c abcˉa\cdot b \cdot \bar c

Tableau à 44 variables

cdcd\rightarrow

abab\downarrow

0000 0101 1111 1010
0000 aˉbˉcˉdˉ\bar a \cdot \bar b \cdot \bar c \cdot \bar d aˉbˉcˉd\bar a \cdot \bar b \cdot \bar c \cdot d aˉbˉcd\bar a \cdot \bar b \cdot c \cdot d aˉbˉcdˉ\bar a \cdot \bar b \cdot c \cdot \bar d
0101 aˉbcˉdˉ\bar a \cdot b \cdot \bar c \cdot \bar d aˉbcˉd\bar a \cdot b \cdot \bar c \cdot d aˉbcd\bar a \cdot b \cdot c \cdot d aˉbcdˉ\bar a \cdot b \cdot c \cdot \bar d
1111 abcˉdˉa \cdot b \cdot \bar c \cdot \bar d abcˉda \cdot b \cdot \bar c \cdot d abcda \cdot b \cdot c \cdot d abcdˉa \cdot b \cdot c \cdot \bar d
1010 abˉcˉdˉa \cdot \bar b \cdot \bar c \cdot \bar d abˉcˉda \cdot \bar b \cdot \bar c \cdot d abˉcda \cdot \bar b \cdot c \cdot d abˉcdˉa \cdot \bar b \cdot c \cdot \bar d
bannière à retenir

À retenir

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

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

aa bb cc S\red S
00 00 00 0\red 0
00 00 11 0\red 0
00 11 00 0\red 0
00 11 11 1\red1
11 00 00 0\red0
11 00 11 1\red1
11 11 00 1\red1
11 11 11 1\red1
  • Nous obtenons le tableau de Karnaugh suivant :

bcbc\rightarrow

aa\downarrow

0000 0101 1111 1010
00 00 00 11 00
11 00 11 11 11

Par exemple :

  • la cellule en orange (0 010\ 01, soit aˉbˉc\bar a\cdot \bar b\cdot c) correspond à la deuxième ligne de la table de vérité ;
  • la cellule en jaune (1 111\ 11, soit abca\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 110\ 11 et 1 111\ 11. Nous le savons, l’équation de vérité contiendra les termes : aˉbc+abc\bar a\cdot b\cdot c + a\cdot b \cdot c.

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

aˉbc+abc=aˉ(bc)+a(bc)=(bc)(aˉ+a)=(bc)1=bc\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 aa, qui est la seule changeant de valeur !
bannière à retenir

À 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 22 (11, 22, 44, 88, 1616, 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=aa + 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.
bannière attention

Attention

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

  • Il ne faut donc pas faire des groupes de 33, 55, 77, 1010… termes !

Regardons deux tableaux de Karnaugh avec 44 variables.

première sciences de l’ingénieur table de vérité tableau de Karnaugh

Nous regroupons les 44 termes égaux à 11. Dans le groupe ainsi formé :

  • aa change de valeur ;
  • bb ne change pas de valeur ;
  • cc change de valeur ;
  • dd ne change pas de valeur.
  • Nous pouvons éliminer aa et cc.
  • L’équation logique est : S=bdˉS=b\cdot \bar d.

première sciences de l’ingénieur table de vérité tableau de Karnaugh

Nous pouvons ici former 22 groupes, l’un de 44 termes, l’autre de 88 termes.

  • Dans le premier groupe (encadré en rouge), aa et dd changent de valeur.

Nous écrivons le terme correspondant : bcˉb\cdot \bar c.

  • Dans le deuxième groupe (encadré en bleu), seul aa ne change pas de valeur.

Nous écrivons le terme correspondant : aa.

  • D’où l’équation logique : S=a+bcˉS=a+b\cdot \bar c .

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

première sciences de l’ingénieur table de vérité tableau de Karnaugh

Nous constituons 33 groupes de 22 termes.

  • Pour celui encadré en bleu, seul aa change de valeur : bcb\cdot c.
  • Pour celui encadré en rouge, seul bb change de valeur : aca\cdot c.
  • Pour celui encadré en vert, seul cc change de valeur : aba\cdot b.
  • D’où l’équation logique : S=ab+ac+bcS=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 !

Conclusion :

Vous l’avez vu, l’algèbre de Boole est régie par des lois proches de celle que vous manipulez depuis longtemps.
Apprendre les formules, bien sûr, mais, en réalité, il ne s’agit que de logique, donc faites travailler votre bon sens et peut-être qu’une lumière s’allumera !

Ainsi pouvez-vous retrouver comment tout cela fonctionne et manipuler les portes logiques même si elles sont nombreuses et qu’elles dépendent de nombreuses variables. Comme dans un microprocesseur, par exemple !