dateimg

Simplification selon Karnaugh

- Sciences

- logique, boole, conditions, mathématiques, parking

notrepassor

Devant le bureau de poste, vous pouvez vous stationner si:

  • Ce n’est pas le weekend, ce n’est pas l’hiver, la voiture n’est pas éléctrique et il y a plus d'un passager OU

  • Ce n’est pas le weekend, ce n’est pas l’hiver, la voiture est électrique et il y a plus d’un passager OU

  • Ce n’est pas le weekend, c’est l’hiver, la voiture n’est pas électrique et il n’y a pas plus d’un passager OU

  • Ce n’est pas le weekend, c’est l’hiver, la voiture est électrique et il n’y a pas plus d’un passager OU

  • C’est le weekend, c’est l’hiver, la voiture n’est pas électrique et il n’y a pas plus d’un passager OU

  • C’est le weekend, c’est l’hiver, la voiture est électrique et il n’y a pas plus d’un passager.

... Déjà à l'instinct, on se doute qu'il y a moyen de simplifier ces conditions. Par contre, lorsque les conditions dépassent une certaine complexité (généralement lorsqu'il y a plus de trois variables), la simplification se fait difficilement par instinct. La technique du Tableau de Karnaugh nous permettra de simplifier la formule.

Mais avant tout, il faut extraire les variables à partir de l'énoncé:

a: C'est le weekend
b: C'est l'hiver
c: La voiture est électrique
d: Il y a plus d'un passager 

Produisons maintenant la formule avec variables et opérateur (considérant que les négations sont représentées par un "¬", que les variables d'une même condition sont regroupées, et que ces groupes sont séparés par l'opérateur OU représenté par un "+" ) :

¬a¬b¬cd + ¬a¬bcd + ¬ab¬c¬d + ¬abc¬d + ab¬c¬d + abc¬d

Afin de construire le tableau de Karnaugh il faut identifier les valeurs positives et négatives:

¬a ¬b ¬c  d ¬a ¬b  c  ¬a ¬c ¬d ¬a ¬d ¬c ¬d ¬d
0 0 0 1   0 0 1 1   0 1 0 0   0 1 1 0   1 1 0 0   1 1 1 0

 
Nous sommes prêts à construire le tableau. Il y a 4 variables, donc 4 lignes et 4 colonnes. Les lignes représenteront les variables a et b, et les colonnes représenteront les variables c et d. Chaque ligne et chaque colonne représente en fait la valeur qu'une variable peut prendre et les intersections entre les deux représentent toutes les combinaisons possibles:

ab \ cd   00     01     11     10  
00 0000 0001 0011 0010
01 0100 0101 0111 0110
11 1100 1101 1111 1110
10 1000 1001 1011 1010

Maintenant, nous pouvons mettre un 1 pour chacune des 6 combinaisons et des 0 pour le reste:

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

Prochaine étape on repère les 1 qui sont regroupés en carré (2, 4, 8...) et on les regroupe. Important à savoir, le tableau est comme un cylindre (ou un beigne), les bordures se rejoignent, regardez comment on regroupe les quatres 1: 

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

Nous avons deux groupes de 1... ce qui signifie qu'au final il ne restera que deux groupes de variables séparés par un "+". Mais comment identifier ces groupes de variables?

Simplement en identifiant ce qu'il y a de commun entre chaque recoupement ligne/colonne d'un groupe.

Dans le groupe vert, nous avons 0001 et 0011, représentant respectivement ¬a¬b¬cd et ¬a¬bcd ... qu'on t-il en commun? ¬a¬bd

Dans le groupe bleu, nous avons 0100, 0110, 1100, 1110 (¬ab¬c¬d, ¬abc¬d, ab¬c¬d, abc¬d). Ces quatres groupes ont en commun b¬d

Donc la simplification de la formule est ¬a¬bd + b¬d

Phew...

Si on converti les variables pour reformuler la liste de conditions de départ, ça nous donne:

Devant le bureau de poste, vous pouvez vous stationner si:

  • Ce n'est pas le weekend, ce n'est pas l'hiver et il y a plus d'un passager OU
  • C'est l'hiver et il n'y a pas plus d'un passager

Beaucoup plus simple n'est-ce pas? On constate même que le fait que la voiture soit électrique ou non n'a jamais eu aucune importance.

Il n'est pas toujours simple de faire simple, mais l'effort fait pour simplifier à la source sera toujours bénéfique, il permet des structures logiques plus propres, plus claires, limitant les erreurs d'interprétations.
 

spagatte

 

 

img_ref


retourner en haut de la page

Si nous étions seuls dans l'univers, ça ferait un beau gaspillage d'espace.

Limat