Logique et types de démonstration en L1 de maths : cours et méthodes

Une assertion est un énoncé mathématique qui possède une et une seule valeur de vérité : vrai (noté V) ou faux (noté F). Un prédicat est un énoncé qui dépend d’une ou de plusieurs variables et devient une assertion dès qu’on leur donne une valeur.

On définit :

• la négation \(\neg P\) (« non \(P\) »), vraie exactement quand \(P\) est fausse ;
• la conjonction \(P \wedge Q\) (« \(P\) et \(Q\) »), vraie exactement quand \(P\) et \(Q\) sont vraies toutes les deux ;
• la disjonction \(P \vee Q\) (« \(P\) ou \(Q\) »), vraie dès que l’une au moins des deux est vraie ;
• l’implication \(P \Rightarrow Q\), fausse dans un seul cas : \(P\) vraie et \(Q\) fausse ;
• l’équivalence \(P \Leftrightarrow Q\), vraie exactement quand \(P\) et \(Q\) ont la même valeur.

Voici la table de vérité des connecteurs binaires.

\[
\begin{array}{|c|c|c|c|c|c|}
\hline
P & Q & P \wedge Q & P \vee Q & P \Rightarrow Q & P \Leftrightarrow Q \\
\hline
V & V & V & V & V & V \\
V & F & F & V & F & F \\
F & V & F & V & V & F \\
F & F & F & F & V & V \\
\hline
\end{array}
\]

Pour toutes assertions \(P\), \(Q\) et \(R\) :

• \(\neg(\neg P) \equiv P\) ;
• \(\neg(P \wedge Q) \equiv \neg P \vee \neg Q\) et \(\neg(P \vee Q) \equiv \neg P \wedge \neg Q\) (lois de De Morgan) ;
• \(P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)\) et \(P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)\) ;
• \((P \Rightarrow Q) \equiv (\neg P \vee Q)\) et donc \(\neg(P \Rightarrow Q) \equiv P \wedge \neg Q\) ;
• \((P \Leftrightarrow Q) \equiv (P \Rightarrow Q) \wedge (Q \Rightarrow P)\).

Chaque point se vérifie en comparant deux tables. Traitons la quatrième équivalence. D’abord, \(\neg P \vee Q\) est fausse seulement si \(\neg P\) et \(Q\) sont fausses. Cela revient à dire que \(P\) est vraie et \(Q\) fausse. Or c’est aussi l’unique cas où \(P \Rightarrow Q\) est fausse. Les deux tables coïncident donc. Enfin, la loi de De Morgan donne \(\neg(\neg P \vee Q) \equiv P \wedge \neg Q\).

Montrons que \(P \Rightarrow (Q \Rightarrow R)\) équivaut à \((P \wedge Q) \Rightarrow R\). Cette règle permet de rassembler deux hypothèses en une seule.

1. La première assertion est fausse si et seulement si \(P\) est vraie et \(Q \Rightarrow R\) est fausse.
2. Or \(Q \Rightarrow R\) est fausse si et seulement si \(Q\) est vraie et \(R\) fausse.
3. Ainsi, la première assertion est fausse exactement sur la ligne « \(P\) vraie, \(Q\) vraie, \(R\) fausse ».
4. De même, \((P \wedge Q) \Rightarrow R\) est fausse exactement quand \(P \wedge Q\) est vraie et \(R\) fausse : c’est la même ligne.

Les deux assertions sont fausses sur la même unique ligne de la table : elles sont donc équivalentes.

Soit l’implication \(P \Rightarrow Q\).

• Sa réciproque est \(Q \Rightarrow P\).
• Sa contraposée est \(\neg Q \Rightarrow \neg P\).

Lorsque \(P \Rightarrow Q\) est vraie, on dit que \(Q\) est une condition nécessaire pour \(P\), et que \(P\) est une condition suffisante pour \(Q\).

Une implication et sa contraposée sont logiquement équivalentes : \((P \Rightarrow Q) \equiv (\neg Q \Rightarrow \neg P)\).

D’après la partie 1, \(P \Rightarrow Q\) équivaut à \(\neg P \vee Q\). De même, \(\neg Q \Rightarrow \neg P\) équivaut à \(\neg(\neg Q) \vee \neg P\), c’est-à-dire à \(Q \vee \neg P\). Or la disjonction est commutative. Les deux assertions ont donc la même table de vérité.

Soit \(x\) un réel. Montrons que \(x^2 + 2x = 8 \Leftrightarrow (x = 2 \ \text{ou}\ x = -4)\).

1. Sens direct : on suppose \(x^2 + 2x = 8\). Alors \(x^2 + 2x – 8 = 0\), soit \((x – 2)(x + 4) = 0\). Or un produit de deux réels ne s’annule que si un facteur vaut zéro. Donc \(x = 2\) ou \(x = -4\).
2. Sens réciproque : si \(x = 2\), alors \(x^2 + 2x = 4 + 4 = 8\). Si \(x = -4\), alors \(x^2 + 2x = 16 – 8 = 8\).

