La négation d'une implication

Stratégie : on calcule, on ne raisonne pas. L'implication n'est pas un objet mystérieux : le cours la définit comme $(\neg P)\vee Q$. Les deux équivalences demandées sont donc de simples réécritures, obtenues par les lois de De Morgan et la double négation.

1) La négation d'une implication. On part de la définition et on nie :

$$\neg (P\Rightarrow Q)=\neg ((\neg P)\vee Q).$$

La loi de De Morgan transforme la négation d'une disjonction en conjonction des négations :

$$\neg ((\neg P)\vee Q)=\neg (\neg P)\wedge \neg Q=P\wedge \neg Q,$$

la dernière égalité étant la double négation. D'où

$$\neg (P\Rightarrow Q)⟺(P\wedge \neg Q).$$

⚠️ Le point délicat est la nature du résultat. La négation d'une implication est une conjonction, pas une implication. Elle affirme deux choses à la fois : que $P$ est vraie, et que $Q$ est fausse. Écrire « $P\Rightarrow \neg Q$ » serait une faute grossière, car cette dernière assertion est vraie dès que $P$ est fausse, alors que la négation de $P\Rightarrow Q$ exige au contraire que $P$ soit vraie.

2) La contraposition. On applique la définition aux deux membres. À gauche, $P\Rightarrow Q$ vaut $(\neg P)\vee Q$. À droite, $\neg Q\Rightarrow \neg P$ vaut $\neg (\neg Q)\vee \neg P$, c'est-à-dire $Q\vee \neg P$ par double négation. Or la disjonction est commutative : $(\neg P)\vee Q$ et $Q\vee (\neg P)$ sont la même assertion. D'où

$$(P\Rightarrow Q)⟺(\neg Q\Rightarrow \neg P).$$

Contrôle sur un exemple. Prenons l'assertion « si $n$ est un multiple de $4$, alors $n$ est pair », pour $n$ entier. Sa négation est : « il existe un entier qui est multiple de $4$ et qui n'est pas pair » — une conjonction, effectivement fausse. Sa contraposée est : « si $n$ est impair, alors $n$ n'est pas multiple de $4$ » — vraie, comme l'assertion de départ. En revanche, l'assertion « si $n$ est multiple de $4$, alors $n$ n'est pas pair » est fausse : elle n'est donc pas la négation de la première, puisque de deux assertions dont l'une nie l'autre, exactement une est vraie.

Ce que l'exercice installe. Deux automatismes de toute l'année. Pour nier une implication, on n'y touche pas au connecteur : on écrit l'hypothèse vraie et la conclusion fausse. Et pour démontrer une implication, on a désormais deux portes d'entrée équivalentes — c'est le raisonnement par contraposition, qui rend faciles quantité d'énoncés sur les entiers.