17 - Booléens et logique

Cours associé : 07 - Booléens .

Exercice 1 : QCM – vérification des prérequis

Pour chaque question, une seule réponse est correcte.

1. Quelle est la valeur de True and False ?

• A. True
• B. False
• C. None
• D. Erreur

Correction publiée après la séance.

2. Quelle est la table de vérité de l’opérateur OU ?

• A. OU ne vaut True que si les deux entrées sont True
• B. OU ne vaut True que si une seule des deux entrées est True
• C. OU vaut True dès qu’au moins une des deux entrées est True
• D. OU vaut True uniquement si les deux entrées sont différentes

Correction publiée après la séance.

3. Que vaut not(True or False) ?

• A. True
• B. False
• C. not True
• D. Erreur

Correction publiée après la séance.

4. En Python, le ET logique est noté :

• A. &&
• B. AND
• C. and
• D. &

Correction publiée après la séance.

Exercice 2 : table de vérité

On veut la table de vérité de l’expression $\overline{x} \text{ ou } y$, qui s’écrit not x or y en Python.

1. Combien de lignes la table comporte-t-elle ? Pourquoi ?

   Indice

   Chaque variable vaut 0 ou 1 : combien de couples $(x, y)$ différents peut-on former ?

2. Recopier et compléter le tableau. On calcule d’abord la colonne $\overline{x}$, puis on applique le OU entre cette colonne et la colonne $y$.

3. Pour quelle ligne l’expression est-elle fausse ?

4. On considère la phrase « si $x$ est vrai, alors $y$ est vrai ». Dans quel cas cette phrase est-elle fausse ? Comparer avec la réponse à la question 3.

   Indice

   Quand une promesse « si $x$, alors $y$ » est-elle rompue ? Envisager les quatre cas possibles pour $x$ et $y$.

Correction publiée après la séance.

Exercice 3 : tables de vérité guidées

3.1 Tables de base

Compléter les tables de vérité des opérateurs NON ET (NAND) et OU exclusif (XOR).

NAND : $\overline{x \text{ et } y}$

XOR : vrai si exactement un des deux est vrai

Correction publiée après la séance.

3.2 Expression composée

Construire la table de vérité de $(x \text{ et } \overline{y}) \text{ ou } (\overline{x} \text{ et } y)$ en suivant la méthode de l’exercice 2 (une colonne par sous-expression).

Comparer la dernière colonne avec la table du XOR (exercice 3.1). Que constate-t-on ?

Correction publiée après la séance.

Exercice 4 : lois de De Morgan

Les lois de De Morgan sont deux identités fondamentales :

$$\overline{x \text{ ou } y} = \overline{x} \text{ et } \overline{y}$$ $$\overline{x \text{ et } y} = \overline{x} \text{ ou } \overline{y}$$

1. Démontrer la seconde loi à l’aide d’une table de vérité.

   Indice

   Une colonne par sous-expression, comme à l’exercice 2 : d’abord $x \text{ et } y$ puis sa négation, ensuite $\overline{x}$, $\overline{y}$ et leur OU. Comparer enfin les deux colonnes obtenues.

2. Vérifier les deux lois en Python pour toutes les combinaisons de x et y.

   Indice

   Deux boucles for imbriquées parcourent [False, True], l’une pour x, l’autre pour y ; un assert vérifie chaque égalité. Attention : not s’applique après ==, et not a == b se lit not (a == b) ; d’où les parenthèses autour de chaque négation.

   Code à copier puis compléter

   for x in [False, True]:
       for y in [False, True]:
           assert (not (x or y)) == (...)
           assert (...) == (not x or not y)
   print("Les deux lois de De Morgan sont vérifiées.")
   

Correction publiée après la séance.

Exercice 5 : logique et vie courante

5.1 Système d’alarme (sécurité)

Un système de sécurité déclenche l’alarme si la porte et la fenêtre sont ouvertes, ou si le détecteur de mouvement est activé. On note $P$ (porte ouverte), $F$ (fenêtre ouverte), $M$ (mouvement détecté) et $A$ (alarme).

1. Écrire l’expression booléenne de $A$ en fonction de $P$, $F$ et $M$.

   Indice

   Traduire la phrase mot à mot : « et » devient ET, « ou » devient OU, et des parenthèses regroupent la condition sur la porte et la fenêtre.

2. Dresser la table de vérité (huit lignes).

   Indice

   Énumérer les valeurs de $P$, $F$, $M$ comme on compte en binaire, de 000 à 111, et ajouter une colonne intermédiaire $P \text{ et } F$.

3. Dans quels cas l’alarme ne se déclenche-t-elle pas ?

Correction publiée après la séance.

5.2 Conditions d’accès à un manège (loisirs)

Un manège autorise l’accès si l’enfant a au moins 10 ans ou mesure au moins 140 cm. De plus, un accompagnateur adulte est requis si l’enfant a moins de 12 ans. On note $G$ (âge ≥ 10), $T$ (taille ≥ 140), $J$ (âge < 12).

1. Écrire l’expression booléenne de l’accès autorisé : $A = G \text{ ou } T$.

2. Écrire l’expression de l’accompagnateur requis : $C = A \text{ et } J$.

3. Un enfant de 11 ans mesurant 135 cm peut-il monter ? Un accompagnateur est-il nécessaire ?

   Indice

   Calculer d’abord $G$, $T$ et $J$ pour cet enfant, puis $A$, et enfin $C$.

Correction publiée après la séance.

5.3 Simplification de conditions en Python (programmation)

Les lois de la logique permettent de simplifier des conditions complexes dans un programme. Pour chacune des conditions suivantes, écrire une condition équivalente simplifiée, puis vérifier en Python que les deux formes donnent le même résultat pour toutes les combinaisons de valeurs.

