Exercices – Tables de vérité et équivalences
BTS SIO SISR 1re année – Mathématiques pour l'informatique – S08
Note
Comment travailler. Cherche d'abord sur papier, avec la méthode du cours : écris les étapes, pas seulement le résultat. Ouvre ensuite « Voir la réponse » pour te corriger. À l'épreuve, aucune réponse sans justification n'est complète.
Exercice 1 – Propositions ?
Parmi les énoncés suivants, lesquels sont des propositions ? Donner la valeur de vérité de celles qui en sont.
- « 2 024 est divisible par 8. »
- « Ferme la porte. »
- « \(n\) est un nombre premier. »
- « Tout entier pair supérieur à 2 n'est pas premier. »
- « Le port 443 est utilisé par HTTPS. »
Voir la réponse
- Proposition, vraie : \(2\,024 = 8 \times 253\).
- Pas une proposition (ordre).
- Pas une proposition : sa valeur dépend de \(n\) (prédicat).
- Proposition, vraie : un pair supérieur à 2 est divisible par 2 avec un quotient supérieur à 1.
- Proposition, vraie (convention d'usage du protocole HTTPS).
Exercice 2 – Tables de vérité
Construire la table de vérité de \((p \Rightarrow q) \wedge (q \Rightarrow p)\) et la comparer à celle de \(p \Leftrightarrow q\).
Voir la réponse
| \(p\) | \(q\) | \(p \Rightarrow q\) | \(q \Rightarrow p\) | \((p \Rightarrow q) \wedge (q \Rightarrow p)\) | \(p \Leftrightarrow q\) |
|---|---|---|---|---|---|
| F | F | V | V | V | V |
| F | V | V | F | F | F |
| V | F | F | V | F | F |
| V | V | V | V | V | V |
Les deux dernières colonnes sont identiques.
Exercice 3 – Équivalences
Montrer par table de vérité : (a) \(\neg(p \vee q) \equiv \neg p \wedge \neg q\) ; (b) \(p \Rightarrow q \equiv \neg q \Rightarrow \neg p\) ; (c) \(p \Rightarrow q\) n'est pas équivalente à \(q \Rightarrow p\).
Voir la réponse
(a)
| \(p\) | \(q\) | \(\neg(p \vee q)\) | \(\neg p \wedge \neg q\) |
|---|---|---|---|
| F | F | V | V |
| F | V | F | F |
| V | F | F | F |
| V | V | F | F |
(b)
| \(p\) | \(q\) | \(p \Rightarrow q\) | \(\neg q \Rightarrow \neg p\) |
|---|---|---|---|
| F | F | V | V |
| F | V | V | V |
| V | F | F | F |
| V | V | V | V |
(c)
| \(p\) | \(q\) | \(p \Rightarrow q\) | \(q \Rightarrow p\) |
|---|---|---|---|
| F | F | V | V |
| F | V | V | F |
| V | F | F | V |
| V | V | V | V |
Les colonnes diffèrent pour \((p, q) = (F, V)\) et \((V, F)\).
Exercice 4 – Tautologie ?
Les expressions suivantes sont-elles des tautologies ? (a) \(((p \Rightarrow q) \wedge p) \Rightarrow q\) ; (b) \((p \vee q) \Rightarrow p\) ; (c) \(p \vee \neg p\).
Voir la réponse
(a) Tautologie (modus ponens).
| \(p\) | \(q\) | \(p \Rightarrow q\) | \((p \Rightarrow q) \wedge p\) | \(((p \Rightarrow q) \wedge p) \Rightarrow q\) |
|---|---|---|---|---|
| F | F | V | F | V |
| F | V | V | F | V |
| V | F | F | F | V |
| V | V | V | V | V |
(b) Pas une tautologie : pour \(p\) faux et \(q\) vrai, \(p \vee q\) est vrai et \(p\) est faux, donc l'implication est fausse.
(c) Tautologie : si \(p\) est vrai le « ou » est vrai, sinon \(\neg p\) est vrai.
Exercice 5 – Réciproque et contraposée
On considère : « Si un compte est administrateur, alors il peut installer des logiciels. »
- Écrire la réciproque, la contraposée et la négation.
- Laquelle de ces trois propositions a la même valeur de vérité que l'énoncé de départ ?
- L'énoncé suivant est-il équivalent : « Si un compte ne peut pas installer de logiciels, alors ce n'est pas un administrateur » ?
Voir la réponse
- Réciproque : « si un compte peut installer des logiciels, alors il est administrateur ». Contraposée : « si un compte ne peut pas installer de logiciels, alors il n'est pas administrateur ». Négation : « il existe un compte administrateur qui ne peut pas installer de logiciels » (c'est \(p \wedge \neg q\)).
- La contraposée est équivalente à l'énoncé de départ.
- Oui, c'est exactement la contraposée.
Exercice 6 – Négation de conditions
Écrire la négation de chaque condition en supprimant le « non » devant la parenthèse (De Morgan), puis l'écrire en Python.
- \(\neg(a > 3 \wedge b \le 5)\)
- \(\neg(\text{port} = 22 \vee \text{port} = 3389)\)
- \(\neg(\text{age} \ge 18 \wedge \text{age} < 65)\)
Voir la réponse
- \(a \le 3 \vee b > 5\) ;
a <= 3 or b > 5. - \(\text{port} \ne 22 \wedge \text{port} \ne 3389\) ;
port != 22 and port != 3389. - \(\text{age} < 18 \vee \text{age} \ge 65\) ;
age < 18 or age >= 65.
On passe de \(\wedge\) à \(\vee\) (et inversement) et on nie chaque comparaison : \(>\) devient \(\le\), \(=\) devient \(\ne\), \(\ge\) devient \(<\).
Exercice 7 – Règle de pare-feu
La règle est : « autoriser si (protocole TCP et port 80 ou 443) ou protocole ICMP », notée \((t \wedge (a \vee b)) \vee i\). Donner la décision pour chacun des paquets suivants.
| Protocole | Port |
|---|---|
| TCP | 80 |
| TCP | 443 |
| TCP | 22 |
| ICMP | 0 |
| UDP | 53 |
| UDP | 443 |
Voir la réponse
| Protocole | Port | \(t\) | \(a \vee b\) | \(i\) | Autorisé ? |
|---|---|---|---|---|---|
| TCP | 80 | V | V | F | V |
| TCP | 443 | V | V | F | V |
| TCP | 22 | V | F | F | F |
| ICMP | 0 | F | F | V | V |
| UDP | 53 | F | F | F | F |
| UDP | 443 | F | V | F | F |
Remarque : (UDP, 443) est refusé, car la règle ne mentionne TCP que pour les ports 80 et 443 (HTTP/3 utilise UDP : une règle plus large serait nécessaire pour l'autoriser).
Exercice 8 – Deux règles équivalentes ?
Règle A : « refuser si non (source interne et port = 22) ». Règle B : « refuser si source externe ou port ≠ 22 ». Sont-elles équivalentes ?
Voir la réponse
Notons \(s\) : « source interne » et \(w\) : « port = 22 ». Règle A : \(\neg(s \wedge w)\). Règle B : \(\neg s \vee \neg w\). D'après De Morgan, \(\neg(s \wedge w) \equiv \neg s \vee \neg w\) : les deux règles sont équivalentes.
| \(s\) | \(w\) | \(\neg(s \wedge w)\) | \(\neg s \vee \neg w\) |
|---|---|---|---|
| F | F | V | V |
| F | V | V | V |
| V | F | V | V |
| V | V | F | F |
Exercice 9 – Condition de boucle
- Quand la boucle s'arrête-t-elle ? (utiliser De Morgan)
- Dérouler pour
t = [4, 8, 15], \(n = 3\), \(x = 15\), puis \(x = 7\). - Que se passerait-il si on avait écrit
t[i] ≠ x ET i < npour \(x = 7\) ?
Voir la réponse
- Elle s'arrête quand \(\neg(i < n \wedge t[i] \ne x) \equiv i \ge n \vee t[i] = x\) : tableau épuisé ou valeur trouvée.
- Pour \(x = 15\) :
i |
i < n |
t[i] != x |
Condition | Action |
|---|---|---|---|---|
| 0 | V | V | V | i ← i + 1 |
| 1 | V | V | V | i ← i + 1 |
| 2 | V | F | F | arrêt |
La boucle s'arrête avec \(i = 2\) : x est trouvé à l'indice 2. Pour \(x = 7\) :
i |
i < n |
t[i] != x |
Condition | Action |
|---|---|---|---|---|
| 0 | V | V | V | i ← i + 1 |
| 1 | V | V | V | i ← i + 1 |
| 2 | V | V | V | i ← i + 1 |
| 3 | F | — | F | arrêt |
La boucle s'arrête avec \(i = 3 = n\) : x est absent.
3. Au dernier tour, \(i = 3\) : on évaluerait t[3] avant de tester i < n, c'est un accès hors du tableau (erreur d'indice). L'ordre des conditions est donc essentiel.
Exercice 10 – Combien de tables ?
- Combien de lignes a la table de vérité d'une expression à 4 variables ? à \(n\) variables ?
- Combien existe-t-il de fonctions différentes de deux variables booléennes ?
Voir la réponse
- \(2^4 = 16\) lignes ; \(2^n\) lignes.
- Une fonction de deux variables est définie par sa colonne de résultats, qui a 4 lignes, chacune valant V ou F : \(2^4 = 16\) fonctions possibles (parmi lesquelles \(\wedge\), \(\vee\), \(\Rightarrow\), \(\Leftrightarrow\), \(\oplus\), et leurs négations).
Je sais faire
Coche honnêtement ; ce que tu ne coches pas se reprend avant la séance suivante.
- Construire une table de vérité à 2 ou 3 variables ;
- Prouver une équivalence par table ;
- Écrire la négation et la contraposée d'une implication ;
- Reconnaître une tautologie ;
- Traduire une règle en expression logique.
Ce que je dois reprendre : ______________________
Ma question à poser à l'enseignant : ______________________