Chapitre 2 : Booléens⚓︎
Partie A - Valeurs, variables et expressions booléennes⚓︎
Définitions et premiers exemples⚓︎
Il existe deux valeurs booléennes, qui sont Vrai (en Python, True ou 1) et Faux (en Python, False ou 0).
Une variable booléenne est une variable dont la valeur est booléenne et une expression booléenne est une expression dont la valeur est booléenne.
Les expressions booléennes apparaissent dans la définition des instructions conditionnelles (if expression_booleenne:) et des boucles non bornées (while expression_booleenne:).
Exercice 2-01 : Variables et expressions booléennes
Objectif : Repérer les variables booléennes et les expressions booléennes dans un code.
Carnet Jupyter à télécharger ici
Carnet Jupyter accessible sur CAPYTALE
Corrigé disponible ici
Activité 2-02 : Conjecture de Syracuse
Objectifs :
- Retravailler les instructions conditionnelles et les boucles.
- Utiliser des expressions booléennes pour étudier un problème mathématique célèbre.
Carnet Jupyter à télécharger ici
Carnet Jupyter accessible sur CAPYTALE
Corrigé disponible ici
Partie B - Opérateurs logiques et tables de vérité⚓︎
Opérateurs logiques non, et, ou, xor⚓︎
Nous avons vu comment utiliser des expressions booléennes simples telles que n == 0, s != 1, -1 <= n <= 2 ou encore s % 2 == 0.
Mais il est parfois nécessaire d'écrire des expressions booléennes plus complexes, composées de plusieurs expressions booléennes reliées entre elles pas des opérateurs logiques. Nous utiliserons quatre opérateurs en particulier : la négation (opérateur non), la conjonction (opérateur et), la disjonction inclusive (opérateur ou) et la disjonction exclusive (opérateur xor encore appelé ou exclusif).
| Opérateur | Nom commun | Mot clé Python |
|---|---|---|
| Négation | non | not |
| Conjonction | et | and |
| Disjonction inclusive | ou (ou inclusif) | or |
| Disjonction exclusive | xor (ou exclusif) | ^ |
Tables de vérité⚓︎
Une table de vérité est un tableau dans lequel apparait la valeur d'une expression booléenne en fonction des valeurs prises par les variables booléennes contenues dans l'expression.
On donne ci-dessous la table de vérité des expressions not A, A and B, A or B, A ^ B.
Table de vérité des opérateurs non, et, ou et xor
Exercice 2-03 : Table de vérité d'expressions booléennes
Objectif : Dresser la table de vérité d'une expression booléenne dépendant de deux ou trois variables booléennes.
Énoncé
1. a et b étant deux variables booléennes, dresser la table de vérité de l'expression (not a) or (a and b).
2. a, b et c étant trois variables booléennes, dresser la table de vérité de l'expression (a or c) and (b or (not c)).
Activité 2-04 : Circuits logiques
Objectif : Comprendre comment un circuit logique peut représenter une expression booléenne.
Énoncé
Un circuit logique est un dispositif électronique qui permet de réaliser des opérations booléennes en combinant des entrées, des sorties et des portes logiques (liées aux opérateurs booléens).
Un point donné du circuit ne peut avoir que deux états : 1 (correspondant à un niveau haut de tension électrique) ou 0 (correspondant à un niveau bas de tension électrique).
L'utilisation d'un interrupteur en entrée permet de passer d'un état à l'autre et donc de matérialiser une variable booléenne. L'utilisation d'une lampe en sortie permet de visualiser l'état.
1. Identifier, dans chaque cas, quelle est l'entrée et quelle est la sortie du circuit logique suivant :
On donne maintenant le circuit logique suivant dans lequel apparaissent quatre portes logiques reliées chacune à une lampe. On a utilisé deux interrupteurs pour matérialiser deux variables booléennes en entrée.
2. Simuler le fonctionnement de ce circuit sur le site Logic gate simulator en chargeant le fichier portes_logiques.json téléchargeable ici.
3. En déduire quelle porte logique est associée à quel opérateur booléen.
4. Déterminer une expression booléenne correspondant à la sortie du circuit logique ci-dessous. On appelle a la variable booléenne associée à l'interrupteur du bas et b celle associée à l'interrupteur du haut.
5. Créer, sur le site Logic gate simulator, un circuit correspondant à l'expression booléenne (a ^ b) or (not a and not b).
6. Sur le même schéma, ajouter un second circuit correspondant à l'expression booléenne not (a and b).
Partie C - Exercices et activités⚓︎
Exercices 2-05 à 2-07
Énoncé
Un vol de bijoux a été commis et quatre hommes sont suspects. Un seul est coupable, un deuxième est son complice et les deux autres sont innocents.
Voici le signalement des quatre suspects :
| Nom du suspect | Moustache | Lunettes | Cicatrice | Boucle d'oreilles |
|---|---|---|---|---|
| Donatello | oui | oui | non | non |
| Leonardo | oui | non | non | oui |
| Michelangelo | non | non | oui | oui |
| Raffaello | non | oui | oui | non |
Lors de leur interrogatoire, les suspects déclarent :
- Donatello : "Le coupable a une cicatrice ou une boucle d'oreille mais pas les deux !"
- Leonardo : "Le coupable a des lunettes !"
- Michelangelo : "Le coupable a une moustache ou des lunettes mais pas les deux !"
- Raffaello : "Le coupable n'a pas de cicatrice !"
Sachant que le coupable et son complice mentent et que les deux innocents disent la vérité, déterminer qui est le coupable et qui est son complice.
Corrigé
Le tableau ci-dessous indique, pour chaque coupable potentiel, quels suspects disent la vérité ou mentent.
| Nom du coupable potentiel | Témoignage de Donatello | Témoignage de Leonardo | Témoignage de Michelangelo | Témoignage de Raffaello | Nombre de menteurs |
|---|---|---|---|---|---|
| Donatello | mensonge | vérité | mensonge | vérité | 2 |
| Leonardo | vérité | mensonge | vérité | vérité | 1 |
| Michelangelo | mensonge | mensonge | mensonge | mensonge | 4 |
| Raffaello | vérité | vérité | vérité | mensonge | 1 |
La seule situation où il y a exactement deux menteurs est celle où Donatello est le coupable. Son complice est donc le second menteur, Michelangelo.
Énoncé
1. a et b et c étant trois variables booléennes, dresser la table de vérité de l'expression (a ^ b) and (not a or c).
2. Représenter l'expression de la question précédente sous forme de circuit logique sur le site Logic gate simulator.
Énoncé
Soient a, b et c trois variables booléennes.
1. Déterminer une forme simplifiée de l'expression booléenne a or (not a and b).
2. Même question pour l'expression booléenne (a or b) and (a or not b).
3. Même question pour l'expression booléenne (not a or b) and (a or b or c) and not c.
Activités 2-08 à 2-10
Objectif : S'entraîner à manipuler les opérateurs logiques.
Boolean Game
Pouvez-vous dépasser les 40 points au jeu Boolean Game ?
Objectifs :
- Comprendre le fonctionnement d'un circuit logique donné.
- Comprendre comment un circuit logique permet d'additionner deux entiers.
Énoncé
1. Dresser la table de vérité du demi-additionneur représenté ci-dessous, en indiquant la valeur des deux sorties en fonction de la valeur des deux entrées.
Il est possible de simuler le comportement du demi-additionneur sur le site Logic gate simulator en chargeant le fichier demi_additionneur.json téléchargeable ici.
2. En déduire une justification du fait que le demi-additionneur permet d'additionner deux bits.
3. Expliquer en quoi le circuit ci-dessous, appelé additionneur complet, permet d'additionner trois bits.
Il est possible de simuler le comportement de l'additionneur complet sur le site Logic gate simulator en chargeant le fichier additionneur_complet.json téléchargeable ici.
4. Sur le schéma de l'additionneur 4 bits ci-dessous, identifier :
- les deux entrées composées de quatre bits chacune,
- les deux sorties : la première composée de quatre bits, la seconde d'un bit unique (retenue),
- les quatre additionneurs complets utilisés,
- les quatre retenues obtenues au cours du calcul.
5. Représenter en rouge les liaisons par lesquelles le courant passe lorsqu'on effectue l'addition 6 + 5.
6. Même question pour l'addition 12 + 5.
Objectifs :
- Déterminer des expressions booléennes à partir de tables de vérité.
- Représenter des expressions booléennes sous forme de circuits logiques.
- Comprendre comment afficher un chiffre hexadécimal sur un afficheur 7 segments.
Énoncé
Un afficheur 7 segments permet d'afficher un chiffre en activant ou désactivant chacun des sept segments qui le composent.
Première partie : cas des chiffres de 0 et 1
Les deux chiffres 0 et 1 se représentent sur un seul bit, qu'on peut associer à une variable booléenne a.
a vaut False pour le chiffre 0. a vaut True pour le chiffre 1.
1. Déterminer, en fonction de la valeur de a, si chacun des sept segments de l'afficheur doit être activé ou pas.
On peut créer un circuit logique qui illustre les sept expressions booléennes trouvées à la question précédente.
2. Simuler le comportement de ce circuit sur le site Logic gate simulator en chargeant le fichier afficheur_1bit.json téléchargeable ici.
Deuxième partie : cas des chiffres de 0 à 3
Les quatre chiffres de 0 à 3 se représentent sur deux bits, qu'on peut associer à deux variables booléennes : a pour le bit de poids fort et b pour le bit de poids faible.
3. Déterminer, en fonction des valeurs de a et b, si chacun des sept segments de l'afficheur doit être activé ou pas.
On peut créer un circuit logique qui illustre les sept expressions booléennes trouvées à la question précédente.
4. Compléter ce circuit puis simuler son comportement sur le site Logic gate simulator après avoir chargé le fichier afficheur_2bits_vierge.json téléchargeable ici.
Troisième partie : cas des seize chiffres hexadécimaux
Les seize chiffres hexadécimaux se représentent sur quatre bits, qu'on peut associer à quatre variables booléennes a, b, c et d : a pour le bit de poids le plus fort et d pour le bit de poids le plus faible.
5. Après avoir dressé la table de vérité de l'expression booléenne (a and d) or (c and (a or not b or not d)) or ((a ^ b) and not c), justifier que cette expression permet l'activation du segment central pour l'affichage des seize chiffres hexadécimaux.
6. Déterminer une expression booléenne (en fonction des variables a, b, c et d) permettant l'activation du segment situé en bas à gauche pour l'affichage des seize chiffres hexadécimaux.
Ce qu'il faut savoir et savoir faire⚓︎
- Repérer variables booléennes et expressions booléennes dans un algorithme ou un programme.
- Écrire une expression booléenne complexe en utilisant les opérateurs
non,et,ou,xor. - Donner la table de vérité des opérateurs
non,et,ou,xor. - Donner la table de vérité d'une expression booléenne complexe contenant des variables booléennes.
- Faire le lien entre une expression booléenne complexe contenant des variables booléennes et un circuit de portes logiques.
- Utiliser les opérateurs
//(quotient de la division euclidienne),%(reste de la division euclidienne) et**(puissance). - Mesurer le temps moyen d'exécution d'une cellule de carnet Jupyter à l'aide de l'outil Time it.