Algèbre de boole (structure)

Algèbre de Boole (structure)

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

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 au moins deux éléments particuliers, notés $\perp$ et $\top$ (ou 0 et 1), muni de deux lois de composition internes, $\vee$ et $\wedge$, et qui vérifie les axiomes suivants :

• 1. associativité : Pour tous a, b et c de E,

$(a \vee b) \vee c = a \vee (b \vee c)$ et $(a \wedge b) \wedge c = a \wedge (b \wedge c)$

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

$\quad a \vee b = b \vee a$ et $a \wedge b = b \wedge a$

• 3. absorption : Pour tous a et b de E,

$a \wedge (a \vee b) = a$ et $a \vee (a\wedge b) = a$

• 4. distributivité d'une loi par rapport à l'autre : Pour tous a, b et c de E,

$(a \vee b) \wedge c = (a \wedge c) \vee (b \wedge c)$ et $(a \wedge b) \vee c = (a \vee c) \wedge (b \vee c)$

• 5. idempotence : Pour tout a de E,

$a \vee a = a$ et $a \wedge a = a$

• 6. bornes : Pour tout a de E,

$\top \vee a = \top$ et $\perp \wedge a = \perp$

• 7. complémentarité : Pour tout a de E,

$a\quad$ possède un complémentaire noté $\neg a$, tel que $a \vee \neg a = \top$ et $a \wedge \neg a = \perp$

Les propriétés 1, 2, 3 et 5 définissent une structure de treillis, en particulier on définit un ordre, en posant

a ≤ b si et seulement si a=a ∧ b, (ou de façon équivalente b = a ∨ b).

Les éléments $\scriptstyle\perp$ et $\scriptstyle\top$ sont respectivement le plus petit et le plus grand élément du treillis. Ainsi, une algèbre de Boole est un treillis borné, distributif et complémenté.

Propriétés

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

• $\top = \neg \perp$.
• $\perp = \neg \top$.
• Pour tout a de E, $\neg \; \neg a = a$.
• Pour tout a de E, le complémentaire est défini de manière unique. Autrement dit :

$a \lor b = \top \;{\rm et}\; a \land b = \bot \Rightarrow b = \lnot a$

• $\top$ est l'élément neutre de la loi $\wedge$.
• $\perp$ est l'élément neutre de la loi $\vee$.
• Pour tout a et b de E,

$\neg(a\vee b) = \neg a \wedge \neg b$.

$\neg(a\wedge b) = \neg a \vee \neg b$

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

Exemples et applications des algèbres de Boole

L'algèbre de Boole binaire

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

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^e 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

Les ensembles de parties d'un ensemble, munis des opérations d'union, d'intersection et de complémentation fournissent d'autres exemples d'algèbre de Boole (dont l'algèbre de Boole a deux éléments dans le cas des singletons).

Voir aussi

• Calcul des propositions
• Ensemblist, un jeu video qui utilise l'algèbre de Boole.

Ce document provient de « Alg%C3%A8bre de Boole (structure) ».