Algèbre de Boole (structure)

Restez toujours informé : suivez-nous sur Google (☆)

Introduction

En mathématiques, une algèbre de Boole ou un treillis booléen est un type de structure algébrique.

Définition

Une algèbre de Boole est un ensemble E contenant deux éléments particuliers distincts, notés $⊥$ et $⊤$ (ou 0 et 1), et muni de deux lois de composition internes, $\lor$ et $\land$ , vérifiant les propriétés suivantes :

1. associativité : pour tout a, b et c de E,

$(a \lor b) \lor c = a \lor (b \lor c)$ et $(a \land b) \land c = a \land (b \land c)$

2. commutativité : pour tous a et b de E,

$a \lor b = b \lor a$ et $a \land b = b \land a$

3. loi d'absorption : pour tous a et b de E,

a \land (a \lor b) = a = a \lor (a \land b)

4. distributivité de chaque loi par rapport à l'autre : pour tous a, b et c de E,

$(a \lor b) \land c = (a \land c) \lor (b \land c)$ et $(a \land b) \lor c = (a \lor c) \land (b \lor c)$

5. bornes : pour tout a de E,

$⊤ \lor a = ⊤$ et $⊥ \land a =⊥$

6. complémentarité : Pour tout a de E, a possède au moins un complémentaire, c'est-à-dire un élément $\neg$ a tel que :

a \land (\neg a) =⊥ et a \lor (\neg a) = ⊤.

Les propriétés 1, 2 et 3 expriment que cette structure est un treillis, en particulier :

tout élément a de E est idempotent pour les deux lois :

$a \lor a = a et a \land a = a$ ;

l'une des deux propriétés de distributivité (dans la propriété 4) suffit à garantir l'autre ;
on définit un ordre, en posant

$a \leq b$ si et seulement si $a = a \land b$ , (ou de façon équivalente $b = a \lor b$ ).

Les propriétés 5 et 6 expriment que ce treillis est borné (les éléments $⊥$ et $⊤$ sont respectivement le plus petit et le plus grand élément) et complémenté.

Ainsi, « algèbre de Boole » est synonyme de « treillis distributif, borné et complémenté » .

Propriétés

Les propriétés suivantes se démontrent à partir des axiomes de la structure :

Pour tout a de E, le complémentaire est défini de manière unique. Autrement dit :

(a \lor b = ⊤ e t a \land b = ⊥) \Leftrightarrow b = \neg a

$⊤$ est l'élément neutre de la loi $\land$ .
$⊤ = \neg ⊥$ .
$⊥= \neg⊤$ .
Pour tout a de E, $\neg \neg a = a$ .
$⊥$ est l'élément neutre de la loi $\lor$ .
Pour tous a et b de E,

$\neg (a \lor b) = \neg a \land \neg b$ .

\neg (a \land b) = \neg a \lor \neg b

(ces deux dernières formules sont les lois de De Morgan).

Exemples et applications des algèbres de Boole

L'algèbre de Boole binaire

L'algèbre de Boole la plus simple a deux éléments (une algèbre de Boole a au moins deux éléments). On peut la voir comme l'ensemble des valeurs de vérité {Vrai, Faux} muni des lois ET et OU. Elle permet d'interpréter les formules du calcul propositionnel. Le mathématicien britannique George Boole l'introduisit au milieu du XIX siècle. On l'appelle aussi le Calcul booléen. Les opérations de l'algèbre de boole binaire sont implémentées sous forme de portes logiques dans les circuits électroniques et dans les microprocesseurs des ordinateurs.

Algèbres de Boole sur les ensembles

L'ensembles des parties de n'importe quel ensemble U, muni des opérations d'union, d'intersection et de complémentation, est une algèbre de Boole (c'est l'algèbre de Boole à deux éléments dans le cas où U est un singleton).

Anneaux de Boole

La donnée d'une structure d'algèbre de Boole sur un ensemble E permet de munir E d'une structure d'anneau de Boole (qui est un cas particulier de Z/2Z-algèbre) en posant

$0 =⊥, 1 = ⊤, a . b = a \land b, a + b = (a \lor b) \land \neg (a \land b)$ .

Inversement, la donnée d'une structure d'anneau de Boole sur E permet de munir E d'une structure d'algèbre de Boole en posant

$⊥= 0, ⊤ = 1, a \land b = a . b, a \lor b = (a + b) + (a . b)$ .

Ces deux transformations sont inverses l'une de l'autre.