Algèbre de Boole (logique)

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

L'algèbre de Boole, ou calcul booléen, est la partie des mathématiques, de la logique et de l'électronique qui s'intéresse aux opérations et aux fonctions sur les variables logiques. Plus spécifiquement, l'algèbre booléenne permet d'utiliser des techniques algébriques pour traiter les expressions à deux valeurs du calcul des propositions. Elle fut initiée en 1854 par le mathématicien britannique George Boole.

Aujourd'hui, l'algèbre de Boole trouve de nombreuses applications en informatique et dans la conception des circuits électroniques. Elle fut utilisée la première fois pour les circuits de commutation téléphoniques par Claude Shannon.

L'algèbre de Boole des fonctions logiques permet de modéliser des raisonnements logiques, en exprimant un « état » en fonction de conditions. Par exemple dans les expressions

Communication = Émetteur ET Récepteur: Communication serait « VRAI » si à la fois Émetteur ET Récepteur étaient actif (c'est une fonction logique dépendant des variables Émetteur et Récepteur)
Décrocher = ( Décision de répondre ET Sonnerie ) 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é.

Algèbre de Boole des valeurs de vérité [modifier]

On appelle B l'ensemble constitué de deux éléments appelés valeurs de vérité {VRAI, FAUX}. Cet ensemble est aussi noté

B = {1, 0}
B = $\{\top , \perp \}$ .

On privilégiera dans la suite la notation B = {1, 0}.

Sur cet ensemble on peut définir deux lois (ou opérations ou foncteurs), les lois ET et OU et une transformation appelée complémentaire, inversion ou contraire.

Conjonction [modifier]

Articles connexes : Fonction ET et Conjonction logique.

Table de la loi ET
b\a	0	1
0	0	0
1	0	1

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

$\cdot \,$
$\wedge$
« & » ou « && » dans quelques langages de programmation (Perl, C, PHP…)
« AND » dans certains langages de programmation (Ada, Pascal, Python, PHP…)
« ∧ » dans quelques notations algébriques, ou en APL
« * » (une multiplication ordinaire), pour quelques langages ne disposant pas de fonction adaptée

On privilégiera dans la suite la notation $\cdot \,$ .

On peut construire la table de cette loi (comme une table d'addition ou de multiplication de notre enfance) mais on ne la confondra pas avec une table de vérité.

Disjonction [modifier]

Table de la loi OU
b\a	0	1
0	0	1
1	1	1

Articles connexes : Fonction OU et Disjonction logique.

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

$+$
« ∨ » (« $\vee$ ») en mathématiques (et en logique mathématique) ou en APL.
« | » ou « || » dans certains langages de programmation
En toute lettre « or » ou « OR » en logique ou dans certains langages de programmation ..

On privilégiera dans la suite la notation $+$ mais on prendra garde 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 $+$ 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.

Négation [modifier]

Articles connexes : Fonction NON et Négation logique.

Le contraire de "a" est VRAI si et seulement si a est FAUX. Le contraire de a est noté

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

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

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

Propriétés [modifier]

Propriétés des opérateurs [modifier]

Associativité: Comme avec les opérations habituelles, certaines parenthèses sont inutiles:; $( a + b ) + c = a + (b + c) = a + b + c$; $( a . b ) . c = a . (b . c) = a . b . c$
Commutativité: L'ordre est sans importance:; $a + b = b + a$; $a . b = b . a$
Distributivité: Comme avec les opérations habituelles, il est possible de distribuer :; $a . ( b + c ) = a . b + a . c$; Attention : comportement différent par rapport aux opérateurs + et * habituels :; $a +( b . c ) = ( a + b ) . ( a + c )$
Idempotence: $a + a + a + [...] + a = a$; $a . a . a . [...] . a = a$
Éléments neutres: $a+0=a$; $a.1=a$
Absorption: $0 . a = 0$; $1+a=1,\quad\text{donc}\quad b.(b+a)=b+b.a=b$
Simplification: $a + \overline{a} . b = a + b$; $a . ( \overline{a} + b ) = a . b$
Redondance: $a . b + \overline{a} . c = a . b + \overline{a} . c + b . c$
Complémentarité: $a = \overline{\overline{a}}$
(« La lumière est allumée » = « la lumière n'est pas non allumée »); $a + \overline{a} = 1$
(« VRAI » SI lumière_allumée OU SI lumière_non_allumée → c'est toujours le cas → vrai dans tous les cas → toujours VRAI, donc =1); $a . \overline{a} = 0$

(« VRAI » SI lumière_allumée ET SI lumière_non_allumée → impossible → faux dans tous les cas → toujours FAUX donc =0)

Structure [modifier]

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

Priorité [modifier]

Pour faciliter leur compréhension, il a été décidé que ces opérations seraient soumises aux mêmes règles que les opérations « de tous les jours », la fonction ET (multiplication logique) est ainsi prioritaire par rapport à la fonction OU (somme logique) ; on peut, pour s'aider, placer des parenthèses dans les opérations.

Exemple :

${ a = 0 ; b = 1 ; c = 1 }$
On cherche $a . b + c = ???$
D'abord on calcule $a . b$ :
$a . b = 0 . 1$
$0 . 1 = 0$
Puis, on calcule $0 + c$ :
$0 + c = c$
$c = 1$
Le résultat final est donc:
$a . b + c = ( a . b )+ c = 1$

Théorème de De Morgan [modifier]

Première loi de De Morgan (négation de la conjonction): s'exprime par l'égalité suivante $\overline{ a + b } = \overline{a} . \overline{b}$

Table de vérité/Table de fonctionnement
a	b	a+b	$\overline{ a + b }$	$\overline{ a }$	$\overline{ b }$	$\overline{a} . \overline{b}$
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

Dans les deux cas, l'expression ne sera VRAIE que si a et b sont fausses.

Deuxième loi de De Morgan (négation de la disjonction): $\overline{ a . b } = \overline{a} + \overline{b}$

Table de vérité/Table de fonctionnement
a	b	$a . b$	$\overline{ a . b }$	$\overline{ a }$	$\overline{ b }$	$\overline{a} + \overline{b}$
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Dans les deux cas, l'expression ne sera FAUSSE que si a et b sont vraies.

Fonctions logiques [modifier]

Article détaillé : Fonction logique.

Mathématiquement, une fonction logique ou opérateur logique est une application de Bⁿ dans B.

En électronique, une fonction logique est une boîte noire qui reçoit en entrée un certain nombre de variables logiques et qui rend en sortie une variable logique dépendant des variables d'entrée. L'article fonction logique précise comment construire les boîtes noires de quelques fonctions fondamentales.

Une table de vérité permet de préciser l'état de la sortie en fonction des états des entrées. Elle caractérise la fonction logique.

Toute table de vérité, et donc toute fonction logique, peut se décrire à l'aide des trois opérations de base :

disjonction (OU)
conjonction (ET)
négation (NON)

On démontre aussi qu'il existe exactement $2^{2^n}$ fonctions logiques de $n$ paramètres. Il suffit en effet de considérer toutes les tables de vérités possibles, ou de considérer le développement d'une fonction de $n$ paramètres

Fonctions logiques fondamentales [modifier]

Elles sont issues des trois opérations de base et définissent alors

une fonction de B dans B : le complémentaire ou inversion
deux fonctions de B² dans B qui sont la somme (OU) et le produit (ET)

Table de vérité de l'inverse
a	$\bar a$
0	1
1	0

Table de vérité de la somme
a	b	a $+ \,$ b
0	0	0
0	1	1
1	0	1
1	1	1

Table de vérité du produit
a	b	a $\cdot \,$ b
0	0	0
0	1	0
1	0	0
1	1	1

Fonctions logiques composées [modifier]

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.

Disjonction exclusive [modifier]

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

Équivalence [modifier]

Table de vérité de EQV
a	b	a $\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: $a\ \operatorname{EQV}\ b = \overline{a\ \operatorname{XOR}\ b} =\overline{(a+b)}+(a\cdot b) = (a\cdot b) + (\overline{a}\cdot\overline{b}) = (\overline{a}+b)\cdot(a+\overline{b})$

L'équivalence est souvent notée par le signe $\Leftrightarrow$ . Elle peut aussi être notée "==" dans certains langages (C, C++, PHP…).

Implication [modifier]

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

Article détaillé : implication (logique).

L'implication (notée IMP) s'écrit de la manière suivante: $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 $a\ \operatorname{IMP}\ b = \overline{b}\ \operatorname{IMP}\ \overline{a}$

illustration :

de l'affirmation "Si j'habite en France, alors j'habite en Europe." on peut déduire "Si je n'habite pas en Europe, alors je n'habite pas en France." mais pas "Si je n'habite pas en France, alors je n'habite pas en Europe. car on ne sait pas si j'habite en Europe mais ailleurs qu'en France..

Inhibition [modifier]

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

L'inhibition (notée INH) se compose comme suit: $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.

Exemple de fonctions logiques à trois ou quatre variables [modifier]

Fonction logique à trois variables [modifier]

Table de vérité de décrocher
a	b	c	d
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Si l'on reprend l'exemple du téléphone, on se trouve en présence de 3 variables :

a = "le téléphone sonne"
b = "on a envie de répondre"
c = "on a envie d'appeler quelqu'un"

la variable d = "on décroche" est fonction logique des 3 précédentes. On écrira que

car on décroche quand ça sonne et qu'on a envie de répondre ou quand on a envie d'appeler quelqu'un.

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

Table de vérité de décrocher2
a	b	c	d2
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

L'observation de la table montre que notre analyse première comportait une situation absurde: le téléphone sonne, on a envie d'appeler quelqu'un, mais on n'a pas envie de répondre et on décroche quand même. Cela n'est certainement pas le comportement souhaité, il est donc préférable de modifier la fonction décrocher de façon à ce qu'on obtienne le tableau suivant (à droite):

En lisant le procédé de la simplification des expressions ci-dessous, on voit que la formule de décrocher2 correspond à $d2 =\bar a.c + a.b$ .

Fonction logique à quatre variables [modifier]

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

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 = $a.b.({\bar c}+d)$

Minimisation d'une expression [modifier]

Une fonction logique peut être déterminée

soit sous forme d'une expression faisant intervenir les 3 opérations ( $+\,$ , $\cdot\,$ , $\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 "téléphoner2", on s'aperçoit que le résultat est à 1 quand (a, b, c) = (0, 0, 1) ou (0, 1, 1) ou (1, 1, 0) ou (1, 1, 1).

Cela permet de définir d2 par $d2 =\bar a.\bar b.c + \bar a.b.c + a.b.\bar c + a.b.c$

Il est alors intéressant 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 en

$d2 =\bar a.c + a.b$

par factorisation des deux premiers termes par $\bar a.c$ et factorisation des deux derniers termes par $a.b \,$

Arbre d'expression [modifier]

Les expressions logiques sont souvent représentées en informatique sous forme d'arborescence. A un premier sommet (racine) sont rattachés différents sous-arbres (ou branches). Les sommets sans issue sont appelés feuilles. Chaque sommet interne correspond à un sélecteur booléen S(x, y, z )= "si x alors y sinon z", qui ramène une question x à deux sous-questions plus simples, éventuellement réduites à 1/vrai ou 0/faux. L'évaluation d'une fonction f dépendant d'une variable q choisie pour la première question est alors f=S(q,f(q=1), f(q=0)), qui ramène à deux expressions indépendantes de q. Soit f = a.b+a.d.f+c.d+e.f ; on peut écrire f= S(a, f(a=1), f(a=0))= S(a, b+c.d+d.f+e.f, c.d+e.f)= S(a, S(b,1,d.f+c.d+e.f), S(c,d+e.f, e.f))... Les arbres dépendant de l'expression et de l'ordre des questions, pour une même expression certains questionnaires seront plus simples que d'autres.