Shannon : la logique devient circuit

L’étudiant et les relais

Au MIT, en 1937, Claude Shannon a vingt et un ans et un travail ingrat : entretenir les centaines de relais électriques de l’analyseur différentiel de Vannevar Bush, une machine à calculer grande comme une salle. Un relais est un interrupteur commandé : ouvert ou fermé, rien entre les deux. À la même époque, les compagnies téléphoniques en câblent des millions dans leurs centraux, et leurs ingénieurs conçoivent ces réseaux au métier, à l’intuition, à l’essai-erreur.

Shannon, lui, se souvient d’un cours suivi au Michigan : l’algèbre de George Boole, cette curiosité de 1854 où le raisonnement se calcule avec des 0 et des 1. Et il voit ce que personne n’avait vu en quatre-vingt-trois ans. Deux interrupteurs montés en série ne laissent passer le courant que si le premier et le second sont fermés. Deux interrupteurs en parallèle le laissent passer si l’un ou l’autre est fermé. Codez « fermé » par 1, « ouvert » par 0 : la série calcule $a \wedge b$, le parallèle calcule $a \vee b$, et un relais inverseur calcule $\neg a$. Tout le calcul booléen du chapitre, connecteurs, tables de vérité, équivalences, devient du matériel.

La thèse de master qui en résulte, A Symbolic Analysis of Relay and Switching Circuits, est déposée en août 1937 et publiée en 1938. Le psychologue Howard Gardner la qualifiera de thèse de master la plus importante, et la plus célèbre, du vingtième siècle. Son théorème central est un pont à double sens : toute formule booléenne se câble, et tout réseau d’interrupteurs se met en formule.

Simplifier une formule, c’est économiser du cuivre

Le double sens fait toute la puissance de l’idée : deux formules équivalentes décrivent deux circuits qui font exactement la même chose. Si l’une est plus courte, son circuit coûte moins de relais. Voyez ce cahier des charges à trois variables :

$$E = (a \wedge b \wedge c) \vee (a \wedge b \wedge \neg c) \vee (a \wedge \neg b).$$

Câblé naïvement : trois branches en parallèle, la première portant trois interrupteurs en série ($a$, $b$, $c$), la deuxième trois aussi ($a$, $b$ et un inverseur de $c$), la troisième deux ($a$ et un inverseur de $b$). Total : huit interrupteurs. Dressons la table de vérité :

$a$	$b$	$c$	$E$
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

La colonne de $E$ est, ligne à ligne, celle de $a$. Le calcul le confirme, avec les équivalences du cours. La distributivité regroupe les deux premières branches :

$$(a \wedge b \wedge c) \vee (a \wedge b \wedge \neg c) = (a \wedge b) \wedge (c \vee \neg c) = a \wedge b,$$

car $c \vee \neg c$ est toujours vraie. Puis le même geste achève le travail :

$$(a \wedge b) \vee (a \wedge \neg b) = a \wedge (b \vee \neg b) = a.$$

Le circuit de huit interrupteurs se remplace par un seul : l’interrupteur $a$, tout court. Même table, même comportement, sept relais rendus au magasin. C’est exactement le programme de Shannon : simplifier les formules pour simplifier les machines, avec la distributivité comme ici, ou les lois de De Morgan quand une négation porte sur tout un bloc et qu’il faut la faire descendre sur chaque interrupteur. Vos exercices d’équivalences logiques sont, mot pour mot, le métier d’un concepteur de circuits.

Du circuit au jeu

Le DM vous a mené plus loin : la stratégie gagnante du jeu de Nim, celle du théorème de Bouton, n’est qu’un calcul booléen, le OU exclusif appliqué colonne par colonne aux écritures binaires des tas. Autrement dit, l’adversaire parfait au Nim est un circuit, et rien de plus ; dès 1940, une machine à relais jouait déjà au Nim devant le public de l’Exposition universelle de New York. La vôtre vous attend sur ce site, en page interactive : affrontez la machine, elle applique Bouton sans jamais se tromper, et vous savez désormais exactement ce qui se passe dans ses fils.

Du chapitre A0 à votre téléphone, le fil est continu : les tables de vérité que vous dressez sont celles que Shannon a câblées, et les processeurs d’aujourd’hui n’en sont que la version gravée, des milliards de fois plus petite.

Sources

• Claude E. Shannon, A Symbolic Analysis of Relay and Switching Circuits, thèse de master, MIT, 1937 ; publiée dans les Transactions of the American Institute of Electrical Engineers, vol. 57, 1938.
• Howard Gardner, The Mind’s New Science, Basic Books, 1985 (le jugement sur la thèse de Shannon).
• Charles L. Bouton, « Nim, a game with a complete mathematical theory », Annals of Mathematics, vol. 3, 1901, p. 35-39.
• History of Information, notice « Shannon’s Symbolic Analysis of Relay and Switching Circuits », historyofinformation.com.