ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Les algèbres et anneaux de Boole          
    
Anneau de Boole , Algèbre de Boole et structure d'anneau

Un ensemble E possède une structure d'algèbre de Boole s'il est muni de deux lois de composition interne associatives et commutatives notées + (addition booléenne) et * (multiplication booléenne) :

  1. Les lois + et * sont distributives l'une par rapport à l'autre :
    Pour tous x, y et z de E : x + (y*z) = (x + y) * (x + z)  et  x * (y + z) = x*y + x * z

  2. Les lois + et * admettent un élément neutre notés respectivement 0 et 1 avec 0 1.

  3. Tout élément x de E possède un unique élément, dit complémenté de x, souvent noté x, vérifiant les principes du tiers exclu : x + x = 1 et de contradiction x * x = 0.

On notera (E,+,*,0,1) une telle algèbre de Boole. Comme s'en doute certainement le lecteur, notons déjà ici que le complémenté de x , soit , est x lui-même : formules de Morgan.

  Pour plus de généralité, on peut remplacer la relation d'égalité par une relation d'équivalence. La maintenance du signe d'égalité dans les écritures s'interprète alors comme une égalité entre classes d'équivalences.

Théorème d'idempotence des lois :    

Dans une algèbre de Boole, tout élément est idempotent pour chaque loi : x + x = x et x * x = x

Preuve : on a x + x = (x + x)*1 = (x + x)*(x + x) = x + x*x  par distributivité de + sur *. Donc x + x = x + 0 = x. D'autre part x*x =x*x + 0 = x*x + x*x = x*(x +x ) = x*1 = x.

Propriétés des éléments neutres :   

a/ Vu l'axiome 3, on a 0 + 0 = 1 et 0 étant neutre pour l'addition booléenne, on déduit 0 = 1. Vu x * x = 0, on déduit 1 = 0.

b/ 1 est absorbant pour l'addition : pour tout x de E, 1 + x = x.
    En effet, 1 + x = (x + x) + x = (x + x) + x = x + x = 1

c/ 0 est absorbant pour la multiplication : pour tout x de E, 0 * x = 0.
    En effet, 0 * x = (x * x) * x =(x * x)*x = x*x = 0.

Opération, loi de composition, généralités, propriétés :

  Dans tous les calculs qui vont suivre, on adoptera la convention pratique habituelle évitant des parenthèses inutiles en considérant la multiplication prioritaire sur la l'addition.

Au sens des structures algébriques, une algèbre de Boole n'en est pas une : ce n'est pas un espace vectoriel ! Par algèbre, il faut entendre des règles calculatoires rappelant les calculs de l'algèbre usuelle. Mais cette algèbre est très particulière. Elle vérifie des propriétés que l'on vérifiera facilement comme :

Théorème (ou règle) d'absorption :    

Pour tous x et y on a : x + x*y = x, règle d'absorption du produit par l'addition et, inversement :
x*(x + y) = x, règle d'absorption de la somme par le produit, dite formule duale.

Preuve : concernant la 1ère règle : x + x*y = x*1 + x*y = x*(1 + y) = x*1 = x. Concernant la seconde : x*(x + y) = x*x + x*y = x + x*y = x d'après la 1ère règle.

Théorème (ou règle) de simplification :    

Pour tous x et y on a : x + x*y = x + y et la règle duale: x * (x + y) = x * y

Les schémas électriques associés à ces lois peuvent être ainsi décrits :

Interprétation électrique de la logique booléenne (site externe) :

La plus petite algèbre de Boole concevable contient deux éléments 0 (élément nul) et 1 (élément unité). C'est l'algèbre des circuits : le courant passe 1, ne passe pas 0. On obtient les tables d'addition et de multiplication :

   0 + 0 = 0, 0 + 1 = 1 + 0 = 1 et 1 + 1 = 1 (idempotence de +)
   0 * 1 = 1 * 0 = 0 * 0 = 0 et 1 * 1 = 1

et on vérifiera facilement que ces opérations définissent une algèbre de Boole sur {0,1}.

  Dans une algèbre de Boole, on a les propriétés, dites lois (ou formules) de de Morgan :

x * y = x + y   et   x + y = x * y


Vérifier ces égalités en effectuant respectivement les produits  x * y * (x + y )  et  (x + y) * x * y.
Déduire de l'une ou l'autre ces égalités que = x pour tout x.

