De la logique à l'addition

De la logique à l'addition. L'algèbre de Boole, appliquée aux circuits par Shannon en 1937, est à la base de l'électronique numérique : un processeur additionne avec des portes logiques. On représente un bit par l'entier $0$ ou $1$, et on se donne trois portes :

def et(a, b):
    return a * b

def ou(a, b):
    return a + b - a * b

def oux(a, b):          # ou exclusif : 1 si a et b different
    return (a + b) % 2

• Un additionneur complet reçoit deux bits $a$, $b$ et une retenue entrante $r$, et renvoie le bit de somme $s$ et la retenue sortante $r^{\prime }$, de sorte que $a+b+r=s+2r^{\prime }$. Montrer que $s=(a\oplus b)\oplus r$ et $r^{\prime }=(a\text{ ET }b)\text{ OU }(r\text{ ET }(a\oplus b))$ conviennent, où $\oplus$ désigne le ou exclusif.
• Écrire additionneur_complet(a, b, r) qui renvoie le couple (s, r2), et le vérifier sur les huit cas.
• Un nombre de $n$ bits est représenté par la liste de ses bits, du poids fort au poids faible ([1, 0, 1, 1] pour $11$). Écrire additionner(x, y) qui additionne deux listes de même longueur en chaînant des additionneurs complets, et renvoie une liste ayant un bit de plus.
• Vérifier la fonction sur tous les couples de nombres de $4$ bits.