Implication, équivalence et lois de De Morgan

L'implication P ⇒ Q (« si P, alors Q ») est fausse dans un seul cas : quand P est vraie et Q fausse. L'équivalence P ⇔ Q (« P si et seulement si Q ») est vraie quand P et Q ont la même valeur. Ce chapitre explique ces deux connecteurs, la réciproque, la contraposée et la négation d'une implication, puis les lois du calcul propositionnel, dont les lois de De Morgan.

L'implication (si P, alors Q)

L'implication de P vers Q se note P ⇒ Q et se lit « P implique Q » ou « si P, alors Q ». P s'appelle l'hypothèse (ou prémisse), Q la conclusion.

Les deux dernières lignes surprennent toujours : quand l'hypothèse est fausse, l'implication est vraie, quelle que soit la conclusion. Pour le comprendre, vois l'implication comme une promesse. Ton professeur te dit : « Si tu as au moins 15 à l'écrit blanc, je te dispense de l'oral blanc. »

• Tu as 16 et tu es dispensé : promesse tenue (V, V : vrai).
• Tu as 16 et tu passes quand même l'oral : promesse rompue (V, F : faux).
• Tu as 12 et tu es dispensé quand même : la promesse ne disait rien de ce cas, elle n'est pas rompue (F, V : vrai).
• Tu as 12 et tu passes l'oral : promesse tenue (F, F : vrai).

La promesse n'est trahie que dans un cas : hypothèse vraie, conclusion fausse. C'est exactement la table de P ⇒ Q.

Tu peux le vérifier par une table : ¬P ∨ Q est faux seulement quand ¬P et Q sont faux tous les deux, donc quand P est vraie et Q fausse. Cette réécriture est la clé de presque tous les calculs sur les implications.

Condition nécessaire, condition suffisante

Quand P ⇒ Q est vraie, on dit aussi :

• P est une condition suffisante pour Q : il suffit que P soit vraie pour que Q le soit ;
• Q est une condition nécessaire pour P : il faut que Q soit vraie pour que P puisse l'être ; si Q est fausse, P l'est aussi.

Exemple : « si un poste est dans le VLAN 10, alors il a une adresse en 10.0.10.0/24 » (règle d'adressage d'une entreprise). Être dans le VLAN 10 suffit pour avoir une telle adresse ; avoir une telle adresse est nécessaire pour être dans le VLAN 10.

Le français offre plusieurs façons de dire P ⇒ Q, et les sujets les utilisent toutes :

Réciproque, contraposée et négation

À partir d'une implication P ⇒ Q, on fabrique trois autres énoncés que les sujets demandent souvent d'écrire.

Prenons une implication vraie : « si une adresse IPv4 commence par 10, alors c'est une adresse privée » (le bloc 10.0.0.0/8 est réservé aux réseaux privés).

• Réciproque : « si une adresse est privée, alors elle commence par 10 ». Fausse : 192.168.1.20 est privée et ne commence pas par 10.
• Contraposée : « si une adresse n'est pas privée, alors elle ne commence pas par 10 ». Vraie, comme l'implication de départ.
• Négation : « il existe une adresse qui commence par 10 et qui n'est pas privée ». Fausse, puisque l'implication est vraie.

Pourquoi la contraposée a-t-elle toujours la même valeur ? Par le calcul : ¬Q ⇒ ¬P ≡ ¬(¬Q) ∨ ¬P ≡ Q ∨ ¬P ≡ ¬P ∨ Q ≡ P ⇒ Q. C'est ce qui permet de démontrer une implication en démontrant sa contraposée, souvent plus simple.

Pourquoi la négation de P ⇒ Q est-elle P ∧ ¬Q ? Parce que l'implication n'est fausse que si P est vraie et Q fausse. Par le calcul : ¬(P ⇒ Q) ≡ ¬(¬P ∨ Q) ≡ ¬¬P ∧ ¬Q ≡ P ∧ ¬Q (avec la loi de De Morgan, ci-dessous).

L'équivalence : si et seulement si

L'équivalence de P et Q, notée P ⇔ Q, se lit « P si et seulement si Q » (en abrégé « ssi »). Elle est vraie quand P et Q ont la même valeur de vérité.

L'équivalence est une double implication : P ⇔ Q ≡ (P ⇒ Q) ∧ (Q ⇒ P). Dire « P si et seulement si Q », c'est dire « P si Q » et « P seulement si Q ». Compare sa table à celle du ou exclusif : elles sont exactement contraires, donc P ⇔ Q ≡ ¬(P ⊕ Q).

