L’algèbre de Boole a été imaginée à la fin du dix-neuvième siècle par le mathématicien George Boole. Son but premier était de représenter les raisonnements logiques en utilisant un formalisme mathématique. Aujourd’hui, elle constitue un élément fondamental dans la conception des systèmes électroniques numériques.

L’algèbre de Boole travaille sur un ensemble de deux éléments appelés valeurs de vérité, permettant de caractériser l’état, vrai ou faux, d’une proposition. Il existe différentes notations pour désigner les éléments de cet ensemble. Dans ce document l’état vrai sera représenté par le bit 1, l’état faux sera représenté par le bit 0.

Les fonctions logiques de base

L’algèbre de Boole définit les trois opérations, ou fonctions logiques, de base suivantes : ET (conjonction), OU (disjonction), NON (négation). Ces opérations peuvent être composées pour former des expressions plus complexes.

Une fonction logique peut être représentée sous la forme d’un tableau appelé table de vérité. Ce tableau est construit en énumérant toutes les combinaisons possibles d’opérandes et en leur associant les résultats correspondants.

La fonction NON

La négation logique exprime le contraire d’une proposition. Par exemple, « On appelle extraterrestre un être vivant qui NE provient PAS de la Terre. »

$a$ (je proviens de la Terre)	$y = \overline a$ (je suis un extraterrestre)
0	1
1	0

Vous trouverez différents symboles pour représenter l’opération NON dans une expression :

\begin{array}{c} \overline a \\ \neg a \\ ! a \end{array}

Lorsqu’on applique deux fois la fonction NON, on retrouve la valeur d’origine :

\overline{\overline a} = a

La fonction ET

La fonction ET vérifie si deux conditions sont vraies simultanément. Elle est conforme au sens du mot « et » de la langue française. Par exemple, représentons la table de vérité de l’expression suivante : « Seuls les élèves présents ET silencieux seront récompensés. »

$a$ (je suis présent)	$b$ (je suis silencieux)	$y = a\cdot b$ (je serai récompensé)
0	0	0
0	1	0
1	0	0
1	1	1

Vous trouverez différents symboles pour représenter l’opération ET dans une expression :

\begin{array}{rcl} a & \cdot & b \\ a & \wedge & b \\ a & \& & b \end{array}

Nous utiliserons le premier symbole (point) qui rappelle le fait que l’opération ET ressemble à une multiplication. D’ailleurs, le résultat d’un ET est parfois appelé « produit ».

On remarque quelques propriétés intéressantes de la fonction ET :

\begin{aligned} a \cdot 0 &= 0 \\ a \cdot 1 &= a \\ a \cdot a &= a \\ a \cdot\overline a &= 0 \\ a \cdot b &= b \cdot a \\ a \cdot (b \cdot c) &= (a \cdot b) \cdot c \end{aligned}

La fonction OU

La fonction OU vérifie si au moins une condition est vraie. Considérons, par exemple, la table de vérité correspondant à la proposition : « Seules les personnes majeures OU accompagnées d’un adulte peuvent participer. »

$a$ (je suis majeur)	$b$ (je suis accompagné d’un adulte)	$y = a + b$ (je peux participer)
0	0	0
0	1	1
1	0	1
1	1	1

Contrairement à la signification courante du mot « ou » de la langue française, l’opération OU booléenne est inclusive : dans cet exemple, je peux participer même si je suis majeur et accompagné d’un adulte.

Vous trouverez différents symboles pour représenter l’opération OU dans une expression :

\begin{array}{rcl} a & + & b \\ a & \vee & b \\ a & | & b \end{array}

Nous utiliserons le premier symbole (plus) qui rappelle le fait que l’opération OU ressemble à une addition. D’ailleurs, le résultat d’un OU est parfois appelé « somme ».

On remarque quelques propriétés intéressantes de la fonction OU :

\begin{aligned} a + 0 &= a \\ a + 1 &= 1 \\ a + a &= a \\ a + \overline a &= 1 \\ a + b &= b + a \\ a + (b + c) &= (a + b) + c \end{aligned}

