vignette|Exemple d'algèbre de Boole : l'ensemble des parties de l'ensemble {x, y, z} illustré par son diagramme de Hasse.
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 estVoir pour cette caractérisation. un treillis E 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 ⊥), et un plus grand élément noté dans la suite 1 (il est souvent noté également ⊤) ; 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 a 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 : a1 = (a ∧ a’) ∨ a1 = (a ∨ a1) ∧ (a’ ∨ a1) = a’ ∨ a1 c'est-à-dire que a’ ≤ a. De même, 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 Ce système d'axiomes pour les algèbres de Boole est donné dans .:
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) eta ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)(distributivité)Complémenta ∧ 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 ) {| style="text-align:center; width:48em" |- |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) : {| style="text-align:center; width:34em" |- |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éd'après , caractérisation due « essentiellement » à , dans Sets of independent postulates for the algebra of logic, Transactions of the American Mathematical Society, vol. 5 (1904), ; Huntington en a donné plusieurs autres..
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 équivalenteDéfinition d'Algèbre de Boole dans ., 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 : {| style="text-align:left;" |- |width="150" |(a+b)+c = a+(b+c) | (associativité +) |- |a+b = b+a | (commutativité +) |- |0 + a = a | (élément neutre +) |- |colspan=2|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 : {| style="text-align:left;" |- |width="150" |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 : {| style="text-align:left;" |- |width="150" |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)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 , ou notée XOR. 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., 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.
Algèbre de Boole 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
L'ensemble des formules du calcul propositionnel quotienté 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(p1, ... , pn) est (f(p’1, ... , p’n))'.
Sous-algèbres