Exemple : « un entier est pair si et seulement si son écriture binaire se termine par 0 ». Les deux sens sont vrais : un nombre pair se termine par 0 en binaire, et un nombre qui se termine par 0 en binaire est pair.

Les lois du calcul propositionnel

Les équivalences suivantes sont toutes vraies ; chacune se vérifie par une table de vérité. Elles permettent de transformer une formule sans dresser de table, et elles deviendront les règles de l'algèbre de Boole.

S'y ajoutent la double négation ¬¬P ≡ P, l'écriture de l'implication P ⇒ Q ≡ ¬P ∨ Q et celle de l'équivalence P ⇔ Q ≡ (P ⇒ Q) ∧ (Q ⇒ P).

Remarque la symétrie du tableau : chaque loi de la colonne de droite s'obtient à partir de celle de gauche en échangeant ∧ et ∨, et V et F. C'est le principe de dualité, qui divise par deux ce que tu as à retenir.

Les lois de De Morgan

Les lois de De Morgan (du mathématicien britannique Augustus De Morgan, XIXe siècle) disent comment nier un « et » ou un « ou » :

Vérification de la première loi par une table de vérité :

Les colonnes 4 et 7 sont identiques : les deux formules sont équivalentes. La seconde loi se vérifie de la même façon.

En français : le contraire de « le serveur est allumé et connecté au réseau » est « le serveur est éteint ou déconnecté du réseau ». Le contraire de « l'utilisateur a oublié son badge ou son mot de passe » est « l'utilisateur n'a oublié ni son badge ni son mot de passe », c'est-à-dire ni l'un, ni l'autre.

Les lois se généralisent à plus de deux propositions : ¬(P ∧ Q ∧ R) ≡ ¬P ∨ ¬Q ∨ ¬R, et ¬(P ∨ Q ∨ R) ≡ ¬P ∧ ¬Q ∧ ¬R.

Démontrer une équivalence : table ou calcul

Deux méthodes, que les sujets acceptent toutes les deux :

1. Par une table de vérité : tu dresses la table des deux formules et tu constates que leurs colonnes sont identiques. Méthode sûre, mécanique, mais longue au-delà de trois variables.
2. Par le calcul : tu transformes une formule en l'autre avec les lois, en citant la loi utilisée à chaque étape.

Exemple. Montrer que (P ⇒ Q) ∧ (P ⇒ R) ≡ P ⇒ (Q ∧ R).

Par le calcul :

• (P ⇒ Q) ∧ (P ⇒ R)
• ≡ (¬P ∨ Q) ∧ (¬P ∨ R), en réécrivant chaque implication ;
• ≡ ¬P ∨ (Q ∧ R), par distributivité de ∨ sur ∧ (lue de droite à gauche) ;
• ≡ P ⇒ (Q ∧ R), en réécrivant l'implication.

En français : « si P alors Q, et si P alors R » revient à « si P, alors Q et R ».

Exercices

Exercice 1 sur 6 Implication et réciproque Réussi À revoir

1. Dresse les tables de vérité de P ⇒ Q et de Q ⇒ P dans un même tableau.
2. Sur quelles lignes diffèrent-elles ? Qu'en conclus-tu ?

Voir la réponseMasquer la réponse de l'exercice 1

1.

P	Q	P ⇒ Q	Q ⇒ P
F	F	V	V
F	V	V	F
V	F	F	V
V	V	V	V

2. Elles diffèrent sur les lignes 2 (P fausse, Q vraie) et 3 (P vraie, Q fausse). Une implication et sa réciproque ne sont donc pas équivalentes : savoir que l'une est vraie ne dit rien de l'autre.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 2 sur 6 Réciproque, contraposée, négation Réussi À revoir

Une entreprise applique la règle R : « si un salarié est administrateur, alors son compte a la double authentification ».

1. Écris la réciproque de R, sa contraposée et sa négation, en français.
2. On sait que R est respectée. Que peux-tu dire d'un salarié dont le compte n'a pas la double authentification ?

Voir la réponseMasquer la réponse de l'exercice 2

Notons A : « le salarié est administrateur » et D : « son compte a la double authentification ». R s'écrit A ⇒ D.

