Partie 1

Logique : propositions, quantificateurs et tables de vérité

Avant de raisonner, il faut savoir de quoi

Propositions logiques

Définition

Une proposition est un énoncé mathématique auquel on peut attribuer une valeur de vérité : \(\mathrm{V}\) (vrai) ou \(\mathrm{F}\) (faux) — jamais les deux à la fois, jamais aucune des deux.

Exemples

« \(2+2=4\) » est une proposition vraie.

« \(7\) est un nombre pair » est une proposition fausse.

« \(x+1=5\) » n'est pas une proposition tant que \(x\) n'est pas fixé : c'est un prédicat \(P(x)\), une phrase qui devient une proposition dès qu'on remplace \(x\) par une valeur.

Attention

« Cette phrase est fausse » n'est pas une proposition mathématique valide (paradoxe du menteur) : le principe de bivalence (vrai/faux, sans autre possibilité) est un axiome de la logique classique, pas une loi de la nature — on l'admet pour construire toute la théorie.

Les connecteurs logiques

Fabriquer de nouvelles propositions à partir d'anciennes.

2.1 — La négation « non P »

La négation de \(P\), notée \(\text{non } P\) ou \(\neg P\), est vraie exactement quand \(P\) est fausse.

\(P\)	\(\neg P\)
V	F
F	V

2.2 — La conjonction « P et Q »

\(P \text{ et } Q\) (notée \(P\wedge Q\)) est vraie si, et seulement si, \(P\) et \(Q\) sont toutes les deux vraies.

\(P\)	\(Q\)	\(P \text{ et } Q\)
V	V	V
V	F	F
F	V	F
F	F	F

2.3 — La disjonction « P ou Q »

\(P \text{ ou } Q\) (notée \(P\vee Q\)) est vraie si au moins l'une des deux propositions est vraie (« ou » inclusif : les deux à la fois, ça compte).

\(P\)	\(Q\)	\(P \text{ ou } Q\)
V	V	V
V	F	V
F	V	V
F	F	F

Lois de De Morgan \[ \neg(P \text{ et } Q) \iff (\neg P) \text{ ou } (\neg Q) \qquad\quad \neg(P \text{ ou } Q) \iff (\neg P) \text{ et } (\neg Q) \]

Pour nier un « et », on nie chaque proposition et on relie par « ou » — et réciproquement.

Implication et équivalence

3.1 — L'implication « P ⇒ Q »

\(P\Longrightarrow Q\) se lit « \(P\) implique \(Q\) » ou « si \(P\) alors \(Q\) ». Par définition :

\[ (P\Longrightarrow Q) \quad\text{est, par définition,}\quad (\neg P)\text{ ou } Q \]

\(P\)	\(Q\)	\(P\Rightarrow Q\)
V	V	V
V	F	F
F	V	V
F	F	V

Le seul cas à retenir

\(P\Rightarrow Q\) est fausse dans un seul cas : \(P\) vraie et \(Q\) fausse. En particulier, une implication dont l'hypothèse \(P\) est fausse est toujours vraie — quelle que soit \(Q\). C'est déroutant au début, mais c'est cohérent : « si \(P\) (qui n'arrive jamais) alors n'importe quoi » ne peut jamais être pris en défaut.

Négation d'une implication \[ \neg(P\Rightarrow Q) \iff P \text{ et } \neg Q \]

Retenir cette formule est essentiel pour le raisonnement par contre-exemple (voir Partie 2).

3.2 — Réciproque et contraposée

Soit \(P\Rightarrow Q\) une implication.

▸ Sa réciproque est \(Q\Rightarrow P\).

▸ Sa contraposée est \(\neg Q\Rightarrow \neg P\).

Propriété fondamentale \[ (P\Rightarrow Q) \iff (\neg Q\Rightarrow \neg P) \]

Une implication et sa contraposée sont toujours équivalentes — c'est ce qui justifie le raisonnement par contraposée. En revanche, la réciproque n'a en général rien à voir avec l'implication de départ.

Contre-exemple classique

« \(n\) pair \(\Rightarrow n^2\) pair » est vraie. Sa réciproque « \(n^2\) pair \(\Rightarrow n\) pair » est aussi vraie ici — mais ce n'est pas automatique : « \(x=1 \Rightarrow x^2=1\) » est vraie, alors que sa réciproque « \(x^2=1 \Rightarrow x=1\) » est fausse (contre-exemple : \(x=-1\)).

3.3 — L'équivalence « P ⇔ Q »

\(P\Longleftrightarrow Q\) est vraie si, et seulement si, \(P\) et \(Q\) ont la même valeur de vérité. Par définition :

\[ (P\Longleftrightarrow Q) \quad\text{est, par définition,}\quad (P\Rightarrow Q)\text{ et }(Q\Rightarrow P) \]

\(P\)	\(Q\)	\(P\Leftrightarrow Q\)
V	V	V
V	F	F
F	V	F
F	F	V