En termes de propositions, avec x associé à P et y associé à Q, c'est dire : non (P et Q) = (nonP) ou (nonQ) et non (P ou Q) = (nonP) et (nonQ) : un modèle de cette algèbre est en effet la logique propositionnelle classique. L'implication P Q, équivalente à nonP ou Q, peut s'écrire : x + y.


Vérifier que l'équivalence logique (P Q) et (Q P) est alors écrite : x*y +  x * y dont la valeur n'est que si x = y = 1 ou  x = y = 1 
(P et Q toutes deux fausses ou P et Q toutes deux vraies).

Un théorème de M. H. Stone :   

Toute algèbre de Boole finie est isomorphe à l'algèbre ((E),,) des parties d'un ensemble fini E.

  Marshall Harvey Stone            La logique d'Aristote :

Anneau de Boole :

Au moyen de ses opérations, une algèbre de Boole peut être très simplement munie d'une structure d'anneau commutatif : la multiplication * est conservée et l'addition du groupe abélien sous-jacent sera définie par

x y = (x * y) + (x * y)

L'égalité x * x = x pour tout x peut s'écrire x*(x - 1) = 0. Si un anneau de Boole est intègre, alors x = 0 ou x = 1. On en déduit que le seul anneau de Boole intègre est réduit à {0,1} et donc isomorphe au corps Z/2Z des entiers modulo 2.

Noter que x x = (x * x) + (x * x) = 0 + 0 = 0 : tout élément est son propre opposé. On se reportera à l'exemple fondamental ci-après de l'anneau  (E,,,0,1) construit au moyen de l'ordre usuel des algèbres de Boole. Voir aussi :

Compléments sur les anneaux de Boole :

Ordre sur une algèbre de Boole :

Toute algèbre de Boole (E,+,*,0,1) peut être munie d'une structure d'ensemble ordonné au moyen de la relation notée ici définie par :

x y   si et seulement si   x * y = x

Il s'agit plus précisément d'une structure de treillis distributif complémenté, dit treillis de Boole.

Quelques propriétés importantes de cet ordre :   

Preuve : m = x*y minore x car, par associativité et commutativité (x*y)*x = x*(y*x) = x*(x*y) = (x*x)*y = x*y vu que * est idempotente. On a donc m*x = m, soit m x. Un calcul analogue conduira à  m y. Maintenant m doit être le plus grand des minorants : si m' est un minorant commun à x et y, a-t-on m' m ? On a m'*x = m' et m'*y = m'. Or m*m' = (x*y)*m' = m'*(x*y) = (m'*x)*y = m'*y = m'. CQFD

Preuve : M = x*y + x + y majore x car par distributivité et associativité, on peut écrire x*(x*y + x + y) = (x*x)*y + x*x + x*y = x*y + x + x*y = (x*y + x*y) + x = x*y + x = x (absorption), donc x M. Un calcul analogue conduira à  y M. Maintenant M doit être le plus petit des majorants : si M' est un majorant commun à x et y, a-t-on M M' ? On a M'*x = x*M' = x et M'*y = y*M' = y. Or M*M' = (x*y + x + y)*M' = x*y*M' + x*M' + y*M' = xy + x + y = M (on peut omettre les parenthèses vu l'associativité des lois). CQFD

En outre :


1°/ Vérifier que muni des les lois et définies ci-dessus, (E,,,0,1) est une algèbre de Boole.
2°/ En posant x y = (x y ) (x y) et x y = x y conformément à la règle habituelle énoncée ci-dessus,
vérifier que (E, ,,0,1) possède la structure d'anneau commutatif unitaire.
On pourra utiliser un résultat général énoncé ici en complément.

Loi de composition, élément neutre, élément absorbant, distributivité, ... :

Sous-algèbre de Boole :    

Soit F un sous-ensemble d'une algèbre de Boole (E,+,*,0,1), contenant 0 et 1 et stable pour les lois + et * de E. Alors F est une algèbre, sous-algèbre de E.     ensemble stable pour une loi


Avec les notations ci-dessus, vérifier que F est une sous-algèbre de Boole de E si et seulement si :
0F , F est stable pour la loi + (ou bien *) et par complémentation (xF xF).
Pour la stabilité par rapport à une seconde loi, utiliser les lois de de Morgan

Algèbre de Lindenbaum :

Pour en savoir plus :


Ada Byron   Weierstrass
© Serge Mehl - www.chronomath.com