Algèbre de Boole (structure)

En mathématiques, une algèbre de Boole, ou parfois anneau de Boole, est une structure algébrique étudiée en particulier en logique mathématique. Une algèbre de Boole peut être définie soit comme une structure ordonnée particulière, soit comme une structure algébrique particulière, soit comme un anneau (unitaire) dont tout élément égale son carré.

Pour tout ensemble, l'ensemble de ses parties est une algèbre de Boole, l'ordre associé étant l'inclusion et les lois d'anneau la différence symétrique et l'intersection. Un autre exemple est donné par l'ensemble des formules du calcul propositionnel prises à équivalence (en logique classique) près (sur un nombre de variables de cardinal arbitraire), l'ordre associé étant la relation de conséquence logique et les lois d'anneau la disjonction exclusive et la conjonction.

Définitions

Algèbre de Boole comme treillis

Une algèbre de Boole E ^[1] est un treillis avec plus grand et plus petit éléments, dont chacune des deux opérations de borne inférieure et de borne supérieure est distributive par rapport à l'autre, et dont tout élément possède un complément. Autrement dit :

(E, ≤) est un ensemble ordonné ;
Deux éléments a, b de E ont une borne supérieure, notée dans la suite a ∨ b, et une borne inférieure notée dans la suite a ∧ b (c'est-à-dire que c'est un treillis) ;
Il existe un plus petit élément, noté dans la suite 0 (il est souvent noté également $\bot$ ), et un plus grand élément noté dans la suite 1 (il est souvent noté également $\top$ ) ;
L'opération ∧ est distributive sur l'opération ∨, et l'opération ∨ est distributive sur l'opération ∧, c'est-à-dire que pour tous a, b et c de E :

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c),

a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) ;

pour tout élément a de E, il existe un élément a’ de E, appelé complément de E et vérifiant :

a ∧ a’ = 0 et a ∨ a’ = 1.

Ainsi une algèbre de Boole est un treillis distributif, borné (avec plus petit et plus grand élément), et complémenté. Il suffirait de donner une des lois de distributivité, l'une entraînant l'autre dans un treillis (voir l'article lié).

On montre que chaque élément possède un unique complément. En effet si a¹ et a’ sont des compléments de a, en utilisant les propriétés des compléments, de l'ordre, et la distributivité on obtient :

a¹ = (a ∧ a’) ∨ a¹ = (a ∨ a¹) ∧ (a’ ∨ a¹) = a’ ∨ a¹

c'est-à-dire que a’ ≤ a¹. De la même façon a¹ = a’ ∧ a¹, donc a¹ ≤ a’, d'où l'égalité.

Par unicité du complément, l'application qui à a associe son complément est involutive (a’’ = a). Elle échange 0 et 1. Également par unicité du complément et par distributivité on montre que le passage au complément échange ∧ et ∨, ce sont les lois de De Morgan (voir paragraphe suivant).

On déduit des axiomes d'ordres que les opérations ∧ et ∨ sont associatives, commutatives, que 0 est neutre pour ∨ et absorbant pour ∧, que 1 est neutre pour ∧ et absorbant pour ∨, et que ces opérations sont idempotentes.

Algèbre de Boole comme structure algébrique

La structure ordonnée précédente est un treillis, et donc il est possible de la définir de façon algébrique, directement en termes des deux opérations binaires que sont la borne inférieure et la borne supérieure, de l'opération unaire de passage au complément, et des deux constantes 0 et 1. Une algèbre de Boole peut alors être définie comme une structure (E, ∧, ∨, (.)', 0, 1) vérifiant pour tous éléments a, b et c de E ^[2]:

Treillis distributif avec plus petit et plus grand éléments
(a ∧ b) ∧ c = a ∧ (b ∧ c)	et	(a ∨ b) ∨ c = a ∨ (b ∨ c)	(associativité)
a ∧ b = b ∧ a	et	a ∨ b = b ∨ a	(commutativité)
a ∧ a = a	et	a ∨ a = a	(idempotence)
1 ∧ a = a	et	0 ∨ a = a	(élément neutre)
0 ∧ a = 0	et	1 ∨ a = 1	(élément absorbant)
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)	et	a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)	(distributivité)
Complément
a ∧ a’ = 0	et	a ∨ a’ = 1	(complément)
a’’ = a			(involutivité du complément)
(a ∧ b)’ = a’ ∨ b’	et	(a ∨ b)’ = a’ ∧ b’	(lois de De Morgan)

Les lois d'absorption se déduisent de la distributivité par les lois d'éléments neutres, absorbants et la commutativité ( a ∧ (a ∨ b) = (a ∨ 0 ) ∧ (a ∨ b) = a ∨ (0 ∧ b) = a ∨ 0 = a )

a ∧ (a ∨ b) = a

et

a ∨ (a ∧ b) = a

(absorption)

La relation d'ordre peut se définir de deux façons (la réflexivité de l'ordre se déduit de l'idempotence, l'antisymétrie de la commutativité et la transitivité de l'associativité pour l'opération en jeu) :

a ≤ b équivaut à a ∧ b = a

a ≤ b équivaut à a ∨ b = b

Ce système d'axiomes est facile à exploiter pour les démonstrations, mais il est très redondant. Comme on retrouve la définition de treillis en termes de relation d'ordre à partir des axiomes de treillis, l'involutivité du complément, les lois de De Morgan et le fait que 0 et 1 soient absorbants se déduisent des autres axiomes, comme au paragraphe précédent. Une possibilité (parmi d'autres) est de se restreindre aux seuls axiomes d'élément neutre, de complément, de commutativité et de distributivité^[3].

La symétrie du système d'axiomes met en évidence la dualité dans les algèbres de Boole.

Algèbre de Boole comme anneau

De façon équivalente^[4], une algèbre de Boole peut également être définie comme un anneau de Boole, c'est-à-dire un anneau dans lequel tout élément est idempotent. La structure (E, +, •, 0, 1) est donc un anneau de Boole si elle vérifie les identités :

(a+b)+c = a+(b+c)	(associativité +)
a+b = b+a	(commutativité +)
0 + a = a	(élément neutre +)
Tout élément a possède un opposé, noté −a :
(-a)+a = 0	(opposé)
(a•b)•c = a•(b•c)	(associativité •)
1 • a = a	(élément neutre •)
a•(b+c) = a•b+a•c	(distributivité à gauche)
(b+c)•a = b•a+c•a	(distributivité à droite)
a•a = a	(idempotence)

On déduit de l'idempotence du produit, en calculant de deux façons (a + a)² (distributivités) et en simplifiant, que chaque élément est son propre opposé, c'est-à-dire qu'un anneau de Boole est de caractéristique 2 :

a+a = 0

(un élément est son propre opposé)

L'anneau est donc une algèbre sur le corps à deux éléments.

On déduit toujours de l'idempotence, en calculant de deux façons (a + b)², que a•b + b•a = 0, et donc la commutativité de la multiplication, d'après la propriété précédente :

a•b = b•a

(commutativité •)

Les lois d'anneau diffèrent des lois d'algèbre de Boole du paragraphe précédent, en particulier seule la multiplication est distributive sur l'addition.

À partir d'une algèbre de Boole (E, ∧, ∨, 0, 1), on obtient bien un anneau de Boole en posant

a•b = a ∧ b
a + b = (a ∧ b’ ) ∨ (a’ ∧ b)^[5]

les constantes 0 et 1 sont conservées. La vérification des identités d'anneau se fait directement, en utilisant les identités d'algèbre de Boole du paragraphe précédent.

Réciproquement, à partir d'un anneau de Boole (E, +, •, 0, 1), on obtient une algèbre de Boole en posant :

a ∧ b = a•b
a’ = 1 + a
a ∨ b = a + b + a•b

