Éducation Nationale Française · MP2I

Logique

⌚ ~402 min ▢ 48 blocs ✓ 195 exercices PDFCours complet PDFFiche d'exercices PDFCorrections ➣ Prérequis : Raisonnement et Démonstration

Vue d'ensemble du chapitre

Toute démonstration s'écrit avec quelques mots : non, et, ou, si … alors, si et seulement si, pour tout, il existe. Ce chapitre fait de ces mots un langage précis. Un connecteur est défini par sa table de vérité ; les règles familières — lois de De Morgan, négation d'une implication, équivalence d'une implication avec sa contraposée, négation d'un énoncé quantifié — deviennent des lois, c'est-à-dire des formules vraies quelles que soient les propositions auxquelles on les applique, et chacune est démontrée : en raisonnant sur les lignes de la table où elle pourrait être fausse, par un calcul avec des lois déjà démontrées, ou par la table elle-même. Derrière les schémas de démonstration du chapitre Raisonner et rédiger — déduire, distinguer des cas, contraposer, raisonner par l'absurde — se tiennent ces lois. Le chapitre se termine par les quantificateurs : comment les nier, quand deux d'entre eux peuvent s'échanger, comment ils se combinent avec « et » et « ou ».
Notations. Les deux valeurs de vérité sont notées V (vrai) et F (faux). Les lettres $p$, $q$, $r$ désignent des propositions, et une loi s'énonce « pour toutes propositions $p$, $q$ : … ». L'équivalence s'écrit $\iff$, l'implication $\Rightarrow$.

Signaler une erreur

Prérequis

Ce chapitre suppose connus le chapitre Raisonnement et démonstration — propositions, connecteurs et leurs tables de vérité, la Méthode « Construire une table de vérité », quantificateurs — et le chapitre Raisonner et rédiger : les schémas de démonstration et leurs Méthodes, la négation d'un énoncé quantifié comme méthode de rédaction, le contre-exemple, la récurrence simple et la récurrence forte. Les exemples utilisent aussi : le calcul sur les réels (identités, inégalités, valeur absolue et inégalité triangulaire) ; la divisibilité des entiers, les nombres pairs et impairs ; les fonctions usuelles ; les suites, la définition de la convergence étant rappelée là où elle sert ; les approximations décimales d'un réel ; le langage des ensembles du chapitre Théorie des ensembles (élément, inclusion, ensemble vide, définition en compréhension, intersection, réunion, complémentaire).

Signaler une erreur

I Propositions et connecteurs

I.1 Propositions et prédicats

La table est la définition

Les propositions se combinent à l'aide de connecteurs : non, et, ou, si … alors, si et seulement si. En mathématiques, un connecteur est défini par sa table de vérité, qui donne la valeur de vérité de la proposition composée pour chaque combinaison des valeurs de vérité de ses composantes. La table n'est pas une illustration du connecteur : elle en est la définition. Une loi de la logique est alors un énoncé sur des tables, qui se lit sur elles ou se calcule à partir de lois déjà démontrées.

Signaler une erreur

Des énoncés vrais ou faux

La logique étudie les énoncés qui sont vrais ou faux, et la façon dont ils se combinent. Deux sortes d'énoncés se distinguent dès le départ : une proposition a une valeur de vérité telle qu'elle est écrite ; un prédicat dépend d'une variable et n'acquiert une valeur de vérité qu'une fois cette variable fixée. Les quantificateurs font d'un prédicat une proposition d'une autre façon.

Signaler une erreur

Définition — Proposition, valeur de vérité, prédicat

Une proposition est un énoncé déclaratif auquel on peut attribuer exactement l'une des deux valeurs de vérité V (vrai) ou F (faux). On note les propositions par des lettres minuscules $p, q, r, \dots$. Une proposition n'est jamais simultanément V et F ; c'est le principe de non-contradiction, que l'on adopte comme loi primitive du discours mathématique.
Un énoncé qui dépend d'une variable libre, par exemple « $n$ est pair » ou « $f(x) > 0$ », est appelé prédicat. Un prédicat n'a pas de valeur de vérité tel quel ; il n'en acquiert une qu'une fois la variable fixée.

Deux principes

Deux principes gouvernent toute proposition — le premier déjà énoncé dans la Définition « Proposition, valeur de vérité, prédicat » :

le principe de non-contradiction : aucune proposition n'est à la fois vraie et fausse ;
le principe du tiers exclu : toute proposition est vraie ou fausse — il n'y a pas de troisième valeur.

Ensemble, ils disent que toute proposition a exactement l'une des deux valeurs V et F. C'est pourquoi une table de vérité n'utilise que ces deux valeurs, et compte $2^n$ lignes pour $n$ propositions. Certains schémas de démonstration reposent sur le tiers exclu ; la Proposition « Raisonnement par l'absurde » montre exactement où il sert.

Signaler une erreur

Exemple — Des propositions, et des phrases qui n'en sont pas

« $7$ est un nombre premier » est une proposition, de valeur V.
« $\sqrt{2}$ est un nombre rationnel » est une proposition, de valeur F : une phrase fausse reste une proposition.
« Tout entier pair strictement supérieur à $2$ est la somme de deux nombres premiers » est une proposition — la conjecture de Goldbach — dont la valeur est inconnue à ce jour : une proposition a une valeur de vérité même quand personne ne la connaît.
« Soit $x$ un réel » et l'expression $x^2 + 1$ ne sont pas des propositions : la question « est-ce vrai ? » n'a pas de sens pour l'introduction d'une lettre, ni pour une expression, qui n'affirme rien.

Exemple — Un prédicat devient une proposition

Pour un entier $n$, la phrase $P(n)$ : « $n$ est pair » est un prédicat ; elle n'a pas de valeur de vérité tant que $n$ n'est pas fixé. Fixer $n$ donne des propositions : $P(4)$ est vraie, $P(5)$ est fausse, $P(0)$ est vraie. Quantifier $n$ est une autre façon : « pour tout entier $n$, $n$ est pair » est une proposition, de valeur F, et « il existe un entier $n$ tel que $n$ soit pair » est une proposition, de valeur V. Dans ces deux phrases, la lettre $n$ ne désigne plus un entier particulier.

Compétences à pratiquer

Déterminer la valeur de vérité d'une proposition ★
Distinguer une proposition d'un prédicat ★

I.2 Négation, conjonction, disjonction

Des connecteurs vérifonctionnels

Un connecteur construit une proposition à partir d'une ou de plusieurs propositions : « non », « et », « ou », mais aussi « parce que ». Un connecteur est vérifonctionnel lorsque la valeur de vérité de la proposition composée ne dépend que des valeurs de vérité de ses composantes, et non de leur sens. Les connecteurs des mathématiques sont tous vérifonctionnels : c'est pourquoi chacun d'eux est entièrement décrit par sa table de vérité. Le connecteur « parce que » ne l'est pas. Pour une fonction $f$ dérivable, « $f$ est continue parce que $f$ est dérivable » est vraie, alors que « $f$ est continue parce que $7$ est premier », dont les deux composantes sont vraies elles aussi, est fausse : que $7$ soit premier n'est une raison de rien pour $f$.

Signaler une erreur

Définition — Négation

La négation d'une proposition $p$, notée $\neg p$ (lue « non $p$ »), est la proposition dont la valeur de vérité est l'opposée de celle de $p$. Sa table de vérité est :

$p$	$\neg p$
V	F
F	V

Exemple — Nier n'est pas prendre le contraire

La négation de « $x \ge 0$ » est « $x < 0$ », et non « $x \le 0$ » : le réel $0$ vérifie à la fois « $x \ge 0$ » et « $x \le 0$ », alors qu'une proposition et sa négation n'ont jamais la même valeur.
La négation de « $f$ est croissante sur $\mathbb{R}$ » est « $f$ n'est pas croissante sur $\mathbb{R}$ », ce qui n'est pas « $f$ est décroissante sur $\mathbb{R}$ » : la fonction $x \longmapsto x^2$ n'est ni croissante ni décroissante sur $\mathbb{R}$, puisque $-1 < 0$ et $(-1)^2 > 0^2$, alors que $0 < 1$ et $0^2 < 1^2$.
La négation de « l'entier $n$ est pair » est « $n$ est impair » : ici la propriété contraire est la négation, parce que tout entier est pair ou impair, et pas les deux.

Nier une propriété, c'est affirmer qu'elle est en défaut ; cela ne coïncide avec une propriété contraire que lorsque les deux couvrent tous les cas et s'excluent.

Définition — Conjonction

La conjonction de deux propositions $p$ et $q$, notée $p \wedge q$ (lue « $p$ et $q$ »), est vraie lorsque $p$ et $q$ sont vraies toutes les deux, et fausse sinon. Sa table de vérité est :

$p$	$q$	$p \wedge q$
V	V	V
V	F	F
F	V	F
F	F	F

Exemple — Deux conjonctions

La double inégalité $-1 \le x \le 1$ est une conjonction : elle signifie « $-1 \le x$ et $x \le 1$ ». Pour $x = 0$ les deux parties sont vraies, donc elle est vraie ; pour $x = 2$ la seconde partie est fausse, donc elle est fausse.
Pour un entier $n$, la conjonction « $2 \mid n$ et $3 \mid n$ » est vraie exactement lorsque $6 \mid n$. Si $6 \mid n$, écrivons $n = 6k$ avec $k \in \mathbb{Z}$ ; alors $$ \begin{aligned} n &= 2 \times 3k && \text{(} 6 = 2 \times 3\text{)} \\ &= 3 \times 2k, \end{aligned} $$ donc $2 \mid n$ et $3 \mid n$ : les deux parties sont vraies. Si $2 \mid n$ et $3 \mid n$, il existe $a, b \in \mathbb{Z}$ tels que $n = 2a$ et $n = 3b$, et $$ \begin{aligned} n &= 3n - 2n && \text{(} 3 - 2 = 1\text{)} \\ &= 3 \times 2a - 2 \times 3b && \text{(} n = 2a \text{ et } n = 3b\text{)} \\ &= 6(a - b), \end{aligned} $$ avec $a - b \in \mathbb{Z}$ : $6 \mid n$.

Définition — Disjonction

La disjonction de deux propositions $p$ et $q$, notée $p \vee q$ (lue « $p$ ou $q$ »), est vraie lorsque au moins l'une de $p$ ou $q$ est vraie, et fausse sinon. C'est le « ou » inclusif : $p$ seul, $q$ seul, ou les deux, sont acceptés. Sa table de vérité est :

$p$	$q$	$p \vee q$
V	V	V
V	F	V
F	V	V
F	F	F

Exemple — Ou inclusif, ou exclusif

En mathématiques, « ou » est inclusif : « $2 \mid 6$ ou $3 \mid 6$ » est vraie, et ses deux parties sont vraies. La langue courante emploie souvent un « ou » exclusif : « fromage ou dessert », sur un menu, exclut de prendre les deux. Le ou exclusif, vrai lorsque exactement l'une des propositions $p$ et $q$ est vraie, se dit « ou bien $p$, ou bien $q$ » ; sa table ne diffère de celle de $p \vee q$ que sur la première ligne :

$p$	$q$	$p \vee q$	ou exclusif
V	V	V	F
V	F	V	V
F	V	V	V
F	F	F	F

Compétences à pratiquer

Évaluer une proposition composée ★
Traduire une phrase en formule ★★

I.3 Implication et équivalence

La convention de l'hypothèse fausse

Une implication « si $p$, alors $q$ » n'affirme qu'une chose : chaque fois que $p$ est vraie, $q$ est vraie. Elle n'est donc fausse que dans un cas, $p$ vraie et $q$ fausse, et vraie dans tous les autres — en particulier chaque fois que $p$ est fausse. Cette convention est exigée par les énoncés « pour tout $x$ » : le théorème « pour tout réel $x$, si $x \ge 2$, alors $x^2 \ge 4$ » est vrai, donc l'implication doit être vraie pour tout $x$, y compris pour ceux pour lesquels $x \ge 2$ est fausse. Une implication n'est pas une causalité : « si $0 = 0$, alors $7$ est premier » est vraie, bien que l'égalité $0 = 0$ ne soit en rien une raison pour que $7$ soit premier ; seules comptent les valeurs de vérité.

Signaler une erreur

Définition — Implication

L'implication de $p$ vers $q$, notée $p \Rightarrow q$ (lue « si $p$, alors $q$ » ou « $p$ implique $q$ »), est la proposition qui est fausse uniquement lorsque $p$ est vraie et $q$ est fausse ; elle est vraie dans tous les autres cas. En particulier, une implication d'hypothèse fausse est automatiquement vraie. Sa table de vérité :