1. not(age >= 18 and solde >= 0)
2. not(note < 10 or absent)
3. not(not inscrit or not majeur)

Correction publiée après la séance.

Exercice 6 : multiplexeur et porte logique

6.1 Multiplexeur

On définit $\text{mux}(x,y,z) = (\overline{x} \text{ et } y) \text{ ou } (x \text{ et } z)$.

Compléter la table de vérité :

Que fait cette fonction ? (Quel rôle joue $x$ ?)

Correction publiée après la séance.

Exercice 7 : synthèse – simplification et énigme logique

7.1 Simplification avec l’algèbre de Boole

Simplifier les expressions suivantes en utilisant les propriétés de l’algèbre de Boole (absorption, De Morgan, distributivité).

1. $A = a + a \cdot b$

   Indice

   Mettre $a$ en facteur : $a + a \cdot b = a \cdot (1 + b)$. Que vaut $1 + b$ ?

2. $C = a + \overline{a} \cdot b$

   Indice

   Utiliser la distributivité de l’addition sur le produit : $x + y \cdot z = (x + y) \cdot (x + z)$. Que vaut $a + \overline{a}$ ?

Correction publiée après la séance.

7.2 Énigme logique (raisonnement)

Sur la planète CSI vivent les Profs (qui disent toujours la vérité) et les Élèves (qui mentent toujours). Vous croisez deux personnes A et B. A affirme : « Au moins l’un de nous deux est un élève. »

Déterminer ce que sont A et B.

Correction publiée après la séance.

Exercice 8 : table de vérité du XNOR

La fonction XNOR (NON OU exclusif) est définie par $a \odot b = \overline{a \oplus b}$.

1. Construire la table de vérité de $a \odot b$ (colonnes $a$, $b$, $a \oplus b$, $a \odot b$).

2. À quelle condition a-t-on $a \odot b = 1$ ?

   Indice

   Lire les lignes où $a \odot b$ vaut 1 : que remarque-t-on sur les valeurs de $a$ et de $b$ ?

3. Montrer que $a \odot b = a \cdot b + \overline{a} \cdot \overline{b}$.

   Indice

   Calculer $a \cdot b + \overline{a} \cdot \overline{b}$ sur chacune des quatre lignes, puis comparer avec la colonne $a \odot b$.

Correction publiée après la séance.

Exercice 9 : le théorème du consensus

Le théorème du consensus affirme que $a \cdot b + \overline{a} \cdot c + b \cdot c = a \cdot b + \overline{a} \cdot c$.

1. Vérifier cette égalité à l’aide d’une table de vérité à huit lignes (colonnes $a$, $b$, $c$, $a \cdot b$, $\overline{a} \cdot c$, $b \cdot c$, membre de gauche, membre de droite).

2. Expliquer sans table pourquoi le terme $b \cdot c$ est redondant.

   Indice

   Supposer $b \cdot c = 1$ : que valent alors $b$ et $c$ ? Examiner les deux cas $a = 1$ et $a = 0$ : l’un des deux autres termes vaut-il déjà 1 ?

Correction publiée après la séance.

Exercice 10 : profs et élèves

Sur la planète CSI vivent des Profs, qui disent toujours la vérité, et des Élèves, qui mentent toujours. Vous croisez deux habitants A et B. A affirme : « Au moins l’un de nous deux est un élève. »

1. On note $a$ le booléen qui vaut 1 si A est un Prof et 0 si A est un Élève, et de même $b$ pour B. Écrire l’expression logique de l’affirmation de A.

   Indice

   « A est un élève » s’écrit $\overline{a}$, et « au moins l’un des deux » se traduit par un OU.

2. Si A est un Prof, son affirmation est vraie : qu’en déduire sur B ?

3. Si A est un Élève, son affirmation est fausse : que se passe-t-il ?

   Indice

   Remplacer $a$ par 0 dans l’expression de la question 1 : que vaut-elle, quelle que soit la valeur de $b$ ? Est-ce compatible avec un menteur ?

4. Conclure : que sont A et B ?

Correction publiée après la séance.

Exercice 11 : conditions d’accès

Un système de sécurité autorise l’accès si l’utilisateur a un badge valide et entre un code correct, ou s’il est administrateur (quels que soient le badge et le code). On note $B$ « badge valide », $C$ « code correct » et $A$ « administrateur ».

1. Écrire l’expression logique de la condition d’accès.

   Indice

   Traduire mot à mot, comme à l’exercice 5.1 : « et » devient $\cdot$, « ou » devient $+$.

2. Construire sa table de vérité (huit lignes).

3. Peut-on simplifier l’expression ? Que signifie la propriété d’absorption $A + A \cdot X = A$ pour ce système ?

   Indice

   Chaque variable n’apparaît qu’une fois dans l’expression : peut-on en retirer une sans changer la table ? Pour l’absorption, imaginer qu’on ajoute la condition « administrateur avec un badge valide », $A \cdot B$.

Correction publiée après la séance.

Exercice 12 : comparateur 1 bit

On souhaite concevoir un circuit qui compare deux bits $a$ et $b$ et produit trois sorties : $S$ vaut 1 si $a > b$, $E$ vaut 1 si $a = b$, $I$ vaut 1 si $a < b$.

1. Compléter la table de vérité (colonnes $a$, $b$, $S$, $E$, $I$).

2. Donner l’expression booléenne de chacune des sorties.

   Indice

   Pour chaque sortie, repérer les lignes où elle vaut 1 et écrire pour chacune un produit ($a$ ou $\overline{a}$, $b$ ou $\overline{b}$), puis faire la somme de ces produits.

3. Quelle relation lie $S$, $E$ et $I$ ?

   Indice

   Sur chaque ligne de la table, combien de sorties valent 1 ?

Correction publiée après la séance.