et en vérifiant que les éléments neutres 0 et 1 sont bien les plus petits et plus grands éléments. En particulier dans un anneau de Boole, on retrouve la structure ordonnée par :

a ≤ b si et seulement si a = a•b

Là aussi, les vérifications des identités d'algèbre se font simplement, en utilisant les identités d'anneau de Boole (commutativité et caractéristique 2 comprises).

Dans la suite, on appelle algèbre ou anneau de Boole l'une comme l'autre structure.

Exemples d'algèbres de Boole

Si 0 = 1 l'algèbre de Boole possède un seul élément, elle est dite dégénérée^[6], ou triviale.

L'algèbre de Boole à deux éléments

Une algèbre de Boole non dégénérée a au moins deux éléments distincts 0 et 1, et l'algèbre de Boole la plus simple est l'algèbre à deux éléments. On peut la voir comme l'ensemble des deux valeurs de vérité {Faux, Vrai} de la logique classique. En tant qu'anneau, c'est Z/2Z, et, à cause de l'idempotence de la loi multiplicative, c'est le seul anneau de Boole intègre, donc le seul qui soit un corps.

Article détaillé : algèbre de Boole (logique).

Algèbre de Boole des parties d'un ensemble

Article détaillé : Algèbre des parties d'un ensemble.

L'ensemble des parties de n'importe quel ensemble A, ordonné par inclusion est une algèbre de Boole. La borne inférieure est l'intersection, la borne supérieure la réunion, le complément le passage au complémentaire dans A, l'ensemble vide et A sont les éléments neutres, l'addition la différence symétrique. Quand A est vide, l'algèbre de Boole est dégénérée. Quand A est un singleton, on retrouve l'algèbre de Boole à deux éléments du paragraphe précédent.

Algèbre de Lindenbaum

Article détaillé : Algèbre de Lindenbaum.

L'ensemble des formules du calcul propositionnel quotientés par la relation d'équivalence logique (deux formules propositionnelles sont équivalentes quand elles ont même table de vérité), avec la relation de déduction comme relation d'ordre est (en logique classique) une algèbre de Boole.

Plus généralement, pour n'importe quelle théorie T du calcul des prédicats, l'ensemble des énoncés (formules closes) du langage de cette théorie quotienté par la relation d'équivalence dans T et avec comme relation d'ordre la relation de déduction dans T, est une algèbre de Boole, l'algèbre de Lindenbaum de la théorie T.

La borne inférieure est donnée par la conjonction, la borne supérieure par la disjonction, le complément par la négation. La classe d'équivalence d'une proposition toujours fausse donne le neutre pour la disjonction, et la classe d'équivalence d'une proposition toujours vraie donne le neutre pour la conjonction. L'addition est donnée par la disjonction exclusive.

L'algèbre de Lindenbaum du calcul propositionnel sur une infinité, par exemple dénombrable, de variables est différente de l'ensemble des parties d'un ensemble, car tout élément possède un minorant strict non nul (par conjonction avec une variable propositionnelle non présente dans la formule) ce qui n'est pas le cas des singletons pour l'ensemble des parties d'un ensemble.

Dualité