$p$	$q$	$p \Rightarrow q$
V	V	V
V	F	F
F	V	V
F	F	V

Exemple — Trois sortes de lignes

L'implication « $0 = 1 \Rightarrow 1 = 1$ » est vraie, et « $0 = 1 \Rightarrow 0 = 2$ » aussi : leur hypothèse est fausse.
La proposition « pour tout réel $x$, si $x$ est un entier naturel, alors $x \ge 0$ » est vraie. Selon $x$, l'implication qu'elle contient tombe sur trois sortes de lignes de la table : pour $x = 3$, entier naturel, elle est du type « V $\Rightarrow$ V » ; pour $x = \frac{1}{2}$, positif sans être un entier naturel, du type « F $\Rightarrow$ V » ; pour $x = -1$, du type « F $\Rightarrow$ F ». Elle est vraie sur chacune. La quatrième sorte, « V $\Rightarrow$ F », ne se produit jamais : c'est exactement ce qu'affirme la proposition.

Définition — Équivalence, contraposée, réciproque

Soient $p$ et $q$ deux propositions. L'équivalence de $p$ et $q$, notée $p \iff q$ et lue « $p$ si et seulement si $q$ », est la proposition qui est vraie lorsque $p$ et $q$ ont la même valeur de vérité, et fausse sinon. Sa table de vérité est :

$p$	$q$	$p \iff q$
V	V	V
V	F	F
F	V	F
F	F	V

La contraposée de l'implication $p \Rightarrow q$ est l'implication $\neg q \Rightarrow \neg p$ ; sa réciproque est l'implication $q \Rightarrow p$.

Exemple — Une réciproque fausse

Pour un réel $x$, l'implication « $x = 1 \Rightarrow x^2 = 1$ » est vraie : si $x = 1$, alors $x^2 = 1^2 = 1$. Sa réciproque « $x^2 = 1 \Rightarrow x = 1$ » est un autre énoncé, et elle est fausse pour $x = -1$ : l'hypothèse $(-1)^2 = 1$ est vraie et la conclusion $-1 = 1$ est fausse. Sa contraposée « $x^2 \ne 1 \Rightarrow x \ne 1$ », en revanche, est vraie pour tout réel $x$, comme l'implication elle-même : une implication et sa contraposée ont toujours la même valeur de vérité, ce qu'établit la Proposition « Équivalence avec la contraposée ».

Compétences à pratiquer

Déterminer la valeur de vérité d'une implication ★
Résoudre une énigme logique ★★★

II Tautologies et lois logiques

II.1 Tautologies et équivalence logique

Les lois de la logique

Une fois les connecteurs définis par leurs tables, certaines formules s'avèrent vraies quelles que soient les valeurs de vérité de leurs lettres : « $p$ ou non $p$ », « si $p$ et $q$, alors $p$ ». Ces formules sont les lois de la logique. Chaque loi se démontre — par sa table, par un calcul avec des lois déjà démontrées, ou en raisonnant sur les lignes où elle pourrait être fausse — et chacune reçoit un nom, pour qu'une démonstration puisse la citer, comme un calcul algébrique cite la distributivité.

Signaler une erreur

Vraie sur chaque ligne

Une table de vérité montre pour quelles valeurs de ses lettres une formule est vraie. Deux cas extrêmes méritent un nom : la formule vraie sur chaque ligne, comme $p \vee \neg p$, et la formule fausse sur chaque ligne, comme $p \wedge \neg p$. Une formule vraie sur chaque ligne ne dit rien des propositions qu'elle combine ; elle dit quelque chose de la logique elle-même.

Signaler une erreur

Définition — Formule propositionnelle, tautologie, contradiction, équivalence logique

Une formule propositionnelle est une expression construite à partir de lettres $p, q, r, \dots$, qui représentent des propositions quelconques, avec les connecteurs $\neg$, $\wedge$, $\vee$, $\Rightarrow$, $\iff$ et des parenthèses ; par exemple $\neg(p \wedge q) \Rightarrow r$. Une négation porte sur la plus courte formule qui la suit ($\neg p \wedge q$ est $(\neg p) \wedge q$), et $\Rightarrow$, $\iff$ séparent des parties plus grandes que $\wedge$, $\vee$ ($p \wedge q \Rightarrow r$ est $(p \wedge q) \Rightarrow r$). Un choix de valeurs de vérité pour les lettres est une ligne de la table de vérité ; sur chaque ligne, la formule prend une valeur de vérité, calculée avec les tables des connecteurs. Une formule à $n$ lettres propositionnelles distinctes a $2^n$ lignes.

Une tautologie est une formule vraie sur chaque ligne de sa table. Une tautologie s'appelle aussi une loi de la logique.
Une contradiction est une formule fausse sur chaque ligne de sa table ; on dit aussi une antilogie.
Deux formules $A$ et $B$ sont logiquement équivalentes lorsque $A \iff B$ est une tautologie, c'est-à-dire lorsque $A$ et $B$ ont la même valeur de vérité sur chaque ligne.

Une loi $A \iff B$ s'énonce « pour toutes propositions $p$, $q$ : $A \iff B$ ».

Exemple — Tiers exclu et non-contradiction

La formule $p \vee \neg p$ est une tautologie : c'est le principe du tiers exclu écrit comme une formule. La formule $p \wedge \neg p$ est une contradiction, et sa négation $\neg(p \wedge \neg p)$ est une tautologie : le principe de non-contradiction. Leur table commune :

$p$	$\neg p$	$p \vee \neg p$	$p \wedge \neg p$	$\neg(p \wedge \neg p)$
V	F	V	F	V
F	V	V	F	V

La table n'a que deux lignes parce que toute proposition a exactement l'une des deux valeurs : elle reformule les deux principes plus qu'elle ne les démontre.

Exemple — Une tautologie et sa réciproque

Décider si la formule $(p \wedge q) \Rightarrow (p \vee q)$ est une tautologie, puis si sa réciproque $(p \vee q) \Rightarrow (p \wedge q)$ en est une.

Correction

On liste les quatre lignes, puis on construit les colonnes, par la Méthode « Construire une table de vérité » du chapitre Raisonnement et démonstration :

$p$	$q$	$p \wedge q$	$p \vee q$	$(p \wedge q) \Rightarrow (p \vee q)$	$(p \vee q) \Rightarrow (p \wedge q)$
V	V	V	V	V	V
V	F	F	V	V	F
F	V	F	V	V	F
F	F	F	F	V	V

La colonne de $(p \wedge q) \Rightarrow (p \vee q)$ vaut V sur chaque ligne : cette formule est une tautologie. La colonne de la réciproque vaut F sur les lignes (V, F) et (F, V) : la réciproque n'est pas une tautologie. Une ligne où une formule est fausse suffit à montrer que ce n'est pas une tautologie : la ligne $p$ vraie, $q$ fausse, où $p \vee q$ est vraie et $p \wedge q$ fausse, aurait suffi.
Être une tautologie ne dépend que de la forme. L'implication « $x \ge 1 \Rightarrow x \ge 0$ » est vraie pour tout réel $x$, mais sa forme $p \Rightarrow q$ n'est pas une tautologie : sa vérité vient de l'ordre des réels, non de la logique.
Seconde méthode : seulement les lignes qui décident. Une implication n'est fausse que sur une ligne où son hypothèse est vraie. L'hypothèse $p \wedge q$ n'est vraie que sur la ligne (V, V), où $p \vee q$ est vraie : aucune ligne ne rend $(p \wedge q) \Rightarrow (p \vee q)$ fausse, c'est donc une tautologie. Avec la ligne (V, F) pour la réciproque, deux lignes tranchent les deux questions, au lieu des quatre lignes de la table : c'est la voie « par le sens » de la Méthode « Démontrer une loi logique ».

Proposition — Principe de remplacement

Soient $A$, $B$ et $F$ des formules propositionnelles telles que $A \iff B$ soit une tautologie, et $F'$ la formule obtenue à partir de $F$ en remplaçant une apparition de $A$ par $B$. Alors $F \iff F'$ est une tautologie : dans toute formule, une partie peut être remplacée par une formule logiquement équivalente. De plus, une tautologie reste une tautologie quand on met des formules à la place de ses lettres, la même formule à la place de chaque apparition d'une même lettre.

Preuve

Remplacement. Fixons une ligne, c'est-à-dire des valeurs de vérité pour toutes les lettres qui apparaissent dans $F$ ou dans $F'$. Sur cette ligne, la tautologie $A \iff B$ est vraie, donc $A$ et $B$ ont la même valeur de vérité, par la table de l'équivalence. La valeur de $F$ sur cette ligne se calcule à partir des valeurs de ses parties, connecteur par connecteur, des parties les plus internes jusqu'à $F$ elle-même, et chaque connecteur n'utilise que les valeurs des parties qu'il relie : il est vérifonctionnel. Le calcul de $F'$ est le même, à ceci près que la partie $B$ se trouve là où était $A$, avec la même valeur. Ainsi chaque partie de $F'$ a la même valeur que la partie correspondante de $F$, et $F'$ a la même valeur que $F$. La ligne étant quelconque, $F$ et $F'$ ont la même valeur sur chaque ligne : $F \iff F'$ est une tautologie. Plusieurs apparitions de $A$ se remplacent l'une après l'autre.
Substitution. Soient $L$ une tautologie en les lettres $p_1, \dots, p_n$, et $L'$ la formule obtenue en mettant des formules $G_1, \dots, G_n$ à la place de ces lettres. Fixons une ligne de la table de $L'$ ; sur elle, $G_1, \dots, G_n$ prennent des valeurs de vérité $v_1, \dots, v_n$. La valeur de $L'$ sur cette ligne se calcule à partir de $v_1, \dots, v_n$ exactement comme la valeur de $L$ sur sa ligne où $p_1, \dots, p_n$ prennent les valeurs $v_1, \dots, v_n$ : elle vaut V, puisque $L$ est une tautologie. La ligne étant quelconque, $L'$ est une tautologie.

Méthode — Démontrer une loi logique

Pour démontrer qu'une formule est une tautologie, ou que deux formules sont logiquement équivalentes, trois voies sont ouvertes :

Par la table de vérité. Lister les $2^n$ lignes, construire les colonnes, comparer : la Méthode « Construire une table de vérité » du chapitre Raisonnement et démonstration. La voie aboutit toujours, mais la table double à chaque nouvelle lettre.
Par le calcul. Écrire une chaîne alignée d'équivalences d'un membre à l'autre, chaque étape justifiée dans la colonne de droite par une loi déjà démontrée, appliquée à une partie de la formule par le principe de remplacement ; la loi de la dernière étape est nommée dans la phrase qui suit la chaîne. Une loi appliquée à une partie d'une formule passe toujours par le principe de remplacement, même là où une chaîne ne le répète pas. Chaque étape conserve la valeur de vérité sur chaque ligne de la table, donc les deux extrémités de la chaîne sont logiquement équivalentes.
Par le sens. N'étudier que les lignes où la formule pourrait être fausse : une implication n'est fausse que sur une sorte de ligne, une conjonction dès que l'une de ses parties est fausse. Pour une équivalence $A \iff B$, montrer que $A$ et $B$ sont fausses sur les mêmes lignes.

Essayer d'abord le sens quand un membre n'est faux ou vrai que sur peu de lignes (une implication ou une disjonction n'est fausse que sur une ligne, une conjonction n'est vraie que sur une ligne), le calcul quand des lois connues s'appliquent, et garder la table en dernier recours. Par exemple, $p \Rightarrow (q \Rightarrow p)$ est une tautologie : elle ne pourrait être fausse que sur une ligne où $p$ est vraie et $q \Rightarrow p$ fausse ; or $q \Rightarrow p$ n'est fausse que lorsque $p$ est fausse. Aucune ligne ne rend la formule fausse.

Compétences à pratiquer

Reconnaître une tautologie ★
Compter les lignes où une formule est vraie ★
Démontrer une équivalence logique par une table de vérité ★
Démontrer une loi par la méthode la plus courte ★★★

II.2 Lois de la négation, de la conjonction et de la disjonction

Des lois qui portent un nom

Les lois les plus utilisées portent un nom : double négation, lois de De Morgan, commutativité, associativité, distributivité. Un nom permet à un calcul de justifier chaque étape par la loi qu'il applique, comme un calcul algébrique justifie $x(y + z) = xy + xz$ par la distributivité ; la Méthode « Simplifier une formule » met ces lois au travail.

Signaler une erreur

Proposition — Double négation

Pour toute proposition $p$ : $$ \neg\neg p \iff p. $$ Nier deux fois redonne la proposition.

Preuve

