Aller au menu - Aller au contenu

Icône L'algèbre de Boole

Par alcinos
Mise à jour : 25/10/2010
Difficulté : Facile Facile Durée d'étude : 1 jour Creative Commons BY-NC-SA
295 visites depuis 7 jours, classé 343/786
Nous allons dans ce tuto étudier l'algèbre de boole. Derrière ce nom barbare se cache en fait quelque chose que tout programmeur, même débutant, utilise sans le savoir, dans les conditions.
Il est assez peu utile dans la plupart des cas :p , mais il peut avoir son utilité en algorithmique, pour la recherche de performances au niveau des conditions, en SQL, pour les requêtes, ou en électronique, pour limiter le nombre de câblage de portes logiques.
Retour en haut
Sommaire du tutoriel :
Icône du chapitre
Retour en haut

Les variables booléennes

L'algèbre de Boole est une structure algébrique qui ne contient que deux éléments, que l'on appelle couramment variables booléennes. Ces variables ne peuvent avoir que deux états, 1 ou 0 (true ou false dans certains langages de programmation), et respectent quelques règles de calcul que nous détaillerons plus loin.

Mais quel est le rapport avec les conditions ? o_O


J'y viens ^^ . En fait n'importe quel test exécuté dans une condition est une variable booléenne.
Prenons un exemple
Code : Autre
1

SI (A=B) ALORS ...

Le test (A=B) peut avoir deux valeurs : 1 si A est réellement égal à B et 0 sinon. On dit que c'est la variable booléenne associée au test A=B.
Retour en haut

Les opérateurs logiques