Étant donné une expression booléenne écrite avec les seules constantes et opérations de treillis algébrique (0, 1, ∧, ∨, ( )'), le dual de cette expression est celle obtenue en échangeant la borne supérieure ∨ et la borne inférieure ∧ d'une part, 0 et 1 d'autre part. Par exemple, voici l'expression de l'addition des anneaux de Boole (différence symétrique) et son expression duale :

le dual de ( a ∧ b' ) ∨ ( a' ∧ b ) est ( a ∨ b' ) ∧ ( a' ∨ b )

Cette définition se généralise aux énoncés, par substitution. Pour la seconde définition comme treillis algébrique, les axiomes d'algèbre de Boole sont présentés par paire, l'un des axiomes étant l'énoncé dual de l'autre. Par conséquent, à tout théorème des algèbres de Boole énoncé dans ce langage correspond un théorème dual : c'est le principe de dualité pour les algèbres de Boole.

Par exemple, les lois d'absorption sont duales l'une de l'autre : il suffit donc d'en démontrer une, et on déduit que l'autre est un théorème par dualité.

La dualité transforme l'ordre en son ordre réciproque : la forme duale de a ≤ b (a ∧ b = a) est a ≥ b (a ∨ b = a).

On vérifie que la duale d'une expression booléenne f(p₁, ... , p_n) est (f(p’₁, ... , p’_n))'.

Sous-algèbres

Une sous-algèbre de Boole est un sous-anneau de l'algèbre de Boole en tant qu'anneau unitaire, c'est-à-dire (dans ce cas particulier) un sous-ensemble stable par addition, multiplication et ayant même élément neutre multiplicatif. On montre que les sous-algèbres de Boole sont les sous-ensembles des algèbres de Boole contenant 0 et 1, stables par borne supérieure, borne inférieure et complémentaire (le fait que la sous-algèbre possède, en tant que sous-anneau, le même neutre multiplicatif est indispensable pour que la stabilité par passage au complément soit assurée). Pour vérifier qu'un sous-ensemble d'une algèbre de Boole est une sous-algèbre, il suffit de vérifier la stabilité par complément, par l'une des deux opérations ∧, ∨ et que 0 ou 1 appartient au sous-ensemble.

Un exemple de sous-algèbre de Boole de l'ensemble des parties d'un ensemble infini est l'ensemble des parties finies et cofinies (c'est-à-dire de complémentaire fini) de ce même ensemble.

Si F est un sous-ensemble strict de E, l'ensemble des parties de F est une algèbre de Boole qui est un sous-ensemble de l'ensemble des parties de E, mais qui n'est pas une sous-algèbre de Boole car les éléments maximaux (E et F) ne sont pas les mêmes, de même que les compléments.

Morphismes

Les morphismes d'algèbres de Boole sont les morphismes d'anneaux (unitaires) usuels pour la structure d'anneau de Boole.

De façon équivalente, ce sont les morphismes de treillis qui passent au complément (il suffit alors de vérifier que soit les bornes supérieures soit les bornes inférieures sont conservées par les lois de De Morgan).

Algèbre de Boole complète

Article détaillé : Algèbre de Boole complète (en).

Tout sous-ensemble fini d'une algèbre de Boole possède une borne supérieure et une borne inférieure.

