Introduction à la logique

Algèbre de Bool

Algèbre de Boole (logique)

Opération bit à bit

Exemple introductif

Algèbre de Boole des valeurs de vérité

Propriétés

Fonctions logiques

Opérateurs

Décalage de bit

Conjonction

Disjonction

Négation

Fonctions logiques fondamentales

Fonctions logiques composées

NOT

AND

OR

XOR

Propriétés des opérateurs

Structure

Priorité

Théorème de De Morgan

Disjonction exclusive

Équivalence

Implication

Inhibition

L'algèbre de Boole, ou calcul booléen, est la partie des mathématiques qui s'intéresse à une approche algébrique de la logique, vue en termes de variables, d'opérateurs et de fonctions sur les variables logiques. Ce qui 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.

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 actifs (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é.

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.

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 la plupart des langages de programmation (Perl, C, PHP, Swift…)
« AND » dans certains langages de programmation (Ada, Pascal, Perl, 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é.

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

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 toutes lettres « or » ou « OR » en logique ou dans certains langages de programmation.

On privilégiera dans la suite la notation mais on prendra garde du fait que cette loi n'est pas l'addition usuelle . 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 .

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
$\bar{a}$
$\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 $\bar{a}$ .

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

Associativité

Comme avec les opérations habituelles, certaines parenthèses sont inutiles:

Commutativité

L'ordre est sans importance:

Distributivité

Idempotence

Éléments neutres

Absorption

$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é

involution : $a = \overline{\overline{a}}$

"La lumière est allumée" = "la lumière n'est pas non allumée", "la lumière n'est pas éteinte"

tiers-exclus : $a + \overline{a} = 1$

"lumière allumée" OU "lumière non allumée" est toujours VRAI

non-contradiction : $a . \overline{a} = 0$

"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 faciliter leur compréhension, on a 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.

Première loi de De Morgan (négation de la conjonction/ET)

s'exprime par l'égalité suivante $\overline{ a + b } = \overline{a} . \overline{b}$

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/OU)

$\overline{ a . b } = \overline{a} + \overline{b}$

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

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. 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)

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

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 $\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

$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 : $a\ \operatorname{XOR}\ b = (a+b)\ \bmod\ 2$

Le « ou exclusif » est parfois noté par le signe arithmétique $\ne$ (différent de). Fonctionnellement, on utilise aussi un + entouré : $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 : $\bar a = a\oplus\ 1$ , et $a + b = a \oplus\ b \oplus\ a\cdot b$

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 = 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 $\Leftrightarrow$ . Elle peut aussi être notée « == » dans certains langages (C, C++, PHP…) et « ⊙ » en électronique.

Table de vérité de IMP
a	b	a $\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

$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 (métropolitaine), 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 je peux habiter en Europe ailleurs qu'en France, sans contredire l'énoncé initial.

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.

Opération manipulant les données de manière binaires, directement au niveau des bits. Elles sont utiles dès qu'il s'agit de manipuler les données à bas niveau : codages, couches basses du réseau (par exemple TCP/IP), cryptographie,. Les opérations bit à bit courantes comprennent des opérations logiques bit par bit, et des opérations de décalage des bits, vers la droite ou vers la gauche.

Représente la négation logique, le complément d'une expression.

Par exemple, NOT 7 = 8 :

NOT 0111

  = 1000

Le et logique de deux expressions.

Ex : 5 AND 3 = 1 :

AND 0011

  = 0001

Le ou logique de deux expressions.

Ex : 5 OR 3 = 7 :

OR 0011

 = 0111

Le ou exclusif de deux expressions.

Ex : 5 XOR 3 = 6 :

XOR 0011

  = 0110

Table de vérité/Table de fonctionnement

$\overline{ a + b }$

$\overline{ a }$

$\overline{ b }$

$\overline{a} . \overline{b}$

Décalage de bit à gauche.

   00010111 (+23) LEFT-SHIFT

=  00101110 (+46)

Décalage de bit à droite.

   00010111 (+23) RIGHT-SHIFT

=  00001011 (+11)