L'algèbre de Boole utilise plusieurs opérateurs que l'on nomme opérateurs booléens, opérateurs logiques, ou encore fonctions logiques ou portes logiques (terme plus propre à l'électronique).
En voici les principaux.

L'opérateur OU



Il correspond à la réunion de deux conditions. Par exemple : je souhaite acheter une voiture bleue OU climatisée. Les voitures correspondant à mon choix seront donc soit bleue, soit climatisée, soit les deux à la fois.

On symbolise l'opérateur OU dans les conditions par un OR ou ||
En algèbre de Boole, il est symbolisée par un +
La matheux préfèrent quant à eux la symbolisation \vee

Exemple :
Code : C
1
if(a==1 OR a==2){

Équivaut à
Code : Autre
1

SI((a=1)+(a=2)) alors


Si on prend des variables booléennes, on obtient :
a \operatorname{OU} b \Leftrightarrow a+b

Table de vérité :
a b a+b
0 0
0
1 0
1
0 1
1
1 1
1

Dans ce tableau on voit le résultat du test a+b en fonction des valeurs de a et de b

L'opérateur ET



Il correspond à l'intersection de deux conditions. Par exemple : je souhaite acheter une voiture bleue ET climatisée. correspondant à mon choix seront donc à la fois bleues et climatisées.

On symbolise l'opérateur ET dans les conditions par un AND ou &&
En algèbre de Boole, il est symbolisée par un \cdot
En maths on écrira plutôt \wedge

Exemple :
Code : C
1
if(a==1 AND a==2){

Équivaut à
Code : Autre
1

SI((a=1).(a=2)) alors


Si on prend des variables booléennes, on obtient :
a \operatorname{ET} b \Leftrightarrow a \cdot b

Table de vérité :
a b a.b
0 0
0
1 0
0
0 1
0
1 1
1

Dans ce tableau on voit le résultat du test a \cdot b en fonction des valeurs de a et de b

L'opérateur NON




Il correspond au complément à 1 d'une condition. Par exemple : je souhaite acheter une voiture NON polluante. Les voitures correspondant à mon choix seront donc écologiques.

L'opérateur NON est souvent représenté dans les conditions par un !
En algèbre de Boole, il est symbolisée par une barre au dessus de(s) variable(s)
En maths on utilise le symbole \neg
Exemple :
Code : C
1
if(a!=1){

Équivaut à

SI \left(\overline{a=1}\right) alors ...


Si on prend des variables booléennes, on obtient :
!a équivaut à \bar{a}

Table de vérité :
a \bar{a}
0
1
1
0

Dans ce tableau on voit le résultat du test \bar{a} en fonction des valeurs de a

L'opérateur XOR (OU exclusif)




Il correspond à l'intersection de deux conditions, privée de la réunion de ces deux conditions. Par exemple : le menu propose du fromage OU EXCLUSIF un dessert : Je peux prendre soit l'un soit l'autre, mais pas les deux.

L'opérateur XOR est représenté dans les conditions par un XOR
En algèbre de Boole, il est symbolisée par un \oplus
Exemple :

a\operatorname{XOR}b\Leftrightarrow a\oplus b

Table de vérité :
a b a\oplusb
0 0
0
1 0
1
0 1
1
1 1
0

Dans ce tableau on voit le résultat du test a\oplus b en fonction des valeurs de a et de b

Note : a\oplus b=\overline{a}\cdot b+a\cdot \overline{b}

L'opérateur NXOR (NON OU exclusif)



Cet opérateur n'a pas de symbolisation propre, on le note simplement NXOR

Table de vérité :
a b a NXOR b
0 0
1
1 0
0
0 1
0
1 1
1

Cet opérateur est appelé opérateur coincidence. En effet le test "a \operatorname{NXOR} b" n'est vrai que si a et b sont dans le même état logique (0 ou 1)

Note : a \operatorname{NXOR} b=a \cdot b + \overline{a} \cdot \overline{b}

L'opérateur NAND (NON ET) ou connecteur de Sheffer



La fonction NAND est l'enchainement de la fonction ET et de la fonction NON. On la symbolise par ↑

Table de vérité :
a b a\uparrowb
0 0
1
1 0
1
0 1
1
1 1
0

L'opérateur NAND est appelé opérateur universel : il est possible de recréer n'importe quelle fonction logique uniquement en utilisant la fonction NAND. Nous verrons plus loin dans ce tuto comment.

Note : a \uparrow b}=\overline{a \cdot b}=\overline{a} + \overline{b}

L'opérateur NOR (NON OU)



La fonction NOR est l'enchainement de la fonction OU et de la fonction NON. On la symbolise par ↓

Table de vérité :
a b a\downarrowb
0 0
1
1 0
0
0 1
0
1 1
0

L'opérateur NOR est également un opérateur universel.

Note : a \downarrow b}=\overline{a + b}=\overline{a} \cdot \overline{b}
Retour en haut

Régles de simplification

Entrons maintenant dans le vif du sujet en apprenant les règles de l'algèbre, qui vont nous permettre de simplifier nos conditions.

Règle 1 : la commutativité


Même si elle parait évidente, il me semble bon de la préciser :

a + b = b + a
a \cdot b = b \cdot a

Règle 2 : l'idempotence


Un nom barbare pour une propriété simple :

a + a = a
a \cdot a = a

Règle 3 : l'élément nul



Comme son nom l'indique, il prend le dessus dans l'égalité :

a + 1 = 1
a \cdot 0 = 0

Règle 4 : l'élément neutre


Il ne change rien à l'égalité :

a \cdot 1=a
a + 0=a

Règle 5 : l'associativité


Elle parait évidente aussi :

a + \left(b + c\right)=\left(a + b\right) + c
a \cdot \left(b \cdot c\right)=\left(a \cdot b\right) \cdot c

Règle 6 : la complémentarité


\overline{\overline{a}} = a \quad\text{(Non Non = Oui)}
a + \overline{a}=1
a \cdot \overline{a} = 0

Règle 7 : la distributivité


Attention, les deux lois sont distributives l'une par rapport à l'autre, contrairement à l'algèbre classique

a \cdot \left(b + c\right)=a \cdot b + a \cdot c
a + \left(b \cdot c\right)=\left(a + b\right) \cdot \left(a+c\right)

Règle 8 : théorème de De Morgan


Règle très utile, mais attention aux erreurs de changement d'opérateur

\overline{a.b}=\overline{a}+\overline{b}
\overline{a+b}=\overline{a}.\overline{b}

Et les autres


Il existe d'autres règles qui découlent plus ou moins simplement des précédentes. Notamment :
a+\overline{a}.b=a+b

Démonstration :

\begin{align*}\overline{a + \overline{a} \cdot b} &= \overline{a} \cdot \overline{\overline{a} \cdot b} & \text{(R\`{e}gle 8)} \\& =\overline{a} \cdot \left(\overline{\overline{a}} + \overline{b}\right) & \text{(R\`{e}gle 8)} \\& =\overline{a} \cdot \left(a + \overline{b}\right) & \text{(R\`{e}gle 6)} \\& =\overline{a} \cdot a + \overline{a} \cdot \overline{b} & \text{(R\`{e}gle 7)} \\& =0+\overline{a} \cdot \overline{b} & \text{(R\`{e}gle 6)} \\& =\overline{a} \cdot \overline{b} & \text{(R\`{e}gle 4)} \\& =\overline{a + b} & \text{(R\`{e}gle 4)} \end{align*}

\text{Donc } \overline{a+\overline{a}.b}=\overline{a+b}\text{, soit } a+\overline{a}.b=a+b

Autre règle :
a+a.b=a

Démonstration :

\begin{align*}a + a \cdot b &= a \cdot 1 + a \cdot b & \text{(R\`{e}gle 4)} \\& = a \cdot \left(1 + b\right) & \text{(R\`{e}gle 7)} \\& = a \cdot 1 & \text{(R\`{e}gle 3)} \\& = a & \text{(R\`{e}gle 4)}\end{align*}


Voilà, vous connaissez maintenant les principales règles de l'algèbre de boole, vous en savez assez pour simplifier la grande majorité des équations. Pour les plus récalcitrantes, un autre outil existe, il s'agit du tableau de Karnaugh
Retour en haut

Spécificités des portes composées

Dans cette partie nous allons vois les règles qui s'appliquent (ou pas) aux portes logiques composées, c'est à dire XOR, NXOR, NAND, et NOR.

L'universalité des portes NAND et NOR



La porte NAND



Comme je vous l'ai dit précédemment, il est possible de réaliser n'importe quelle fonction logique de base en utilisant uniquement des portes NAND. C'est notamment très utile en électronique, puisqu'on peut alors produire en masse (et donc moins coûteusement) uniquement ces portes la, pour câbler ensuite n'importe quelle équation logique.

La fonction NON : a \uparrow 1=\overline{a \cdot 1}=\overline{a}

La fonction ET : \left(a \uparrow b\right)\uparrow 1=\overline{\overline{a \cdot b}\cdot 1}=\overline{\overline{a \cdot b}}=a.b

La fonction OU : \left(a \uparrow 1\right)\uparrow \left(b \uparrow 1\right)=\overline{\overline{a \cdot 1}\cdot\overline{b \cdot 1}}=\overline{\overline{a}\cdot\overline{b}}=a+b

La porte NOR



La porte NOR possède les mêmes spécificités :

La fonction NON : a \downarrow 0=\overline{a + 0}=\overline{a}

La fonction ET : \left(a \downarrow 0\right)\downarrow \left(b \downarrow 0\right)=\overline{\overline{a + 0}+\overline{b + 0}}=\overline{\overline{a}+\overline{b}}=a.b

La fonction OU : \left(a \downarrow b\right)\downarrow 0=\overline{\overline{a + b}+0}=\overline{\overline{a + b}}=a + b

Règles de calcul spécifiques



Pour effectuer des simplifications avec des portes composées, il existe deux solutions. La première consiste a transformer la fonction composée de façon à n'utiliser que les portes de base (NON, OU, ET). Il faut pour cela utiliser les équivalences que j'ai indiqué à la définition de chaque porte. Par exemple : a \oplus b \Leftrightarrow a.\overline{b}+\overline{a}.b On peut alors utiliser les règles de simplifications listées plus haut.

Le deuxième choix qui s'offre à nous est d'utiliser les règles de calcul spécifiques aux portes composées (utile par exemple s'il faut garder un seul type de porte dans les équations)


Règles spécifiques à la porte XOR



Quelques règles qui sont en fait des propriétés aisément déductibles des règles précédentes
  • a \oplus 1 = \overline{a}
  • a \oplus 0 = a
  • a \oplus a = 0
  • a \oplus \overline{a} = 1


Règles spécifiques à la porte NAND



Voici les propriétés de la porte NAND
  • a \uparrow 1=\overline{a}
  • a \uparrow 0=1
  • a \uparrow a=\overline{a}
  • a \uparrow \overline{a}=1

Il n'y a PAS d'associativité avec les portes NAND : a \uparrow \left(b \uparrow c \right) \neq \left(a \uparrow b \right)\uparrow c

Règles spécifiques à la porte NOR



Voici les propriétés de la porte NOR
  • a \downarrow 1=0
  • a \downarrow 0=\overline{a}
  • a \downarrow a=\overline{a}
  • a \downarrow \overline{a}=0

Il n'y a PAS non plus d'associativité avec les portes NOR : a \downarrow \left(b \downarrow c \right) \neq \left(a \downarrow b \right)\downarrow c
Retour en haut

Exercices

Bon voilà, ça fait beaucoup de connaissances à ingurgiter d'un coup ^^ . Il va falloir s'entrainer un peu pour vérifier que tout est bien acquis :-° .

Exercice 1



Bon on va commencer doucement :D . Munissez vous d'un papier, d'un crayon et surtout de patience, car ce n'est pas forcement évident au début ;) .

Simplifier : a \cdot \left(a + b\right)

Solution (cherchez d'abord ! :p )
Secret (cliquez pour afficher)

\begin{align*}a \cdot \left(a+b\right) &=a \cdot a+a \cdot b & \text{(R\`{e}gle 7)} \\& = a+a \cdot b & \text{(R\`{e}gle 2)} \\& = a & \text{(Voir la d\'{e}monstration de la r\`{e}gle compl\'{e}mentaire)}\end{align*}


Facile non ?
Bon, donc on peut compliquer un peu :p

Exercice 2



Légèrement plus difficile :

Simplifier : a+\overline{a}.b+\overline{a}.\overline{b}

Solution :
Secret (cliquez pour afficher)

Pour cette équation (comme souvent), il y a plusieurs façon de procéder. Je vais en donner 3 cette fois ci mais à l'avenir je n'en donnerai qu'une : pas d'inquiétude donc si ce n'est pas la votre, c'est le résultat qui compte ;)

Solution 1 :

\begin{align*}a + \overline{a} \cdot b + \overline{a} \cdot \overline{b} &= a + \overline{a} \cdot \left(b + \overline{b}\right) & \text{(R\`{e}gle 7)} \\& = a + \overline{a} \cdot 1 & \text{(R\`{e}gle 6)} \\& = a + \overline{a} & \text{(R\`{e}gle 4)} \\& = 1 & \text{(R\`{e}gle 6)}\end{align*}

Solution 2 :

\begin{align*}a + \overline{a} \cdot b + \overline{a} \cdot \overline{b} &= a + b + \overline{a} \cdot \overline{b} & \text{(R\`{e}gle Compl\'{e}mentaire)} \\& = a + b + \overline{b} & \text{(R\`{e}gle Compl\'{e}mentaire)} \\& = a + 1 & \text{(R\`{e}gle 6)} \\& = 1 & \text{(R\`{e}gle 3)}\end{align*}

Solution 3 :

\begin{align*}a + \overline{a} \cdot b + \overline{a} \cdot \overline{b} &= a + b + \overline{a} \cdot \overline{b} & \text{(R\`{e}gle Compl\'{e}mentaire)} \\& = a + b + \overline{a + b} & \text{(R\`{e}gle 8)} \\& = \left(a + b\right) + \left(\overline{a + b}\right) &\\& = 1\hspace{1 cm} & \text{(R\`{e}gle 6)}\end{align*}

Si vous avez des difficulté à comprendre ces exercices, un petit retour à la partie précédente s'impose ^^

Remarque : Dans l'exemple précédent, on remarque que quelles que soient les états logiques de a et b, l'équation proposée vaut toujours 1. On parle alors de tautologie


Exercice 3



Plus difficile :

Simplifier : a + b \cdot \overline{c} + \overline{a} \cdot (\overline{b \cdot \overline{c}}) \cdot (a \cdot d + b), puis transformer l'expression obtenue de manière à n'utiliser que l'opérateur NAND

Secret (cliquez pour afficher)

\begin{align*}a + b \cdot \overline{c} + \overline{a} \cdot \left(\overline{b \cdot \overline{c}}\right) \cdot \left(a \cdot d + b\right) &= a + b \cdot \overline{c} + \overline{a} \cdot \left(\overline{b} + c\right) \cdot \left(a \cdot d + b\right) & \text{(R\`{e}gle 8)} \\& = a + b \cdot \overline{c} + \left(\overline{a} \cdot \overline{b} + \overline{a} \cdot c\right) \cdot \left(a \cdot d + b\right) & \text{(R\`{e}gle 7)} \\& = a + b \cdot \overline{c} + \overline{a} \cdot \overline{b} \cdot a \cdot d + \overline{a} \cdot \overline{b} \cdot b + \overline{a} \cdot c \cdot a \cdot d + \overline{a} \cdot c \cdot b) & \text{(R\`{e}gle 7)} \\& = a + b \cdot \overline{c} + 0 \cdot \overline{b} \cdot d + \overline{a} \cdot 0 + 0 \cdot c \cdot d + \overline{a} \cdot c \cdot b) & \text{(R\`{e}gle 6)} \\& = a + b \cdot \overline{c} + 0 + 0 + 0 + \overline{a} \cdot c \cdot b & \text{(R\`{e}gle 3)} \\& = a + b \cdot \overline{c} + \overline{a} \cdot \left(c \cdot b\right) & \text{(R\`{e}gle 4)} \\& = b \cdot \overline{c} + a + \overline{a} \cdot \left(c \cdot b\right) & \text{(R\`{e}gle 1)} \\& = b \cdot \overline{c} + a + \left(c \cdot b\right) & \text{(R\`{e}gle Compl\'{e}mentaire)} \\& = b \cdot \left(\overline{c} + c\right) + a & \text{(R\`{e}gle 7)} \\& = b \cdot \left(1\right) + a & \text{(R\`{e}gle 6)} \\& = b + a & \text{(R\`{e}gle 3)} \\& = \left(a \uparrow 1\right)\uparrow \left(b \uparrow 1\right) & \text{(Voir porte NAND)} \\& \end{align*}

Ne désespérez pas si vous n'y arrivez pas du premier coup, car l'algèbre de Boole, malgré ses ressemblances, est assez différent de l'algèbre classique.

Exercice 4



Exercice sur le théorème de De Morgan :

Simplifier : \overline{\overline{a} \cdot \overline{\overline{\overline{\overline{b} \cdot \overline{c}} \cdot \overline{b}} \cdot \overline{a}}}, puis transformer l'expression obtenue de manière à n'utiliser que l'opérateur NAND

Indice :
Secret (cliquez pour afficher)
Simplifiez les barres de haut en bas


Solution
Secret (cliquez pour afficher)

\begin{align*}\overline{\overline{a} \cdot \overline{\overline{\overline{\overline{b} \cdot \overline{c}} \cdot \overline{b}} \cdot \overline{a}}} &= a + \overline{\overline{\overline{b} \cdot \overline{c}} \cdot \overline{b}} \cdot \overline{a} & \text{(R\`{e}gle 8)} \\& = a + \left(\overline{b} \cdot \overline{c}+b\right) \cdot \overline{a} & \text{(R\`{e}gle 8)} \\& = a + \left(\overline{c}+b\right) \cdot \overline{a} & \text{(R\`{e}gle Compl\'{e}mentaire)} \\& = a + \left(\overline{c}+b\right) & \text{(R\`{e}gle Compl\'{e}mentaire)} \\& = a + \overline{c}+b \\& = \left(a \uparrow 1\right)\uparrow \left(b \uparrow 1\right)\uparrow c & \text{(Voir porte NAND)} &\end{align*}
Retour en haut

La table de vérité

Nous avons déjà abordé les tables de vérité dans la 2ème partie, sans trop s'y attarder, chose que nous allons faire à présent.
Une table de vérité permet de connaitre l'état logique S de l'équation, en fonction des états des variables.
La table de vérité la plus simple est la suivante :

a S
0 0
1 1


Ici on voit que quand la variable a vaut 1 S vaut 1 et quand a vaut 0, S vaut 0.

Pour remplir, une table de vérité, plusieurs étapes sont à respecter :
  1. Placer en haut de chaque colonne le nom de toutes les variables logiques et dans la dernière le nom de la variable résultat (généralement S)
  2. Placer dans les colonnes sous les noms de variables TOUTES les combinaisons des variables dont on connait le résultat logique (il ne doit pas y avoir 2 fois la même combinaison)

Exemple :

On veut faire la table de vérité d'une équation S inconnue a 2 variables logique, que l'on nomme ici a et b.

On commence à remplir le tableau

a b S

Admettons maintenant qu'on connaisse S quel que soit l'état de a et de b. On rempli donc le tableau avec toutes les combinaisons de a et de b possibles :

a b S
0 0 ?
0 1 ?
1 0 ?
1 1 ?

Maintenant on remplit avec les valeurs de S que l'on connait (je vous les donne) :

a b S
0 0 1
0 1 0
1 0 0
1 1 1


Euh, c'est bien beau tout ça mais à quoi ça sert ?? o_O


Minute papillon, j'y viens ^^
Grâce à cette table de vérité, on va pouvoir retrouver l'équation logique reliant a et b !

1ère méthode : la forme normale disjonctive (DNF)



Il va s'agir d'écrire l'équation sous la forme d'une somme de produits. Pour cela, il faut repérer dans la table de vérité toutes les combinaisons pour lesquelles S vaut 1.
On les surligne :
a b S
0 0 1
0 1 0
1 0 0
1 1 1

On a 2 lignes surlignées : on aura donc une somme de 2 produits.
On écrit ces produits en fonction de la combinaison des variables : si une variable vaut 0 alors on écrit :\overline{nom\hspace{0.25 cm}de\hspace{0.25 cm}la\hspace{0.25 cm}variable}, sinon on écrit simplement le nom de la variable.

Dans notre cas, on obtient donc :
  • 1ère ligne
    • a vaut 0 donc on écrit \bar{a}
    • b vaut 0 donc on écrit \bar{b}
  • 4ème ligne
    • a vaut 1 donc on écrit a
    • b vaut 1 donc on écrit b

En français, pour que S soit égal à 1, il faut que a=0 ET b=0, OU que a=1 ET b=1
On traduit donc par l'égalité suivante :
\bar{a}.\bar{b}+a.b
On a bien une somme de 2 produits.
On appelle parfois les produits issus d'une seule case de la table de vérité des mintermes. Il est possible de démontrer que la DNF (non simplifiée) est unique à l'ordre des termes près.

2ème méthode : la forme normale conjonctive



On veut cette fois obtenir un produit de sommes. Il faut pour cela repérer toutes les combinaisons pour lesquelles S vaut 0 :
On les surligne dans le tableau :
a b S
0 0 1
0 1 0
1 0 0
1 1 1

On a 2 lignes surlignées : on aura donc un produit de 2 sommes.
On écrit ces somme en fonction de la combinaison des variables : si une variable vaut 0 alors on écrit :\overline{nom\hspace{0.25 cm}de\hspace{0.25 cm}la\hspace{0.25 cm}variable}, sinon on écrit simplement le nom de la variable.

Dans notre cas, on obtient donc :
  • 2ème ligne
    • a vaut 0 donc on écrit \bar{a}
    • b vaut 1 donc on écrit b
  • 3ème ligne
    • a vaut 1 donc on écrit a
    • b vaut 1 donc on écrit \bar{b}

En français, pour que S soit égal à 1, il ne faut PAS que a=0 ET b=1, OU que a=1 ET b=0
On traduit donc par l'égalité suivante :
\overline{\overline{a}.b+a.\overline{b}}
La grande barre symbolise le "PAS". en effet, on ne veut que les cas ou S vaut 1
On simplifie ensuite en utilisant le théorème de De Morgan :
\overline{\overline{a}.b+a.\overline{b}}=\overline{(\overline{a}.b)}.\overline{(a.\overline{b})}
=(a+\overline{b}).(\overline{a}+b)
On a bien un produit de 2 sommes.
On peut vérifier que cette égalité est équivalente à la précédente :
On distribue :
\hspace{56 cm}=a.\bar{a}+a.b+\bar{b}.\bar{a}+\bar{b}.b
On simplifie ce qui doit l'être :
\hspace{56 cm}=a.\bar{b}+b.\bar{a}
Et on retrouve bien l'égalité du 1)

Les formes normales, du fait de leur unicité, permettent de vérifier très rapidement l'égalité deux deux équations booléennes. En revanche, elles sont en générales très lourdes à manier puisque faisant intervenir tous les termes : il convient donc de les simplifier pour pouvoir les exploiter.
On se rend en revanche assez vite compte qu'une simplification à l'aide des règles usuelles est très fastidieuse, et source de nombreuses erreurs. C'est pourquoi nous allons maintenant étudier un outil puissant pour simplifier les tables de vérités complexes : le tableau de Karnaugh.
Retour en haut

Le tableau de Karnaugh

Le tableau de Karnaugh est un outil qui permet de simplifier des équations booléennes, avec moins de chances de se tromper qu'en utilisant les règles de l'algèbre de Boole classique. On peut l'utiliser avec au maximum 5-6 variables, au-delà il devient rapidement inefficace.

Créer et remplir un tableau de Karnaugh


A partir d'une table de vérité


Prenons la table de vérité suivante :
a b c d S
0 0 0 0 0
0 0 0 1 1
0 0 1 0 0
0 0 1 1 1
0 1 0 0 1
0 1 0 1 0
0 1 1 0 0
0 1 1 1 1
1 0 0 0 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 0
1 1 1 0 0
1 1 1 1 1

Avec 4 variables, on a 2⁴=16 combinaisons. On va donc créer un tableau de 4 colonnes et 4 lignes (4*4=16), pour ainsi avoir toutes les combinaisons :
Image utilisateur

C'est un peu comme une bataille navale, sauf que chaque case a 4 indices : l'état des 4 variables. Les cases 'AB' et 'CD' indiquent l'ordre des variables sur la ligne ou colonne associée : par exemple, sur la ligne 1, on voit la case 'AB', ce qui implique que '00' signifie A=0 et B=0 ou encore \overline{a} et \overline{b}
ATTENTION : c'est très important que d'une case consécutive à l'autre, une seule variable change d'état ! Sans cela, tous ce que vous pourrez entreprendre par la suite sera tout bonnement faux. Ce tableau donnera par exemple des résultats faux :


Image utilisateur

En effet, pour passer de la case C0 à la case C1, les A et B changent toutes deux d'état : A passe de 0 à 1, et B de 1 à 0.

Ces mises en gardes terminées, on peut maintenant remplir le tableau en fonction de notre table de vérité : on commence par la première ligne de la, qui est, je vous le rappelle :
a b c d S
0 0 0 0 0

On va dans le tableau, et on cherche la case d'indice a=0, b=0,c=0 et d=0, c'est à dire la première case, et on y inscrit la valeur de S donnée par la table de vérité (ici 0) :
Image utilisateur

On continue avec la 2ème ligne de la table :
a b c d S
0 0 0 1 1

Ce qui donne :
Image utilisateur

Et ainsi de suite pour toutes les autres cases. On obtient donc :
Image utilisateur

A partir d'une équation booléenne


On peut également remplir un tableau directement à l'aide d'une équation booléenne. Cela permet par exemple de la simplifier plus qu'avec les règles de l'algèbre.
Pour cela il faut avoir une équation sous la forme d'une somme de produit.
Exemple : \overline{a}.b.\overline{c}.\overline{d}+a.\overline{b}.c+a.c+b.d+a.b
On isole le premier produit et on identifie les variables :
\usepackage{color}\definecolor{vert}{cmyk}{0.5,0,0.5,0.5}\definecolor{jaune}{cmyk}{0,0.33,0.94,0}\overline{\textcolor{vert}{a}}.\textcolor{red}{b}.\overline{\textcolor{blue}{c}}.\overline{\textcolor{jaune}{d}}
On va donc chercher la case du tableau qui vérifie ces conditions : \usepackage{color}\definecolor{vert}{cmyk}{0.5,0,0.5,0.5}\definecolor{jaune}{cmyk}{0,0.33,0.94,0}\textcolor{vert}{a=0}\hspace{0.2 cm}\textcolor{red}{b=1}\hspace{0.2 cm}\textcolor{blue}{c=0}\hspace{0.2 cm}\textcolor{jaune}{d=0}, c'est à dire un cas où l'équation est vraie, et on ajoute un 1 dans la case
Image utilisateur

On passe au deuxième produit :
\usepackage{color}\definecolor{vert}{cmyk}{0.5,0,0.5,0.5}\definecolor{jaune}{cmyk}{0,0.33,0.94,0}\textcolor{vert}{a}.\overline{\textcolor{red}{b}}.\textcolor{blue}{c}
On voit que dans ce produit la variable d n'apparait pas. Cela signifie que l'équation est vraie si :\usepackage{color}\definecolor{vert}{cmyk}{0.5,0,0.5,0.5}\definecolor{jaune}{cmyk}{0,0.33,0.94,0}\textcolor{vert}{a=1}\hspace{0.2 cm}{\textcolor{red}{b=0}\hspace{0.2 cm}\textcolor{blue}{c=1}\hspace{0.2 cm}et\hspace{0.2 cm}\textcolor{jaune}{d=0}\hspace{0.2 cm}OU\hspace{0.2 cm}\textcolor{jaune}{d=1}
Image utilisateur

On procède de même pour les trois autres produits, où il y a à chaque fois deux variables indéterminées, ce qui signifie qu'on rempli 4 cases pour chaque produit. On obtient finalement :
Image utilisateur


Remarque : il est fort probable que plusieurs produits conduisent à remplir la même case, c'est tout à fait normal :)

Retrouver l'équation booléenne simplifiée


Réaliser les groupements


Il s'agit maintenant de réaliser des "groupements" de 1 : on va entourer des groupes de 1 dans le tableau en respectant quelques règles :
  • Les groupements peuvent utiliser plusieurs fois le même 1
  • Ils ne doivent pas contenir de 0
  • Tous les 1 doivent être contenus dans un groupement
  • Ils doivent être les plus grands possible
  • Ils doivent être rectangulaire (ou carré)
  • Leur dimensions doivent être des puissances entières de 2 (2⁰=1, 2¹=2, 2²=4, etc) Exemples : un carré de 2 par 2 ou un rectangle de 1 par 4
  • On imagine que les lignes et colonnes sont bouclées : on peut utiliser par exemple un 1 de la première colonne avec un de la dernière colonne

Reprenons le tableau rempli précédemment avec la table de vérité. On commence par le groupement le plus évident, le rectangle de 4 par 1 :
Image utilisateur

Ensuite vient le groupement de 2 par 1 du haut :
Image utilisateur

On peut se servir du fait que les lignes sont bouclées et qu'on peut réutiliser plusieurs fois le même 1 pour faire un groupement de 2 par 2 :
Image utilisateur

Il ne reste plus qu'un seul 1 que l'on place dans un groupement le plus grand possible, 2 par 1 (le groupement de 3 par 1 ne serait pas possible car 3 n'est pas une puissance entière de 2) :
Image utilisateur

Déduire l'équation simplifiée


Maintenant on va déduire chaque groupement réalisé une partie de l'équation finale.
Pour cela, on va repérer pour chaque groupement les variables qui ne varient pas, et ce quelle que soit la case du groupement. Cela peut paraître compliqué dit comme ça, mais vous verrez qu'avec un ou deux exemples, ça sera très facile ;)
On va s'occuper en premier de notre groupement vert. On étudie chaque variable l'une après l'autre :

Commençons par la variable A :
Image utilisateur

On s'aperçoit que pour les cases du groupement vert, la variable A n'est pas constante : elle prend comme valeur 0 et 1. On ne tiendra donc pas compte de cette variable.

Voyons maintenant la variable B :
Image utilisateur

Pour les deux cases du groupement, la variable B est constante : B=1. Cela signifie que pour que ce groupement soit vrai, il faut que B le soit aussi. On peut donc écrire provisoirement que : groupementVert=B

Pour la variable C :
Image utilisateur

C'est la même chose que pour la variable B, sauf que C est tout le temps égale à 0. Cela signifie que pour que ce groupement soit vrai, il faut en plus que C soit faux (\overline{C}) . On rajoute cette information à notre équation temporaire : groupementVert=B.\overline{C}

La variable D se comporte exactement comme la variable C. On obtient donc groupementVert=B.\overline{C}.\overline{D}
On procède exactement pour le groupent bleu : groupementBleu=A.\overline{B}.C
Pour les groupements jaune et rouge, c'est encore similaire, à la nuance que les groupements sont plus grands, donc il y a une variable de moins qui ne varie pas (d'où l'intérêt de faire les groupements les plus grands possibles). Essayer de les retrouver par vous même pour vous entrainer.

Secret (cliquez pour afficher)
groupementRouge=C.D
groupementJaune=\overline{B}.D


Bon et que fait-on avec tout ça ? Et bien on retrouve l'équation pardi !
On a trouvé les équations des groupements, c'est à dire les conditions au niveau des variables pour appartenir à un groupement. Comme les groupements regroupent toutes les combinaisons qui donnent un résultat vrai, il suffit qu'une combinaison vérifie l'équation d'un des groupement pour qu'on soit sûrs que la sortie soit vraie. A l'inverse, on peut être sûrs que la sortie sera fausse. D'où l'équation finale :
S=groupementJaune+groupementRouge+groupementBleu+groupementVert
ce qui signifie que S=B.\overline{C}.\overline{D}+A.\overline{B}.C+C.D+\overline{B}.D

Et voilà ! Vous avez trouvé l'équation la plus simple possible de la table de vérité du début !
Essayer de simplifier avec les règles de l'algèbre de Boole, vous parviendrez tout au plus à factoriser mais en aucun cas à simplifier.

Exercice



Pour vous entrainer, vous pouvez essayer de retrouver l'équation du tableau de Karnaugh qu'on a rempli avec une équation. Le voici pour mémoire :
Image utilisateur


Vous devez obtenir :
Secret (cliquez pour afficher)
S=A.C+B.\overline{C}+B.D
Retour en haut
Voilà, vous en savez assez pour vous débrouiller comme des grands avec l'algèbre de Boole ^^
Je tiens à remercier particulièrement Talus pour son soutien et son travail de correction.

Pour ceux qui veulent s'entrainer ou qui sont intéressés, un solveur de l'algèbre de Boole est disponible ici. Attention, ce logiciel est encore en phase de test, il se peut donc qu'il reste quelques erreurs dans les équations retournées.


Bon courage ;)
Retour en haut

Partager

Retour en haut

Lire aussi

Icône
TP : convertisseur de bases
Icône
Les conditions I
Icône
Langage machine et Assembleur
Icône
Un ordinateur, c'est très bête : ça ne sait pas compter jusqu'à deux !
Retour en haut
54 commentaires pour "L'algèbre de Boole"
Note moyenne : 3.04 / 4 (54 votes)
Pseudo Commentaire
Hors ligne bidibam # Posté le 02/08/2011 à 14:45:39
jupiter-7 juillet 2010
Avatar

 Bon tuto
il me semble (mais je peux me tromper) qu'il y a une erreur dans l'exercice 2, la 2ème solution :
tu dis que a+b+ !a.!b = a + b + !b
ça ne serait pas plutôt = a + b + !a
ceci dit ça ne change pas le résultat puisque a+b+!a = b+1 = 1
bonne continuation ;)
"Les choses sont ce qu'on pense d'elles"
 
Hors ligne Yoofz0ra # Posté le 03/09/2011 à 10:50:37
Avatar

 Tres bon tuto, j'ai examen de ca et ca m'a bien aider, surtout pour les tableaux de Karnaugh c'etait si mal expliquer dans mon livre...
Let the game Begin!

 
Hors ligne ghyosri # Posté le 19/09/2011 à 19:03:34

Avis : Très bon

Très bon tutoriel, Merci
Hors ligne handek # Posté le 02/02/2012 à 22:54:57
Avatar

 Je viens de me rendre compte qu'en vingt minutes de lectures, j'ai mieux compris qu'en deux mois de cours sur l'algebre de boole! Merci !
Image utilisateur
 
Hors ligne @lgorythme # Posté le 03/04/2012 à 20:59:09
Maths, algorithmie et C++ !
Avatar

Avis : Très bon

Merci !

C'est un excellent tutoriel qui m'a sauvé la vie pour résoudre l'un de problèmes d’entrainement de France IOI !

Bravo à toi !
Algorithmie :
France IOI : niveau 3
Prologin, SPOJ, Projet Euler
Programmation :
C++, C++, C++, et C++ !
 

Voir tous les commentaires