Une algèbre de Boole est dite complète si c'est un treillis complet, c'est-à-dire si tous ses sous-ensembles (finis ou infinis) ont une borne supérieure et une borne inférieure (en fait l'une des deux hypothèses suffit).

Exemples et contre-exemples :

toute algèbre de Boole finie est évidemment complète ;
l'algèbre de Boole des parties d'un ensemble est complète : toute famille de sous-ensembles possède une borne supérieure, qui est la réunion de ces sous-ensembles, et une borne inférieure, qui est l'intersection de ces sous-ensembles ;
l'algèbre de Boole des parties finies ou cofinies d'un ensemble infini n'est pas complète ;
l'algèbre de Lindenbaum du calcul propositionnel sur une infinité de variables non plus.
Toute algèbre de Boole A est la sous-algèbre d'une algèbre de Boole B complète, telle que tout élément de B soit la borne supérieure d'une partie de A. B s'appelle le complété de A. Il est unique à isomorphisme près.

Atomes

Dans une algèbre de Boole, la notion d'atome est celle qui correspond aux singletons dans l'algèbre de Boole des parties d'un ensemble. Une algèbre de Boole n'a cependant pas nécessairement d'atomes.

Définition

Un atome^[7] d'une algèbre de Boole B est un élément n'ayant d'autre minorant strict que 0 :

a est un atome si et seulement si pour tout élément x de B, 0 ≤ x ≤ a ⇒ (x = 0 ou x = a).

Il est immédiat que les singletons sont des atomes de l'algèbre de Boole des parties d'un ensemble. Celle-ci a de plus la propriété que tout élément non nul est minoré par au moins un atome : une telle algèbre de Boole est dite atomique. Il existe également des algèbres de Boole sans atomes, comme l'algèbre de Lindenbaum du calcul propositionnel sur une infinité de variables.

Algèbres de Boole finies

Toute algèbre de Boole finie est isomorphe à l'ensemble des parties d'un ensemble fini, qui est l'ensemble des atomes de l'algèbre. Son cardinal est donc une puissance de 2.

Idéaux et filtres

Les idéaux d'une algèbre de Boole sont les idéaux de l'algèbre en tant qu'anneau commutatif. La stabilité de l'idéal par multiplication par un élément quelconque de l'algèbre a pour conséquence qu'un idéal est une section initiale de la structure ordonnée. On peut caractériser les idéaux en termes de treillis ; le sous-ensemble I de E est un idéal de l'algèbre de Boole (E, ≤, ∧, ∨, 0, 1) quand il vérifie :

0 ∈ I
∀ x, y ∈ I x ∨ y ∈ I ;
∀ x ∈ I ∀ y∈ E (y ≤ x ⇒ y ∈ I).

Un idéal propre est un idéal différent de l'algèbre tout entière, nécessairement il ne contient pas l'élément maximal 1. Il ne peut donc contenir un élément x et son complément 1 + x.

La notion duale d'idéal propre est celle de filtre : un sous-ensemble de l'algèbre est un filtre si l'ensemble de ses compléments est un idéal. Plus directement le sous-ensemble F de E est un filtre de l'algèbre de Boole (E, ≤, ∧, ∨, 0, 1) quand il vérifie :

1 ∈ F et 0 ∉ F ;
∀ x, y ∈ F x ∧ y ∈ F ;
∀ x ∈ F ∀ y ∈ E (y ≥ x ⇒ y ∈ F).

L'application qui à un élément x associe son complément x' établit une bijection entre les filtres et les idéaux.

Un idéal maximal est un idéal maximal au sens de l'inclusion parmi les idéaux propres. La notion duale est celle d'ultrafiltre : un ultrafiltre est un filtre maximal au sens de l'inclusion, et c'est aussi l'ensemble des compléments d'un idéal maximal.

Le théorème de l'idéal maximal, ou théorème de Krull, énonce que tout idéal est inclus dans un idéal maximal. Dans le cas des algèbres de Boole il donne par dualité le théorème de l'ultrafiltre : tout filtre est inclus dans un ultrafiltre.

Le quotient d'une algèbre de Boole par un idéal maximal est le corps à deux éléments {0, 1}, seul anneau de Boole qui soit un corps, le morphisme canonique associé est donc à valeur dans {0, 1}.

De façon générale, dans une algèbre de Boole donnée, il est équivalent de se donner un idéal maximal, un ultrafiltre ou un morphisme de cette algèbre de Boole dans {0,1}, le noyau d'un tel morphisme étant un idéal maximal, et l'ensemble des éléments de valeur 1 par ce morphisme un ultrafiltre.

Théorème de Stone

Article détaillé : Théorème de représentation de Stone pour les algèbres de Boole.

On a vu qu'une algèbre de Boole finie est isomorphe à l'ensemble des parties d'un ensemble, en l'occurrence celui de ses atomes. Le théorème de représentation de Stone permet de généraliser ce résultat à une algèbre de Boole quelconque, au sens où dans le cas général, une algèbre de Boole est isomorphe à une sous-algèbre de l'ensemble des parties d'un ensemble.

Il est bien nécessaire de considérer des sous-algèbres : l'algèbre de Lindebaum du calcul propositionnel sur une infinité de variables propositionnelles, ou de façon isomorphe, l'algèbre de Boole librement engendrée par une infinité d'éléments, n'est pas atomique (voir ci-dessus), donc ne peut être isomorphe à l'ensemble des parties d'un ensemble.

Suivant une démarche commune en théorie des anneaux, l'ensemble en question peut être choisi comme l'ensemble des idéaux maximaux de l'algèbre de Boole A, ou, dans le cas des algèbres de Boole, comme l'ensemble S(A) des homorphismes de cette algèbre dans {0,1}, appelé espace de Stone de A. On vérifie alors que l'application suivante est un morphisme injectif de A dans l'ensemble 𝒫(S(A)) des parties de l'espace de Stone^[8] :

$\varphi :{\begin{array}{lcl}A&\to &{\mathcal {P}}\left(S(A)\right)\\x&\mapsto &\{h\in S(A)\mid h(x)=1\}\end{array}}$

Lorsqu'on considère S(A) comme une partie de 2^A, ensemble des fonctions de A dans {0,1} muni de la topologie produit, S(A) est un espace de Stone, c'est-à-dire un espace compact totalement discontinu. Il admet pour base d'ouverts ses parties ouvertes-fermées (clopen). L'image du morphisme $\varphi$ est alors exactement l'ensemble des ouverts-fermés de S(A).

Réciproquement, si X est un espace de Stone, alors l'ensemble de ses ouverts-fermés muni des opérations ensemblistes usuelles constitue une algèbre de Boole.

Par cette double correspondance, le théorème de représentation de Stone établit fonctoriellement une équivalence entre la catégorie des algèbres de Boole et celle des espaces de Stone.

Notes et références

↑ Voir Cori et Lascar 1993, p. 96 pour cette caractérisation.
↑ Ce système d'axiomes pour les algèbres de Boole est donné dans Givant et Halmos 2009, p. 10.
↑ d'après Givant et Halmos 2009, p. 10, caractérisation due « essentiellement » à E. V. Huntington (en), dans Sets of independent postulates for the algebra of logic, Transactions of the American Mathematical Society, vol. 5 (1904), p. 288–309 ; Huntington en a donné plusieurs autres.
↑ Définition d'Algèbre de Boole dans Cori et Lascar 1993, p. 91.
↑ Cet usage du signe « + » est en contradiction avec une certaine tradition de présentation du calcul booléen, qui note « + » l'opération « ∨ », la loi ici notée « + » étant cerclée $\oplus$ , ou notée XOR.
↑ Givant et Halmos 2009, p. 10.
↑ Cori et Lascar 1993, p. 99.
↑ Givant et Halmos 2009, p. 188-192, Cori et Lascar 1993, p. 120-126.

Voir aussi

Articles connexes

Bibliographie

René Cori et Daniel Lascar, Logique mathématique I. Calcul propositionnel, algèbres de Boole, calcul des prédicats, 1993 [détail des éditions], chap. 2.
(en) Steven Givant et Paul Halmos, Introduction to Boolean Algebras, Springer, 2009, 574 p. (ISBN 978-0-387-40293-2).
Daniel Ponasse, Logique mathématique, Chapitre V : Aspect algébrique – Structure d’anneau booléien , éditeur O.C.D.L., Paris, 1967.

[1] Voir Cori et Lascar 1993, p. 96 pour cette caractérisation.

[2] Ce système d'axiomes pour les algèbres de Boole est donné dans Givant et Halmos 2009, p. 10.

[3] 'après Givant et Halmos 2009, p. 10, caractérisation due « essentiellement » à E. V. Huntington (en), dans Sets of independent postulates for the algebra of logic, Transactions of the American Mathematical Society, vol. 5 (1904), p. 288–309 ; Huntington en a donné plusieurs autres.

[4] Définition d'Algèbre de Boole dans Cori et Lascar 1993, p. 91.

[5] Cet usage du signe « + » est en contradiction avec une certaine tradition de présentation du calcul booléen, qui note « + » l'opération « ∨ », la loi ici notée « + » étant cerclée $\oplus$ , ou notée XOR.

[6] Givant et Halmos 2009, p. 10.

[7] Cori et Lascar 1993, p. 99.

[8] Givant et Halmos 2009, p. 188-192, Cori et Lascar 1993, p. 120-126.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]