Booléens et addition binaire
Dresser la table de vérité d’une expression booléenne, découvrir le ou exclusif, et s’en servir pour programmer l’addition binaire de deux octets, comme le fait un circuit du processeur.
Un processeur additionne deux bits et . Combien de cas différents peut-il rencontrer ? Pour chacun, écrire le résultat de en base 2. Combien de bits faut-il pour écrire ce résultat ?
Tables de vérité
Un bit et un booléen sont deux façons de voir la même information : 1 correspond à True (vrai) et 0 à False (faux). En Python, int(True) vaut 1 et bool(0) vaut False.
Les opérateurs and, or et not ont été rencontrés dans le Doc. 2,3. Une expression booléenne qui dépend de deux variables et ne peut prendre que quatre combinaisons de valeurs d’entrée. On peut donc décrire complètement son comportement dans un tableau qui donne sa valeur pour chaque combinaison : sa table de vérité.
On écrit toutes les combinaisons des entrées, dans l’ordre où l’on compte en binaire (00, 01, 10, 11), puis la valeur de l’expression :
a and b |
||
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
a and b n’est vrai que si les deux entrées sont vraies.
Python peut produire ces tables à l’aide de deux boucles imbriquées :
- Dresser à la main la table de vérité de
a or bet celle denot a. - Vérifier la table de
a or ben modifiant le programme ci-dessus.
Dresser les tables de vérité de not (a and b) et de (not a) or (not b). Que constate-t-on ? Reformuler ce résultat par une phrase en français, en partant de : « Il est faux que et soient tous les deux vrais… ».
Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.
Combien de lignes compte la table de vérité d’une expression qui dépend de deux variables booléennes ?
Chaque variable a deux valeurs possibles : combinaisons, 00, 01, 10 et 11.
Pour quelles valeurs de et l’expression a or b vaut-elle 0 ?
a or b est vrai dès qu’au moins une des entrées est vraie.
Quelle expression est équivalente à not (a and b) ?
C’est une des lois de De Morgan : il est faux que et soient tous les deux vrais signifie qu’au moins l’un des deux est faux. (not a) and (not b) ne vaut 1 que si les deux sont faux.
Le ou exclusif
Dans la langue courante, « ou » a deux sens. « Fromage ou dessert » au restaurant signifie qu’on ne peut pas avoir les deux. L’opérateur or de Python, lui, est vrai aussi quand les deux entrées sont vraies : c’est un ou inclusif.
Le ou exclusif, noté xor (de l’anglais exclusive or), est vrai lorsqu’une seule des deux entrées est vraie, mais pas les deux.
- Dresser la table de vérité du ou exclusif.
- Pour deux booléens, le ou exclusif peut s’écrire
a != b. Expliquer pourquoi. - Écrire une expression qui donne le ou exclusif en n’utilisant que
and,oretnot. Vérifier sa table de vérité avec Python.
Traduire mot à mot : « ou est vrai, et il est faux que et soient vrais tous les deux ».
En Python, l’opérateur ^ calcule le ou exclusif de deux entiers égaux à 0 ou 1 : 1 ^ 1 vaut 0 et 1 ^ 0 vaut 1.
Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.
Quelles lignes de la table du ou exclusif valent 1 ?
Le ou exclusif est vrai lorsqu’une seule des deux entrées est vraie. La troisième proposition est la table de or, le ou inclusif.
Pour deux booléens a et b, quelles expressions donnent le ou exclusif ?
Le ou exclusif est vrai exactement quand les entrées sont différentes. a or b est aussi vrai quand les deux entrées sont vraies.
Que vaut 1 ^ 1 en Python ?
^ calcule le ou exclusif : les deux entrées sont égales, le résultat vaut 0. Ce n’est pas une puissance.
Additionner deux bits avec des opérateurs booléens
Compléter la table de l’addition de deux bits et , en séparant le résultat en deux bits : la somme (chiffre des unités) et la retenue. Comparer les deux colonnes de sortie aux tables de vérité déjà rencontrées.
| somme | retenue | ||
|---|---|---|---|
| 0 | 0 | ||
| 0 | 1 | ||
| 1 | 0 | ||
| 1 | 1 |
Pour additionner deux nombres de plusieurs bits, chaque colonne reçoit en plus la retenue venue de la colonne de droite. Il faut donc additionner trois bits. On peut démontrer que :
- la somme vaut xor xor ;
- la retenue sortante vaut 1 lorsqu’au moins deux des trois bits valent 1.
Vérifier ces deux règles sur la ligne , , , puis sur la ligne , , , en comparant avec le calcul écrit en base 2.
Écrire la fonction additionne_bits, qui retourne un tuple :
Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.
Lorsqu’on additionne deux bits et , quelles opérations donnent la somme (chiffre des unités) et la retenue ?
: la somme vaut 0 et la retenue 1. Seul le ou exclusif donne 0 pour la somme sur cette ligne.
On additionne trois bits , et . Que valent la somme et la retenue ?
. Avec les règles : xor xor , et deux bits valent 1, donc la retenue vaut 1.
Quelles expressions donnent la somme de trois bits a, b et r ?
(a + b + r) // 2 donne la retenue, pas la somme.
Additionner deux octets
On additionne deux octets comme on pose l’addition à la main (Doc. 4,2) : de la droite vers la gauche, en reportant la retenue d’une colonne sur la suivante. La retenue qui sort de la colonne de gauche est perdue, puisque le résultat est rangé sur 8 bits.
Pour parcourir les indices de droite à gauche, on utilise range avec trois arguments : range(7, -1, -1) produit 7, 6, 5, …, 0.
Écrire la fonction addition, qui doit utiliser additionne_bits :
- Avant la boucle : un résultat vide et une retenue nulle.
- Dans la boucle, pour l’indice
i: convertirbits1[i]etbits2[i]en entiers, appeleradditionne_bits, déballer le tuple obtenu. - Chaque nouveau chiffre se place à gauche du résultat déjà construit.
Dans le Doc. 4,3, s’écrit et s’écrit sur 8 bits.
- Prévoir le résultat de
addition("00000101", "11111011"), puis vérifier. - Calculer
addition("00000011", "11111011"). Quel entier relatif ce résultat représente-t-il ? Le calcul est-il juste ?
Recopier la fonction complement_a_1 du Doc. 4,3, puis écrire en une ligne la fonction complement_a_2 :
Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.
Que produit range(7, -1, -1) ?
On part de 7, on retire 1 à chaque fois, et la borne est exclue.
Que retourne addition("11111111", "00000001") ?
Toutes les colonnes produisent une retenue, et la retenue finale est perdue : c’est un dépassement de capacité.
En complément à 2 sur 8 bits, quel entier relatif représente le résultat de addition("00000011", "11111011"), c’est-à-dire de ?
Le résultat '11111110' commence par 1 : il est négatif et vaut . La même fonction additionne aussi les entiers négatifs.
Un détail qui compte : l’évaluation séquentielle
Dans le Doc. 2,3, on a vu que Python évalue a and b de gauche à droite et s’arrête dès que le résultat est connu : si a est faux, b n’est même pas évalué. De même, si a est vrai, a or b est vrai sans que b soit évalué. La table de vérité ne dit rien de cet ordre, mais il change le comportement d’un programme.
On exécute x = 0 dans la console. Prévoir le résultat de chacune des deux expressions, puis vérifier :
D’après leurs tables de vérité, ces deux expressions devraient être équivalentes. Pourquoi ne le sont-elles pas dans un programme ?
Répondez aux questions une par une ; le résultat s'affiche à la fin. Recommencez jusqu'à obtenir 100 % : vous pouvez aussi afficher les réponses, mais vous ne pourrez alors plus retenter ce QCM.
Avec x = 0, que donne x != 0 and 10 / x > 1 ?
x != 0 est faux : Python n’évalue pas la suite, et le résultat est False.
Avec x = 0, que donne 10 / x > 1 and x != 0 ?
Python évalue de gauche à droite : la division par zéro a lieu avant que la condition x != 0 soit examinée. On place en premier la condition qui protège la seconde.
Bilan
- associer les bits 0 et 1 aux booléens
FalseetTrue; - dresser la table de vérité d’une expression booléenne, à la main et avec deux boucles imbriquées ;
- reconnaître deux expressions équivalentes en comparant leurs tables de vérité ;
- définir le ou exclusif et l’écrire avec
!=,^ou les opérateursand,oretnot; - expliquer que la somme de deux bits est un ou exclusif et la retenue un
and; - programmer l’addition de deux octets en propageant la retenue, et constater qu’elle fonctionne aussi en complément à 2 ;
- expliquer pourquoi l’ordre des opérandes de
andet deorpeut éviter une erreur.
Dans le Doc. 4,5, on quitte les entiers pour les nombres à virgule, et on découvre pourquoi 0.1 + 0.2 n’est pas égal à 0.3.