Par la Définition « Négation », la valeur de vérité de $\neg p$ est l'opposée de celle de $p$, et la valeur de vérité de $\neg\neg p$ est l'opposée de celle de $\neg p$. Il n'y a que deux valeurs de vérité, donc l'opposée de l'opposée d'une valeur est cette valeur elle-même : $\neg\neg p$ a la valeur de vérité de $p$, sur les deux lignes. Donc $\neg\neg p \iff p$ est une tautologie.
Seconde démonstration : par la table de vérité.

$p$	$\neg p$	$\neg\neg p$
V	F	V
F	V	F

Les colonnes de $p$ et de $\neg\neg p$ coïncident sur les deux lignes.

Proposition — Lois de De Morgan

Pour toutes propositions $p$, $q$ : $$ \neg(p \wedge q) \iff \neg p \vee \neg q \qquad \text{et} \qquad \neg(p \vee q) \iff \neg p \wedge \neg q. $$ La négation échange « et » et « ou », et nie chaque partie.

Preuve

Première loi. Par la Définition « Conjonction », $p \wedge q$ est fausse exactement lorsque l'une au moins des propositions $p$, $q$ est fausse, c'est-à-dire lorsque l'une au moins des propositions $\neg p$, $\neg q$ est vraie — ce qui signifie que $\neg p \vee \neg q$ est vraie, par la Définition « Disjonction ». Ainsi $\neg(p \wedge q)$, vraie exactement lorsque $p \wedge q$ est fausse, et $\neg p \vee \neg q$ sont vraies sur les mêmes lignes : elles sont logiquement équivalentes.
Seconde loi. Elle découle de la première, appliquée aux propositions $\neg p$ et $\neg q$ : $$ \begin{aligned} \neg(p \vee q) &\iff \neg(\neg\neg p \vee \neg\neg q) && \text{(double négation, deux fois, et remplacement)} \\ &\iff \neg\neg(\neg p \wedge \neg q) && \text{(première loi pour } \neg p, \neg q\text{, et remplacement)} \\ &\iff \neg p \wedge \neg q. \end{aligned} $$ La dernière équivalence est la double négation, appliquée à $\neg p \wedge \neg q$.
Seconde démonstration : par la table de vérité.

$p$	$q$	$\neg p$	$\neg q$	$p \wedge q$	$\neg(p \wedge q)$	$\neg p \vee \neg q$	$p \vee q$	$\neg(p \vee q)$	$\neg p \wedge \neg q$
V	V	F	F	V	F	F	V	F	F
V	F	F	V	F	V	V	V	F	F
F	V	V	F	F	V	V	V	F	F
F	F	V	V	F	V	V	F	V	V

Les colonnes de $\neg(p \wedge q)$ et de $\neg p \vee \neg q$ coïncident, de même que les colonnes de $\neg(p \vee q)$ et de $\neg p \wedge \neg q$.

Exemple — Nier une double inégalité

