Algèbre de Boole à deux éléments

En mathématiques et en algèbre abstraite, l'algèbre de Boole à deux éléments est l'algèbre booléenne dont l'univers B est le domaine booléen. Les éléments du domaine booléen sont 1 et 0 par convention, afin que B = {0, 1}. Paul Halmos a nommé cette algèbre « 2 », celle-ci a été utilisée en littérature, et sera utilisée ici.

Définition modifier

B est un ensemble partiellement ordonné et les éléments de B sont aussi ses partie bornée.

Une opération d'arité n est une application de Bⁿ à B. L'algèbre booléenne se compose de deux opérations binaires et de complémentation unaire. Les opérations binaires ont été nommées et notées de diverses manières. Ici, elles sont appelées « somme » et « produit », et notées '+' et '∙', respectivement. La somme et le produit sont commutatifs et associé, comme dans l'algèbre des nombres réels. En ce qui concerne l'ordre des opérations, les parenthèses sont décisives si elles sont présentes. Sinon, '∙' précède '+'. Par conséquent, A ∙ B + C peut être écrit (A ∙ B) + C et non pas A ∙ (B + C). La complémentation est notée en notant une barre au-dessus de l'argument. L'analogue numérique du complément de X est 1 - X. Dans le langage de l'algèbre universelle, une algèbre Booléenne est une algèbre $\langle B,+,.,{\overline {..}},1,0\rangle$ de type $\langle 2,2,1,0,0\rangle$ .

Une bijection entre {0,1} et {Vrai, Faux} rend une logique bivalente classique sous la forme d'équation : la complémentation est lue comme NON. Si 1 est lu comme Vrai, '+' est lu comme OU, et « ∙ » comme ET, et vice-versa si 1 est lu comme Faux.

Quelques identités basiques modifier

2 peut être considérée comme fondée sur l'arithmétique « booléenne » triviale suivante :

{\begin{aligned}&1+1=1+0=0+1=1\\&0+0=0\\&0\cdot 0=0\cdot 1=1\cdot 0=0\\&1\cdot 1=1\\&{\overline {1}}=0\\&{\overline {0}}=1\end{aligned}}

Notez que :

'+' et '∙' exercent exactement la même fonction que dans l'arithmétique numérique, sauf que 1 + 1 = 1. '+' et '∙' sont dérivées par analogie de l'arithmétique numérique.
La permutation de 0 et 1, et de '+' et '∙' préserve la vérité; telle est l'essence de la dualité qui imprègne toutes les algèbres de Boole.

Cette arithmétique booléenne suffit de vérifier toute équation de 2, y compris les axiomes, en examinant toute assignation possible de 0 et de 1 à chaque variable (voir la procédure de décision).

Les équations suivantes peuvent maintenant être vérifiées :

{\begin{aligned}&A+A=A\\&A\cdot A=A\\&A+0=A\\&A+1=1\\&A\cdot 0=0\\&{\overline {\overline {A}}}=A\end{aligned}}

Les signes '+' et '∙' peuvent être distribués les uns sur les autres :

$\ A\cdot (B+C)=A\cdot B+A\cdot C;$
$\ A+(B\cdot C)=(A+B)\cdot (A+C).$

La distribution de '∙' sur '+' est en accord avec l'algèbre élémentaire, mais pas '+' sur '∙'. Pour cela et pour d'autres raisons, une somme de produits (conduisant à une synthèse NAND) est plus souvent employé que le produit de sommes (conduisant à une synthèse NOR).

Chacun des '+' et '∙' peuvent être définis en termes de l'autre :

$A\cdot B={\overline {{\overline {A}}+{\overline {B}}}}$
$A+B={\overline {{\overline {A}}\cdot {\overline {B}}}}.$

Nous avons seulement besoin d'une opération binaire, et la concaténation suffit pour le désigner. Ainsi la concaténation et la barre supérieure suffisent à annoter 2.

Une base pour 2 est un ensemble d'équations, appelées axiomes, à partir desquelles toutes les équations ci-dessus (et plus) peuvent être dérivés. Il y a beaucoup de bases connues pour toutes les algèbres de Boole, et donc pour 2. Une base élégante transcrite en utilisant seulement la concaténation et la barre supérieure est la suivante :

$\ ABC=BCA$
${\overline {A}}A=1$ (2 est un treillis, avec une limite supérieure de 1)
$\ A0=A$ (0 est la limite inférieure).
$A{\overline {AB}}=A{\overline {B}}$ (2 est un treillis distributif)

Où la concaténation = OR, 1 = vrai, et 0 = faux, ou la concaténation = AND, 1 = faux, et 0 = vrai. (la barre supérieur représente la négation dans les deux cas.)

Si 0=1, (1)-(3) sont alors les axiomes d'un groupe abélien.

Ces bases permettent une approche facile à la preuve, appelée calcul, qui procède par la simplification des expressions à 0 ou 1, en invoquant axiomes (2) - (4), et les identités élémentaires $AA=A,{\overline {\overline {A}}}=A,1+A=1$ , et la loi distributive.

Métathéorie modifier

Le théorème de De Morgan déclare que si l'on fait ce qui suit, dans l'ordre donné, à toute fonction booléenne : complémenter chaque variable, échanger les opérateurs '+' et '∙' (en prenant soin d'ajouter des parenthèses pour s'assurer que l'ordre des opérations reste le même), complémenter le résultat, le résultat est logiquement équivalent avec la fonction de départ.

Un métathéorème puissant et non-trivial stipule que tout théorème 2 est valable pour toutes les algèbres de Boole^[1]. À l'inverse, une identité qui est valable pour une algèbre booléenne non-triviale tient également dans 2. Ainsi tout le contenu mathématique de l'algèbre de Boole est détenu par 2. Ce théorème est utile parce que toute équation de 2 peut être vérifiée par une procédure de décision. Les logiciens se réfèrent à ce fait que "2 est décidable".

Références modifier

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Two-element Boolean algebra » (voir la liste des auteurs).

↑ Givant, S., and Halmos, P. Introduction to Boolean Algebras (2009) DOI 10.1007/978-0-387-68436-9, Springer Verlag.

Voir aussi modifier

Lectures supplémentaires modifier

Stanford Encyclopedia of Philosophy: "The Mathematics of Boolean Algebra." de J. Donald Monk.
Burris, Stanley N., et H.P. Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. (ISBN 3-540-90578-2).

[1] Givant, S., and Halmos, P. Introduction to Boolean Algebras (2009) DOI 10.1007/978-0-387-68436-9, Springer Verlag.

[1]