Table de vérité, implication et équivalence des propositions.

Implication et équivalence sont deux éléments importants lorsqu’on veut faire des raisonnements. Cet article a pour but d’en présenter les bases
Equivalence

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.

ABnon Anon A ou B A => B (par définition)
VraiVraiFauxVrai Vrai
VraiFauxFauxFauxFaux
FauxVraiVraiVraiVrai
FauxFauxVraiVraiVrai
Table de vérité de “A => B”

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é

ABCA \Rightarrow BB \Rightarrow CA \Rightarrow C((A \Rightarrow B) et ( B \Rightarrow C)) \\ \Rightarrow (A \Rightarrow C )
VraiVraiVraiVraiVraiVraiVrai
VraiVraiFauxVraiFauxFauxVrai
VraiFauxVraiFauxVraiVraiVrai
VraiFauxFauxFauxVraiFauxVrai
FauxVraiVraiVraiVraiVraiVrai
FauxVraiFauxVraiFauxVraiVrai
FauxFauxVraiVraiVraiVraiVrai
FauxFauxFauxVraiVraiVraiVrai
Transitivité de l’implication

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

AB A \Rightarrow B A \Leftarrow B A \Leftrightarrow B
VraiVrai VraiVraiVrai
VraiFauxFauxVraiFaux
FauxVraiVraiFauxFaux
FauxFauxVraiVraiVrai
Table de vérité de “A <=> B”

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

(A \Leftrightarrow B) \\ \Rightarrow ((A \Rightarrow B) et (A \Leftarrow B)) ( par définition de l’équivalence)

\\ \Rightarrow ( (A \Leftarrow B) et (A \Rightarrow B) ) ( par symétrie de “et” )

\\ \Rightarrow( (B \Rightarrow A) et (B \Leftarrow A) ) ( par changement de notation )

\\ \Rightarrow (B \Leftrightarrow A) ( par définition de l’équivalence )

On montre maintenant l’implication dans l’autre sens pour obtenir l’équivalence, les justifications sont les mêmes.

\\ (B \Leftrightarrow A) \\ \Rightarrow ((B \Rightarrow A) et (B \Leftarrow A))

\\ \Rightarrow ( (B \Leftarrow A) et (B \Rightarrow A) )

\\ \Rightarrow ( (A \Rightarrow B) et (A \Leftarrow B) )

\\ \Rightarrow (A \Leftrightarrow B)

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.

ABA \sim BA \Leftrightarrow B(A et B) ou (non A et non B)
VraiVraiVraiVraiVrai
VraiFauxFauxFauxFaux
FauxVraiFauxFauxFaux
FauxFauxVraiVraiVrai
Table de vérité de l’équivalence des équivalences

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.

((A \ et \ B )\Rightarrow C) \\ \Leftrightarrow (non(A \ et \ B ) \ ou \ C) ( par définition)

\\ \Leftrightarrow (non \ A \ ou \ non \ B \ ou \ C) ( distributivité de “non” sur “et”)

\\ \Leftrightarrow (non\ A \ ou \ non \ B \ ou \ C \ ou \ C) ( car C \Leftrightarrow C \ ou \ C)

\\ \Leftrightarrow (non \ A \ ou \ C \ ou \ non \ B \ ou \ C) ( symétrie de “ou”)

\\ \Leftrightarrow ( (non \ A \ ou \ C) \ ou \ (non \ B \ ou \ C) ) ( associativité de “ou”)

\\ \Leftrightarrow ( (A \Rightarrow C) \ ou \ (B \Rightarrow C) ) ( par définition)

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

  1. Démontrer la transitivité de l’équivalence on pourra utiliser la symétrie de l’équivalence, et la transitivité de l’implication.
  2. 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).
  3. Montrer que ( A \Rightarrow (B \ et \ C) )\Leftrightarrow ((A \Rightarrow B) \ et \ (A \Rightarrow C ) ).
  4. Montrer que ( A \Rightarrow (B \ ou \ C) )\Leftrightarrow ((A \Rightarrow B)\ ou \ (A \Rightarrow C ) ).
  5. Réduire (A \ ou \ B) \Rightarrow ( A \ et \ B ).
  6. Démontrer l’équivalence du raisonnement par contraposée, (A \Rightarrow B) \Leftrightarrow (non B \Rightarrow non A) .
  7. 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 ) .
Total
0
Shares
1 commentaire

Laisser un commentaire

Articles similaires