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) :
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
Les lois + et * admettent un élément neutre notés
respectivement 0 et 1 avec 0
1.
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.
Un exemple élémentaire est le
suivant :
Soit E un ensemble non vide. On vérifiera facilement que l'ensemble
(E) des
parties de E est une algèbre de Boole,
la réunion (
)
jouant le rôle de l'addition et l'intersection (
)
le rôle de la multiplication. L'élément nul est l'ensemble vide, l'élément
unité est E et le complémenté A
d'une partie A est sa partie complémentaire dans E.
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.
C'est dire, par exemple, que x*y + z = (x*y) + z ou encore x*y + x*z = (x*y) + (x*z) et surtout pas x*(y + x)*z qui pourrait alors s'écrire par distributivité : (x*y + x*x)*z = (x*y + 0)*z = x*y*z !!!
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 +)
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).
La logique d'Aristote :
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.
| 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.
Eu égard à l'idempotence de la loi *, la relation est manifestement réflexive. Elle est antisymétrique car * étant commutative x = x * y = y * x = y. Elle est transitive : prouvez-le en usant deux fois de l'associativité de la loi *.
Vérifier que l'inclusion coïncide avec l'ordre
pour l'algèbre de Boole ((E),,,
,E)
dont il est fait état en début de page.
Quelques propriétés importantes de cet ordre :
0 et 1 sont respectivement les plus
"petit" et plus "grand" éléments de E pour la relation d'ordre
.
Tout couple (x,y) de (E,+,*,0,1,)
admet une borne inférieure, à savoir x*y, notée xy.
On a en effet :
xy
x et xy
y.
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
Tout couple (x,y) de (E,+,*,0,1,)
admet une borne supérieure, à savoir x*y + x + y, notée xy.
On a en effet :
x
xy et y
xy.
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
En outre :
Les lois
et
sont commutatives
Pour tout x de (E,+,*,0,1,)
:
0x = 0, 1x
= 1, 0x =
x, 1x = 1.
Les lois
et
sont associatives et distributives l'une par rapport à l'autre.
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 :
0
F , 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 :
A brief history of the notation of Booles's
algebra (en anglais) :
http://www.hf.uio.no/ifikk/filosofi/njpl/vol2no1/history/history.pdf
par Michael Schröder de l'université de Hanovre.
Weierstrass
