Allumer une lampe de deux, trois, $n$ endroits : le va-et-vient est un OU exclusif

La stratégie. On traduit la spécification en mots (« la lampe s'allume si les deux aiguillages choisissent la même navette ») en table de vérité, puis on écrit chaque chemin conducteur comme une série de contacts, et l'ensemble comme leur parallèle.

1) La table. L'aiguillage $a$ envoie le courant sur la navette 1 si $a=0$, sur la navette 2 si $a=1$ ; l'aiguillage $b$ le recueille sur la navette 1 si $b=0$, sur la navette 2 si $b=1$. Le circuit est fermé si et seulement si les deux aiguillages sont sur la même navette, c'est-à-dire si $a=b$ :

La colonne $1001$ est celle de la porte XNOR : $\ell =\overline{a\oplus b}$, le comparateur d'égalité. Si l'on croise les navettes (repos de $a$ vers travail de $b$), la lampe s'allume quand les aiguillages sont dans des positions différentes : $\ell =a\oplus b$, la porte XOR. Le choix du câblage ne fixe que l'état de la lampe au repos.

2) Quatre contacts. Deux chemins conduisent : par la navette 1, le contact repos de $a$ en série avec le contact repos de $b$, qui conduit si $\overline{a}\overline{b}=1$ ; par la navette 2, les deux contacts travail en série, qui conduisent si $ab=1$. Les deux chemins sont en parallèle : $$\ell =\overline{a}\overline{b}+ab=\overline{a\oplus b}.$$ Quatre contacts suffisent, et l'on retrouve la forme normale disjonctive complète de la table : un produit par ligne où $\ell =1$ (lignes $00$ et $11$).

3) Pourquoi forcément XOR ou XNOR. Notons $v=\ell (0,0)$. Basculer $a$ doit changer la lampe : $\ell (1,0)=\overline{v}$ ; basculer $b$ aussi : $\ell (0,1)=\overline{v}$ ; enfin, depuis $(1,0)$, basculer $b$ donne $\ell (1,1)=\overline{\overline{v}}=v$. La table est entièrement fixée par $v$ : pour $v=1$, c'est $1001$ (XNOR) ; pour $v=0$, c'est $0110$ (XOR). Deux fonctions sur seize : le va-et-vient n'est pas une astuce d'électricien, c'est la seule réponse à la spécification.

4) Trois endroits, puis $n$. Le permutateur croise les navettes quand $c=1$ : le courant parti sur la navette d'indice fixé par $a$ change de navette si $c=1$ ; la lampe s'allume si la navette d'arrivée est celle que choisit $b$. En notant $0$ la navette 1 et $1$ la navette 2, la navette d'arrivée est $a\oplus c$, et la lampe s'allume si $a\oplus c=b$, c'est-à-dire si $a\oplus b\oplus c=0$ : $$\ell =\overline{a\oplus b\oplus c}.$$

La lampe est allumée quand le nombre de commandes à $1$ est pair, et basculer n'importe laquelle change sa parité. Pour $n$ endroits, on met deux aiguillages aux extrémités et $n-2$ permutateurs en chaîne entre eux ; chaque permutateur basculé échange les navettes, et $$\ell =\overline{a_1\oplus a_2\oplus \cdots \oplus a_n}.$$ La lampe lit la parité du nombre d'interrupteurs basculés : c'est un OU exclusif à $n$ entrées, réalisé avec $4(n-1)$ contacts seulement (chaque aiguillage compte un contact repos et un contact travail, chaque permutateur deux aiguillages, soit quatre contacts).

5) L'aiguillage, multiplexeur. La borne commune est reliée à la borne repos, au niveau $b$, si $a=0$, et à la borne travail, au niveau $\overline{b}$, si $a=1$ : elle vaut $\overline{a}b+a\overline{b}=a\oplus b$. Un aiguillage dont les deux bornes reçoivent $e_0$ et $e_1$ délivre $\overline{a}{e}_0+a{e}_1$ : c'est le multiplexeur 2 vers 1 du cours, rencontré ici comme une simple association d'interrupteurs ; avec $e_0=b$ et $e_1=\overline{b}$, il calcule le OU exclusif.

6) Un facteur un milliard. $\frac{10\times 10^{-3}\mathrm{s}}{10\times 10^{-12}\mathrm{s}}=10^9$ : les tables de vérité d'un calculateur à relais de 1941 et d'un processeur actuel sont les mêmes ; seule la durée d'une commutation a été divisée par un milliard. C'est l'intérêt de la description par tables : elle ne dépend pas de la technologie de l'interrupteur.

Ce que l'exercice installe. Une spécification en mots se traduit en table, et la table nomme la porte : « basculer un interrupteur change toujours la lampe » ne laisse que XOR et XNOR. Un chemin conducteur est une série de contacts, l'ensemble des chemins leur parallèle : on lit ainsi la forme normale disjonctive complète sur le schéma. Et le OU exclusif à $n$ entrées est un détecteur de parité.