Algèbre de Boole/Simplification des expressions booléennes
Une expression booléenne peut souvent se simplifier.
Table de Karnaugh
[modifier | modifier le wikicode]
Comme une table de vérité, une table de Karnaugh pour une expression booléenne établit l'ensemble des résultats possibles pour chacune des combinaisons de ses paramètres d'entrée. Toutefois cette table est organisée de manière différente. Chaque case de cette table contient le résultat de l'expression (vrai ou faux) pour la combinaison de paramètres désignée par la ligne et la colonne.
L'ordre des combinaisons désignant les lignes et les colonnes est celui du code binaire réfléchi ou code de Gray, où chaque nouvelle combinaison de paramètre ne diffère de la précédente que par la valeur d'un seul paramètre.
Exemple
[modifier | modifier le wikicode]Dans cet exemple, on représente l'expression booléenne suivante :
(a ET b) OU (b ET NON c) ou (NON c ET b ET a)
| 0 | 0 | 1 | 1 | a | |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | b | |
| 0 | 0 | 1 | 1 | 0 | |
| 1 | 0 | 0 | 1 | 0 | |
| c |
Les lignes et colonnes, au lieu d'utiliser des 0 et des 1, peuvent utiliser un espace vierge et une barre. Selon la convention choisie, la barre peut symboliser la valeur vrai (1) ou bien la valeur fausse c'est à dire la barre de l'opérateur NON (a par ex).
| _ | _ | a | |||
|---|---|---|---|---|---|
| _ | _ | b | |||
| 0 | 1 | 1 | 0 | ||
| | | 0 | 0 | 1 | 0 | |
| c |
Simplification de l'expression
[modifier | modifier le wikicode]Une fois la table de Karnaugh créée, il faut construire l'expression simplifiée en regroupant les "1" de la table par groupe ayant une taille qui soit une puissance de 2.
Pour l'exemple précédent, on peut établir les groupes suivants :
Groupe 1[modifier | modifier le wikicode]
a ET b |
Groupe 2[modifier | modifier le wikicode]
b ET NON c |
Résultat[modifier | modifier le wikicode]L'expression simplifiée est donc :
(a ET b) OU (b ET NON c) |
Groupement circulaire
[modifier | modifier le wikicode]Il faut considérer la table comme circulaire : un groupe peut se poursuivre sur le bord opposé de la table.
Exemple : Simplifions l'expression suivante :
(NON a ET NON b ET NON c et NON d) OU (a ET NON b ET NON c et NON d) OU
(NON a ET NON b ET c et NON d) OU (a ET NON b ET c et NON d)
La table de Karnaugh et la suivante :
| _ | _ | a | ||||
|---|---|---|---|---|---|---|
| _ | _ | b | ||||
| 1 | 0 | 0 | 1 | |||
| | | 0 | 0 | 0 | 0 | ||
| | | | | 0 | 0 | 0 | 0 | |
| | | 1 | 0 | 0 | 1 | ||
| c | d |
On simplifie l'expression en trouvant le groupe suivant :
| _ | _ | a | ||||
|---|---|---|---|---|---|---|
| _ | _ | b | ||||
| 1 | 0 | 0 | 1 | |||
| | | 0 | 0 | 0 | 0 | ||
| | | | | 0 | 0 | 0 | 0 | |
| | | 1 | 0 | 0 | 1 | ||
| c | d |
NON b ET NON d