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 ou
¬
x
vérifiant les principes
a) du
tiers
exclu : x +
x
= 1 b) de
contradiction
x *
x
= 0.
On notera (E,+,*,0,1) ou simplement (E,+,*) s'il n'y a pas d'ambiguïté, une telle algèbre de Boole. Comme s'en doute certainement le lecteur, notons déjà ici que le complémenté du complémenté de x est x lui-même : ¬ (¬ x) = x » formules de Morgan.
Un exemple élémentaire est le suivant : Soit E un ensemble non vide. On vérifiera facilement que l'ensemble P(E) des parties de E est une algèbre de Boole, la réunion (∪) 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. On peut noter (P(E),∪,∩,Ø,E) cette algèbre.
Théorème d'idempotence des lois :
Dans une algèbre de Boole (E,+,*), 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, en utilisant les propriétés 3a et 3b du complémenté : 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 : développer et utiliser 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é). Elle correspond à 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 de ces égalités que ¬ (¬
x) = x pour tout x (¬ x = 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 bien 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 (P(E),∪,∩) des parties d'un ensemble fini E.
» Marshall Harvey Stone La logique d'Aristote : »
| 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'ordre ‹ coïncide avec l'inclusion dans l'algèbre de Boole (P(E),∪,∩,Ø,E) évoquée 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 x∧y.
On a en effet :
x∧y
‹
x et x∧y
‹
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 ‹ 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
Tout couple (x,y) de (E,+,*,0,1,‹)
admet une borne supérieure, à savoir x*y + x + y, notée x∨y.
On a en effet :
x
‹
x∨y et y
‹
x∨y.
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 :
Les lois ∧ et ∨ sont commutatives
Pour tout x de (E,+,*,0,1,‹) : 0∧x = 0, 1∧x = 1, 0∨x = x, 1∨x = 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 (x∈F
⇒
x∈F).
Pour la stabilité par rapport à une seconde loi, utiliser les lois de
de Morgan
Algèbre de Lindenbaum : »
| 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 : »
➔ Pour en savoir plus :
Weierstrass