Dans les expressions logiques, l’opérateur ET sera prioritaire par rapport à l’opérateur OU. L’opération ET est distributive par rapport à l’opération OU :

a\cdot (b + c) = a\cdot b + a\cdot c

La fonction OU exclusif

La fonction OU exclusif a une signification proche du mot « ou » de la langue française, ou plus précisément de l’expression « soit… soit ». Par exemple, « Le menu à 10€ inclut soit du fromage, soit un dessert. »

$a$ (je prends du fromage)	$b$ (je prends un dessert)	$y = a\oplus b$ (je peux prétendre au menu à 10€)
0	0	0
0	1	1
1	0	1
1	1	0

Vous trouverez différents symboles pour représenter l’opération OU exclusif dans une expression :

\begin{array}{rcl} a & \oplus & b \\ a & \veebar & b \end{array}

On peut construire la fonction ou exclusif à partir des fonctions de base :

a \oplus b = a\cdot\overline b + b\cdot\overline a

En français, « Je prends du fromage et pas de dessert ou je prends un dessert et pas de fromage. »

Il n’existe pas de fonction ET exclusif. La négation du OU exclusif correspond à la fonction Coïncidence qui produit un résultat vrai lorsque ses opérandes sont égaux.

La fonction NON-OU

La fonction NON-OU consiste simplement à prendre la négation du résultat de la fonction OU. En français, elle a la même signification que l’expression « ni… ni ». Par exemple, « Seuls les véhicules qui ne sont NI polluants, NI bruyants ont le droit de circuler. »

$a$ (mon véhicule pollue)	$b$ (mon véhicule est bruyant)	$y = \overline{a + b}$ (mon véhicule peut circuler)
0	0	1
0	1	0
1	0	0
1	1	0

Vous trouverez différentes manières de représenter l’opération NON-OU dans une expression :

\begin{array}{c} \overline{a + b} \\ \neg (a \vee b) \\ a\ \downarrow\ b \end{array}

L’opération NON-OU peut également être réécrite de la manière suivante :

\overline{a + b} = \overline a \cdot \overline b

Cette identité fait partie des lois de De Morgan. En reformulant notre exemple, cela donne : « Seuls les véhicules qui sont NON polluants ET NON bruyants ont le droit de circuler. »

La fonction NON-ET

La fonction NON-ET consiste simplement à prendre la négation du résultat de la fonction ET. Nous pouvons l’illustrer par un exemple : « Tout le personnel peut retourner à son poste, SAUF les personnes qui font partie de l’équipe de sécurité ET qui ont été embauchées cette semaine. »

$a$ (je fais partie de l’équipe de sécurité)	$b$ (j’ai été embauché cette semaine)	$y = \overline{a\cdot b}$ (je peux retourner à mon poste)
0	0	1
0	1	1
1	0	1
1	1	0

Vous trouverez différentes manières de représenter l’opération NON-ET dans une expression :

\begin{array}{c} \overline{a \cdot b} \\ \neg (a \wedge b) \\ a\ \uparrow\ b \end{array}

L’opération NON-ET peut également être réécrite de la manière suivante :

\overline{a \cdot b} = \overline a + \overline b

Cette identité fait partie des lois de De Morgan. En reformulant notre exemple, cela donne : « Seules Les personnes qui NE font PAS partie de l’équipe de sécurité OU qui N’ont PAS été embauchées cette semaine peuvent retourner à leur poste. »

Résumé

L’algèbre de Boole définit les fonctions logiques de base sur les valeurs binaires. Une fonction logique peut être représentée par une table de vérité.

Voici un récapitulatif des fonctions logiques présentées dans cette page :

Nom en français	Nom en anglais	Symbole mathématique et identité
ET	AND	$a\cdot b$
OU	OR	$a + b$
NON	NOT	$\overline a$
OU exclusif	XOR	$a\oplus b = a\cdot\overline b + b\cdot\overline a$
NON-OU	NOR	$\overline{a + b} = \overline a \cdot \overline b$
NON-ET	NAND	$\overline{a \cdot b} = \overline a + \overline b$

Fonctions logiques