Algèbre de Boole (structure)

Pour les articles homonymes, voir « Algèbre de Boole ».

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 — c'est un treillis avec plus grand et plus petit élément, dont les opérations de borne inférieure et de borne supérieure, sont chacune distributives par rapport à l'autre, et dont tout élément possède un complément, 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é est la relation de conséquence logique, les lois d'anneau la disjonction exclusive et la conjonction.

Définitions

Algèbre de Boole comme structure ordonnée

Une algèbre de Boole^[1] est un ensemble ordonné (E, ≤) :

• 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$) ;
• 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) ;
• 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 sont 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 treillis

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é)

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^[5]

• a•b = a ∧ b
• a + b = (a ∧ b’ ) ∨ (a’ ∧ b)

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

et en vérifiant que les éléments neutres 0 et 1 sont bien les plus petit et plus grand éléments, que a ∧ b = a•b et :

• a ∨ b = a + b + a•b

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 fait 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

L'algèbre de Boole binaire

Une algèbre de Boole 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.

Algèbre de Boole des parties d'un ensembles

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

L'ensembles des parties de n'importe quel ensemble non vide 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 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 formules closes 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 : le dual de a ≤ b (a ∧ b = a) est a ≥ b (a ∨ b = a).

On vérifie que le dual 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). 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ément 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'anneau (unitaire) 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 Morgan).

Algèbre de Boole complète

Les bornes supérieures et inférieures se généralisent à des ensembles infinis. Dans l'algèbre de Boole des parties d'un ensemble, toute famille de sous-ensemble 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. Une algèbre de Boole telle que tous ses sous-ensembles ont une borne supérieure et une borne inférieure (en fait l'une des deux hypothèses suffit) est appelée algèbre de Boole complète.

Tout sous-ensemble fini d'une algèbre de Boole possède une borne supérieure et une borne inférieure, l'hypothèse porte donc réellement sur les sous-ensembles infinis. en particulier toute algèbre de Boole finie est complète.

L'algèbre de Boole des parties finies et 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.

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^[6] 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érise 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 in 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).

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. 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}.

Théorème de Stone

Notes et références

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. ↑ 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), pp. 288–309 ; Huntington en a donné plusieurs autres.
4. ↑ Définition d'Algèbre de Boole dans Cori et Lascar 1993, p. 91
5. ↑ On prendra garde qu'en calcul booléen, en particulier dans la conception des circuits logiques, notre loi + est notée $\oplus$ ou XOR, tandis que notre loi ∨ est notée +.
6. ↑ Cori et Lascar 1993, p. 99

Bibliographie

• René Cori et Daniel Lascar, Logique mathématique I. Calcul propositionnel, algèbres de Boole, calcul des prédicats [détail des éditions], chap. 2 .
• (en) Steven Givant et Paul Halmos, Introduction to Boolean Algebras, Springer, 2009 (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.