Table des matières
Notions de Logique
1ère Année Baccalauréat – Sciences Mathématiques
Proposition, fonction propositionnelle, quantificateurs
Activité
On considère les énoncés suivants :
-
« \(2 + 3 = 5\) » (E1)
-
« Tout nombre réel est positif » (E2)
-
« \(x^2 \geq 0\) » où \(x\) désigne un nombre réel (E3)
-
« Bonjour ! » (E4)
-
« Pour tout réel \(x\), on a \(x^2 \geq 0\) » (E5)
Pour chacun, indiquer s’il est doué d’un sens mathématique, et le cas échéant, s’il est vrai, faux, ou dépend d’une valeur particulière.
Proposition
Définition
Une proposition (ou assertion) est tout énoncé mathématique ayant un sens et qui peut être soit vrai, soit faux, mais jamais les deux à la fois.
\(\bullet\)Si la proposition \(P\) est vraie, sa valeur de vérité est notée V (ou \(1\)).
\(\bullet\)Si elle est fausse, sa valeur de vérité est notée F (ou \(0\)).
Notations. Les propositions sont usuellement notées par les lettres majuscules \(P,\, Q,\, R,\dots\) La table de vérité d’une proposition \(P\) recense les valeurs possibles que peut prendre \(P\) :
| \(P\) |
|---|
| V |
| F |
Exemple
Déterminer la valeur de vérité des propositions suivantes :
-
« \(1 \in \mathbb{Z}\) »
-
« \(\sqrt{9+16} = \sqrt{9} + \sqrt{16}\) »
-
« \(2\) est un nombre décimal »
-
« \(2\) est l’unique entier naturel pair et premier »
-
« Un carré est un parallélogramme »
Fonction propositionnelle
Définition
Une fonction propositionnelle (ou prédicat) est un énoncé mathématique contenant une (ou plusieurs) variable(s) dans un ensemble \(E\), qui devient une proposition dès qu’on substitue à la variable un élément de \(E\).
On la note \(P(x)\), \(Q(x,y)\), \(R(x,y,z)\)…selon le nombre de variables.
Exemple
Soient \(P(x) :\) « \(x^2 \geq 0\) », \(Q(n) :\) « \(n\) est pair », \(R(x,y) :\) « \(x + y = 5\) », dans \(\mathbb{R}\), \(\mathbb{N}\) et \(\mathbb{R}^2\) respectivement.
-
\(P(3)\) : « \(9 \geq 0\) », c’est une proposition vraie.
-
\(Q(4)\) : « \(4\) est pair », vraie ; tandis que \(Q(7)\) est fausse.
-
\(R(2,3)\) : « \(2 + 3 = 5\) », vraie ; tandis que \(R(1,1)\) est fausse.
Quantificateurs
Pour transformer une fonction propositionnelle \(P(x)\) en proposition, on quantifie la variable.
Définition
Soit \(P(x)\) une fonction propositionnelle définie sur un ensemble \(E\) non vide.
\(\bullet\)Le quantificateur universel \(\forall\) se lit « pour tout » ou « quel que soit ». La proposition
\[(\forall x \in E) \; P(x)\]
est vraie ssi \(P(x)\) est vraie pour tout élément \(x\) de \(E\).
\(\bullet\)Le quantificateur existentiel \(\exists\) se lit « il existe (au moins un) ». La proposition
\[(\exists x \in E) \; P(x)\]
est vraie ssi il existe au moins un élément \(x\) de \(E\) pour lequel \(P(x)\) est vraie.
\(\bullet\)Le symbole \(\exists\,!\) se lit « il existe un unique ». La proposition \((\exists\, ! x \in E) \, P(x)\) est vraie ssi il existe exactement un élément \(x\) de \(E\) vérifiant \(P(x)\).
Exemple
Écrire les propositions suivantes à l’aide de quantificateurs, puis déterminer leur valeur de vérité.
\(P\) : « L’équation \(x^2 + x + 1 = 0\) admet au moins une solution réelle. »
\(Q\) : « Tout entier naturel est positif ou nul. »
\(R\) : « Certains nombres réels ne sont pas rationnels. »
\(S\) : « L’équation \(2x + 1 = 0\) admet une unique solution dans \(\mathbb{R}\). »
Permutation des quantificateurs
Proposition
Soient \(P(x,y)\) une fonction propositionnelle sur \(E \times F\).
(a) On peut permuter deux quantificateurs de même nature :
\[(\forall x \in E)(\forall y \in F)\, P(x,y) \;\Leftrightarrow\; (\forall y \in F)(\forall x \in E)\, P(x,y)\]
\[(\exists x \in E)(\exists y \in F)\, P(x,y) \;\Leftrightarrow\; (\exists y \in F)(\exists x \in E)\, P(x,y)\]
(b) On ne peut pas permuter des quantificateurs de natures différentes : en général
\[(\forall x \in E)(\exists y \in F)\, P(x,y) \quad \text{n'équivaut pas à} \quad (\exists y \in F)(\forall x \in E)\, P(x,y).\]
Remarque
Dans l’énoncé \((\forall x)(\exists y)\, P(x,y)\), l’élément \(y\) dépend de \(x\) (il peut varier avec lui). En revanche dans \((\exists y)(\forall x)\, P(x,y)\), l’élément \(y\) est fixé une fois pour toutes, indépendamment de \(x\) : c’est une condition strictement plus forte.
Illustration concrète. La phrase « Pour toute personne, il existe un numéro de téléphone » est vraie – chacun a un numéro. Mais « Il existe un numéro de téléphone valable pour toute personne » est fausse : il faudrait que tout le monde ait le même numéro.
Exemple
Étudier la valeur de vérité des propositions suivantes :
\[P_1 : (\forall x \in \mathbb{R})(\exists y \in \mathbb{R})\; y > x \qquad P_2 : (\exists y \in \mathbb{R})(\forall x \in \mathbb{R})\; y > x\]
Application
-
Écrire avec des quantificateurs et déterminer la valeur de vérité :
-
\(T\) : « Pour tout entier naturel \(n\) et pour tout entier naturel \(m\) on a \(m = 2n\). »
-
\(U\) : « Pour tout \(x \in \mathbb{R}\), il existe \(y \in \mathbb{R}\) tel que \(y > x\). »
-
\(V\) : « Il existe \(y \in \mathbb{R}\) tel que pour tout \(x \in \mathbb{R}\), \(y > x\). »
-
-
Étudier la valeur de vérité de :
\[A_1 : (\exists x \in \mathbb{R})\; x^2 = 4 \qquad A_2 : (\forall x \in \mathbb{R})\; x^2 + 2x + 1 \geq 0\]
\[A_3 : (\exists x \in \mathbb{N})\; 3x - 1 = 0 \qquad A_4 : (\forall x \in \mathbb{R})\; |x| = x\]
Négation d’une proposition
Négation d’une proposition simple
Définition
Soit \(P\) une proposition. La négation de \(P\), notée \(\overline{P}\) (ou \(\neg P\), ou « non \(P\) »), est la proposition qui est vraie lorsque \(P\) est fausse, et fausse lorsque \(P\) est vraie.
| \(P\) | \(\overline{P}\) |
|---|---|
| V | F |
| F | V |
Proposition
Pour toute proposition \(P\) : \(\overline{(\overline{P})} \Leftrightarrow P\) (loi de double négation).
Exemple
Écrire la négation des propositions suivantes et préciser leur valeur de vérité :
-
\(P : 1 + \sqrt{4} = 3\)
-
\(Q : \sqrt{11} \in [3\,;\,4]\)
-
\(R : \pi > 3{,}14\)
Négation des propositions quantifiées
Théorème
Soient \(E\) un ensemble non vide et \(P(x)\) une fonction propositionnelle sur \(E\).
(a) \(\overline{(\forall x \in E)\, P(x)} \;\;\Leftrightarrow\;\; (\exists x \in E)\, \overline{P(x)}\)
(b) \(\overline{(\exists x \in E)\, P(x)} \;\;\Leftrightarrow\;\; (\forall x \in E)\, \overline{P(x)}\)
Méthode
Comment nier une proposition quantifiée.
-
Remplacer chaque \(\forall\) par \(\exists\) et chaque \(\exists\) par \(\forall\).
-
Nier la fonction propositionnelle qui suit les quantificateurs.
-
Respecter l’ordre d’apparition des quantificateurs : il ne change pas.
Exemple
Écrire la négation des propositions suivantes :
-
\(A : (\forall x \in \mathbb{R})\; x^2 \geq 0\)
-
\(B : (\exists x \in \mathbb{N})\; 2x = 7\)
-
\(C : (\forall x \in \mathbb{R})(\exists y \in \mathbb{R})\; y = 2x\)
-
\(D : (\exists M \in \mathbb{R})(\forall n \in \mathbb{N})\; u_n \leq M\) (« la suite \((u_n)\) est majorée »)
Remarque
Quelques résultats utiles à retenir :
\[\sqrt{2} \notin \mathbb{Q} \qquad ; \qquad x \in \mathbb{Q} \;\Leftrightarrow\; \bigl(\exists (a,b) \in \mathbb{Z} \times \mathbb{N}^*\bigr)\; \Bigl(x = \tfrac{a}{b}\, \text{ et } \,\mathrm{pgcd}(a,b) = 1\Bigr)\]
Convention de notation. Dans ce cours, le symbole « \(\wedge\) » désigne exclusivement la conjonction logique. Pour le plus grand commun diviseur, on utilise \(\mathrm{pgcd}(a,b)\).
Application
Déterminer la négation et la valeur de vérité de :
\[P_1 : (\exists x \in \mathbb{N})\; x^2 = 36 \qquad P_2 : (\forall x \in \mathbb{R})\; x^3 > x\]
\[P_3 : (\forall n \in \mathbb{N})(\exists y \in \mathbb{N})\; y = 2n \qquad P_4 : (\exists n \in \mathbb{N})(\forall m \in \mathbb{N})\; n + m = 0\]
Opérations sur deux propositions
Soient \(P\) et \(Q\) deux propositions.
Conjonction et disjonction
Définition
\(\bullet\)La conjonction de \(P\) et \(Q\), notée \(P \wedge Q\) (lue « \(P\) et \(Q\) »), est la proposition qui est vraie uniquement si \(P\) et \(Q\) sont vraies en même temps.
\(\bullet\)La disjonction de \(P\) et \(Q\), notée \(P \vee Q\) (lue « \(P\) ou \(Q\) »), est la proposition qui est vraie si au moins l’une des deux propositions est vraie.
Implication et équivalence
Définition
\(\bullet\)L’implication \(P \Rightarrow Q\) (lue « \(P\) implique \(Q\) ») est la proposition qui est fausse uniquement lorsque \(P\) est vraie et \(Q\) est fausse.
\(\bullet\)L’équivalence \(P \Leftrightarrow Q\) (lue « \(P\) équivaut à \(Q\) ») est vraie lorsque \(P\) et \(Q\) ont la même valeur de vérité.
Table de vérité commune.
| \(P\) | \(Q\) | \(P \wedge Q\) | \(P \vee Q\) | \(P \Rightarrow Q\) | \(P \Leftrightarrow Q\) |
|---|---|---|---|---|---|
| V | V | V | V | V | V |
| V | F | F | V | F | F |
| F | V | F | V | V | F |
| F | F | F | F | V | V |
Remarque
Lectures alternatives de l’implication \(P \Rightarrow Q\) :
-
« Si \(P\), alors \(Q\) » ;
-
« \(P\) est une condition suffisante pour \(Q\) » ;
-
« \(Q\) est une condition nécessaire pour \(P\) » ;
-
« Pour que \(Q\), il suffit que \(P\) » ;
-
« Pour que \(P\), il faut que \(Q\) ».
L’implication réciproque de \(P \Rightarrow Q\) est \(Q \Rightarrow P\). Attention : \(P \Rightarrow Q\) et \(Q \Rightarrow P\) n’ont pas la même table de vérité ; l’implication n’est pas commutative.
Lectures de l’équivalence \(P \Leftrightarrow Q\) :
-
« \(P\) si et seulement si \(Q\) » ;
-
« \(P\) est une condition nécessaire et suffisante pour \(Q\) ».
Exemple
Déterminer la valeur de vérité de :
-
\(2 < 7\) et \(10 = 5\)
-
\(2 < 7\) ou \(10 = 5\)
-
\(\pi \in \mathbb{N} \Rightarrow 1 \neq 2\)
-
\(1 = 2 \Rightarrow 3 = 4\)
-
\(5\) est impair \(\Rightarrow (\forall x \in \mathbb{R})\, x^2 \geq 0\)
-
\(|-4| = 4 \Leftrightarrow 3 \leq 12\)
Négations des connecteurs
Théorème
(Lois de De Morgan). Pour toutes propositions \(P\) et \(Q\) :
(a) \(\overline{P \wedge Q} \;\Leftrightarrow\; \overline{P} \vee \overline{Q}\)
(b) \(\overline{P \vee Q} \;\Leftrightarrow\; \overline{P} \wedge \overline{Q}\)
(c) \(\overline{P \Rightarrow Q} \;\Leftrightarrow\; P \wedge \overline{Q}\)
(d) \(\overline{P \Leftrightarrow Q} \;\Leftrightarrow\; (P \wedge \overline{Q}) \vee (\overline{P} \wedge Q)\)
Démonstration
On démontre (a), (b), (c) en construisant la table de vérité commune.
| \(P\) | \(Q\) | \(P \wedge Q\) | \(\overline{P\wedge Q}\) | \(\overline{P}\) | \(\overline{Q}\) | \(\overline{P} \vee \overline{Q}\) | \(P \vee Q\) | \(\overline{P \vee Q}\) | \(\overline{P}\wedge \overline{Q}\) |
|---|---|---|---|---|---|---|---|---|---|
| V | V | V | F | F | F | F | V | F | F |
| V | F | F | V | F | V | V | V | F | F |
| F | V | F | V | V | F | V | V | F | F |
| F | F | F | V | V | V | V | F | V | V |
On lit les égalités de colonnes : \(\overline{P\wedge Q}\) et \(\overline{P}\vee \overline{Q}\) coïncident, prouvant (a) ; de même \(\overline{P\vee Q}\) et \(\overline{P}\wedge \overline{Q}\) coïncident, prouvant (b).
Pour (c), on dresse :
| \(P\) | \(Q\) | \(P \Rightarrow Q\) | \(\overline{P \Rightarrow Q}\) | \(\overline{Q}\) | \(P \wedge \overline{Q}\) |
|---|---|---|---|---|---|
| V | V | V | F | F | F |
| V | F | F | V | V | V |
| F | V | V | F | F | F |
| F | F | V | F | V | F |
Les colonnes \(\overline{P \Rightarrow Q}\) et \(P \wedge \overline{Q}\) sont identiques. \(\square\)
(d) se traite de même par table de vérité (laissé en application).
Propriétés algébriques des connecteurs
Proposition
Pour toutes propositions \(P\), \(Q\), \(R\) :
Commutativité : \(\;P \wedge Q \Leftrightarrow Q \wedge P\) et \(P \vee Q \Leftrightarrow Q \vee P\).
Associativité : \(\;(P \wedge Q) \wedge R \Leftrightarrow P \wedge (Q \wedge R)\) et \((P \vee Q) \vee R \Leftrightarrow P \vee (Q \vee R)\).
Distributivité :
\[P \wedge (Q \vee R) \;\Leftrightarrow\; (P \wedge Q) \vee (P \wedge R)\]
\[P \vee (Q \wedge R) \;\Leftrightarrow\; (P \vee Q) \wedge (P \vee R)\]
Forme disjonctive de l’implication :
\[(P \Rightarrow Q) \;\Leftrightarrow\; (\overline{P} \vee Q)\]
Démonstration
On démontre la distributivité \(\,P \wedge (Q \vee R) \Leftrightarrow (P \wedge Q) \vee (P \wedge R)\,\) par table de vérité (les 8 lignes correspondent aux 8 affectations possibles de \(P,Q,R\)).
| \(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 |
Les colonnes encadrant l’équivalence à démontrer sont identiques. \(\square\)
Forme disjonctive. Comparons \(P \Rightarrow Q\) et \(\overline{P} \vee Q\) :
| \(P\) | \(Q\) | \(P \Rightarrow Q\) | \(\overline{P}\) | \(\overline{P} \vee Q\) |
|---|---|---|---|---|
| V | V | V | F | V |
| V | F | F | F | F |
| F | V | V | V | V |
| F | F | V | V | V |
Colonnes identiques, donc \((P \Rightarrow Q) \Leftrightarrow (\overline{P} \vee Q)\). \(\square\)
Distribution sur les quantificateurs
Proposition
Soient \(P(x)\) et \(Q(x)\) deux fonctions propositionnelles sur un même ensemble \(E \neq \emptyset\).
(a) \((\forall x \in E)\, \bigl(P(x) \wedge Q(x)\bigr) \;\Leftrightarrow\; \bigl((\forall x \in E)\, P(x)\bigr) \wedge \bigl((\forall x \in E)\, Q(x)\bigr)\)
(b) \((\exists x \in E)\, \bigl(P(x) \vee Q(x)\bigr) \;\Leftrightarrow\; \bigl((\exists x \in E)\, P(x)\bigr) \vee \bigl((\exists x \in E)\, Q(x)\bigr)\)
Remarque
Attention : les implications suivantes ne sont pas des équivalences.
\[(\forall x \in E)\, \bigl(P(x) \vee Q(x)\bigr) \quad \not\Leftrightarrow \quad \bigl((\forall x \in E)\, P(x)\bigr) \vee \bigl((\forall x \in E)\, Q(x)\bigr)\]
\[(\exists x \in E)\, \bigl(P(x) \wedge Q(x)\bigr) \quad \not\Leftrightarrow \quad \bigl((\exists x \in E)\, P(x)\bigr) \wedge \bigl((\exists x \in E)\, Q(x)\bigr)\]
Contre-exemple. Sur \(E = \mathbb{R}\), posons \(P(x) :\) « \(x \geq 0\) » et \(Q(x) :\) « \(x \leq 0\) ». Alors \((\forall x \in \mathbb{R})\, (P(x) \vee Q(x))\) est vraie (tout réel est \(\geq 0\) ou \(\leq 0\)), mais aucune des deux propositions \((\forall x \in \mathbb{R})\, P(x)\), \((\forall x \in \mathbb{R})\, Q(x)\) n’est vraie individuellement.
Application
-
Démontrer la propriété (d) (négation de l’équivalence) par table de vérité.
-
Montrer que \(\overline{P \Rightarrow Q} \Leftrightarrow P \wedge \overline{Q}\) sans utiliser de table de vérité, mais en utilisant la forme disjonctive et les lois de De Morgan.
-
Simplifier \(\overline{\bigl((\forall x \in \mathbb{R})\; x \geq 1 \Rightarrow x^2 \geq 1\bigr)}\).
Lois logiques (tautologies)
Définition
Définition
On appelle loi logique (ou tautologie) toute proposition composée à partir de propositions élémentaires \(P, Q, R,\dots\) et de connecteurs logiques, qui prend la valeur de vérité V quelle que soit la valeur de vérité de chaque proposition élémentaire.
Méthode
Pour montrer qu’une proposition est une loi logique, il suffit de dresser sa table de vérité et de vérifier qu’elle ne contient que des V dans la colonne finale.
Lois logiques fondamentales
Théorème
Les propositions suivantes sont des lois logiques :
(L1) \(P \vee \overline{P}\) (principe du tiers exclu)
(L2) \(\overline{(P \wedge \overline{P})}\) (principe de non-contradiction)
(L3) \(\overline{(\overline{P})} \Leftrightarrow P\) (double négation)
(L4) \((P \Rightarrow Q) \Leftrightarrow (\overline{Q} \Rightarrow \overline{P})\) (contraposition)
(L5) \(\bigl[(P \Rightarrow Q) \wedge (Q \Rightarrow R)\bigr] \Rightarrow (P \Rightarrow R)\) (transitivité de l’implication)
(L6) \(\bigl[(P \Rightarrow Q) \wedge P\bigr] \Rightarrow Q\) (modus ponens)
(L7) \(\bigl[(P \Rightarrow Q) \wedge \overline{Q}\bigr] \Rightarrow \overline{P}\) (modus tollens)
Démonstration
Loi de contraposition (L4). Table de vérité :
| \(P\) | \(Q\) | \(P \Rightarrow Q\) | \(\overline{P}\) | \(\overline{Q}\) | \(\overline{Q} \Rightarrow \overline{P}\) | \((P\Rightarrow Q) \Leftrightarrow (\overline{Q} \Rightarrow \overline{P})\) |
|---|---|---|---|---|---|---|
| V | V | V | F | F | V | V |
| V | F | F | F | V | F | V |
| F | V | V | V | F | V | V |
| F | F | V | V | V | V | V |
La dernière colonne contient uniquement V, donc l’équivalence est une loi logique. \(\square\)
Transitivité (L5). Posons \(A = (P \Rightarrow Q) \wedge (Q \Rightarrow R)\) et \(B = P \Rightarrow R\).
| \(P\) | \(Q\) | \(R\) | \(P \Rightarrow Q\) | \(Q \Rightarrow R\) | \(A\) | \(B = P \Rightarrow R\) | \(A \Rightarrow B\) |
|---|---|---|---|---|---|---|---|
| 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 |
Colonne finale uniformément V. \(\square\)
Exemple
Montrer que la proposition \(\bigl[P \vee (Q \wedge R)\bigr] \Leftrightarrow \bigl[(P \vee Q) \wedge (P \vee R)\bigr]\) est une loi logique.
Application
Montrer que les propositions suivantes sont des lois logiques :
-
\(P \Rightarrow (P \vee Q)\)
-
\((P \wedge Q) \Rightarrow P\)
-
\(\bigl[(P \Rightarrow Q) \wedge (P \Rightarrow R)\bigr] \Rightarrow \bigl[P \Rightarrow (Q \wedge R)\bigr]\)
-
\(\bigl[(P \vee Q) \wedge \overline{P}\bigr] \Rightarrow Q\) (syllogisme disjonctif)
Raisonnements mathématiques
Une démonstration mathématique consiste à établir la véracité d’une proposition à partir d’axiomes, de définitions et de théorèmes déjà prouvés. On utilise plusieurs types de raisonnement selon la structure de l’énoncé.
Raisonnement par contre-exemple
Méthode
Pour montrer qu’une proposition de la forme \((\forall x \in E)\, P(x)\) est fausse, il suffit de trouver un seul élément \(x_0 \in E\) tel que \(P(x_0)\) soit fausse. On parle de raisonnement par contre-exemple.
Exemple
Déterminer la valeur de vérité de :
-
\((\forall x \in \mathbb{R})\; x^2 + x - 2 = 0\)
-
\((\forall (x,y) \in \mathbb{R}^2)\; 3x + 5y = 8\)
-
\((\forall x \in \mathbb{R})(\exists y \in \mathbb{R})\; x + y = xy\)
Raisonnement déductif (direct)
Méthode
Pour démontrer une implication \(P \Rightarrow Q\) par raisonnement déductif :
-
Méthode des implications successives : on construit une chaîne \(P \Rightarrow P_1 \Rightarrow P_2 \Rightarrow \cdots \Rightarrow Q\) à l’aide de propriétés et théorèmes connus.
-
Méthode hypothèse-conclusion : on suppose \(P\) vraie, puis on démontre \(Q\) par déduction.
Justification : la loi logique \(\bigl[(P \Rightarrow R) \wedge (R \Rightarrow Q)\bigr] \Rightarrow (P \Rightarrow Q)\) (transitivité).
Exemple
Montrer que : \((\forall x \in \mathbb{R})\; |x| \leq 2 \Rightarrow |3x+1| \leq 7\).
Démonstration. Soit \(x \in \mathbb{R}\). Supposons que \(|x| \leq 2\).
Alors \(|3x| = 3|x| \leq 3 \cdot 2 = 6\).
Par l’inégalité triangulaire : \(|3x + 1| \leq |3x| + |1| \leq 6 + 1 = 7\).
Donc \(|3x+1| \leq 7\). \(\square\)
Exemple
Montrer que : \((\forall a > 0)\; a + \dfrac{1}{a} \geq 2\).
Démonstration. Soit \(a > 0\). Étudions la différence :
\[a + \frac{1}{a} - 2 = \frac{a^2 - 2a + 1}{a} = \frac{(a-1)^2}{a}\]
Or \((a-1)^2 \geq 0\) et \(a > 0\), donc \(\dfrac{(a-1)^2}{a} \geq 0\), c’est-à-dire \(a + \dfrac{1}{a} \geq 2\). \(\square\)
Remarque. L’égalité a lieu ssi \(a = 1\).
Raisonnement par contraposée
Méthode
Pour montrer une implication \(P \Rightarrow Q\) par contraposée, on prouve l’implication équivalente \(\overline{Q} \Rightarrow \overline{P}\).
Justification : loi de contraposition \((P \Rightarrow Q) \Leftrightarrow (\overline{Q} \Rightarrow \overline{P})\).
Exemple
(Démonstration canonique). Soit \(n \in \mathbb{N}\). Montrer que : \(n^2\) pair \(\Rightarrow n\) pair.
Démonstration par contraposée. L’implication contraposée est :
\(n\) impair \(\Rightarrow n^2\) impair.
Supposons donc \(n\) impair. Alors il existe \(k \in \mathbb{N}\) tel que \(n = 2k+1\). On calcule :
\[n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.\]
Posons \(k' = 2k^2 + 2k \in \mathbb{N}\) : alors \(n^2 = 2k' + 1\) est impair.
Ainsi \(n\) impair \(\Rightarrow n^2\) impair, ce qui équivaut à \(n^2\) pair \(\Rightarrow n\) pair. \(\square\)
Exemple
Soient \(a, b\) deux réels tels que \(a \neq -b\). Montrer par contraposée que :
\[\frac{a-b}{a+b} \neq -3 \;\;\Rightarrow\;\; b \neq -2a.\]
Démonstration par contraposée. L’implication contraposée est :
\[b = -2a \;\;\Rightarrow\;\; \frac{a-b}{a+b} = -3.\]
Supposons donc \(b = -2a\). L’hypothèse \(a \neq -b\) s’écrit alors \(a \neq 2a\), soit \(a \neq 0\). On peut donc substituer :
\[\frac{a - b}{a + b} \;=\; \frac{a - (-2a)}{a + (-2a)} \;=\; \frac{3a}{-a} \;=\; -3 \qquad (\text{division licite car } a \neq 0).\]
On obtient bien \(\dfrac{a-b}{a+b} = -3\). \(\square\)
Exemple
Soit \(a \in \mathbb{Z}\). Montrer par contraposée que :
\[a^2 + 1 \text{ pair} \;\;\Rightarrow\;\; a \text{ impair}.\]
Démonstration. Contraposée : \(a\) pair \(\Rightarrow a^2 + 1\) impair.
Supposons \(a\) pair. Alors \(a = 2k\) pour un certain \(k \in \mathbb{Z}\). Donc
\[a^2 + 1 \;=\; 4k^2 + 1 \;=\; 2 \cdot (2k^2) + 1,\]
qui est impair. \(\square\)
Remarque
Ne pas confondre :
-
La négation de \(P \Rightarrow Q\) est : \(P \wedge \overline{Q}\).
-
La réciproque de \(P \Rightarrow Q\) est : \(Q \Rightarrow P\).
-
La contraposée de \(P \Rightarrow Q\) est : \(\overline{Q} \Rightarrow \overline{P}\) (\(\Leftrightarrow P \Rightarrow Q\)).
Raisonnement par équivalences successives
Méthode
Pour démontrer une équivalence \(P \Leftrightarrow Q\), deux approches :
-
Équivalences successives : construire une chaîne \(P \Leftrightarrow P_1 \Leftrightarrow P_2 \Leftrightarrow \cdots \Leftrightarrow Q\) à l’aide de propriétés conservant l’équivalence (manipulations algébriques réversibles).
-
Double implication : démontrer séparément \(P \Rightarrow Q\) et \(Q \Rightarrow P\). C’est la méthode à privilégier quand certaines étapes ne sont pas réversibles, par exemple un passage au carré ou une mise à l’exponentielle.
Exemple
Résoudre dans \(\mathbb{R} \setminus \{-1\}\) l’inéquation \(\dfrac{x-1}{x+1} \leq 2\), et exprimer son ensemble de solutions comme équivalence logique.
Raisonnement par disjonction des cas
Méthode
Pour montrer une proposition de la forme \((\forall x \in E)\, P(x)\) par disjonction des cas, on partage \(E\) en sous-ensembles \(E_1, E_2, \dots, E_n\) recouvrant \(E\), et l’on démontre \(P(x)\) séparément sur chaque sous-ensemble.
Justification : loi \(\bigl[(R \Rightarrow P) \wedge (Q \Rightarrow P)\bigr] \Rightarrow \bigl[(R \vee Q) \Rightarrow P\bigr]\).
Exemple
(Démonstration canonique). Montrer que : \((\forall n \in \mathbb{N})\; n(n+1) \text{ est pair}\).
Démonstration par disjonction des cas. Soit \(n \in \mathbb{N}\). On distingue deux cas.
Cas 1 : \(n\) est pair. Il existe \(k \in \mathbb{N}\) tel que \(n = 2k\). Alors \(n(n+1) = 2k(n+1) = 2 \cdot \bigl[k(n+1)\bigr]\), qui est pair.
Cas 2 : \(n\) est impair. Alors \(n + 1\) est pair : il existe \(k \in \mathbb{N}\) tel que \(n + 1 = 2k\). Donc \(n(n+1) = n \cdot 2k = 2 \cdot (nk)\), qui est pair.
Dans les deux cas, \(n(n+1)\) est pair. \(\square\)
Exemple
Montrer que : \((\forall x \in \mathbb{R})\; x^2 - x + 1 \geq |x - 1|\).
Raisonnement par l’absurde
Méthode
Pour montrer une proposition \(P\) par l’absurde, on suppose \(\overline{P}\) vraie et on cherche à aboutir à une contradiction. La contradiction prouve \(\overline{P}\) fausse, donc \(P\) vraie.
Justification : loi \(\bigl[(\overline{P} \Rightarrow R) \wedge (\overline{P} \Rightarrow \overline{R})\bigr] \Rightarrow P\).
Exemple
(Démonstration canonique : irrationalité de \(\sqrt{2}\)).
Montrer que \(\sqrt{2} \notin \mathbb{Q}\).
Démonstration par l’absurde. Supposons par l’absurde que \(\sqrt{2} \in \mathbb{Q}\). Alors il existe deux entiers \(a \in \mathbb{Z}\) et \(b \in \mathbb{N}^*\) tels que
\[\sqrt{2} = \frac{a}{b} \quad \text{avec} \quad \mathrm{pgcd}(a,b) = 1 \quad \text{(fraction irréductible).}\]
En élevant au carré : \(2 = \dfrac{a^2}{b^2}\), donc
\[a^2 = 2 b^2. \tag{$\star$}\]
De \((\star)\), \(a^2\) est pair. D’après la propriété \(\,n^2 \text{ pair} \Rightarrow n \text{ pair}\,\) (déjà démontrée par contraposée sur \(\mathbb{N}\), et qui s’étend immédiatement à \(\mathbb{Z}\) : si \(a \in \mathbb{Z}\) est impair, on écrit \(a = 2k+1\) avec \(k \in \mathbb{Z}\), et \(a^2 = 4k^2 + 4k + 1\) est impair), \(a\) est pair. Il existe donc \(k \in \mathbb{Z}\) tel que \(a = 2k\).
En substituant dans \((\star)\) : \((2k)^2 = 2 b^2\), soit \(4k^2 = 2 b^2\), donc \(b^2 = 2 k^2\).
Ainsi \(b^2\) est pair, donc \(b\) est pair (par la même propriété, appliquée dans \(\mathbb{N}\)).
Conclusion : \(a\) et \(b\) sont tous deux pairs, donc \(2 \mid a\) et \(2 \mid b\). Donc \(\mathrm{pgcd}(a,b) \geq 2\), ce qui contredit l’hypothèse \(\mathrm{pgcd}(a,b) = 1\).
L’absurdité prouve que \(\sqrt{2} \notin \mathbb{Q}\). \(\square\)
Exemple
Soit \(n \in \mathbb{N}\). On pose \(A_n = \dfrac{n+3}{n+1}\). Montrer que \(A_n \neq 1\).
Démonstration par l’absurde. Supposons \(A_n = 1\). Alors \(\dfrac{n+3}{n+1} = 1\), soit \(n + 3 = n + 1\), d’où \(3 = 1\). Contradiction. \(\square\)
Exemple
Soit \(ABC\) un triangle et \(a > 0\) tels que \(BC = 3a\), \(CA = 2a\) et \(AB = 4a\). Montrer que \(ABC\) n’est pas rectangle.
Démonstration par l’absurde. Supposons \(ABC\) rectangle. Dans un triangle rectangle, l’hypoténuse est le côté le plus long ; ici, le côté le plus long est \(AB = 4a\) (car \(4a > 3a > 2a\)). L’angle droit est donc nécessairement au sommet opposé à \(AB\), c’est-à-dire en \(C\).
D’après le théorème de Pythagore, \(ABC\) rectangle en \(C\) entraîne \(AB^2 = BC^2 + CA^2\), soit
\[(4a)^2 = (3a)^2 + (2a)^2 \;\;\Leftrightarrow\;\; 16 a^2 = 9 a^2 + 4 a^2 = 13 a^2.\]
Comme \(a > 0\), \(a^2 > 0\), on peut diviser par \(a^2\) : on obtient \(16 = 13\), contradiction. \(\square\)
Notations \(\Sigma\) et \(\Pi\)
Définition
Soient \((a_k)_{k \in \mathbb{N}}\) une suite de nombres réels et \(m, p \in \mathbb{N}\) avec \(m \leq p\).
\(\bullet\)La somme indexée par \(k\) allant de \(m\) à \(p\) se note :
\[\sum_{k=m}^{p} a_k \;=\; a_m + a_{m+1} + a_{m+2} + \cdots + a_p.\]
\(\bullet\)Le produit indexé par \(k\) allant de \(m\) à \(p\) se note :
\[\prod_{k=m}^{p} a_k \;=\; a_m \cdot a_{m+1} \cdot a_{m+2} \cdots a_p.\]
Proposition
Soient \((a_k)\), \((b_k)\) deux suites réelles, \(m, p \in \mathbb{N}\) avec \(m \leq p\), et \(\lambda \in \mathbb{R}\).
\[\sum_{k=m}^{p} (a_k + b_k) \;=\; \sum_{k=m}^{p} a_k + \sum_{k=m}^{p} b_k \quad ; \quad \sum_{k=m}^{p} \lambda a_k \;=\; \lambda \sum_{k=m}^{p} a_k \quad ; \quad \sum_{k=m}^{p} \lambda \;=\; (p - m + 1)\, \lambda.\]
\[\prod_{k=m}^{p} (a_k \cdot b_k) \;=\; \left(\prod_{k=m}^{p} a_k\right) \cdot \left(\prod_{k=m}^{p} b_k\right) \quad ; \quad \prod_{k=m}^{p} \lambda \;=\; \lambda^{\, p - m + 1}.\]
Exemple
Avec cette notation :
\[1 + 2 + 3 + \cdots + n = \sum_{k=1}^{n} k = \frac{n(n+1)}{2} \quad ; \quad 1 + 3 + 5 + \cdots + (2n+1) = \sum_{k=0}^{n} (2k+1) = (n+1)^2.\]
\[1 \cdot 2 \cdot 3 \cdots n = \prod_{k=1}^{n} k = n! \quad ; \quad \prod_{k=1}^{n} 2 = 2^n.\]
Raisonnement par récurrence
C’est le pilier de la démonstration en \(\mathbb{N}\).
Théorème
(Principe de récurrence).
Soient \(P(n)\) une fonction propositionnelle sur \(\mathbb{N}\) et \(n_0 \in \mathbb{N}\). Si :
-
\(P(n_0)\) est vraie (initialisation) ;
-
\(\forall n \geq n_0\) : \(\;P(n) \Rightarrow P(n+1)\) (hérédité) ;
alors \(P(n)\) est vraie pour tout \(n \geq n_0\).
Méthode
Schéma d’une démonstration par récurrence sur \(P(n)\), à partir de \(n_0\) :
-
Initialisation. Vérifier que \(P(n_0)\) est vraie.
-
Hérédité. Soit \(n \geq n_0\). Supposer \(P(n)\) vraie (\(\,\)hypothèse de récurrence, abrégée HR\(\,\)). Démontrer alors \(P(n+1)\).
-
Conclusion. D’après le principe de récurrence, \(P(n)\) est vraie pour tout \(n \geq n_0\).
Exemple
(Récurrence canonique : somme des \(n\) premiers entiers).
Montrer que : \((\forall n \in \mathbb{N}^*)\;\; 1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}\).
Démonstration par récurrence. Posons \(P(n) :\) \(\displaystyle \sum_{k=1}^{n} k = \frac{n(n+1)}{2}\).
Initialisation (\(n = 1\)). Membre de gauche : \(1\). Membre de droite : \(\dfrac{1 \cdot 2}{2} = 1\). Donc \(P(1)\) est vraie.
Hérédité. Soit \(n \in \mathbb{N}^*\). Supposons \(P(n)\) vraie : \(\displaystyle\sum_{k=1}^n k = \frac{n(n+1)}{2}\) (HR).
Montrons \(P(n+1) : \displaystyle\sum_{k=1}^{n+1} k = \dfrac{(n+1)(n+2)}{2}\).
\[\sum_{k=1}^{n+1} k \;=\; \underbrace{\sum_{k=1}^{n} k}_{\text{HR}} + (n+1) \;=\; \frac{n(n+1)}{2} + (n+1) \;=\; (n+1) \left[\frac{n}{2} + 1\right] \;=\; (n+1) \cdot \frac{n+2}{2} \;=\; \frac{(n+1)(n+2)}{2}.\]
Donc \(P(n+1)\) est vraie.
Conclusion. Par récurrence, \(P(n)\) est vraie pour tout \(n \in \mathbb{N}^*\). \(\square\)
Exemple
(Somme des carrés).
Montrer que : \((\forall n \in \mathbb{N}^*)\;\; \displaystyle\sum_{k=1}^n k^2 = \dfrac{n(n+1)(2n+1)}{6}\).
Démonstration. Posons \(P(n) : \displaystyle\sum_{k=1}^n k^2 = \dfrac{n(n+1)(2n+1)}{6}\).
Init (\(n=1\)). À gauche : \(1^2 = 1\). À droite : \(\dfrac{1 \cdot 2 \cdot 3}{6} = 1\). OK.
Hérédité. Soit \(n \in \mathbb{N}^*\). Supposons \(P(n)\) vraie.
\[\begin{align*} \sum_{k=1}^{n+1} k^2 &= \sum_{k=1}^n k^2 + (n+1)^2 \\ &\overset{\text{HR}}{=} \frac{n(n+1)(2n+1)}{6} + (n+1)^2 \\ &= \frac{(n+1)}{6} \bigl[n(2n+1) + 6(n+1)\bigr] \\ &= \frac{(n+1)}{6}\bigl[2n^2 + n + 6n + 6\bigr] \\ &= \frac{(n+1)(2n^2 + 7n + 6)}{6} \\ &= \frac{(n+1)(n+2)(2n+3)}{6} \qquad \text{(factorisation : } 2n^2 + 7n + 6 = (n+2)(2n+3)\text{)} \\ &= \frac{(n+1)\bigl((n+1)+1\bigr)\bigl(2(n+1)+1\bigr)}{6}. \end{align*}\]
Donc \(P(n+1)\) est vraie.
Conclusion. Par récurrence, la formule est vraie pour tout \(n \in \mathbb{N}^*\). \(\square\)
Exemple
(Inégalité de Bernoulli).
Soit \(a \in \mathbb{R}\) avec \(a > -1\). Montrer que : \((\forall n \in \mathbb{N})\;\; (1 + a)^n \geq 1 + na\).
Démonstration. Posons \(P(n) : (1+a)^n \geq 1 + na\).
Init (\(n=0\)). À gauche : \((1+a)^0 = 1\). À droite : \(1 + 0 \cdot a = 1\). Donc \(P(0)\) est vraie.
Hérédité. Soit \(n \in \mathbb{N}\). Supposons \(P(n) : (1+a)^n \geq 1 + na\) (HR).
Comme \(a > -1\), on a \(1 + a > 0\) ; on peut donc multiplier l’inégalité par \(1 + a\) sans en changer le sens :
\[(1+a)^{n+1} \;=\; (1+a)^n (1+a) \;\overset{\text{HR}}{\geq}\; (1 + na)(1+a) \;=\; 1 + a + na + na^2 \;=\; 1 + (n+1) a + na^2.\]
Comme \(n \geq 0\) et \(a^2 \geq 0\), \(na^2 \geq 0\), donc
\[(1+a)^{n+1} \;\geq\; 1 + (n+1) a + na^2 \;\geq\; 1 + (n+1) a.\]
Donc \(P(n+1)\) est vraie.
Conclusion. Par récurrence, \(P(n)\) est vraie pour tout \(n \in \mathbb{N}\). \(\square\)
Exemple
(Inégalité exponentielle).
Montrer que : \((\forall n \in \mathbb{N})\;\; 2^n \geq n + 1\).
Démonstration. Posons \(P(n) : 2^n \geq n+1\).
Init (\(n=0\)). \(2^0 = 1 \geq 1 = 0+1\). OK.
Hérédité. Soit \(n \in \mathbb{N}\). Supposons \(P(n) : 2^n \geq n+1\) (HR).
\[2^{n+1} \;=\; 2 \cdot 2^n \;\overset{\text{HR}}{\geq}\; 2(n+1) \;=\; 2n + 2 \;\geq\; (n+1) + 1 \quad \text{car } n \geq 0.\]
Donc \(P(n+1)\) est vraie.
Conclusion. Par récurrence, \(2^n \geq n+1\) pour tout \(n \in \mathbb{N}\). \(\square\)
Synthèse
Tableau récapitulatif des opérations logiques
| Connecteur | Lecture | Négation |
|---|---|---|
| \(\overline{P}\) | non \(P\) | \(P\) |
| \(P \wedge Q\) | \(P\) et \(Q\) | \(\overline{P} \vee \overline{Q}\) |
| \(P \vee Q\) | \(P\) ou \(Q\) | \(\overline{P} \wedge \overline{Q}\) |
| \(P \Rightarrow Q\) | si \(P\) alors \(Q\) | \(P \wedge \overline{Q}\) |
| \(P \Leftrightarrow Q\) | \(P\) ssi \(Q\) | \((P \wedge \overline{Q}) \vee (\overline{P} \wedge Q)\) |
| \((\forall x \in E)\, P(x)\) | pour tout \(x\), \(P(x)\) | \((\exists x \in E)\, \overline{P(x)}\) |
| \((\exists x \in E)\, P(x)\) | il existe \(x\), \(P(x)\) | \((\forall x \in E)\, \overline{P(x)}\) |
Stratégie de choix du type de raisonnement
| Forme de l’énoncé | Raisonnement à privilégier |
|---|---|
| \((\forall x \in E)\, P(x)\) est vraie | Raisonnement direct (déductif) sur un \(x\) quelconque de \(E\). |
| \((\forall x \in E)\, P(x)\) est fausse | Contre-exemple. |
| \(P \Rightarrow Q\) avec \(Q\) “compliqué” | Direct si on voit la chaîne, sinon contraposée : on part de \(\overline{Q}\). |
| \(P \Leftrightarrow Q\) avec étapes réversibles | Équivalences successives. |
| \(P \Leftrightarrow Q\) avec étapes non réversibles (carré, exp…) | Double implication. |
| \((\forall x \in E)\, P(x)\) avec \(E\) partitionnable | Disjonction des cas. |
| Énoncé du type “\(x \notin E\)” ou “\(x \neq y\)” | Absurde. |
| \((\forall n \in \mathbb{N})\, P(n)\) | Récurrence. |
Pièges classiques à éviter
Remarque
-
Confondre \(P \Rightarrow Q\) et \(Q \Rightarrow P\). Une implication n’est pas commutative. Ex.: « si \(x = 2\) alors \(x^2 = 4\) » est vraie, mais « si \(x^2 = 4\) alors \(x = 2\) » est fausse (\(x = -2\)).
-
Confondre négation et contraposée. La négation de \(P \Rightarrow Q\) est \(P \wedge \overline{Q}\), pas \(\overline{P} \Rightarrow \overline{Q}\).
-
Permuter \(\forall\) et \(\exists\). Voir l’exemple du numéro de téléphone : \((\forall x)(\exists y) \neq (\exists y)(\forall x)\).
-
Récurrence sans initialisation. La proposition « \(n = n+1\) » se transmet héréditairement (\(P(n) \Rightarrow P(n+1)\)) mais n’est jamais vraie : l’initialisation est cruciale.
-
Contre-exemple pour démontrer une affirmation universelle. Un seul exemple ne prouve pas \((\forall x)\, P(x)\) : il ne sert qu’à la réfuter.
-
Élever au carré sans précaution. L’implication \(a = b \Rightarrow a^2 = b^2\) est vraie, mais pas la réciproque. Quand on passe au carré dans une équivalence, il faut justifier la réversibilité (signes des deux membres).
Fin du chapitre 1 – Notions de Logique