1. Les trois énoncés :
   • réciproque (D ⇒ A) : « si le compte d'un salarié a la double authentification, alors ce salarié est administrateur » ;
   • contraposée (¬D ⇒ ¬A) : « si le compte d'un salarié n'a pas la double authentification, alors ce salarié n'est pas administrateur » ;
   • négation (A ∧ ¬D) : « il y a un salarié administrateur dont le compte n'a pas la double authentification ».
2. La contraposée est vraie puisque R l'est : ce salarié n'est pas administrateur. En revanche, un salarié qui a la double authentification n'est pas forcément administrateur : la réciproque n'est pas garantie.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 3 sur 6 Nier avec De Morgan Réussi À revoir

Écris la négation de chaque phrase, sans commencer par « il est faux que ».

1. « Le poste est sous Windows et il est à jour. »
2. « Le ticket est clos ou il est en attente. »
3. « Le mot de passe contient un chiffre et un caractère spécial, ou il fait plus de 20 caractères. »
4. « S'il y a une coupure, l'onduleur prend le relais. »

Voir la réponseMasquer la réponse de l'exercice 3

1. « Le poste n'est pas sous Windows ou il n'est pas à jour. » (¬(W ∧ J) ≡ ¬W ∨ ¬J)
2. « Le ticket n'est pas clos et il n'est pas en attente. » (¬(C ∨ A) ≡ ¬C ∧ ¬A)
3. Avec C : « contient un chiffre », S : « contient un caractère spécial », L : « fait plus de 20 caractères », la phrase est (C ∧ S) ∨ L. Sa négation : ¬((C ∧ S) ∨ L) ≡ ¬(C ∧ S) ∧ ¬L ≡ (¬C ∨ ¬S) ∧ ¬L. En français : « le mot de passe ne contient pas de chiffre ou pas de caractère spécial, et il fait au plus 20 caractères ».
4. La négation d'une implication est « hypothèse et non conclusion » : « il y a une coupure et l'onduleur ne prend pas le relais ».

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 4 sur 6 Une règle de déduction Réussi À revoir

Montre par une table de vérité que ((P ⇒ Q) ∧ P) ⇒ Q est une tautologie. Traduis ce résultat en une phrase.

Voir la réponseMasquer la réponse de l'exercice 4

P	Q	P ⇒ Q	(P ⇒ Q) ∧ P	((P ⇒ Q) ∧ P) ⇒ Q
F	F	V	F	V
F	V	V	F	V
V	F	F	F	V
V	V	V	V	V

La dernière colonne ne contient que des V : c'est une tautologie. En français : « si P implique Q et que P est vraie, alors Q est vraie ». C'est la règle de déduction la plus utilisée en mathématiques (elle s'appelle le modus ponens).

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 5 sur 6 Nécessaire ou suffisant ? Réussi À revoir

Complète par « nécessaire », « suffisante » ou « nécessaire et suffisante ».

1. Avoir au moins 18 ans est une condition … pour voter en France.
2. Avoir une adresse IP dans le bon sous-réseau est une condition … pour qu'un poste communique avec sa passerelle sans routage.
3. Être divisible par 4 est une condition … pour qu'un entier soit pair.
4. Avoir une écriture binaire qui se termine par 0 est une condition … pour qu'un entier soit pair.

Voir la réponseMasquer la réponse de l'exercice 5

1. Nécessaire : il faut avoir au moins 18 ans pour voter, mais il faut aussi la nationalité française et être inscrit sur les listes électorales.
2. Nécessaire : sans adresse dans le sous-réseau de la passerelle, le poste ne peut pas la joindre directement ; mais il faut aussi un câble branché, une passerelle configurée, etc.
3. Suffisante : un multiple de 4 est pair, mais 6 est pair sans être divisible par 4.
4. Nécessaire et suffisante : un entier est pair si et seulement si son bit de poids faible vaut 0.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 6 sur 6 Démontrer par le calcul Réussi À revoir

Montre, en citant les lois utilisées, que P ∨ (¬P ∧ Q) ≡ P ∨ Q.

Voir la réponseMasquer la réponse de l'exercice 6

• P ∨ (¬P ∧ Q)
• ≡ (P ∨ ¬P) ∧ (P ∨ Q), par distributivité de ∨ sur ∧ ;
• ≡ V ∧ (P ∨ Q), par complémentarité ;
• ≡ P ∨ Q, car V est neutre pour ∧.

Cette équivalence revient souvent en simplification : dans « P ou (non P et Q) », le « non P » est inutile, car quand P est vraie la formule est déjà vraie.

Tu avais trouvé ?

Oui, j'avais bonPas encore