Les deux sens sont établis, ce qui prouve l’équivalence.

Soit \(E\) un ensemble et \(A(x)\) un prédicat portant sur les éléments \(x\) de \(E\).

• \(\forall x \in E,\ A(x)\) se lit « pour tout \(x\) de \(E\), \(A(x)\) ». Elle est vraie si \(A(x)\) est vraie pour chaque élément de \(E\).
• \(\exists x \in E,\ A(x)\) se lit « il existe \(x\) dans \(E\) tel que \(A(x)\) ». Elle est vraie si au moins un élément de \(E\) vérifie \(A\).
• \(\exists !\, x \in E,\ A(x)\) affirme de plus l’unicité : exactement un élément de \(E\) vérifie \(A\).

L’implication \(\left(\exists y,\ \forall x,\ A(x, y)\right) \Rightarrow \left(\forall x,\ \exists y,\ A(x, y)\right)\) est toujours vraie. Sa réciproque est fausse en général.

On suppose qu’un élément \(y_0\) vérifie \(A(x, y_0)\) pour tout \(x\). Soit alors \(x\) quelconque. Le choix \(y = y_0\) convient, puisque \(A(x, y_0)\) est vraie. Ainsi, pour tout \(x\), un \(y\) convient. Enfin, le couple d’assertions \((A)\) et \((B)\) ci-dessus fournit un cas où la réciproque échoue.

Pour tout prédicat \(A(x)\) sur un ensemble \(E\) :

\[
\neg\left(\forall x \in E,\ A(x)\right) \equiv \left(\exists x \in E,\ \neg A(x)\right)
\quad\text{et}\quad
\neg\left(\exists x \in E,\ A(x)\right) \equiv \left(\forall x \in E,\ \neg A(x)\right)
\]

Pour nier un énoncé quantifié :

1. recopier les quantificateurs dans le même ordre, en échangeant \(\forall\) et \(\exists\) ;
2. garder les ensembles de chaque variable sans les modifier ;
3. nier la propriété finale avec les règles de la partie 1 : \(\neg(P \Rightarrow Q) \equiv P \wedge \neg Q\), De Morgan pour « et » et « ou » ;
4. relire la phrase obtenue en français pour vérifier qu’elle décrit bien le contraire.

On considère l’assertion suivante, qui dit que les inverses des entiers deviennent plus petits que tout réel strictement positif :

\[
\forall a \in \left]0, +\infty\right[,\ \exists n \in \mathbb{N}^{*},\ \frac{1}{n} < a
\]

On échange d’abord les quantificateurs, puis on nie l’inégalité stricte. On obtient :

\[
\exists a \in \left]0, +\infty\right[,\ \forall n \in \mathbb{N}^{*},\ \frac{1}{n} \geqslant a
\]

Cette négation est fausse, car l’assertion de départ est vraie. En effet, pour \(a > 0\) donné, tout entier \(n > 1/a\) convient.

Montrons que pour tous réels \(x\) et \(y\), on a \(x^2 + xy + y^2 \geqslant 0\).

1. Soient \(x\) et \(y\) deux réels quelconques.
2. On reconnaît le début d’un carré : \(x^2 + xy = \left(x + \frac{y}{2}\right)^2 – \frac{y^2}{4}\).
3. Par conséquent, \(x^2 + xy + y^2 = \left(x + \frac{y}{2}\right)^2 + \frac{3y^2}{4}\).
4. Cette expression est une somme de deux réels positifs, donc elle est positive.

Comme \(x\) et \(y\) étaient quelconques, l’inégalité vaut pour tous les réels. On remarque de plus qu’il y a égalité si et seulement si \(y = 0\) et \(x = 0\).

Soient \(a\) et \(b\) deux réels. Montrons que si \(a + b > 10\), alors \(a > 5\) ou \(b > 5\).

1. La conclusion est une disjonction. Sa négation est \(a \leqslant 5\) et \(b \leqslant 5\), qui se manipule facilement.
2. On démontre donc la contraposée : on suppose \(a \leqslant 5\) et \(b \leqslant 5\).
3. En ajoutant ces deux inégalités, on obtient \(a + b \leqslant 10\).
4. C’est exactement la négation de \(a + b > 10\).

La contraposée est vraie, donc l’implication de départ aussi.

Il n’existe pas de plus petit réel strictement positif.

