Quand le vrai et le faux deviennent des nombres — deux valeurs, trois opérations, et un socle sur lequel repose tout ordinateur.
George Boole publie en 1854 une algèbre où les seules valeurs possibles sont Vrai (1) et Faux (0). Quatre-vingts ans plus tard, Claude Shannon remarque que ces mêmes lois décrivent exactement le comportement d'un circuit électrique fait d'interrupteurs : un raisonnement logique devient un calcul, un calcul devient un circuit, un circuit devient une puce. C'est tout le trajet de ce cahier.
Une variable booléenne ne prend que deux valeurs : 1 (Vrai) ou 0 (Faux) — jamais autre chose, jamais « à moitié ». Trois opérations suffisent à tout construire : NON (¬), qui inverse ; ET (∧), qui exige les deux ; OU (∨), qui se contente d'un seul. Cliquez sur les interrupteurs pour changer A et B.
Le circuit électrique (interrupteurs, pile, lampe) et la formule booléenne donnent toujours le même verdict.
Comme l'algèbre des nombres, l'algèbre de Boole obéit à des lois fixes — mais certaines surprennent : ici le OU distribue sur le ET tout autant que le ET distribue sur le OU, ce qui n'arrive jamais avec + et ×. Choisissez une loi : elle est vérifiée ligne par ligne sur toutes les combinaisons possibles de ses variables, sans exception admise.
Chaque case bleue = 1, chaque case claire = 0. La colonne « accord » compare membre de gauche et membre de droite, ligne par ligne.
Une fonction booléenne de n variables n'est qu'une table de 2ⁿ sorties : il en existe 2^(2ⁿ) au total (65 536 pour quatre variables). Sa table de vérité se relit directement comme une somme de cas particuliers — la forme normale disjonctive. La table de Karnaugh range ensuite ces cas en grille pour repérer, sans calcul, les regroupements qui raccourcissent la formule. Cliquez sur une case pour en changer la sortie.
Forme canonique (somme des mintermes) :
Forme simplifiée (Quine-McCluskey) :
Chaque opérateur booléen se dessine comme un composant physique — une porte logique — et une formule devient un schéma. En chaînant quelques portes on obtient un additionneur : la même opération, retenue comprise, que celle qui tourne des milliards de fois par seconde dans un processeur.
Deux demi-additionneurs (OU-EXCLUSIF + ET) et un OU final : a+b+retenue tient toujours sur deux bits (somme, retenue sortante).
La retenue se propage d'un additionneur complet au suivant, du bit de poids faible vers le bit de poids fort.
Voici le fait le plus utile de tout le cahier : la porte NON-ET (NAND) suffit, à elle seule, à reconstruire NON, ET et OU — et donc n'importe quelle fonction booléenne. C'est pour cela qu'un circuit intégré ne fabrique presque qu'un seul motif, répété des milliards de fois.
NON = NAND(a,a). ET = NAND(a,b) puis NAND de ce résultat avec lui-même. OU = NAND des deux compléments (loi de De Morgan).
Il existe exactement 2⁴ = 16 fonctions booléennes de deux variables. Chacune peut s'écrire comme une somme de mintermes (planche 3), et chaque morceau de cette somme n'est lui-même qu'un assemblage de portes NAND (ci-dessus). Cliquez sur une case pour voir le détail.
Trois opérations — NON, ET, OU — suffisent à tout exprimer. Elles obéissent à des lois précises (commutativité, distributivité dans les deux sens, De Morgan) qui forment une structure algébrique complète, vérifiable case par case sur des tables de vérité finies.
N'importe quelle table de vérité se relit directement comme une somme de produits (forme normale disjonctive). Les tables de Karnaugh et l'algorithme de Quine-McCluskey trouvent ensuite l'écriture la plus courte, sans jamais changer la fonction représentée.
Chaque opérateur booléen se câble avec des portes logiques. Un additionneur n'est qu'un empilement de portes ET, OU et NON-EXCLUSIF ; et une seule porte, le NON-ET, suffit à reconstruire toutes les autres — c'est pourquoi les puces modernes répètent un unique motif des milliards de fois.
L'algèbre de Boole se généralise en treillis distributif complémenté ; l'anneau de Boole (𝒫(E), Δ, ∩) en est un avatar déjà rencontré dans le cahier sur les structures algébriques. Claude Shannon, « A Symbolic Analysis of Relay and Switching Circuits » (1937), fait le pont explicite avec les circuits. La complétude fonctionnelle de {NON-ET} et {NON-OU} est un cas particulier du théorème de Post sur les clones de fonctions booléennes (1941).