Accueil |

Algèbre de Boole

         

En mathématiques ou en informatique, les algèbres de Boole ou les treillis booléens sont des structures algébriques qui décrivent les fonctions logiques comme la conjonction (et), la disjonction (ou) et la négation; de même que les opérations sur les ensembles comme l'inclusion, l'intersection ou le complément d'un ensemble.

Le nom provient de George Boole, un mathématicien britannique qui durant le milieu du XIXe siècle restructura complètement la logique en un système formel. Plus spécifiquement, l'algèbre booléenne permet d'utiliser des techniques algébriques pour traiter les expressions à  deux valeurs de la logique des propositions. Aujourd'hui, l'algèbre de Boole trouve de nombreuses applications en informatique et dans la conception des circuits électroniques. Elle fut utilisée la première fois pour les circuits de commutation téléphoniques par Claude Shannon.

L'algèbre de Boole permet de modéliser des raisonnements logiques, en exprimant un "état" en fonction de conditions. Par exemple :

Vert = Bleu ET Jaune
Vert est "VRAI" SI il ya du bleu ET du jaune
Décrocher = ( Envie de répondre ET Sonnerie ) OU envie_d'appeler
Décrocher est "VRAI" SI on entend la sonnerie ET que l'on envie de répondre OU SI l'on a envie d'appeler

Sommaire
1 Définitions
2 Table de vérité
3 Opérateurs Logiques
4 Propriétés des opérateurs
5 Opérateurs composés
6 Voir aussi :

Définitions

Exemple avec un état:
0 = lampe éteinte
1 = lampe allumée

Table de vérité

Une table de vérité est une table permettant de connaître les valeurs de sortie d'un opérateur logique en fonction des valeurs en entrée.

a b valeur de a opérateur b
0 0 x1
0 1 x2
1 0 x3
1 1 x4

Opérateurs Logiques

Il existe trois "opérateurs logiques" élémentaires:

Ils se lisent: Explication de la notation . et + : ATTENTION:

Somme Logique ("OU", notée "+")

Il suffit qu'un des termes soit "VRAI" (=1) pour que l'expression soit "VRAIE" (=1).

Règles:

Table de verité
a b a OU b
0 0 0
0 1 1
1 0 1
1 1 1

Multiplication Logique ("ET", notée ".")

Il faut que les deux termes soient "VRAIS" (=1) pour que l'expression soit "VRAIE" (=1).

Règles :

Table de verité
a b a ET b
0 0 0
0 1 0
1 0 0
1 1 1

Inversion ("NON", notée "¯")

Elle est égale à  l'inverse de ce à  quoi elle s'applique.
Exemple :
a = 0 <-> a| = 1
a ne peut avoir que deux états possibles 1 ou 0, si a = 0 alors a| = 1. La fonction NON remplace le 0 par 1 et le 1 par 0.

Table de verité
a NON a
0 1
1 0

Propriétés des opérateurs

Il s'agit de règles permettant d'aboutir à  autre manière de décrire la situation. Par exemple, il est plus facile de dire que "la lumière doit être allumée" que "la lumière ne doit pas être éteinte".

Priorité

Pour faciliter leur compréhension, il a été décidé que ces opérations seraient soumises aux même règles que les opérations "de tous les jours", la fonction ET (multiplication logique) est ainsi prioritaire par rapport à  la fonction OU (somme logique); on peut, pour s'aider, placer des parenthèses dans les opérations.

Exemple :
{ a = 0 ; b = 1 ; c = 1 }
On cherche a . b + c = ???
D'abord on calcule a . b:
a . b = 0 . 1
0 . 1 = 0
Puis, on calcule 0 + c:
0 + c = c
c = 1
Le résultat final est donc:
a . b + c = 1

Commutativité

Comme avec les opérations habituelles, certaines parenthèses sont inutiles:
( a + b ) + c = a + b + c
( a . b ) . c = a . b . c

Distributivité

Comme avec les opérations habituelles, il est possible de distribuer:
a . ( b + c ) = a . b + a . c
Attention: comportement différent par rapport aux opérateurs + et * habituels:
a + ( b . c ) = ( a + b ) . ( a + c )

Idempotence

a + a + a [...] = a
a . a . a [...] = a

Complémentarité

a|| = a

("La lumière ne doit pas n'être pas allumée" = "la lumière doit être allumée")
a + a| = 1
("VRAI" SI lumière_est_allumée OU SI lumière_n'est_pas_allumée -> toujours le cas -> toujours VRAI)
a . a| = 0
("VRAI" SI lumière_est_allumée ET SI lumière_est_éteinte -> impossible -> toujours FAUX)

Théorème de De Morgan

( a + b )| = a| . b|

Dans les deux cas, l'expression ne sera VRAIE que si a et b sont fausses.
( a . b )| = a| + b|
Dans les deux cas, l'expression ne sera VRAIE que si a ou b sont fausses.

Opérateurs composés

à€ partir de ces opérateurs élémentaires, on peut en composer un certain nombre d'autres :

OU exclusif

Le OU étudié jusqu'à  présent doit se comprendre de la manière suivante : "l'un ou l'autre ou les deux". Il est également appelé "OU inclusif". Le OU exclusif (ou XOR) s'entend comme : "l'un ou l'autre mais pas les deux". Il se compose de la manière suivante :

a XOR b = (a+b).(a.b)|

Table de verité
a b a XOR b
0 0 0
0 1 1
1 0 1
1 1 0

Equivalence

L'équivalence (notée EQV) est vrai si les deux entrées ont la même valeur et faux sinon. Elle se compose comme suit :

a EQV b = (a+b)|+(a.b) On peut aussi dire que : a EQV b = (a XOR b)|

Table de verité
a b a EQV b
0 0 1
0 1 0
1 0 0
1 1 1

Implication

L'implication (notée IMP) s'écrit de la manière suivante :

a IMP b = a+b|

Cette opération n'est pas commutative.

Table de verité
a b a IMP b
0 0 1
0 1 0
1 0 1
1 1 1

Inhibition

L'inhibition (notée INH) se compose comme suit :

a INH b = a.b|

Cette opération n'est pas commutative.

Table de verité
a b a INH b
0 0 0
0 1 0
1 0 1
1 1 0

Voir aussi :

Fonction logique ~ calcul des propositions ~ systèmes de numération ~ électronique numérique