Un précédent article introduisait la table de vérité, ainsi que les opérateurs négation, disjonction et conjonction.
Le but de celui-ci est de venir le compléter, en présentant les définitions d’implication et équivalence, et faire quelques exercices pour s’habituer à manipuler les équivalences.
Implication
L’implication de deux phrases est noté “ A \Rightarrow B” ou symétriquement “ B \Leftarrow A “, qui se lit “A implique B”. Elle est défini comme prenant les mêmes valeurs de vérité que “non A ou B “.
Il est courant d’utiliser la structure “Si … alors … ” dans la langue française, et c’est exactement de cela qu’il s’agit.
| A | B | non A | non A ou B | A => B (par définition) |
| Vrai | Vrai | Faux | Vrai | Vrai |
| Vrai | Faux | Faux | Faux | Faux |
| Faux | Vrai | Vrai | Vrai | Vrai |
| Faux | Faux | Vrai | Vrai | Vrai |
Il est important de remarquer que la phrase “ A \Rightarrow B ” est fausse uniquement lorsque A vrai et B fausse. Subséquemment lorsque A est fausse, qu’importe B, “ A \Rightarrow B” est vrai.
Par exemple, parmi les nombres réels, “ 1 = 2 \Rightarrow 1 = 3 “, ainsi que “ 1 =2 \Rightarrow 4 = 2+2 ” sont vrais, car dans tout les cas “A” est fausse.
Pour montrer qu’une implication est vrai, on se contente de traiter du cas où A est supposé vrai, puisque “ A \Rightarrow B ” est déjà vrai dans le cas où “A” est fausse. La moitié du travail est déjà faite !
L’intérêt de l’implication réside dans la transitivité
| A | B | C | A \Rightarrow B | B \Rightarrow C | A \Rightarrow C | ((A \Rightarrow B) et ( B \Rightarrow C)) \\ \Rightarrow (A \Rightarrow C ) |
| Vrai | Vrai | Vrai | Vrai | Vrai | Vrai | Vrai |
| Vrai | Vrai | Faux | Vrai | Faux | Faux | Vrai |
| Vrai | Faux | Vrai | Faux | Vrai | Vrai | Vrai |
| Vrai | Faux | Faux | Faux | Vrai | Faux | Vrai |
| Faux | Vrai | Vrai | Vrai | Vrai | Vrai | Vrai |
| Faux | Vrai | Faux | Vrai | Faux | Vrai | Vrai |
| Faux | Faux | Vrai | Vrai | Vrai | Vrai | Vrai |
| Faux | Faux | Faux | Vrai | Vrai | Vrai | Vrai |
Toujours “(A \Rightarrow B) et ( B \Rightarrow C) \Rightarrow (A \Rightarrow C )”. Ceci permet d’enchainer plusieurs implications, assez courte et simple, tout en s’assurant que la première phrase de la chaine impliquera les autres.
Quand on demande de justifier plus amplement un exercice. Il est sous-entendu de rajouter des implications intermédiaires plus simple. Pour être assuré que vous maitrisez bien les détails de chaque ligne.
Équivalence
On note l’équivalence de deux phrases logiques “A” et “B” par “ A \Leftrightarrow B“, et défini par “ (A \Rightarrow B) et (A \Leftarrow B) “, ce qui donne
| A | B | A \Rightarrow B | A \Leftarrow B | A \Leftrightarrow B |
| Vrai | Vrai | Vrai | Vrai | Vrai |
| Vrai | Faux | Faux | Vrai | Faux |
| Faux | Vrai | Vrai | Faux | Faux |
| Faux | Faux | Vrai | Vrai | Vrai |
L’équivalence est symétrique, cela peut être vérifié par la chaine de “calcul logique” suivante, on utilise les propriétés des opérateurs précédents
On montre maintenant l’implication dans l’autre sens pour obtenir l’équivalence, les justifications sont les mêmes.
Dans la table de vérité il est clair que “ A \sim B” prend simultanément les mêmes valeurs de véracité que “ A \Leftrightarrow B “, c’est à dire lorsque “A” et “B” sont vrai simultanément.
Remarque : “ (A \sim B ) \sim (A \Leftrightarrow B) ” est vrai, et tout aussi bien “ (A \sim B ) \Leftrightarrow (A \Leftrightarrow B) “.
La convention est d’utiliser “ \Leftrightarrow ” donc on évite d’utiliser le symbole “ \sim “.
L’équivalence est transitive, la preuve est un exercice.
| A | B | A \sim B | A \Leftrightarrow B | (A et B) ou (non A et non B) |
| Vrai | Vrai | Vrai | Vrai | Vrai |
| Vrai | Faux | Faux | Faux | Faux |
| Faux | Vrai | Faux | Faux | Faux |
| Faux | Faux | Vrai | Vrai | Vrai |
Par la suite, les tables deviennent du plus en plus complexe lorsque le nombre de phrase augmente.
Il est donc plus approprié de retenir les propriétés des opérateurs logiques, et démontrer équivalence/implication comme résultat d’un calcul de proposition.
Pour montrer une implication “ A \Rightarrow B “, on commence par supposer que A est vrai, il s’agit de montrer que B l’est aussi.
Pour montrer une équivalence, on doit montrer les deux implications correspondantes ou raisonner avec une chaine d’équivalence simple.
Donc on a montré que ( (A \ et \ B) \Rightarrow C ) \Leftrightarrow ( (A \Rightarrow C) \ ou \ (B \Rightarrow C) ). Ce qui peut perturber quand on y pense.
Exercices
- Démontrer la transitivité de l’équivalence on pourra utiliser la symétrie de l’équivalence, et la transitivité de l’implication.
- Montrer que ( (A \ ou \ B) \Rightarrow C ) \Leftrightarrow ( (A \Rightarrow C) \ et \ (B \Rightarrow C) )(Astuce procédé par chaine d’équivalence, comme exemple précédant).
- Montrer que ( A \Rightarrow (B \ et \ C) )\Leftrightarrow ((A \Rightarrow B) \ et \ (A \Rightarrow C ) ).
- Montrer que ( A \Rightarrow (B \ ou \ C) )\Leftrightarrow ((A \Rightarrow B)\ ou \ (A \Rightarrow C ) ).
- Réduire (A \ ou \ B) \Rightarrow ( A \ et \ B ).
- Démontrer l’équivalence du raisonnement par contraposée, (A \Rightarrow B) \Leftrightarrow (non B \Rightarrow non A) .
- Démontrer qu’importe n \in \mathbb{N}, que ( E_1\Rightarrow E_2 et E_2 \Rightarrow E_3 \cdots et E_{n-1} \Rightarrow E_n et E_n \Rightarrow E_1 ) \Leftrightarrow ( E_1\Leftrightarrow E_2 \Leftrightarrow E_3 \cdots \Leftrightarrow E_{n-1} \Leftrightarrow E_n ) .