Les quantificateurs

\(\forall\) — « quel que soit » · \(\exists\) — « il existe »

Quantificateur universel

\(\forall x\in E,\ P(x)\) se lit « pour tout \(x\) de \(E\), \(P(x)\) » et est vraie si tous les éléments de \(E\) vérifient \(P\).

Quantificateur existentiel

\(\exists x\in E,\ P(x)\) se lit « il existe \(x\) de \(E\) tel que \(P(x)\) » et est vraie s'il y a au moins un élément de \(E\) qui vérifie \(P\).

Existence et unicité

\(\exists!\,x\in E,\ P(x)\) signifie « il existe un unique \(x\) de \(E\) tel que \(P(x)\) » : c'est plus fort que \(\exists\) seul (voir le chapitre Rédaction, §5).

L'ordre des quantificateurs compte

\(\forall x,\ \exists y\) et \(\exists y,\ \forall x\) n'ont pas le même sens : dans le premier, \(y\) peut dépendre de \(x\) ; dans le second, un seul \(y\) doit convenir pour tous les \(x\) à la fois.

Exemple : \(\forall x\in\mathbb{R},\ \exists y\in\mathbb{R},\ y>x\) est vraie (il suffit de prendre \(y=x+1\)), alors que \(\exists y\in\mathbb{R},\ \forall x\in\mathbb{R},\ y>x\) est fausse (aucun réel \(y\) ne majore strictement tous les réels).

Négation des quantificateurs \[ \neg\big(\forall x\in E,\ P(x)\big) \iff \exists x\in E,\ \neg P(x) \] \[ \neg\big(\exists x\in E,\ P(x)\big) \iff \forall x\in E,\ \neg P(x) \]

Nier fait basculer \(\forall\) en \(\exists\) et inversement, et fait passer la négation à l'intérieur, sur \(P(x)\).

Négation d'un énoncé quantifié composé

Pour nier une phrase avec plusieurs quantificateurs, on applique la règle de proche en proche, de gauche à droite :

\[ \neg\big(\forall x\in E,\ \exists y\in F,\ P(x,y)\big) \iff \exists x\in E,\ \forall y\in F,\ \neg P(x,y) \]

Énoncé

Écrire la négation de \(\forall x\in\mathbb{R},\ x^2\geq 0\).

Solution

La négation est \(\exists x\in\mathbb{R},\ x^2<0\) — qui est fausse, ce qui confirme que l'énoncé de départ est vrai.

Applications

Exercice 1

Énoncé

1.Écrire la négation de \(\forall x\in\mathbb{R},\ \exists y\in\mathbb{R},\ x+y=0\).

2.Écrire la contraposée de « si \(n\) est premier et \(n>2\), alors \(n\) est impair ».

3.L'implication \(\forall x\in\mathbb{R},\ x^2=4\Rightarrow x=2\) est-elle vraie ? Justifier.

Exercice 2

Énoncé

On considère les deux énoncés suivants :

\[ (A):\ \forall x\in\mathbb{R}_+,\ \exists n\in\mathbb{N},\ n>x \qquad\qquad (B):\ \exists n\in\mathbb{N},\ \forall x\in\mathbb{R}_+,\ n>x \]

Que dire de la valeur de vérité de \((A)\) et de \((B)\) ? Commenter.

Exercice 3

Énoncé

Dresser la table de vérité de \((P\Rightarrow Q)\text{ et }(Q\Rightarrow P)\), puis comparer avec la table de \(P\Leftrightarrow Q\). Que constate-t-on ?

Correction

\(P\)	\(Q\)	\(P\Rightarrow Q\)	\(Q\Rightarrow P\)	les deux
V	V	V	V	V
V	F	F	V	F
F	V	V	F	F
F	F	V	V	V

La dernière colonne coïncide exactement avec la table de \(P\Leftrightarrow Q\) vue en §3.3 — ce qui confirme la définition \((P\Leftrightarrow Q) \iff (P\Rightarrow Q)\text{ et }(Q\Rightarrow P)\), et justifie la méthode par double implication (voir Partie 2, §3).

Résumé

Une proposition est vraie ou fausse, jamais les deux.
\(P\Rightarrow Q\) est fausse dans un seul cas : \(P\) vraie et \(Q\) fausse.
\(\neg(P\Rightarrow Q) \iff P \text{ et } \neg Q\).
Une implication est toujours équivalente à sa contraposée — jamais, en général, à sa réciproque.
\(P\Leftrightarrow Q \iff (P\Rightarrow Q)\text{ et }(Q\Rightarrow P)\).
Nier fait basculer \(\forall\) en \(\exists\) (et réciproquement), et fait entrer la négation à l'intérieur de la proposition.
L'ordre des quantificateurs \(\forall\dots\exists\dots\) n'est jamais interchangeable avec \(\exists\dots\forall\dots\)

« Bien nier un énoncé, c'est déjà savoir le démontrer. »

Exercice 48