Algèbre de Boole (logique)

Communication = Émetteur ET Récepteur

Communication serait « VRAI » si à la fois les variables Émetteur ET Récepteur étaient actifs (c'est une fonction logique dépendant des variables Émetteur et Récepteur)

Décrocher = (Sonnerie ET Décision de répondre) OU Décision d'appeler

Décrocher serait « VRAI » soit si à la fois on entend la sonnerie ET l'on décide de répondre, soit (OU) si simplement l'on décide d'appeler.

L'algèbre de Boole étant un domaine commun à trois disciplines, on rencontre des notations différentes pour désigner un même objet. Dans le reste de l'article, on indiquera les diverses notations, mais on en privilégiera une pour conserver une certaine homogénéité.

Elle est définie de la manière suivante : a ET b est VRAI si et seulement si a est VRAI et b est VRAI.

Cette loi est aussi notée :

• ${\displaystyle \cdot \,}$ ;
• ${\displaystyle \wedge }$ ;
• « & » ou « && » : cette implémentation fait partie de plusieurs langages de programmation tels que Perl, C, PHP, Swift ;
• « and » ou « AND » : la plupart des langages de programmation comme, par exemple, Ada, Pascal, Perl, Python, PHP proposent cette fonction ;
• « ∧ » : utilisée dans plusieurs notations algébriques et en APL ;
• « * » ; le symbole d'une multiplication ordinaire est utilisée dans quelques langages ne disposant pas de fonction adaptée.

On privilégiera dans la suite la notation « ${\displaystyle \cdot }$ ».

La table de cette loi (analogue à une table d'addition ou de multiplication) n'est pas une table de vérité.

Elle est définie de la manière suivante : a OU b est VRAI si et seulement si a est VRAI ou b est VRAI. (En particulier, si a est vrai et que b est vrai aussi, alors a OU b est vrai.)

Cette loi est aussi notée :

• ${\displaystyle +}$
• « ∨ » (« ${\displaystyle \vee }$ ») en mathématiques (et en logique mathématique) ou en APL ;
• «|» ou «||» dans certains langages de programmation ;
• en toutes lettres « or » ou « OR » en logique ou dans certains langages de programmation.

On privilégiera dans la suite la notation ${\displaystyle +}$ mais on prendra garde du fait que cette loi n'est pas l'addition usuelle dans Z/2Z. C'est pourquoi, en mathématiques et en logique mathématique, la notation ${\displaystyle +}$ n'est pas utilisée pour désigner le « ou inclusif » : elle est réservée au « ou exclusif », opération qui (jointe au « et ») fait de toute algèbre de Boole un anneau de Boole, en particulier une Z/2Z-algèbre.

La négation de a est VRAIE si et seulement si a est FAUX.

La négation de a est notée :

• non-a, non a, not a
• ${\displaystyle {\bar {a}}}$
• ${\displaystyle a/}$
• ${\displaystyle \neg a}$
• « ~a » dans quelques notations algébriques, en APL et dans quelques langages d'interrogation de bases de données (SQL…) ;
• « ! » dans quelques langages de programmation (C, C++…) ;
• « 1- » dans quelques langages ne disposant pas de fonctions adaptées (Batch…) (puisque 1-0=1 et 1-1=0).

On privilégiera dans la suite la notation ${\displaystyle {\bar {a}}}$.

On obtient alors ${\displaystyle {\bar {0}}=1}$ et ${\displaystyle {\bar {1}}=0}$.

Les opérateurs sont concernés par plusieurs propriétés communes :

• associativité : ${\displaystyle (a+b)+c=a+(b+c)}$ , qui est parfois écrit pour cette raison : ${\displaystyle a+b+c}$ et ${\displaystyle (a\cdot b)\cdot c=a\cdot (b\cdot c)}$, qui est parfois écrit pour cette raison : ${\displaystyle a\cdot b\cdot c}$ ;
• commutativité : ${\displaystyle a+b=b+a}$ et ${\displaystyle a\cdot b=b\cdot a}$ ;
• distributivité[1] : ${\displaystyle a\cdot (b+c)=(a\cdot b)+(a\cdot c)}$ et ${\displaystyle a+(b\cdot c)=(a+b)\cdot (a+c)}$ ;
• idempotence : ${\displaystyle a+a=a}$ et ${\displaystyle a\cdot a=a}$ .

Par ailleurs, chaque opérateur possède un élément neutre et un élément absorbant :

• ${\displaystyle a+0=0+a=a}$ ;
• ${\displaystyle a+1=1+a=1}$ ;
• ${\displaystyle a.1=1.a=a}$ ;
• ${\displaystyle a.0=0.a=0}$ ;

Des simplifications sont possibles comme :

• ${\displaystyle a+a\cdot b=a}$ ;
• ${\displaystyle a\cdot (a+b)=a}$ ;
• ${\displaystyle a+{\overline {a}}.b=a+b}$ ;
• ${\displaystyle a.({\overline {a}}+b)=a.b}$.

le théorème du consensus s'applique aux opérateurs de l'algèbre de Boole :

• ${\displaystyle a.b+{\overline {a}}.c=a.b+{\overline {a}}.c+b.c}$.

Enfin, ils suivent le principe de complémentarité :

• involution : ${\displaystyle a={\overline {\overline {a}}}}$ (ex. : la proposition "La lumière est allumée" équivaut à "la lumière n'est pas non allumée" ou, dit autrement, "la lumière n'est pas éteinte").
• tiers exclu : ${\displaystyle a+{\overline {a}}=1}$ (la proposition "lumière allumée" OU "lumière non allumée" est toujours VRAI.).
• contradiction ou antilogie : ${\displaystyle a.{\overline {a}}=0}$ (la proposition "lumière allumée" ET "lumière non allumée" est toujours FAUX.).

On retrouve alors toutes les propriétés qui confèrent à B une structure d'algèbre de Boole.

Pour alléger les écritures, il est d'usage que les opérations booléennes soient soumises aux mêmes règles de priorité que les opérations arithmétiques usuelles : la fonction ET (multiplication logique) est ainsi prioritaire par rapport à la fonction OU (somme logique). Ainsi :

${\displaystyle 1+b\cdot 0=1+0=1}$

Il reste possible de placer des parenthèses dans les calculs pour changer l'ordre de priorité des opérations.

Ce sont les fonctions logiques à deux variables. Parmi celles-ci, on en dénombre certaines suffisamment intéressantes pour qu'on leur donne un nom.

Table de vérité de XOR
a	b	a ${\displaystyle \oplus }$ b
0	0	0
0	1	1
1	0	1
1	1	0

Le OU étudié jusqu'à présent doit se comprendre de la manière suivante : « l'un ou l'autre ou les deux ». Il est également appelé « OU inclusif ». Le OU exclusif (ou XOR pour ' eXclusive OR') s'entend comme : « l'un ou l'autre, mais pas les deux ».

a XOR b

${\displaystyle a\ \operatorname {XOR} \ b=a\oplus b=(a+b).{\overline {(a.b)}}=a{\bar {b}}+{\bar {a}}b}$

On peut également le définir avec un modulo sur une somme ordinaire :

${\displaystyle a\ \operatorname {XOR} \ b=(a+b)\ {\bmod {\ }}2}$

Le « ou exclusif » est parfois noté par le signe arithmétique ${\displaystyle \neq }$ (différent de). Fonctionnellement, on utilise aussi un + entouré :${\displaystyle a\oplus b}$.

Propriété - Toute table de vérité, toute fonction logique, peut se décrire à l'aide de la constante 1 et des deux opérations : disjonction exclusive et conjonction, car :${\displaystyle {\bar {a}}=a\oplus \ 1}$, et ${\displaystyle a+b=a\oplus \ b\oplus \ a\cdot b}$

Table de vérité de EQV
a	b	a ${\displaystyle \Leftrightarrow }$ b
0	0	1
0	1	0
1	0	0
1	1	1

L'équivalence (notée EQV ou XNOR) est vraie si les deux entrées ont la même valeur et fausse sinon. C'est la négation du « ou exclusif ».

L'équivalence peut s'écrire

${\displaystyle a\ \operatorname {EQV} \ b=a\odot b={\overline {a\oplus b}}={\overline {a{\overline {b}}+{\overline {a}}b}}=(ab)+({\overline {a}}\cdot {\overline {b}})}$

L'équivalence est souvent notée par le signe ${\displaystyle \Leftrightarrow }$. Elle peut aussi être notée « == » dans certains langages (C++, PHP…) et « ⊙ » en électronique.

Table de vérité de IMP
a	b	a ${\displaystyle \Rightarrow }$ b
0	0	1
0	1	1
1	0	0
1	1	1

L'implication (notée IMP) s'écrit de la manière suivante

${\displaystyle a\ \operatorname {IMP} \ b={\overline {a}}+b}$

Cette opération n'est pas commutative. a est une condition suffisante pour b, qui, elle, est une condition nécessaire pour a.

Mais

${\displaystyle a\ \operatorname {IMP} \ b={\overline {b}}\ \operatorname {IMP} \ {\overline {a}}}$

Table de vérité de INH
a	b	${\displaystyle a.{\overline {b}}}$
0	0	0
0	1	0
1	0	1
1	1	0

L'inhibition (notée INH) se compose comme suit

${\displaystyle a\ \operatorname {INH} \ b=a.{\overline {b}}}$

Si a est VRAI, l'expression vaut VRAI, SAUF si b est VRAI.

Cette opération n'est pas commutative.

L'égalité Décrocher = (Sonnerie ET Décision de répondre) OU Décision d'appeler traduit la situation pratique suivante : On décroche un téléphone quand on décide d'appeler quelqu'un ou quand le téléphone sonne et qu'on décide de répondre.

Elle est constituée de trois variables :

• a = « Sonnerie » ;
• b = « Décision de répondre » ;
• c = « Décision d'appeler ».

la variable d = « Décrocher » est fonction logique des 3 précédentes et peut s'écrire d = a.b + c

La table de vérité de cette fonction d est alors la suivante (à droite) :

La table indique une situation absurde : quand on décide d'appeler quelqu'un et que le téléphone sonne sans qu'on ait envie de répondre, on décrocherait quand même. Une modification de la table comme ci-contre corrigerait cette absurdité. Cette table correspond à une fonction logique Décrocher d2 ou d2 qu'il est possible de déterminer et simplifier en ${\displaystyle d2={\bar {a}}.c+a.b}$.

Un bon élève s'interroge s'il est sage de sortir un soir. Il doit décider en fonction de quatre variables :

• a = il a assez d'argent ;
• b = il a fini ses devoirs ;
• c = le transport en commun est en grève ;
• d = l'automobile de son père est disponible.

Cet élève pourra sortir si :

• il a assez d'argent, a = vrai ;
• il a fini ses devoirs, donc b = vrai ;
• le transport en commun n'est pas en grève, donc c = faux ;
• ou si l'automobile de son père est disponible, donc d = vrai.

L'expression logique de sortir en fonction de l'état des variables a, b, c et d peut donc s'écrire ainsi :Sortir =${\displaystyle a.b.({\bar {c}}+d)}$

Une fonction logique peut être déterminée

• soit sous forme d'une expression faisant intervenir les 3 opérations (${\displaystyle +\,}$, ${\displaystyle \cdot \,}$, ${\displaystyle {\bar {}}\,}$)
• soit sous forme de sa table de vérité. Dans ce cas il sera toujours possible d'effectuer un développement pour écrire cette fonction comme une somme de produits.

Exemple : Dans l'exemple de "Décrocher2", la lecture de la table montre que ${\displaystyle d2}$ égale ${\displaystyle 1}$ quand ${\displaystyle (a,b,c)=(0,0,1)}$ ou ${\displaystyle (0,1,1)}$ ou ${\displaystyle (1,1,0)}$ ou ${\displaystyle (1,1,1)}$.Cela permet de définir d2 par ${\displaystyle d2={\bar {a}}.{\bar {b}}.c+{\bar {a}}.b.c+a.b.{\bar {c}}+a.b.c}$

Il est possible de trouver une expression minimisant le nombre de termes et le nombre de lettres dans chaque terme. C'est l'objectif de certaines techniques comme la méthode de Quine-Mc Cluskey, les diagrammes de Karnaugh, la méthode des consensus, la double dualisation…

Exemple (suite) : la somme précédente peut être réduite par factorisation des deux premiers termes par ${\displaystyle {\bar {a}}.c}$ et factorisation des deux derniers termes par ${\displaystyle a.b\,}$${\displaystyle d2={\bar {a}}.c+a.b}$

• Opération bit à bit
• Les lois de la pensée

• J. Kuntzmann, Algèbre de Boole, Paris, Dunod, 1968
• N. Permingeat, Algèbre de Boole : Théorie, méthodes de calcul, applications, avec exercices, Paris, Dunod, 1988
• Claude François Picard, Théorie des questionnaires, Paris, Gauthier-Villars, 1965