Deux conditions qui disent la même chose
Une table de vérité liste tous les cas possibles d’une condition, vrai ou faux, et le résultat de chacun. Elle permet de prouver que deux conditions sont équivalentes, par exemple avant de simplifier un if.
Une bibliothèque universitaire écrit : « Pas de prêt si la carte est périmée ou si le lecteur a un retard. » Un collègue réécrit la règle autrement. Disent-ils la même chose ? Une table répond sans deviner.
À la fin de cette leçon
Remarque
Je peux construire une table de vérité et décider si deux énoncés sont équivalents.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Proposition | une phrase qui est soit vraie, soit fausse | 7 est pair |
| Connecteur | un mot qui relie des propositions : et, ou, non | |
| Table de vérité | un tableau de tous les cas possibles et du résultat de chacun | |
| Implication | la phrase « si p alors q » | |
| Équivalence | deux formules qui ont exactement la même table | |
| Contre-exemple | un cas où deux formules donnent des résultats différents |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un connecteur combine des propositions
Une proposition est vraie ou fausse, jamais entre les deux. « Le fichier existe » en est une.
Le connecteur « et » est vrai quand les deux côtés sont vrais. Le connecteur « ou » est vrai dès qu’un côté l’est. Le connecteur « non » renverse la valeur.
Une table de vérité liste les quatre cas pour deux propositions p et q.
Exemple travaillé : et, ou, non
| p | q | p et q | p ou q | non p |
|---|---|---|---|---|
| Faux | Faux | Faux | Faux | Vrai |
| Faux | Vrai | Faux | Vrai | Vrai |
| Vrai | Faux | Faux | Vrai | Faux |
| Vrai | Vrai | Vrai | Vrai | Faux |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Le connecteur non, deux cas
python3 -c "for p in (False, True): print(p, not p)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Une implication n’est fausse que dans un cas
L’implication « si p alors q » est une promesse. Elle n’est brisée que si p arrive et que q ne suit pas.
Exemple : « S’il pleut, le match est annulé. » Il ne pleut pas et le match a lieu : la promesse est tenue. Il pleut et le match a lieu : la promesse est brisée.
Exemple travaillé : si p alors q
| p : il pleut | q : match annulé | Si p alors q | La promesse est… |
|---|---|---|---|
| Faux | Faux | Vrai | tenue, il ne pleut pas |
| Faux | Vrai | Vrai | tenue, rien n’était promis |
| Vrai | Faux | Faux | brisée |
| Vrai | Vrai | Vrai | tenue |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Les quatre cas de l’implication
python3 -c "print([(p, q, (not p) or q) for p in (False, True) for q in (False, True)])"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
Beaucoup pensent qu’une implication est fausse quand p est faux. C’est l’inverse. Si p est faux, la promesse n’est pas mise à l’épreuve, donc elle est vraie. Un seul cas la rend fausse : p vrai et q faux.
Deux tables identiques : formules équivalentes
Pour comparer deux formules, on remplit la table de chacune sur les mêmes quatre lignes. Si toutes les lignes sont identiques, les formules sont équivalentes. Une seule ligne différente suffit pour dire non : c’est un contre-exemple.
Une loi célèbre dit que « non (p et q) » équivaut à « non p ou non q ». Lisez-la sur le code ci-dessous.
Comparer deux formules ligne par ligne
# Deux formules sont équivalentes si leurs quatre résultats sont les mêmes.
def formule_a(p, q):
return not (p and q)
def formule_b(p, q):
return (not p) or (not q)
for p in [False, True]:
for q in [False, True]:
print(p, q, formule_a(p, q), formule_b(p, q))
# Changez formule_b en (not p) and (not q) puis relancez : une ligne diffère.
Vérifier la loi en une ligne
python3 -c "print([(not (p and q)) == ((not p) or (not q)) for p in (False, True) for q in (False, True)])"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Une preuve par cas examine chaque situation
Quand les cas sont peu nombreux, on les prend tous. Montrons que n(n+1) est toujours pair.
Premier cas : n est pair, donc le produit contient un facteur pair. Second cas : n est impair, donc n+1 est pair et le produit contient encore un facteur pair. Il n’y a pas de troisième cas : la preuve est complète.
Tester la preuve sur huit nombres
python3 -c "print([n * (n + 1) % 2 for n in range(8)])"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Pour aller plus loin
Modifiez la ligne de la loi dans le terminal : remplacez or par and dans la partie de droite. Dites avant de lancer combien de False la liste affichée contiendra.
Puis écrivez « si p alors q » avec seulement not et or, et comparez-la à p <= q en Python : les deux donnent les mêmes quatre résultats.