Sciences · Mathématiques
L’algèbre de Boole
L’algèbre de Boole est un calcul sur deux valeurs seulement, 0 (faux) et 1 (vrai), avec les opérations ET, OU et NON. Elle est à la base du fonctionnement de tous les circuits numériques.
Mis à jour le 4 min de lecture
En 1854, le mathématicien anglais George Boole publie Les Lois de la pensée, où il propose de traiter le raisonnement logique comme un calcul algébrique. Près d’un siècle plus tard, cette idée devient la base de l’électronique numérique : chaque processeur, chaque mémoire, chaque téléphone exécute des milliards d’opérations booléennes par seconde. L’algèbre de Boole est le pont entre la logique mathématique et l’informatique.
Les opérations de base et leurs tables de vérité
| a | b | NON a | a ET b | a OU b | a XOR b | a NAND b | a NOR b |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
- ET vaut 1 seulement si les deux entrées valent 1 (comme une multiplication).
- OU vaut 1 si au moins une entrée vaut 1 (OU inclusif).
- XOR (OU exclusif) vaut 1 si exactement une entrée vaut 1 : c’est le « ou » de « fromage ou dessert ».
- NAND (NON-ET) et NOR (NON-OU) sont les négations de ET et OU.
Les lois de l’algèbre de Boole
| Loi | Pour ET | Pour OU |
|---|---|---|
| Élément neutre | a · 1 = a | a + 0 = a |
| Élément absorbant | a · 0 = 0 | a + 1 = 1 |
| Idempotence | a · a = a | a + a = a |
| Complément | a · ¬a = 0 | a + ¬a = 1 |
| Commutativité | a · b = b · a | a + b = b + a |
| Associativité | (a · b) · c = a · (b · c) | (a + b) + c = a + (b + c) |
| Distributivité | a · (b + c) = a · b + a · c | a + b · c = (a + b) · (a + c) |
| Absorption | a · (a + b) = a | a + a · b = a |
| De Morgan | ¬(a · b) = ¬a + ¬b | ¬(a + b) = ¬a · ¬b |
Plusieurs règles diffèrent de l’algèbre ordinaire : a + a = a (et non 2a), 1 + 1 = 1, et le OU est distributif sur le ET.
Les lois de De Morgan
Elles indiquent comment nier une expression : la négation d’un ET est le OU des négations, et inversement. « Il ne fait pas beau et chaud » équivaut à « il ne fait pas beau ou il ne fait pas chaud ». Ces lois, formulées par Augustus De Morgan au XIXe siècle, sont aussi présentées dans la fiche logique mathématique.
Simplifier une expression
Pour n variables, la table de vérité compte 2ⁿ lignes. Au-delà de quatre ou cinq variables, on utilise des méthodes systématiques (tableaux de Karnaugh, algorithmes).
Des opérations aux circuits
En 1937-1938, Claude Shannon, alors étudiant au MIT, montre dans son mémoire de master que les circuits à relais électriques peuvent être décrits et simplifiés par l’algèbre de Boole. Un interrupteur fermé vaut 1, ouvert 0 ; deux interrupteurs en série réalisent un ET, deux interrupteurs en parallèle un OU.
Les portes logiques (AND, OR, NOT, XOR, NAND, NOR) sont aujourd’hui réalisées par des transistors. Les portes NAND et NOR sont dites universelles : on peut construire toutes les autres avec l’une d’elles seulement. Par exemple, NON a = a NAND a.
Applications
- Électronique numérique : processeurs, mémoires, calculatrices.
- Programmation : conditions
if (a && b),||et!dans de nombreux langages, filtres et masques binaires. - Recherche documentaire : opérateurs ET, OU, SAUF des moteurs de recherche et des bases de données (voir la recherche documentaire).
- Ensembles : l’intersection, la réunion et le complémentaire obéissent aux mêmes lois que ET, OU et NON.
Questions fréquentes
Qui a inventé l’algèbre de Boole ?
George Boole (1815-1864), mathématicien anglais, dans The Mathematical Analysis of Logic (1847) puis An Investigation of the Laws of Thought (1854).
Pourquoi 1 + 1 = 1 en algèbre de Boole ?
Parce que le signe + y désigne le OU logique : « vrai ou vrai » est vrai. Ce n’est pas l’addition des nombres, qui en binaire donne 1 + 1 = 10.
Quelle est la différence entre OU et XOR ?
Le OU inclusif est vrai si au moins une entrée est vraie, y compris les deux. Le XOR (OU exclusif) n’est vrai que si une seule entrée est vraie.
À quoi sert une table de vérité ?
À donner la valeur d’une expression logique pour toutes les combinaisons possibles de ses variables, afin de la vérifier, de la comparer à une autre ou de concevoir un circuit.