Supposons par l’absurde qu’il existe un réel \(m > 0\) tel que tout réel \(x > 0\) vérifie \(x \geqslant m\). Considérons alors le réel \(x = \frac{m}{2}\). D’une part, \(x > 0\), car \(m > 0\). D’autre part, \(x < m\), puisque \(m – \frac{m}{2} = \frac{m}{2} > 0\). Ainsi, \(x\) est un réel strictement positif inférieur strictement à \(m\) : cela contredit la définition de \(m\). L’hypothèse est donc fausse, ce qui prouve la proposition.

1. Si l’énoncé est universel et qu’on dispose d’un calcul ou d’une identité, on tente d’abord le raisonnement direct.
2. Si la conclusion contient un « ou », un « différent » ou une inégalité large difficile à atteindre, on essaie la contraposition.
3. Si l’énoncé affirme une impossibilité ou une irrationalité, on raisonne par l’absurde.
4. Si l’on cherche tous les objets vérifiant une condition, on fait une analyse-synthèse.
5. Si l’énoncé semble faux, on cherche un contre-exemple parmi les cas simples.

• Analyse : on part d’une solution hypothétique et on accumule ce qu’elle est forcée de satisfaire. On réduit ainsi la recherche à quelques candidats. Si un seul candidat survit, l’unicité est déjà prouvée.
• Synthèse : on vérifie que chaque candidat trouvé convient réellement. Cette étape prouve l’existence.

Déterminons les réels \(x \geqslant -6\) tels que \(\sqrt{x + 6} = x\).

1. Analyse : si \(x\) convient, on élève au carré et l’on obtient \(x + 6 = x^2\), soit \(x^2 – x – 6 = 0\). Or \(x^2 – x – 6 = (x – 3)(x + 2)\). Donc \(x = 3\) ou \(x = -2\).
2. Synthèse pour \(x = 3\) : \(\sqrt{9} = 3\), ce candidat convient.
3. Synthèse pour \(x = -2\) : \(\sqrt{4} = 2 \neq -2\), ce candidat ne convient pas.

L’unique solution est donc \(x = 3\). L’élévation au carré n’était qu’une implication, ce qui explique le candidat parasite.

Toute fonction \(f : \mathbb{R} \to \mathbb{R}\) s’écrit de manière unique \(f = h + g\), où \(h\) est une fonction affine et \(g\) une fonction qui s’annule en \(0\) et en \(1\).

Analyse : supposons \(f = h + g\) avec \(h(x) = ax + b\) et \(g(0) = g(1) = 0\). En évaluant en \(0\), on trouve \(f(0) = b\). En évaluant en \(1\), on trouve \(f(1) = a + b\). Ainsi \(b = f(0)\) et \(a = f(1) – f(0)\). Le couple \((h, g)\) est donc imposé, puisque \(g = f – h\). L’unicité est démontrée.

Synthèse : posons \(h(x) = \left(f(1) – f(0)\right)x + f(0)\) et \(g = f – h\). La fonction \(h\) est affine et \(f = h + g\). De plus, \(g(0) = f(0) – f(0) = 0\) et \(g(1) = f(1) – f(1) = 0\). L’existence est donc établie.

L’énoncé « pour tout réel \(x\), \(x^2 \geqslant x\) » est faux. Le réel \(x = \frac{1}{2}\) donne en effet \(x^2 = \frac{1}{4} < \frac{1}{2}\). La figure montre d’ailleurs que tout réel de \(\left]0, 1\right[\) fournit un contre-exemple.

On pourrait croire qu’une fonction \(f : \mathbb{R} \to \mathbb{R}\) qui vérifie \(f(x + 1) \geqslant f(x)\) pour tout réel \(x\) est croissante. C’est faux. Prenons \(f(x) = x – \lfloor x \rfloor\), où \(\lfloor x \rfloor\) désigne la partie entière. Alors \(f(x + 1) = f(x)\) pour tout \(x\), donc l’hypothèse est vérifiée. Pourtant, \(f(0{,}9) = 0{,}9\) et \(f(1) = 0\) : la fonction n’est pas croissante.

1. Écrire la négation de l’énoncé pour savoir exactement ce qu’il faut exhiber.
2. Tester les cas simples : \(0\), \(1\), \(-1\), \(\frac{1}{2}\), les petits entiers, une fonction constante ou affine.
3. Tester les cas limites : nombres négatifs, valeurs entre \(0\) et \(1\), objets qui vérifient l’hypothèse « de justesse ».
4. Rédiger le contre-exemple avec un calcul complet, sans se contenter d’un dessin.

• S’exercer : exercices corrigés de L1 de maths sur logique et types de démonstration
• Chapitre d’après : Ensembles, applications et bijections
• Vérifier ses acquis : QCM de L1 de maths sur logique et types de démonstration
• Contrôle corrigé en temps limité : Négations et types de démonstration : contrôle de maths en L1
• Tous les chapitres : le sommaire de la L1 de maths
• Après le bac : les maths post-bac, de la MPSI à la L3