Pour un réel $x$, la négation de la double inégalité $-1 \le x \le 1$ se calcule avec la loi de De Morgan : $$ \begin{aligned} \neg(-1 \le x \le 1) &\iff \neg\left((-1 \le x) \wedge (x \le 1)\right) && \text{(une double inégalité est une conjonction)} \\ &\iff \neg(-1 \le x) \vee \neg(x \le 1) && \text{(loi de De Morgan)} \\ &\iff (x < -1) \vee (x > 1). \end{aligned} $$ La dernière équivalence nie chaque inégalité : pour des réels, la négation de $a \le b$ est $a > b$. La négation de « entre $-1$ et $1$ » est « en dehors » : le complémentaire de $[-1, 1]$ dans $\mathbb{R}$ est $]-\infty, -1[ \, \cup \, ]1, +\infty[$. Le « et » est devenu « ou » : aucun réel n'est à la fois strictement inférieur à $-1$ et strictement supérieur à $1$.

Proposition — Commutativité et associativité

Pour toutes propositions $p$, $q$, $r$ : $$ p \wedge q \iff q \wedge p, \qquad (p \wedge q) \wedge r \iff p \wedge (q \wedge r), $$ $$ p \vee q \iff q \vee p, \qquad (p \vee q) \vee r \iff p \vee (q \vee r). $$ Ainsi $p \wedge q \wedge r$ et $p \vee q \vee r$ s'écrivent sans parenthèses. Une formule qui mélange les deux connecteurs garde ses parenthèses : $(p \wedge q) \vee r$ et $p \wedge (q \vee r)$ ne sont pas logiquement équivalentes, et l'on n'écrit jamais $p \wedge q \vee r$.

Preuve

Par la Définition « Conjonction », une conjonction est vraie exactement lorsque ses deux parties sont vraies. Ainsi $p \wedge q$ et $q \wedge p$ sont toutes deux vraies exactement lorsque $p$ et $q$ sont vraies ; et $(p \wedge q) \wedge r$ est vraie exactement lorsque $p \wedge q$ et $r$ sont vraies, c'est-à-dire lorsque $p$, $q$, $r$ sont vraies toutes les trois — exactement comme $p \wedge (q \wedge r)$. Par la Définition « Disjonction », une disjonction est fausse exactement lorsque ses deux parties sont fausses. Ainsi $p \vee q$ et $q \vee p$ sont toutes deux fausses exactement lorsque $p$ et $q$ sont fausses ; et $(p \vee q) \vee r$ et $p \vee (q \vee r)$ sont toutes deux fausses exactement lorsque $p$, $q$, $r$ sont fausses toutes les trois. Dans chacune des quatre lois, les deux membres ont la même valeur de vérité sur chaque ligne.
Sur la ligne où $p$ est fausse et $q$, $r$ vraies, $(p \wedge q) \vee r$ est vraie, puisque $r$ l'est, alors que $p \wedge (q \vee r)$ est fausse, puisque $p$ l'est : les deux formules ne sont pas logiquement équivalentes.

Proposition — Distributivité

Pour toutes propositions $p$, $q$, $r$ : $$ p \wedge (q \vee r) \iff (p \wedge q) \vee (p \wedge r) \qquad \text{et} \qquad p \vee (q \wedge r) \iff (p \vee q) \wedge (p \vee r). $$ Chacun des deux connecteurs se distribue sur l'autre — à la différence de la multiplication et de l'addition des réels, pour lesquelles $x + yz$ et $(x + y)(x + z)$ diffèrent en général.

Preuve

Les tables de la conjonction et de la disjonction donnent, pour toute proposition $X$ : si $p$ est vraie, $p \wedge X$ a la valeur de $X$ et $p \vee X$ est vraie ; si $p$ est fausse, $p \wedge X$ est fausse et $p \vee X$ a la valeur de $X$. On distingue deux cas, selon la valeur de $p$ ; ils couvrent les huit lignes de la table, quatre dans chacun.

Cas $p$ vraie. Les formules $p \wedge (q \vee r)$ et $(p \wedge q) \vee (p \wedge r)$ ont toutes deux la valeur de $q \vee r$, la seconde parce que $p \wedge q$ et $p \wedge r$ ont les valeurs de $q$ et de $r$. Les formules $p \vee (q \wedge r)$ et $(p \vee q) \wedge (p \vee r)$ sont toutes deux vraies, la seconde comme conjonction de deux propositions vraies.
Cas $p$ fausse. Les formules $p \wedge (q \vee r)$ et $(p \wedge q) \vee (p \wedge r)$ sont toutes deux fausses, la seconde comme disjonction de deux propositions fausses. Les formules $p \vee (q \wedge r)$ et $(p \vee q) \wedge (p \vee r)$ ont toutes deux la valeur de $q \wedge r$, la seconde parce que $p \vee q$ et $p \vee r$ ont les valeurs de $q$ et de $r$.

Dans les deux cas, les deux membres de chaque loi ont la même valeur de vérité : les deux lois sont des tautologies.
Seconde démonstration : par la table de vérité. Huit lignes, une table pour chaque loi :

$p$	$q$	$r$	$q \vee r$	$p \wedge (q \vee r)$	$p \wedge q$	$p \wedge r$	$(p \wedge q) \vee (p \wedge r)$
V	V	V	V	V	V	V	V
V	V	F	V	V	V	F	V
V	F	V	V	V	F	V	V
V	F	F	F	F	F	F	F
F	V	V	V	F	F	F	F
F	V	F	V	F	F	F	F
F	F	V	V	F	F	F	F
F	F	F	F	F	F	F	F

$p$	$q$	$r$	$q \wedge r$	$p \vee (q \wedge r)$	$p \vee q$	$p \vee r$	$(p \vee q) \wedge (p \vee r)$
V	V	V	V	V	V	V	V
V	V	F	F	V	V	V	V
V	F	V	F	V	V	V	V
V	F	F	F	V	V	V	V
F	V	V	V	V	V	V	V
F	V	F	F	F	V	F	F
F	F	V	F	F	F	V	F
F	F	F	F	F	F	F	F

Les colonnes de $p \wedge (q \vee r)$ et de $(p \wedge q) \vee (p \wedge r)$ coïncident, de même que les colonnes de $p \vee (q \wedge r)$ et de $(p \vee q) \wedge (p \vee r)$.

Méthode — Simplifier une formule

Pour transformer une formule en une formule équivalente plus simple :

écrire une chaîne alignée d'équivalences qui s'ouvre sur la formule donnée, une loi par ligne, nommée dans la colonne de droite — sauf sur la dernière ligne, dont la loi est nommée dans la phrase qui suit la chaîne ;
simplifier d'abord les parties internes lorsqu'une partie devient une tautologie ou une contradiction, puis faire entrer les négations jusqu'aux lettres, avec les lois de De Morgan et la double négation ;
utiliser les constantes : pour une tautologie $L$ et une contradiction $C$, et toute formule $X$, $$ X \wedge L \iff X, \qquad X \vee L \iff L, \qquad X \wedge C \iff C, \qquad X \vee C \iff X, $$ puisque sur chaque ligne $L$ est vraie et $C$ fausse, et que les tables de $\wedge$ et de $\vee$ donnent la valeur ; par commutativité, il en va de même avec la constante à gauche.

Par le principe de remplacement, chaque formule de la chaîne est logiquement équivalente à la première.

Exemple — Simplifier une négation

Montrer que $\neg(p \vee (\neg p \wedge q)) \iff \neg p \wedge \neg q$ est une tautologie, en simplifiant son membre de gauche.

Correction

La partie interne se simplifie d'abord : $$ \begin{aligned} \neg(p \vee (\neg p \wedge q)) &\iff \neg\left((p \vee \neg p) \wedge (p \vee q)\right) && \text{(distributivité, et remplacement)} \\ &\iff \neg(p \vee q) && \text{(} p \vee \neg p \text{ est une tautologie, neutre pour } \wedge\text{)} \\ &\iff \neg p \wedge \neg q. \end{aligned} $$ La dernière équivalence est la loi de De Morgan. Donc l'équivalence est une tautologie. En mots : « ni $p$, ni ($\neg p$ et $q$) » revient à « ni $p$ ni $q$ ».
Seconde méthode : faire entrer la négation d'abord. $$ \begin{aligned} \neg(p \vee (\neg p \wedge q)) &\iff \neg p \wedge \neg(\neg p \wedge q) && \text{(loi de De Morgan)} \\ &\iff \neg p \wedge (\neg\neg p \vee \neg q) && \text{(loi de De Morgan, et remplacement)} \\ &\iff \neg p \wedge (p \vee \neg q) && \text{(double négation, et remplacement)} \\ &\iff (\neg p \wedge p) \vee (\neg p \wedge \neg q) && \text{(distributivité)} \\ &\iff \neg p \wedge \neg q. \end{aligned} $$ La dernière équivalence vient de ce que $\neg p \wedge p$ est une contradiction, neutre pour $\vee$. La première méthode est plus courte : simplifier d'abord l'intérieur a supprimé toute une partie avant qu'il faille faire entrer la négation.

Compétences à pratiquer

Reconnaître la négation d'une formule ★
Nier une conjonction ou une disjonction ★
Appliquer les lois de De Morgan ★★
Simplifier une formule ★★

II.3 Lois de l'implication

Le connecteur des théorèmes

L'implication est le connecteur des théorèmes : presque tout théorème s'énonce « si …, alors … », et presque toute démonstration en établit une. Ses lois disent comment réécrire une implication — comme une disjonction, par sa négation, par sa contraposée — et comment deux implications font une équivalence.

Signaler une erreur

Proposition — L'implication comme disjonction

Pour toutes propositions $p$, $q$ : $$ (p \Rightarrow q) \iff \neg p \vee q. $$ Une implication est vraie exactement lorsque son hypothèse est fausse ou sa conclusion vraie.

Preuve

Par la Définition « Implication », $p \Rightarrow q$ n'est fausse que sur une ligne : $p$ vraie et $q$ fausse. Par la Définition « Disjonction », $\neg p \vee q$ n'est fausse que lorsque $\neg p$ et $q$ sont fausses toutes les deux, c'est-à-dire sur la même ligne : $p$ vraie et $q$ fausse. Les deux formules sont fausses sur la même ligne et vraies sur les trois autres : elles sont logiquement équivalentes.

Proposition — Négation d'une implication

Pour toutes propositions $p$, $q$ : $$ \neg(p \Rightarrow q) \iff p \wedge \neg q. $$ La négation d'une implication n'est pas une implication : c'est la conjonction « $p$ et non $q$ », qui décrit l'unique ligne où l'implication est fausse.

Preuve

On transforme le membre de gauche : $$ \begin{aligned} \neg(p \Rightarrow q) &\iff \neg(\neg p \vee q) && \text{(l'implication comme disjonction, et remplacement)} \\ &\iff \neg\neg p \wedge \neg q && \text{(loi de De Morgan)} \\ &\iff p \wedge \neg q. \end{aligned} $$ La dernière équivalence est la double négation, appliquée à la partie $\neg\neg p$ par remplacement.
Seconde démonstration : par l'unique ligne fausse. L'implication $p \Rightarrow q$ n'est fausse que sur une ligne, $p$ vraie et $q$ fausse ; donc sa négation n'est vraie que sur cette ligne. La conjonction $p \wedge \neg q$ est vraie exactement lorsque $p$ et $\neg q$ sont vraies, c'est-à-dire lorsque $p$ est vraie et $q$ fausse : sur la même ligne. Les deux formules sont vraies sur la même ligne et fausses sur les autres : elles sont logiquement équivalentes.

Proposition — Équivalence avec la contraposée

Pour toutes propositions $p$, $q$ : $$ (p \Rightarrow q) \iff (\neg q \Rightarrow \neg p). $$ Une implication et sa contraposée ont toujours la même valeur de vérité. Sa réciproque $q \Rightarrow p$, en revanche, ne lui est pas logiquement équivalente.

Preuve

On transforme la contraposée : $$ \begin{aligned} (\neg q \Rightarrow \neg p) &\iff \neg\neg q \vee \neg p && \text{(l'implication comme disjonction)} \\ &\iff q \vee \neg p && \text{(double négation, et remplacement)} \\ &\iff \neg p \vee q && \text{(commutativité)} \\ &\iff (p \Rightarrow q). \end{aligned} $$ La dernière équivalence est la Proposition « L'implication comme disjonction », lue de droite à gauche.
Seconde démonstration : par le sens. La contraposée $\neg q \Rightarrow \neg p$ n'est fausse que sur une ligne : $\neg q$ vraie et $\neg p$ fausse, c'est-à-dire $q$ fausse et $p$ vraie — exactement la ligne où $p \Rightarrow q$ est fausse. Les deux implications sont fausses sur la même ligne et vraies sur les autres : elles sont logiquement équivalentes.
La réciproque. Sur la ligne $p$ fausse, $q$ vraie, l'implication $p \Rightarrow q$ est vraie et sa réciproque $q \Rightarrow p$ est fausse : la formule $(p \Rightarrow q) \iff (q \Rightarrow p)$ est fausse sur cette ligne, donc ce n'est pas une tautologie.

Exemple — Quatre énoncés autour d'une implication

Pour un réel $x$, on considère l'implication « $x = 2 \Rightarrow x^2 = 4$ ». Écrire sa réciproque, sa contraposée et sa négation, et déterminer pour quels réels $x$ chacun des quatre énoncés est vrai.

Correction

L'implication « $x = 2 \Rightarrow x^2 = 4$ » est vraie pour tout réel $x$ : si $x = 2$, alors $x^2 = 2^2 = 4$ ; si $x \ne 2$, son hypothèse est fausse.
La réciproque « $x^2 = 4 \Rightarrow x = 2$ » est fausse pour $x = -2$, où son hypothèse $(-2)^2 = 4$ est vraie et sa conclusion $-2 = 2$ fausse. Elle est vraie pour tout autre réel : pour $x = 2$ sa conclusion est vraie, et pour $x \notin \{-2, 2\}$ son hypothèse est fausse.
La contraposée « $x^2 \ne 4 \Rightarrow x \ne 2$ » est vraie pour tout réel $x$, par l'équivalence avec la contraposée.
La négation « $x = 2$ et $x^2 \ne 4$ », obtenue par la négation d'une implication, est fausse pour tout réel $x$ : elle exigerait $x = 2$ et $2^2 \ne 4$.

L'implication et sa contraposée ont la même valeur de vérité pour tout $x$, et la négation prend la valeur opposée ; la réciproque est un autre énoncé, faux pour $x = -2$ seulement.

Proposition — Équivalence et double implication

Pour toutes propositions $p$, $q$ : $$ (p \iff q) \iff \left((p \Rightarrow q) \wedge (q \Rightarrow p)\right). $$ Une équivalence est une double implication : elle se démontre en démontrant les deux implications.

Preuve

Par la Définition « Conjonction », le membre de droite est faux exactement lorsque l'une des deux implications est fausse : $p \Rightarrow q$ sur la ligne $p$ vraie, $q$ fausse, ou $q \Rightarrow p$ sur la ligne $q$ vraie, $p$ fausse. Ce sont exactement les deux lignes où $p$ et $q$ n'ont pas la même valeur de vérité, c'est-à-dire où $p \iff q$ est fausse, par la Définition « Équivalence, contraposée, réciproque ». Les deux membres sont faux sur les mêmes lignes : ils sont logiquement équivalents.
Seconde démonstration : par la table de vérité.

$p$	$q$	$p \Rightarrow q$	$q \Rightarrow p$	$(p \Rightarrow q) \wedge (q \Rightarrow p)$	$p \iff q$
V	V	V	V	V	V
V	F	F	V	F	F
F	V	V	F	F	F
F	F	V	V	V	V

Les colonnes de $(p \Rightarrow q) \wedge (q \Rightarrow p)$ et de $p \iff q$ coïncident.

Compétences à pratiquer

Nommer la loi d'une équivalence ★
Écrire la contraposée, la réciproque et la négation d'une implication ★★
Démontrer une loi de l'implication par le calcul ★★★

II.4 Conditions nécessaires et suffisantes

Conditions et inclusions

Beaucoup de théorèmes s'énoncent dans le vocabulaire des conditions : « il suffit que », « il faut que », « si et seulement si ». Le chapitre Raisonnement et démonstration lit une implication vraie $p(x) \Rightarrow q(x)$ portant sur un objet $x$ comme une inclusion : l'ensemble des objets qui vérifient $p$ est contenu dans l'ensemble de ceux qui vérifient $q$. Être dans le petit ensemble suffit pour être dans le grand ; être dans le grand est nécessaire pour être dans le petit. « Suffisant » et « nécessaire » sont les deux lectures d'une même implication, en sens opposés.

Signaler une erreur

Définition — Condition nécessaire, suffisante, nécessaire et suffisante

Soient $p$ et $q$ deux propositions.

$p$ est une condition suffisante pour $q$ lorsque $p \Rightarrow q$ est vraie : « pour que $q$, il suffit que $p$ ». On dit aussi « $q$ si $p$ ».
$p$ est une condition nécessaire pour $q$ lorsque $q \Rightarrow p$ est vraie : « pour que $q$, il faut que $p$ » ; sans $p$, pas de $q$. On dit aussi « $q$ seulement si $p$ ».
$p$ est une condition nécessaire et suffisante pour $q$ lorsque $p \iff q$ est vraie : « $q$ si et seulement si $p$ ».

Méthode — Traduire « il faut », « il suffit », « seulement si »

Pour écrire une phrase de conditions comme une formule, trouver son hypothèse et sa conclusion, puis lire le tableau : la même implication $p \Rightarrow q$ se cache derrière quatre formulations.

Phrase	Formule
« il suffit que $p$ pour que $q$ »	$p \Rightarrow q$
« $q$ si $p$ »	$p \Rightarrow q$
« pour que $p$, il faut que $q$ »	$p \Rightarrow q$
« $p$ seulement si $q$ »	$p \Rightarrow q$
« $p$ si et seulement si $q$ »	$p \iff q$

Deux contrôles :

la contraposée : « pour que $p$, il faut que $q$ » dit aussi « sans $q$, pas de $p$ », c'est-à-dire $\neg q \Rightarrow \neg p$, la contraposée de $p \Rightarrow q$ ;
un exemple : sur un cas où l'hypothèse est vraie, la conclusion doit suivre.

« Seulement si » introduit la conclusion : « $p$ seulement si $q$ » est $p \Rightarrow q$, la même implication que « $q$ si $p$ », dont le « si » introduit l'hypothèse.

Exemple — Divisibilité : si, seulement si

Pour un entier $n$ :

« $4 \mid n$ » est une condition suffisante pour « $2 \mid n$ » : si $n = 4k$ avec $k \in \mathbb{Z}$, alors $n = 2 \times 2k$. Autrement dit, « $2 \mid n$ si $4 \mid n$ », ou « $4 \mid n$ seulement si $2 \mid n$ ».
« $4 \mid n$ » n'est pas une condition nécessaire pour « $2 \mid n$ » : $n = 2$ est divisible par $2$ et pas par $4$, donc l'énoncé « pour tout entier $n$, $2 \mid n$ seulement si $4 \mid n$ » est faux.
« $2 \mid n$ et $3 \mid n$ » est une condition nécessaire et suffisante pour « $6 \mid n$ », comme le montre l'Exemple « Deux conjonctions » : « $6 \mid n$ si et seulement si $2 \mid n$ et $3 \mid n$ ».

Compétences à pratiquer

Identifier une condition nécessaire ou suffisante ★
Traduire « il faut », « il suffit », « seulement si » ★
Classer des conditions : nécessaire, suffisante, les deux, aucune ★★
Trouver une condition nécessaire et suffisante ★★★

III Les lois des raisonnements

III.1 Déduire : modus ponens et transitivité

Une tautologie derrière chaque schéma

Chaque schéma de démonstration du chapitre Raisonner et rédiger — déduire, enchaîner des implications, distinguer des cas, contraposer, raisonner par l'absurde — est valide parce qu'une formule est une tautologie : le schéma ne peut pas conduire d'hypothèses vraies à une conclusion fausse, quelles que soient les propositions auxquelles on l'applique. Les lois qui fondent les schémas sont les Propositions « Modus ponens », « Transitivité de l'implication », « La disjonction comme implication », « Disjonction des cas », « Équivalence avec la contraposée », « Équivalence et double implication », « Raisonnement par l'absurde » et « Négation d'une implication quantifiée ». La rédaction de chaque schéma — sa première et sa dernière phrase — reste dans les Méthodes de Raisonner et rédiger, citées par leur nom.

Signaler une erreur

« Donc » est un modus ponens

Dans une démonstration rédigée, « $p$, donc $q$ » relie deux énoncés vrais. Derrière le mot se tiennent une implication $p \Rightarrow q$, le plus souvent non écrite, et une règle qui tire $q$ de $p$ et de $p \Rightarrow q$ : le modus ponens. C'est pourquoi la flèche $\Rightarrow$ ne remplace jamais le mot « donc » : la flèche énonce une implication, le mot en applique une. Une suite de « donc » est une chaîne d'implications, que la transitivité referme.

Signaler une erreur

Proposition — Modus ponens

Pour toutes propositions $p$, $q$, la formule suivante est une tautologie : $$ (p \wedge (p \Rightarrow q)) \Rightarrow q. $$ En mots : de $p$ et de $p \Rightarrow q$, on peut déduire $q$ — la règle de déduction.

Preuve

L'implication $(p \wedge (p \Rightarrow q)) \Rightarrow q$ ne pourrait être fausse que sur une ligne où son hypothèse est vraie et $q$ fausse. Son hypothèse est vraie lorsque $p$ et $p \Rightarrow q$ sont vraies toutes les deux ; or, avec $p$ vraie, $p \Rightarrow q$ n'est vraie que si $q$ est vraie, la ligne ($p$ vraie, $q$ fausse) étant la ligne fausse d'une implication. Aucune ligne ne rend donc la formule fausse : c'est une tautologie.
Seconde démonstration : par la table de vérité.

$p$	$q$	$p \Rightarrow q$	$p \wedge (p \Rightarrow q)$	$(p \wedge (p \Rightarrow q)) \Rightarrow q$
V	V	V	V	V
V	F	F	F	V
F	V	V	F	V
F	F	V	F	V

La dernière colonne vaut V sur chaque ligne.

Exemple — 12 est multiple de 4, donc de 2

Dans la phrase « $12$ est multiple de $4$, donc multiple de $2$ », prenons $p$ : « $12$ est multiple de $4$ » et $q$ : « $12$ est multiple de $2$ ». La proposition $p$ est vraie, puisque $12 = 4 \times 3$, et l'implication $p \Rightarrow q$ est vraie, comme cas particulier de « tout multiple de $4$ est multiple de $2$ » ($4k = 2 \times 2k$). Le modus ponens donne $q$. La phrase écrit $p$ et $q$ ; l'implication et la règle restent non écrites.
Les deux hypothèses sont nécessaires. L'implication seule ne prouve rien sur sa conclusion : « si $14$ est multiple de $4$, alors $14$ est multiple de $8$ » est vraie, puisque son hypothèse est fausse, et $14$ n'est pas multiple de $8$. Et $q$ avec $p \Rightarrow q$ ne prouvent pas $p$ : $6$ est multiple de $2$, tout multiple de $4$ est multiple de $2$, et $6$ n'est pas multiple de $4$.

Proposition — Transitivité de l'implication

Pour toutes propositions $p$, $q$, $r$, la formule suivante est une tautologie : $$ ((p \Rightarrow q) \wedge (q \Rightarrow r)) \Rightarrow (p \Rightarrow r). $$ Deux implications s'enchaînent en une seule.

Preuve

La formule est une implication, donc elle ne pourrait être fausse que sur une ligne où son hypothèse est vraie. Sur une telle ligne, $p \Rightarrow q$ et $q \Rightarrow r$ sont vraies, et $p \Rightarrow r$ ne pourrait être fausse que si $p$ est vraie. Si $p$ est vraie, le modus ponens, appliqué à $p$ et à $p \Rightarrow q$, donne $q$ ; appliqué à $q$ et à $q \Rightarrow r$, il donne $r$ : ainsi $p \Rightarrow r$ est vraie. Aucune ligne ne rend la formule fausse : c'est une tautologie. La transitivité tient en deux modus ponens successifs — la chaîne « $p$, donc $q$, donc $r$ ».
Seconde démonstration : par la table de vérité. Huit lignes ; on note $H$ la formule $(p \Rightarrow q) \wedge (q \Rightarrow r)$.

$p$	$q$	$r$	$p \Rightarrow q$	$q \Rightarrow r$	$H$	$p \Rightarrow r$	$H \Rightarrow (p \Rightarrow r)$
V	V	V	V	V	V	V	V
V	V	F	V	F	F	F	V
V	F	V	F	V	F	V	V
V	F	F	F	V	F	F	V
F	V	V	V	V	V	V	V
F	V	F	V	F	F	V	V
F	F	V	V	V	V	V	V
F	F	F	V	V	V	V	V

La dernière colonne vaut V sur chaque ligne.

Exemple — Une chaîne d'implications

Pour tout entier $n$ : $$ \begin{aligned} 12 \mid n &\Rightarrow 6 \mid n \\ 6 \mid n &\Rightarrow 2 \mid n. \end{aligned} $$ La première implication vient de ce que $n = 12k$ donne $n = 6 \times 2k$, la seconde de ce que $n = 6k$ donne $n = 2 \times 3k$. Par transitivité de l'implication, $12 \mid n \Rightarrow 2 \mid n$. Dans une démonstration, la chaîne s'écrit avec des mots : « si $12 \mid n$, alors $6 \mid n$, donc $2 \mid n$ ». La transitivité ne propage les implications que dans un sens : $2 \mid n \Rightarrow 12 \mid n$ est fausse pour $n = 2$ : $2 \mid 2$, et $12 \nmid 2$.

Compétences à pratiquer

Reconnaître la règle d'une déduction ★
Appliquer le modus ponens et la transitivité ★
Annoter une démonstration ★
Démontrer une règle d'inférence ★★

III.2 Disjonction des cas, contraposition, absurde

Des schémas aux lois

Chacune des Méthodes suivantes du chapitre Raisonner et rédiger repose sur une loi :

la Méthode « Démontrer une implication » : la Définition « Implication », d'après laquelle seules les lignes où l'hypothèse est vraie demandent un argument ;
la Méthode « Démontrer une disjonction » : la Proposition « La disjonction comme implication » ;
la Méthode « Raisonner par disjonction des cas » : la Proposition « Disjonction des cas » ;
la Méthode « Démontrer une implication par contraposée » : la Proposition « Équivalence avec la contraposée » ;
la Méthode « Démontrer une équivalence » : la Proposition « Équivalence et double implication » ;
la Méthode « Rédiger un raisonnement par l'absurde » : la Proposition « Raisonnement par l'absurde » ;
la Méthode « Réfuter une implication » : la Proposition « Négation d'une implication quantifiée ».

Le tiers exclu intervient en une étape : « $p$ n'est pas fausse, donc $p$ est vraie ». Trois schémas reposent sur cette étape — démontrer une disjonction en supposant l'une des parties fausse, démontrer une implication par sa contraposée, raisonner par l'absurde : les démonstrations de leurs lois, les Propositions « La disjonction comme implication », « Équivalence avec la contraposée » et « Raisonnement par l'absurde », passent par elle, par la double négation ou directement. De même toute disjonction des cas dont les deux cas sont $p$ et $\neg p$. D'autres démonstrations du chapitre l'utilisent aussi, comme celles de la double négation et de la négation des quantificateurs. La Méthode « Rédiger une démonstration par analyse-synthèse » ne repose sur aucune étape de ce genre : son analyse démontre une implication, sa synthèse vérifie chaque candidat.

Signaler une erreur

Proposition — La disjonction comme implication

Pour toutes propositions $p$, $q$ : $$ p \vee q \iff (\neg p \Rightarrow q). $$ Pour démontrer une disjonction, il suffit de supposer l'une des parties fausse et de démontrer l'autre.

Preuve

On transforme le membre de droite : $$ \begin{aligned} (\neg p \Rightarrow q) &\iff \neg\neg p \vee q && \text{(l'implication comme disjonction)} \\ &\iff p \vee q. \end{aligned} $$ La dernière équivalence est la double négation, appliquée à la partie $\neg\neg p$ par remplacement.
Seconde démonstration : par le sens. L'implication $\neg p \Rightarrow q$ n'est fausse que lorsque $\neg p$ est vraie et $q$ fausse, c'est-à-dire lorsque $p$ et $q$ sont fausses toutes les deux — l'unique ligne où $p \vee q$ est fausse. Les deux membres sont faux sur la même ligne : ils sont logiquement équivalents.

Proposition — Disjonction des cas

Pour toutes propositions $p$, $q$, $r$ : $$ \left((p \Rightarrow r) \wedge (q \Rightarrow r)\right) \iff \left((p \vee q) \Rightarrow r\right). $$ Une conclusion qui découle de chaque cas découle de leur disjonction : lorsque $p \vee q$ est vraie et que chacune des propositions $p$, $q$ implique $r$, la proposition $r$ est vraie.

Preuve

On transforme le membre de gauche : $$ \begin{aligned} (p \Rightarrow r) \wedge (q \Rightarrow r) &\iff (\neg p \vee r) \wedge (\neg q \vee r) && \text{(l'implication comme disjonction, deux fois)} \\ &\iff (r \vee \neg p) \wedge (r \vee \neg q) && \text{(commutativité, deux fois)} \\ &\iff r \vee (\neg p \wedge \neg q) && \text{(distributivité)} \\ &\iff (\neg p \wedge \neg q) \vee r && \text{(commutativité)} \\ &\iff \neg(p \vee q) \vee r && \text{(loi de De Morgan, et remplacement)} \\ &\iff \left((p \vee q) \Rightarrow r\right). \end{aligned} $$ La dernière équivalence est la Proposition « L'implication comme disjonction », lue de droite à gauche. Si de plus $p \vee q$ est vraie, le modus ponens, appliqué à $p \vee q$ et à $(p \vee q) \Rightarrow r$, donne $r$.
Seconde démonstration : par le sens. Le membre de droite est faux exactement lorsque $p \vee q$ est vraie et $r$ fausse. Le membre de gauche est faux exactement lorsque l'une au moins des deux implications est fausse, c'est-à-dire lorsque $p$ est vraie et $r$ fausse, ou $q$ vraie et $r$ fausse — autrement dit lorsque $r$ est fausse et que l'une au moins des propositions $p$, $q$ est vraie, ce qui signifie $p \vee q$ vraie. Les deux membres sont faux sur les mêmes lignes : ils sont logiquement équivalents.

Proposition — Raisonnement par l'absurde

Pour toutes propositions $p$, $q$ : $$ (\neg p \Rightarrow (q \wedge \neg q)) \iff p. $$ Une proposition dont la négation implique une contradiction est vraie : pour démontrer $p$, il suffit de déduire de $\neg p$ une proposition $q$ accompagnée de sa négation $\neg q$.

Preuve

La proposition $q \wedge \neg q$ est fausse sur chaque ligne, par le principe de non-contradiction. Sur une ligne où $p$ est fausse, $\neg p$ est vraie, donc l'implication $\neg p \Rightarrow (q \wedge \neg q)$, d'hypothèse vraie et de conclusion fausse, est fausse. Sur une ligne où $p$ est vraie, $\neg p$ est fausse, et l'implication est vraie. Par le principe du tiers exclu, toute ligne est de l'une de ces deux sortes : le membre de gauche a la valeur de vérité de $p$ sur chaque ligne, et les deux membres sont logiquement équivalents. Le tiers exclu sert exactement ici : il change « $p$ n'est pas fausse » en « $p$ est vraie ».
Seconde démonstration : par le calcul. $$ \begin{aligned} (\neg p \Rightarrow (q \wedge \neg q)) &\iff \neg\neg p \vee (q \wedge \neg q) && \text{(l'implication comme disjonction)} \\ &\iff p \vee (q \wedge \neg q) && \text{(double négation, et remplacement)} \\ &\iff p. \end{aligned} $$ La dernière équivalence vient de ce que $q \wedge \neg q$ est une contradiction, neutre pour $\vee$ (Méthode « Simplifier une formule »).

Exemple — Une disjonction démontrée par l'absurde

Montrer que pour tout réel $x$, $\lvert x - 1 \rvert \ge 1$ ou $\lvert x + 1 \rvert \ge 1$, et nommer la loi qui fonde chaque étape de la démonstration.

Correction

Soit $x \in \mathbb{R}$. Supposons par l'absurde que la disjonction « $\lvert x - 1 \rvert \ge 1$ ou $\lvert x + 1 \rvert \ge 1$ » soit fausse. Par la loi de De Morgan, sa négation est la conjonction « $\lvert x - 1 \rvert < 1$ et $\lvert x + 1 \rvert < 1$ », la négation de $a \ge 1$ étant $a < 1$. Alors $$ \begin{aligned} 2 &= \lvert (1 - x) + (1 + x) \rvert && \text{(} (1 - x) + (1 + x) = 2\text{)} \\ &\le \lvert 1 - x \rvert + \lvert 1 + x \rvert && \text{(inégalité triangulaire)} \\ &< 1 + 1 && \text{(les deux hypothèses, avec } \lvert 1 - x \rvert = \lvert x - 1 \rvert\text{)} \\ &= 2. \end{aligned} $$ Ainsi $2 < 2$ : on a obtenu la proposition « $2 < 2$ » et sa négation « $2 \ge 2$ ».
Contradiction ! Donc l'hypothèse est fausse, et la disjonction est vraie. Comme $x$ est quelconque, elle vaut pour tout réel $x$.
Les lois utilisées : le schéma repose sur la Proposition « Raisonnement par l'absurde », appliquée à la disjonction ; sa négation se calcule par la loi de De Morgan ; les deux hypothèses servent par la Définition « Conjonction » ; chaque « alors » est un modus ponens ; la dernière phrase applique la Méthode « Démontrer une proposition universelle ».
Seconde méthode : par la Proposition « La disjonction comme implication ». Soit $x \in \mathbb{R}$. Supposons $\lvert x - 1 \rvert \ge 1$ fausse. Montrons $\lvert x + 1 \rvert \ge 1$. Alors $\lvert x - 1 \rvert < 1$, c'est-à-dire $-1 < x - 1 < 1$, et $$ \begin{aligned} \lvert x + 1 \rvert &\ge x + 1 && \text{(} a \le \lvert a \rvert \text{ pour tout réel } a\text{)} \\ &= (x - 1) + 2 \\ &> -1 + 2 && \text{(} x - 1 > -1\text{)} \\ &= 1. \end{aligned} $$ Donc $\lvert x + 1 \rvert \ge 1$. Ainsi « $\lvert x - 1 \rvert \ge 1$ ou $\lvert x + 1 \rvert \ge 1$ » est vraie. Comme $x$ est quelconque, elle vaut pour tout réel $x$. La première méthode est la plus générique : elle n'utilise que l'inégalité triangulaire, et ne transforme jamais une valeur absolue en inégalités sur $x$.
Troisième méthode, directe. Soit $x \in \mathbb{R}$. Alors $$ \begin{aligned} \max\{\lvert x - 1 \rvert, \lvert x + 1 \rvert\} &\ge \frac{\lvert x - 1 \rvert + \lvert x + 1 \rvert}{2} && \text{(un maximum majore la moyenne de ses deux termes)} \\ &\ge \frac{\lvert (1 - x) + (1 + x) \rvert}{2} && \text{(inégalité triangulaire, avec } \lvert x - 1 \rvert = \lvert 1 - x \rvert\text{)} \\ &= 1. \end{aligned} $$ Le maximum est l'un des deux nombres, donc l'un d'eux vaut au moins $1$ : « $\lvert x - 1 \rvert \ge 1$ ou $\lvert x + 1 \rvert \ge 1$ » est vraie. Comme $x$ est quelconque, elle vaut pour tout réel $x$. La contradiction $2 < 2$ de la première méthode venait de ce calcul : quand la contradiction d'un raisonnement par l'absurde est une inégalité calculée, le calcul seul démontre souvent l'énoncé directement.

Méthode — Vérifier un schéma de démonstration

Pour décider si un schéma de démonstration est valide :

l'écrire comme une formule « hypothèses $\Rightarrow$ conclusion » : les hypothèses sont ce que le schéma démontre, reliées par $\wedge$, et la conclusion est ce qu'il affirme ensuite ;
si cette formule est une tautologie, le schéma est valide, quelles que soient les propositions auxquelles on l'applique — par le principe de remplacement, une tautologie le reste quand on met des formules à la place de ses lettres ;
sinon, exhiber une ligne où les hypothèses sont vraies et la conclusion fausse : sur une telle ligne, le schéma démontre un énoncé faux.

Par exemple, « pour démontrer $p \Rightarrow q$, démontrer $\neg p \Rightarrow \neg q$ » est la formule $(\neg p \Rightarrow \neg q) \Rightarrow (p \Rightarrow q)$. Sur la ligne $p$ vraie, $q$ fausse, l'hypothèse $\neg p \Rightarrow \neg q$ est vraie, sa propre hypothèse $\neg p$ étant fausse, et la conclusion $p \Rightarrow q$ est fausse : le schéma n'est pas valide. Avec $p$ : « $x^2 = 4$ » et $q$ : « $x = 2$ », l'implication « $x^2 \ne 4 \Rightarrow x \ne 2$ » est vraie pour tout réel $x$, alors que « $x^2 = 4 \Rightarrow x = 2$ » est fausse pour $x = -2$ : $(-2)^2 = 4$ et $-2 \ne 2$. La formule $\neg p \Rightarrow \neg q$ est la contraposée de la réciproque $q \Rightarrow p$, et non de $p \Rightarrow q$.

Compétences à pratiquer

Associer un schéma de démonstration à sa loi ★
Repérer l'usage du tiers exclu ★★
Décider si un schéma de démonstration est valide ★★
Justifier un schéma de démonstration nouveau ★★★

IV Quantificateurs

IV.1 Quantificateurs universel et existentiel

Des prédicats aux propositions

Un prédicat devient une proposition quand sa variable est fixée, ou quand sa variable est quantifiée : « pour tout $x$ de $E$, … », « il existe $x$ dans $E$ tel que … ». Les quantificateurs ont leurs propres lois : comment les nier, quand deux d'entre eux peuvent s'échanger, comment ils se combinent avec « et » et « ou ». Les définitions de l'analyse — une fonction bornée, une suite convergente, une fonction continue — sont des énoncés à plusieurs quantificateurs, et ces lois calculent leurs négations.

Signaler une erreur

Trois quantificateurs

Le quantificateur universel $\forall$ affirme que tout élément d'un ensemble vérifie un prédicat ; le quantificateur existentiel $\exists$, qu'au moins un élément le vérifie ; $\exists !$, qu'exactement un le vérifie. Une variable quantifiée ne désigne plus un objet particulier : l'énoncé n'en dépend pas, et la lettre pourrait être changée.

Signaler une erreur

Définition — Universel, existentiel, unicité

Soit $P(x)$ un prédicat d'une variable $x$.

$\forall x, \ P(x)$, lu « pour tout $x$, $P(x)$ », est la proposition qui est vraie lorsque tout objet $x$ vérifie $P$, et fausse lorsqu'au moins un objet ne le vérifie pas. Le symbole $\forall$ est le quantificateur universel.
$\exists x, \ P(x)$, lu « il existe $x$ tel que $P(x)$ », est la proposition qui est vraie lorsqu'au moins un objet vérifie $P$, et fausse lorsqu'aucun ne le vérifie. Le symbole $\exists$ est le quantificateur existentiel.

Pour un ensemble $E$, les quantificateurs bornés sont des abréviations : $\forall x \in E, \ P(x)$ abrège $\forall x, \ (x \in E \Rightarrow P(x))$, et $\exists x \in E, \ P(x)$ abrège $\exists x, \ (x \in E \wedge P(x))$. Un objet hors de $E$ rend vraie l'implication $x \in E \Rightarrow P(x)$, donc $\forall x \in E, \ P(x)$ est vraie exactement lorsque tout élément de $E$ vérifie $P$, et fausse lorsqu'au moins un élément de $E$ ne le vérifie pas ; et $\exists x \in E, \ P(x)$ est vraie exactement lorsqu'au moins un élément de $E$ vérifie $P$. Enfin, $\exists ! \, x \in E, \ P(x)$, lu « il existe un unique $x$ dans $E$ tel que $P(x)$ », abrège l'existence et « au plus un » : $$ \left(\exists x \in E, \ P(x)\right) \wedge \left(\forall x, x' \in E, \ (P(x) \wedge P(x')) \Rightarrow x = x'\right). $$ Les symboles $\forall$ et $\exists$ appartiennent aux formules ; ce ne sont pas des abréviations de mots : dans une phrase, on écrit « pour tout entier $n$ », jamais « $\forall$ entier $n$ ».

Définition — Variables libres et variables liées

Dans un énoncé, une occurrence d'une variable est liée lorsqu'elle se trouve dans la portée d'un quantificateur portant sur cette variable, ou d'une notation qui introduit sa propre variable, comme une somme $\sum_{k=1}^{n}$, une intégrale $\int_a^b f(t)\,\mathrm{d}t$ ou un ensemble $\{x \in E \mid \dots\}$ ; une occurrence qui n'est pas liée est libre. La portée d'un quantificateur va jusqu'à la fin de l'énoncé, ou jusqu'à la parenthèse qui renferme le quantificateur. Une même lettre peut avoir des occurrences libres et des occurrences liées : dans $(\forall x \in \mathbb{R}, \ x^2 \ge 0) \wedge (x > 0)$, le dernier $x$ est libre et les autres sont liés. Un énoncé ne dépend que de ses variables libres, celles qui ont une occurrence libre : c'est un prédicat de ses variables libres, et une proposition lorsqu'il n'en a aucune. Une variable liée est muette : les occurrences liées par un même quantificateur peuvent être renommées ensemble, avec une lettre qui n'est pas utilisée ailleurs dans l'énoncé, sans en changer le sens ; $\forall x \in \mathbb{R}, \ f(x) \ge 0$ et $\forall t \in \mathbb{R}, \ f(t) \ge 0$ disent tous deux « $f$ est positive ». Deux quantificateurs portant sur la même lettre, dans deux parties séparées d'un énoncé, lient deux variables différentes : dans $(\exists x \in \mathbb{N}, \ a = bx) \wedge (\exists x \in \mathbb{N}, \ b = ax)$, rien ne dit que les deux $x$ sont égaux, et l'énoncé s'écrit mieux $(\exists x \in \mathbb{N}, \ a = bx) \wedge (\exists y \in \mathbb{N}, \ b = ay)$.

Quantificateurs sur l'ensemble vide

Pour tout prédicat $P$, la proposition $\exists x \in \emptyset, \ P(x)$ est fausse : elle abrège $\exists x, \ (x \in \emptyset \wedge P(x))$, et $x \in \emptyset$ est fausse pour tout $x$. La proposition $\forall x \in \emptyset, \ P(x)$ est vraie : elle abrège $\forall x, \ (x \in \emptyset \Rightarrow P(x))$, une implication d'hypothèse fausse pour tout $x$. « Tout élément de l'ensemble vide est un entier strictement supérieur à $10$ et strictement inférieur à $5$ » est vraie : il n'y a rien à vérifier. C'est la convention de l'hypothèse fausse à l'œuvre ; c'est aussi pourquoi $\emptyset \subset E$ pour tout ensemble $E$.

Signaler une erreur

Exemple — Carrés de réels

Trois propositions vraies sur les carrés de réels :

$\forall x \in \mathbb{R}, \ x^2 \ge 0$ : tout réel a un carré positif.
$\exists x \in \mathbb{R}, \ x^2 = 2$ : au moins un réel a pour carré $2$ — en fait deux, $\sqrt{2}$ et $-\sqrt{2}$ ; donc $\exists ! \, x \in \mathbb{R}, \ x^2 = 2$ est fausse.
$\exists ! \, x \in \mathbb{R}_+, \ x^2 = 2$ : parmi les réels positifs, seul $\sqrt{2}$ a pour carré $2$.

L'ensemble fait partie de l'énoncé : remplacer $\mathbb{R}$ par $\mathbb{R}_+$ change un $\exists !$ faux en un $\exists !$ vrai.

Exemple — Quantificateurs implicites

La phrase « si $x > 2$, alors $x^2 > 4$ », énoncée comme une propriété des réels, porte un quantificateur universel non écrit : elle signifie $\forall x \in \mathbb{R}, \ (x > 2 \Rightarrow x^2 > 4)$. Dans un théorème, une phrase conditionnelle sur un objet est universelle : sa variable est quantifiée par « pour tout ».
Dans $\exists x \in \mathbb{R}, \ x^2 = m$, la variable $x$ est liée et $m$ est libre : c'est un prédicat de $m$, qui dit « l'équation $x^2 = m$ a une solution réelle ». Il est vrai pour $m \ge 0$, avec $x = \sqrt{m}$, et faux pour $m < 0$, un carré étant positif. La proposition $\forall m \in \mathbb{R}_+, \ \exists x \in \mathbb{R}, \ x^2 = m$ est vraie, et ne dépend plus de $m$.

Méthode — Écrire un énoncé avec des quantificateurs

Pour écrire une phrase comme un énoncé quantifié :

nommer les objets et les ensembles qu'ils parcourent ;
écrire les quantificateurs dans l'ordre des dépendances : un objet choisi après un autre peut en dépendre, jamais l'inverse ;
écrire le prédicat, avec ses connecteurs ;
relire l'énoncé en mots, et vérifier que chaque lettre est liée ou désigne un objet donné par la phrase.

Par exemple, « la fonction $f \colon \mathbb{R} \to \mathbb{R}$ admet un minimum » signifie qu'un réel $a$ vérifie $f(x) \ge f(a)$ pour tout réel $x$ : $$ \exists a \in \mathbb{R}, \ \forall x \in \mathbb{R}, \ f(x) \ge f(a). $$ Le point $a$ est choisi d'abord et ne dépend pas de $x$, donc $\exists a$ vient avant $\forall x$. Les lettres $a$ et $x$ sont liées : l'énoncé ne dépend que de $f$.

Compétences à pratiquer

Compter les éléments qui vérifient un énoncé quantifié ★
Repérer les variables libres et liées ★
Traduire un énoncé avec des quantificateurs ★
Traduire des propriétés de fonctions et de suites ★★

IV.2 Négation des quantificateurs

Nier est un calcul

Réfuter un énoncé, c'est démontrer sa négation, et la négation d'un énoncé quantifié se calcule, elle ne se devine pas. La Méthode « Nier un énoncé quantifié » du chapitre Raisonner et rédiger en donne la règle : échanger les quantificateurs, nier la propriété finale. La règle découle de la négation d'un seul quantificateur et d'une remarque : si $P(x) \iff Q(x)$ est vraie pour tout $x \in E$, les deux prédicats sont vérifiés par les mêmes éléments de $E$, donc $\forall x \in E, \ P(x)$ et $\forall x \in E, \ Q(x)$ ont la même valeur de vérité, de même que $\exists x \in E, \ P(x)$ et $\exists x \in E, \ Q(x)$. Une équivalence de prédicats passe sous un quantificateur.

Signaler une erreur

Proposition — Négation des quantificateurs

Pour tout ensemble $E$ et tout prédicat $P(x)$ sur $E$ : $$ \neg\left(\forall x \in E, \ P(x)\right) \iff \exists x \in E, \ \neg P(x) \qquad \text{et} \qquad \neg\left(\exists x \in E, \ P(x)\right) \iff \forall x \in E, \ \neg P(x). $$ La négation échange « pour tout » et « il existe », garde l'ensemble, et nie le prédicat.

Preuve

Première loi. Par la Définition « Universel, existentiel, unicité », $\forall x \in E, \ P(x)$ est fausse exactement lorsqu'au moins un élément de $E$ ne vérifie pas $P$. Un élément $x$ qui ne vérifie pas $P$ est un élément pour lequel $P(x)$ n'est pas vraie, c'est-à-dire, par le tiers exclu, pour lequel $P(x)$ est fausse, et $\neg P(x)$ vraie par la Définition « Négation ». Ainsi $\forall x \in E, \ P(x)$ est fausse exactement lorsque $\exists x \in E, \ \neg P(x)$ est vraie ; et $\neg(\forall x \in E, \ P(x))$, vraie exactement lorsque $\forall x \in E, \ P(x)$ est fausse, a la valeur de vérité de $\exists x \in E, \ \neg P(x)$.
Seconde loi. Elle découle de la première, appliquée au prédicat $\neg P$ : $$ \begin{aligned} \neg\left(\exists x \in E, \ P(x)\right) &\iff \neg\left(\exists x \in E, \ \neg\neg P(x)\right) && \text{(double négation, sous } \exists\text{)} \\ &\iff \neg\neg\left(\forall x \in E, \ \neg P(x)\right) && \text{(première loi pour } \neg P\text{, et remplacement)} \\ &\iff \forall x \in E, \ \neg P(x). \end{aligned} $$ La dernière équivalence est la double négation, appliquée à la proposition $\forall x \in E, \ \neg P(x)$.
Seconde démonstration : par l'abréviation. Le raisonnement de la première loi, avec « tout objet » au lieu de « tout élément de $E$ », donne $\neg(\forall x, \ R(x)) \iff \exists x, \ \neg R(x)$ pour tout prédicat $R$. Appliqué à $R(x)$ : « $x \in E \Rightarrow P(x)$ », $$ \begin{aligned} \neg\left(\forall x \in E, \ P(x)\right) &\iff \neg\left(\forall x, \ (x \in E \Rightarrow P(x))\right) && \text{(quantificateur borné)} \\ &\iff \exists x, \ \neg(x \in E \Rightarrow P(x)) && \text{(négation de } \forall\text{)} \\ &\iff \exists x, \ (x \in E \wedge \neg P(x)) && \text{(négation d'une implication, sous } \exists\text{)} \\ &\iff \exists x \in E, \ \neg P(x). \end{aligned} $$ L'appartenance $x \in E$ n'est pas niée : c'est l'hypothèse de l'implication, et la négation d'une implication garde son hypothèse. La seconde loi découle de la première comme dans la première démonstration.

Proposition — Négation d'une implication quantifiée

Pour tout ensemble $E$ et tous prédicats $P(x)$, $Q(x)$ sur $E$ : $$ \neg\left(\forall x \in E, \ (P(x) \Rightarrow Q(x))\right) \iff \exists x \in E, \ (P(x) \wedge \neg Q(x)). $$ Pour réfuter une implication universelle, on exhibe un contre-exemple : un élément qui vérifie l'hypothèse et pas la conclusion.

Preuve

$$ \begin{aligned} \neg\left(\forall x \in E, \ (P(x) \Rightarrow Q(x))\right) &\iff \exists x \in E, \ \neg(P(x) \Rightarrow Q(x)) && \text{(négation des quantificateurs)} \\ &\iff \exists x \in E, \ (P(x) \wedge \neg Q(x)). \end{aligned} $$ La dernière équivalence est la négation d'une implication, appliquée pour chaque $x$ et passée sous $\exists$. C'est la loi qui fonde la Méthode « Réfuter une implication » du chapitre Raisonner et rédiger.

Proposition — Nier plusieurs quantificateurs

Soient $n \ge 1$, des ensembles $E_1, \dots, E_n$, chaque $E_k$ pouvant dépendre de $x_1, \dots, x_{k-1}$ (comme dans « $\forall n \ge N$ »), un prédicat $P(x_1, \dots, x_n)$, et des quantificateurs $Q_1, \dots, Q_n$, chacun égal à $\forall$ ou à $\exists$ ; on note $Q^*$ l'autre quantificateur : $\forall^*$ est $\exists$, et $\exists^*$ est $\forall$. La négation de $$ Q_1 x_1 \in E_1, \ Q_2 x_2 \in E_2, \ \dots, \ Q_n x_n \in E_n, \ P(x_1, \dots, x_n) $$ a la même valeur de vérité, quels que soient les ensembles et le prédicat, que $$ Q_1^* x_1 \in E_1, \ Q_2^* x_2 \in E_2, \ \dots, \ Q_n^* x_n \in E_n, \ \neg P(x_1, \dots, x_n). $$ Chaque quantificateur est échangé, l'ordre et les ensembles sont gardés, et le prédicat final est nié.

Preuve

Pour $n \ge 1$, notons $H_n$ la propriété « la règle vaut pour tout énoncé à $n$ quantificateurs, quels que soient ses ensembles et son prédicat ».
Initialisation. $H_1$ est la Proposition « Négation des quantificateurs ».
Hérédité. Soit $n \ge 1$. Supposons $H_n$. Montrons $H_{n+1}$. Un énoncé à $n + 1$ quantificateurs s'écrit $Q_1 x_1 \in E_1, \ R(x_1)$, où $R(x_1)$ désigne l'énoncé $$ Q_2 x_2 \in E_2, \ \dots, \ Q_{n+1} x_{n+1} \in E_{n+1}, \ P(x_1, \dots, x_{n+1}). $$ Dans $R(x_1)$, la variable $x_1$ est libre et les autres sont liées : pour chaque $x_1 \in E_1$, c'est un énoncé à $n$ quantificateurs, dont les ensembles peuvent dépendre de $x_1$. Notons $R^*(x_1)$ l'énoncé $$ Q_2^* x_2 \in E_2, \ \dots, \ Q_{n+1}^* x_{n+1} \in E_{n+1}, \ \neg P(x_1, \dots, x_{n+1}). $$ Par $H_n$, $\neg R(x_1) \iff R^*(x_1)$ pour tout $x_1 \in E_1$. Alors $$ \begin{aligned} \neg\left(Q_1 x_1 \in E_1, \ R(x_1)\right) &\iff Q_1^* x_1 \in E_1, \ \neg R(x_1) && \text{(négation des quantificateurs)} \\ &\iff Q_1^* x_1 \in E_1, \ R^*(x_1). \end{aligned} $$ La dernière équivalence est l'hypothèse de récurrence, passée sous $Q_1^*$ ; c'est la règle pour $n + 1$ quantificateurs. Donc $H_{n+1}$.
Conclusion. Puisque $H_1$ est vraie et que $H_n \Rightarrow H_{n+1}$ pour tout $n \ge 1$, par récurrence à partir du rang $1$, $H_n$ est vraie pour tout $n \ge 1$.

Exemple — Deux négations

L'énoncé « tout réel dont le carré est strictement supérieur à $1$ est strictement supérieur à $1$ » s'écrit $\forall x \in \mathbb{R}, \ (x^2 > 1 \Rightarrow x > 1)$. Par la négation d'une implication quantifiée, sa négation est $\exists x \in \mathbb{R}, \ (x^2 > 1 \wedge x \le 1)$, qui est vraie : $x = -2$ vérifie $(-2)^2 = 4 > 1$ et $-2 \le 1$. Donc l'énoncé est faux, et $x = -2$ est un contre-exemple.
La négation de $\exists x \in \mathbb{R}, \ x^2 < 0$ est $\forall x \in \mathbb{R}, \ x^2 \ge 0$, qui est vraie. Donc l'énoncé existentiel est faux.

D'un énoncé et de sa négation, exactement un est vrai : démontrer l'un réfute l'autre.

Exemple — La négation de la convergence

Une suite réelle $(u_n)$ converge vers le réel $\ell$ lorsque $$ \forall \varepsilon > 0, \ \exists N \in \mathbb{N}, \ \forall n \ge N, \ \lvert u_n - \ell \rvert < \varepsilon. $$ Par la Proposition « Nier plusieurs quantificateurs », $(u_n)$ ne converge pas vers $\ell$ lorsque $$ \exists \varepsilon > 0, \ \forall N \in \mathbb{N}, \ \exists n \ge N, \ \lvert u_n - \ell \rvert \ge \varepsilon. $$ La règle opère de gauche à droite : $\forall \varepsilon > 0$ devient $\exists \varepsilon > 0$, puis $\exists N$ devient $\forall N$, puis $\forall n \ge N$ devient $\exists n \ge N$, et enfin $\lvert u_n - \ell \rvert < \varepsilon$ devient $\lvert u_n - \ell \rvert \ge \varepsilon$. Les ensembles sont gardés : « $\varepsilon > 0$ » décrit l'ensemble $]0, +\infty[$ et « $n \ge N$ » les entiers à partir de $N$ — un ensemble qui dépend de $N$, ce que la Proposition permet — et la négation ne les change jamais en « $\varepsilon \le 0$ » ou « $n < N$ ». En mots : une certaine distance $\varepsilon > 0$ à $\ell$ est atteinte ou dépassée par des termes d'indice arbitrairement grand.

Compétences à pratiquer

Nier un énoncé à un quantificateur ★
Nier un énoncé à plusieurs quantificateurs ★★
Démontrer la négation d'une définition ★★★

IV.3 Ordre des quantificateurs

L'ordre compte

Dans un énoncé à plusieurs quantificateurs, leur ordre fait partie du sens. Deux quantificateurs successifs de même sorte peuvent s'échanger lorsque leurs domaines ne dépendent pas des variables échangées ; deux quantificateurs de sortes différentes ne peuvent pas s'échanger en général. Dans « pour tout $x$, il existe $y$ », le $y$ peut dépendre de $x$ ; dans « il existe $y$ tel que, pour tout $x$ », un même $y$ sert pour tous les $x$. Plusieurs notions de l'analyse ne diffèrent que par l'ordre de deux quantificateurs.

Signaler une erreur

Proposition — Échange de quantificateurs

Soient $E$, $F$ des ensembles et $P(x, y)$ un prédicat.

Deux quantificateurs de même sorte peuvent s'échanger : $$ \left(\forall x \in E, \ \forall y \in F, \ P(x, y)\right) \iff \left(\forall y \in F, \ \forall x \in E, \ P(x, y)\right), $$ $$ \left(\exists x \in E, \ \exists y \in F, \ P(x, y)\right) \iff \left(\exists y \in F, \ \exists x \in E, \ P(x, y)\right). $$
« Il existe … pour tout » implique « pour tout … il existe » : $$ \left(\exists y \in F, \ \forall x \in E, \ P(x, y)\right) \Rightarrow \left(\forall x \in E, \ \exists y \in F, \ P(x, y)\right). $$

Preuve

Même sorte. La proposition $\forall x \in E, \ \forall y \in F, \ P(x, y)$ est vraie exactement lorsque, pour tout $x \in E$, $P(x, y)$ est vraie pour tout $y \in F$, c'est-à-dire lorsque $P(x, y)$ est vraie pour tout $x \in E$ et tout $y \in F$ ; la proposition $\forall y \in F, \ \forall x \in E, \ P(x, y)$ est vraie exactement dans le même cas. De même, les deux propositions existentielles sont vraies exactement lorsque $P(x, y)$ est vraie pour au moins un couple $(x, y)$ avec $x \in E$ et $y \in F$.
Sortes différentes. Supposons $\exists y \in F, \ \forall x \in E, \ P(x, y)$, et notons $y_0$ un élément de $F$ tel que $P(x, y_0)$ soit vraie pour tout $x \in E$. Soit $x \in E$. L'élément $y = y_0$ de $F$ vérifie $P(x, y)$ ; donc $\exists y \in F, \ P(x, y)$. Comme $x$ est quelconque dans $E$, $\forall x \in E, \ \exists y \in F, \ P(x, y)$. Le témoin $y_0$ a été choisi avant $x$, et il sert pour tout $x$.

Exemple — Un témoin qui dépend de $x$

Pour le prédicat $P(x, y)$ : « $y > x$ » sur les réels :

$\forall x \in \mathbb{R}, \ \exists y \in \mathbb{R}, \ y > x$ est vraie : soit $x \in \mathbb{R}$ ; alors $y = x + 1$ vérifie $y > x$. Le témoin dépend de $x$.
$\exists y \in \mathbb{R}, \ \forall x \in \mathbb{R}, \ y > x$ est fausse : sa négation $\forall y \in \mathbb{R}, \ \exists x \in \mathbb{R}, \ y \le x$ est vraie, puisque pour $y \in \mathbb{R}$, $x = y$ vérifie $y \le x$.

Ainsi la réciproque de l'implication entre « il existe … pour tout » et « pour tout … il existe », dans la Proposition « Échange de quantificateurs », est fausse pour ce prédicat : un énoncé « pour tout … il existe » peut être vrai alors que l'énoncé « il existe … pour tout » correspondant est faux.

Proposition — Quantificateurs et connecteurs

Soient $E$ un ensemble et $P(x)$, $Q(x)$ des prédicats sur $E$.

« Pour tout » se distribue sur « et » : $$ \left(\forall x \in E, \ (P(x) \wedge Q(x))\right) \iff \left(\forall x \in E, \ P(x)\right) \wedge \left(\forall x \in E, \ Q(x)\right). $$
« Il existe » se distribue sur « ou » : $$ \left(\exists x \in E, \ (P(x) \vee Q(x))\right) \iff \left(\exists x \in E, \ P(x)\right) \vee \left(\exists x \in E, \ Q(x)\right). $$
« Pour tout » avec « ou », « il existe » avec « et » : une seule implication : $$ \left(\forall x \in E, \ P(x)\right) \vee \left(\forall x \in E, \ Q(x)\right) \Rightarrow \left(\forall x \in E, \ (P(x) \vee Q(x))\right), $$ $$ \left(\exists x \in E, \ (P(x) \wedge Q(x))\right) \Rightarrow \left(\exists x \in E, \ P(x)\right) \wedge \left(\exists x \in E, \ Q(x)\right), $$ et les réciproques de ces deux implications sont fausses en général.

Preuve

« Pour tout » et « et ». Le membre de droite est vrai exactement lorsque tout élément de $E$ vérifie $P$ et que tout élément de $E$ vérifie $Q$, c'est-à-dire lorsque tout élément de $E$ vérifie les deux : c'est le membre de gauche.
« Il existe » et « ou ». Par dualité, avec la négation des quantificateurs et les lois de De Morgan : $$ \begin{aligned} \left(\exists x \in E, \ (P(x) \vee Q(x))\right) &\iff \neg\neg\left(\exists x \in E, \ (P(x) \vee Q(x))\right) && \text{(double négation)} \\ &\iff \neg\left(\forall x \in E, \ \neg(P(x) \vee Q(x))\right) && \text{(négation de } \exists\text{)} \\ &\iff \neg\left(\forall x \in E, \ (\neg P(x) \wedge \neg Q(x))\right) && \text{(loi de De Morgan, sous } \forall\text{)} \\ &\iff \neg\left((\forall x \in E, \ \neg P(x)) \wedge (\forall x \in E, \ \neg Q(x))\right) && \text{(« pour tout » et « et », pour } \neg P, \neg Q\text{)} \\ &\iff \neg\left(\forall x \in E, \ \neg P(x)\right) \vee \neg\left(\forall x \in E, \ \neg Q(x)\right) && \text{(loi de De Morgan)} \\ &\iff \left(\exists x \in E, \ \neg\neg P(x)\right) \vee \left(\exists x \in E, \ \neg\neg Q(x)\right) && \text{(négation de } \forall\text{, deux fois)} \\ &\iff \left(\exists x \in E, \ P(x)\right) \vee \left(\exists x \in E, \ Q(x)\right). \end{aligned} $$ La dernière équivalence est la double négation, appliquée sous chaque $\exists$.
Les deux implications. Supposons $(\forall x \in E, \ P(x)) \vee (\forall x \in E, \ Q(x))$, et soit $a \in E$. Si $\forall x \in E, \ P(x)$ est vraie, $P(a)$ est vraie, donc $P(a) \vee Q(a)$ est vraie ; si $\forall x \in E, \ Q(x)$ est vraie, $Q(a)$ est vraie, et $P(a) \vee Q(a)$ est vraie aussi. Comme $a$ est quelconque dans $E$, $\forall x \in E, \ (P(x) \vee Q(x))$. Supposons maintenant $\exists x \in E, \ (P(x) \wedge Q(x))$, et notons $x_0$ un élément de $E$ tel que $P(x_0)$ et $Q(x_0)$ soient vraies : $x_0$ est un témoin pour $\exists x \in E, \ P(x)$ et pour $\exists x \in E, \ Q(x)$.
Les réciproques. Sur $E = \mathbb{R}$, prenons $P(x)$ : « $x \ge 0$ » et $Q(x)$ : « $x \le 0$ ». Tout réel est positif ou négatif, donc $\forall x \in \mathbb{R}, \ (P(x) \vee Q(x))$ est vraie ; mais $\forall x \in \mathbb{R}, \ x \ge 0$ est fausse ($x = -1$) et $\forall x \in \mathbb{R}, \ x \le 0$ est fausse ($x = 1$). Prenons maintenant $P(x)$ : « $x = 1$ » et $Q(x)$ : « $x = 2$ » : $\exists x \in \mathbb{R}, \ P(x)$ et $\exists x \in \mathbb{R}, \ Q(x)$ sont vraies, avec $x = 1$ et $x = 2$, mais aucun réel n'est égal à la fois à $1$ et à $2$.
Seconde démonstration pour « il existe » et « ou » : par le sens. Le membre de gauche est vrai exactement lorsqu'un élément de $E$ vérifie $P$ ou $Q$ ; un tel élément vérifie $P$, ou vérifie $Q$, ce qui rend vrai le membre de droite. Si le membre de droite est vrai, un élément qui vérifie $P$, ou un élément qui vérifie $Q$, vérifie $P \vee Q$, ce qui rend vrai le membre de gauche.

Méthode — Décider un énoncé à deux quantificateurs

Pour décider si un énoncé à deux quantificateurs de sortes différentes est vrai :

Universel, puis existentiel. Pour $\forall x \in E, \ \exists y \in F, \ P(x, y)$, se donner $x \in E$ et chercher $y$ en fonction de $x$. Si un $y$ est trouvé pour tout $x$, l'énoncé est vrai ; si un certain $x$ n'admet aucun $y$, ce $x$ démontre la négation $\exists x \in E, \ \forall y \in F, \ \neg P(x, y)$.
Existentiel, puis universel. Pour $\exists y \in F, \ \forall x \in E, \ P(x, y)$, chercher un seul $y$, indépendant de $x$ ; ou démontrer la négation $\forall y \in F, \ \exists x \in E, \ \neg P(x, y)$, en choisissant $x$ en fonction de $y$.
Les ensembles font partie de l'énoncé : un même prédicat peut donner un énoncé vrai sur un ensemble et faux sur un autre.

Par exemple, $\exists y \in \mathbb{N}, \ \forall x \in \mathbb{N}, \ y \le x$ est vraie : $y = 0$, choisi une fois pour tous les $x$, est inférieur ou égal à tout entier naturel. Sur $\mathbb{Z}$, l'énoncé $\exists y \in \mathbb{Z}, \ \forall x \in \mathbb{Z}, \ y \le x$ est faux : sa négation $\forall y \in \mathbb{Z}, \ \exists x \in \mathbb{Z}, \ x < y$ est vraie, avec $x = y - 1$, choisi en fonction de $y$.

Pour aller plus loin

Toute table est la table d'une formule. Prenons une table quelconque de valeurs de vérité sur les lettres $p_1, \dots, p_n$. Pour chaque ligne où la table donne V, écrivons la conjonction des lettres vraies sur cette ligne et des négations des autres : elle n'est vraie que sur cette ligne. La disjonction de ces conjonctions est vraie exactement sur les lignes où la table donne V — et s'il n'y en a aucune, la formule $p_1 \wedge \neg p_1$ convient. Ainsi $\neg$, $\wedge$ et $\vee$ suffisent à écrire toute table ; le ou exclusif, par exemple, est $(p \wedge \neg q) \vee (\neg p \wedge q)$. Un seul connecteur suffit même : « non-et », noté $p \uparrow q$ et défini comme $\neg(p \wedge q)$. En effet $\neg p \iff p \uparrow p$ et $p \wedge q \iff (p \uparrow q) \uparrow (p \uparrow q)$, et $\vee$ s'écrit avec $\neg$ et $\wedge$ par les lois de De Morgan.
Une logique sans tiers exclu. Certains mathématiciens, les intuitionnistes, rejettent le principe du tiers exclu : pour eux, démontrer « $p$ ou $q$ », c'est démontrer l'une des deux. Dans leur logique, déduire une contradiction de $p$ démontre toujours $\neg p$ ; mais déduire une contradiction de $\neg p$ ne démontre que $\neg\neg p$, qui n'est plus équivalente à $p$. Un raisonnement par l'absurde qui démontre un énoncé autre qu'une négation est alors refusé — précisément l'étape où la démonstration de la Proposition « Raisonnement par l'absurde » utilise le tiers exclu.

Signaler une erreur

Compétences à pratiquer

Lire l'ordre des quantificateurs ★
Décider un énoncé à deux quantificateurs ★★
Distribuer un quantificateur sur un connecteur ★★
Démontrer une loi des quantificateurs ★★★

V Exercices de colle

Compétences à pratiquer

Travailler un exercice de colle ★
Travailler un exercice de colle ★★
Travailler un exercice de colle ★★★
Travailler un exercice de colle ★★★★

VI Problèmes d'écrit

Compétences à pratiquer

Travailler un problème d'écrit ★
Travailler un problème d'écrit ★★
Travailler un problème d'écrit ★★★
Travailler un problème d'écrit ★★★★
Quiz

Devoir facile : un seul connecteur

3 exercices, sur 20 points. Durée indicative : 1 h 30.

À traiter sur papier, puis à photographier : la correction est automatique, par IA.

Ce contrôle ne modifie pas la maîtrise du chapitre, quelle que soit la note.

Aucun exercice composé.

Devoir difficile : décider si une formule est une tautologie

3 exercices, sur 20 points. Durée indicative : 3 h.

À traiter sur papier, puis à photographier : la correction est automatique, par IA.

Ce contrôle ne modifie pas la maîtrise du chapitre, quelle que soit la note.

Aucun exercice composé.

Aller à la section

\(p\)	\(q\)	\(p \vee q\)	ou exclusif
V	V	V	F
V	F	V	V
F	V	V	V
F	F	F	F

\(p\)	\(\neg p\)	\(p \vee \neg p\)	\(p \wedge \neg p\)	\(\neg(p \wedge \neg p)\)
V	F	V	F	V
F	V	V	F	V

\(p\)	\(q\)	\(p \wedge q\)	\(p \vee q\)	\((p \wedge q) \Rightarrow (p \vee q)\)	\((p \vee q) \Rightarrow (p \wedge q)\)
V	V	V	V	V	V
V	F	F	V	V	F
F	V	F	V	V	F
F	F	F	F	V	V

\(p\)	\(q\)	\(\neg p\)	\(\neg q\)	\(p \wedge q\)	\(\neg(p \wedge q)\)	\(\neg p \vee \neg q\)	\(p \vee q\)	\(\neg(p \vee q)\)	\(\neg p \wedge \neg q\)
V	V	F	F	V	F	F	V	F	F
V	F	F	V	F	V	V	V	F	F
F	V	V	F	F	V	V	V	F	F
F	F	V	V	F	V	V	F	V	V

\(p\)	\(q\)	\(r\)	\(q \vee r\)	\(p \wedge (q \vee r)\)	\(p \wedge q\)	\(p \wedge r\)	\((p \wedge q) \vee (p \wedge r)\)
V	V	V	V	V	V	V	V
V	V	F	V	V	V	F	V
V	F	V	V	V	F	V	V
V	F	F	F	F	F	F	F
F	V	V	V	F	F	F	F
F	V	F	V	F	F	F	F
F	F	V	V	F	F	F	F
F	F	F	F	F	F	F	F

\(p\)	\(q\)	\(p \Rightarrow q\)	\(q \Rightarrow p\)	\((p \Rightarrow q) \wedge (q \Rightarrow p)\)	\(p \iff q\)
V	V	V	V	V	V
V	F	F	V	F	F
F	V	V	F	F	F
F	F	V	V	V	V

Phrase	Formule
« il suffit que \(p\) pour que \(q\) »	\(p \Rightarrow q\)
« \(q\) si \(p\) »	\(p \Rightarrow q\)
« pour que \(p\), il faut que \(q\) »	\(p \Rightarrow q\)
« \(p\) seulement si \(q\) »	\(p \Rightarrow q\)
« \(p\) si et seulement si \(q\) »	\(p \iff q\)