Notions de Logique v2 — version HTML
Motivations
Il est important d'avoir un langage rigoureux. La langue française est souvent ambigüe. Prenons l'exemple de la conjonction « ou » : au restaurant « fromage ou dessert » signifie l'un ou l'autre mais pas les deux. Par contre si dans un jeu de cartes on cherche « les as ou les cœurs » alors il ne faut pas exclure l'as de cœur.
Il y a des notions difficiles à expliquer avec des mots : par exemple la continuité d'une fonction est souvent expliquée par « on trace le graphe sans lever le crayon ». Voici la définition mathématique de la continuité d'une fonction \(f : I \to \RR\) en un point \(x_0 \in I\) :
C'est le but de ce chapitre de rendre cette ligne plus claire ! C'est la logique. Enfin, les mathématiques tentent de distinguer le vrai du faux : pour savoir si une affirmation est vraie, il faut suivre une démarche logique qui mène à la conclusion. On parle de raisonnement.
1. Proposition
Exemples :
- « Il pleut. »
- « Je suis plus grand que toi. »
- « \(2 + 2 = 4\) » — vraie.
- « \(2 \times 3 = 7\) » — fausse.
- « Pour tout \(x \in \RR\), on a \(x^2 \geq 0\) » — vraie.
- « Pour tout \(z \in \mathbb{C}\), on a \(|z| = 1\) » — fausse.
2. Opérations logiques
Dans toutes les tables ci-dessous, 1 signifie vrai (V) et 0 signifie faux (F).
2.1. L'opérateur logique « et »
La proposition « \(P\) et \(Q\) » est vraie si \(P\) est vraie et \(Q\) est vraie. La proposition « \(P\) et \(Q\) » est fausse sinon. On résume ceci en une table de vérité :
| P | Q | P et Q |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
Par exemple si \(P\) est la proposition « Cette carte est un as » et \(Q\) la proposition « Cette carte est cœur » alors « \(P\) et \(Q\) » est vraie si la carte est l'as de cœur, et fausse pour toute autre carte.
2.2. L'opérateur logique « ou »
La proposition « \(P\) ou \(Q\) » est vraie si l'une (au moins) des deux propositions \(P\) ou \(Q\) est vraie. La proposition « \(P\) ou \(Q\) » est fausse si les deux propositions \(P\) et \(Q\) sont fausses.
| P | Q | P ou Q |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
Si \(P\) est la proposition « Cette carte est un as » et \(Q\) la proposition « Cette carte est cœur » alors « \(P\) ou \(Q\) » est vraie si la carte est un as ou bien un cœur (en particulier elle est vraie pour l'as de cœur).
2.3. La négation « non »
La proposition « non \(P\) » est vraie si \(P\) est fausse, et fausse si \(P\) est vraie. On note \(\overline{P}\) la négation de la proposition \(P\).
| P | non P |
|---|---|
| 1 | 0 |
| 0 | 1 |
2.4. L'implication \(\Rightarrow\)
Sa table de vérité est donc la suivante :
| P | Q | P ⇒ Q |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
La proposition « \(P \Rightarrow Q\) » se lit en français « \(P\) implique \(Q\) ». Elle se lit souvent aussi « si \(P\) est vraie alors \(Q\) est vraie » ou « si \(P\) alors \(Q\) ».
Par exemple :
- « \(0 \leq x \leq 25 \Rightarrow \sqrt{x} \leq 5\) » est vraie (prendre la racine carrée).
- « \(x \in ]-\infty, -4[ \Rightarrow x^2 + 3x - 4 > 0\) » est vraie (étudier le binôme).
- « \(\sin(\theta) = 0 \Rightarrow \theta = 0\) » est fausse (regarder pour \(\theta = 2\pi\) par exemple).
- « \(2 + 2 = 5 \Rightarrow \sqrt{2} = 2\) » est vraie ! Eh oui, si \(P\) est fausse alors l'assertion « \(P \Rightarrow Q\) » est toujours vraie.
2.5. L'équivalence \(\Leftrightarrow\)
On dira « \(P\) est équivalent à \(Q\) » ou « \(P\) équivaut à \(Q\) » ou « \(P\) si et seulement si \(Q\) ». Cette proposition est vraie lorsque \(P\) et \(Q\) sont vraies ou lorsque \(P\) et \(Q\) sont fausses. La table de vérité est :
| P | Q | P ⇔ Q |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Exemples :
- Pour \(x, x' \in \RR\), l'équivalence « \(x \cdot x' = 0 \Leftrightarrow (x = 0 \text{ ou } x' = 0)\) » est vraie.
- Voici une équivalence toujours fausse (quelle que soit la proposition \(P\)) : « \(P \Leftrightarrow \text{non}(P)\) ».
3. Loi logique ou tautologie
Proposition 1 — Lois logiques usuelles
Soient \(P, Q, R\) trois propositions. Nous avons les équivalences (vraies) suivantes :
- \(P \Leftrightarrow \text{non}(\text{non}(P))\)
- \((P \text{ et } Q) \Leftrightarrow (Q \text{ et } P)\) — commutativité de « et »
- \((P \text{ ou } Q) \Leftrightarrow (Q \text{ ou } P)\) — commutativité de « ou »
- \(\text{non}(P \text{ et } Q) \Leftrightarrow (\text{non } P) \text{ ou } (\text{non } Q)\) — 1re loi de De Morgan
- \(\text{non}(P \text{ ou } Q) \Leftrightarrow (\text{non } P) \text{ et } (\text{non } Q)\) — 2e loi de De Morgan
- \(P \text{ et } (Q \text{ ou } R) \Leftrightarrow (P \text{ et } Q) \text{ ou } (P \text{ et } R)\) — distributivité
- \(P \text{ ou } (Q \text{ et } R) \Leftrightarrow (P \text{ ou } Q) \text{ et } (P \text{ ou } R)\) — distributivité
- « \(P \Rightarrow Q\) » \(\Leftrightarrow\) « \(\text{non}(Q) \Rightarrow \text{non}(P)\) » — contraposition
On compare les deux propositions « \(\text{non}(P \text{ et } Q)\) » et « \((\text{non } P) \text{ ou } (\text{non } Q)\) » pour toutes les valeurs possibles de \(P\) et \(Q\). Par exemple si \(P\) est vraie et \(Q\) est vraie, alors « \(P\) et \(Q\) » est vraie donc « \(\text{non}(P \text{ et } Q)\) » est fausse ; d'autre part \(\text{non } P\) est fausse, \(\text{non } Q\) est fausse donc « \((\text{non } P) \text{ ou } (\text{non } Q)\) » est fausse. Ainsi dans ce cas les deux propositions sont fausses. On dresse ainsi les deux tables de vérité : comme elles sont identiques, les deux propositions sont équivalentes.
| P | Q | non(P et Q) | (non P) ou (non Q) |
|---|---|---|---|
| 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 |
Par définition, l'implication « \(P \Rightarrow Q\) » est la proposition « \((\text{non } P) \text{ ou } Q\) ». Donc l'implication « \(\text{non}(Q) \Rightarrow \text{non}(P)\) » est équivalente à « \(\text{non}(\text{non}(Q)) \text{ ou } \text{non}(P)\) » qui équivaut encore à « \(Q \text{ ou } \text{non}(P)\) », et donc est équivalente à « \(P \Rightarrow Q\) ».
4. Quantificateurs et fonction propositionnelle
Si une proposition \(P\) dépend d'un paramètre \(x\), on l'appelle fonction propositionnelle.
4.1. Définition
4.2. Le quantificateur \(\forall\) : « pour tout »
Exemples :
- « \(\forall x \in [1 ; +\infty[\,: x^2 \geq 1\) » est une proposition vraie.
- « \(\forall x \in \RR\,: x^2 \geq 1\) » est une proposition fausse.
- « \(\forall n \in \NN\,: n(n+1) \text{ est divisible par } 2\) » est vraie.
4.3. Le quantificateur \(\exists\) : « il existe »
Exemples :
- « \(\exists x \in \RR\,: x(x-1) < 0\) » est vraie (par exemple \(x = \tfrac{1}{2}\) vérifie bien la propriété).
- « \(\exists n \in \NN\,: n^2 - n \geq n\) » est vraie (il y a plein de choix : \(n = 3\) convient, mais aussi \(n = 10\), ou même \(n = 100\) ; un seul suffit pour dire que la proposition est vraie).
- « \(\exists x \in \RR\,: x^2 = -1\) » est fausse (aucun réel au carré ne donnera un nombre négatif).
4.4. La négation des quantificateurs
Par exemple la négation de « \(\forall x \in [1, +\infty[\,: x^2 \geq 1\) » est la proposition « \(\exists x \in [1, +\infty[\,: x^2 < 1\) ». En effet la négation de \(x^2 \geq 1\) est \(\text{non}(x^2 \geq 1)\) mais s'écrit plus simplement \(x^2 < 1\).
Voici des exemples :
- La négation de « \(\exists z \in \mathbb{C}\,: z^2 + z + 1 = 0\) » est « \(\forall z \in \mathbb{C}\,: z^2 + z + 1 \neq 0\) ».
- La négation de « \(\forall x \in \RR\,: x + 1 \in \ZZ\) » est « \(\exists x \in \RR\,: x + 1 \notin \ZZ\) ».
- Pour l'assertion complexe : \[ \forall x \in \RR \quad \exists y > 0 \quad (x + y > 10) \] sa négation est \[ \exists x \in \RR \quad \forall y > 0 \quad (x + y \leq 10). \]
4.5. Remarques
L'ordre des quantificateurs est très important. Les deux phrases logiques
\[ \forall x \in \RR \quad \exists y \in \RR \quad (x + y > 0) \qquad \text{et} \qquad \exists y \in \RR \quad \forall x \in \RR \quad (x + y > 0) \]sont différentes. La première est vraie : elle se lit « Pour tout réel \(x\), il existe un réel \(y\) (qui peut dépendre de \(x\)) tel que \(x + y > 0\) » — prendre par exemple \(y = |x| + 1\). La seconde est fausse : elle se lit « Il existe un réel \(y\) tel que, pour tout réel \(x\), \(x + y > 0\) ». Cela ne peut pas être le même \(y\) qui convient pour tous les \(x\) !
En français : la phrase « Pour toute personne, il existe un numéro de téléphone » est vraie (le numéro dépend de la personne), tandis que « Il existe un numéro pour toutes les personnes » est fausse (ce serait le même numéro pour tout le monde).
Quand on écrit « \(\exists x \in \RR\,: f(x) = 0\) » cela signifie qu'il existe au moins un réel pour lequel \(f\) s'annule. Rien ne dit que ce \(x\) est unique. Afin de préciser que \(f\) s'annule en une unique valeur, on rajoute un point d'exclamation :
\[ \exists!\, x \in \RR \quad f(x) = 0. \]5. Raisonnements
Voici des méthodes classiques de raisonnements.
5.1. Raisonnement direct
On veut montrer que la proposition « \(P \Rightarrow Q\) » est vraie. On suppose que \(P\) est vraie et on montre qu'alors \(Q\) est vraie. C'est la méthode à laquelle vous êtes le plus habitué.
Soient \(x \in \RR^*_+\) et \(y \in \RR^*_+\) tels que \(0 < x < 2\) et \(0 < y < 2\). Montrer que :
\[ \begin{cases} 0 < x < 2 \\ 0 < y < 2 \end{cases} \;\Rightarrow\; \frac{1}{x} + \frac{1}{y} > 1. \]Supposons \(0 < x < 2\) et \(0 < y < 2\). Alors
\[ \begin{cases} x < 2 \;\Rightarrow\; \dfrac{1}{x} > \dfrac{1}{2} \\[6pt] y < 2 \;\Rightarrow\; \dfrac{1}{y} > \dfrac{1}{2} \end{cases} \]En sommant membre à membre ces deux inégalités (toutes deux strictes dans le même sens) :
\[ \frac{1}{x} + \frac{1}{y} > \frac{1}{2} + \frac{1}{2} = 1. \]D'où le résultat.
5.2. Raisonnement par disjonction des cas
Si l'on souhaite vérifier une proposition \(P(x)\) pour tous les \(x\) dans un ensemble \(E\), on montre la proposition pour les \(x\) dans une partie \(A\) de \(E\), puis pour les \(x\) n'appartenant pas à \(A\). C'est la méthode de disjonction des cas (ou méthode cas par cas).
Montrer que : \(\forall x \in \RR,\; |x - 1| \leq x^2 - x + 1\).
Soit \(x \in \RR\). Nous distinguons deux cas.
Premier cas : \(x \geq 1\). Alors \(|x-1| = x-1\), et
\[ \begin{aligned} (x^2 - x + 1) - (x - 1) &= x^2 - 2x + 2 \\ &= (x - 1)^2 + 1 \geq 0. \end{aligned} \]Ainsi \(x^2 - x + 1 \geq |x-1|\).
Deuxième cas : \(x < 1\). Alors \(|x-1| = -(x-1) = 1-x\), et
\[ (x^2 - x + 1) + (x - 1) = x^2 \geq 0. \]Donc \(x^2 - x + 1 \geq |x-1|\).
Conclusion. Dans tous les cas, \(x^2 - x + 1 \geq |x-1|\), c'est-à-dire \(|x-1| \leq x^2 - x + 1\).
Montrer que \(n(n+1)(n+2)\) est un multiple de \(3\) pour tout \(n \in \NN\).
Soit \(n \in \NN\). Il y a trois cas possibles pour \(n\) selon son reste modulo \(3\) :
\[ n = 3k \quad \text{ou} \quad n = 3k+1 \quad \text{ou} \quad n = 3k+2 \qquad (k \in \NN). \]1er cas : \(n = 3k\).
\[ n(n+1)(n+2) = 3k(3k+1)(3k+2) = 3k' \quad \text{avec} \quad k' = k(3k+1)(3k+2). \]Donc \(n(n+1)(n+2)\) est un multiple de \(3\).
2e cas : \(n = 3k+1\).
\[ n(n+1)(n+2) = (3k+1)(3k+2)(3k+3) = 3(3k+1)(3k+2)(k+1) = 3k'. \]Donc \(n(n+1)(n+2)\) est un multiple de \(3\).
3e cas : \(n = 3k+2\).
\[ n(n+1)(n+2) = (3k+2)(3k+3)(3k+4) = 3(3k+2)(k+1)(3k+4) = 3k'. \]Donc \(n(n+1)(n+2)\) est un multiple de \(3\).
Conclusion. \(\forall n \in \NN\), \(n(n+1)(n+2)\) est un multiple de \(3\).
5.3. Raisonnement par contraposition
Le raisonnement par contraposition est basé sur l'équivalence suivante (voir Proposition 1, point 8) :
Donc, si l'on souhaite montrer la proposition « \(P \Rightarrow Q\) », on montre en fait que \(\text{non}(Q) \Rightarrow \text{non}(P)\) est vraie.
Soit \(x \in \RR\) avec \(x \neq -5\). Montrer que :
\[ x \neq -8 \;\Rightarrow\; \frac{x+2}{x+5} \neq 2. \]Montrons la contraposée :
\[ \frac{x+2}{x+5} = 2 \;\Rightarrow\; x = -8. \]On a :
\[ \begin{aligned} \frac{x+2}{x+5} = 2 &\Rightarrow x + 2 = 2(x+5) \\ &\Rightarrow x + 2 = 2x + 10 \\ &\Rightarrow x = -8. \end{aligned} \]Conclusion : par contraposition, \(x \neq -8 \Rightarrow \dfrac{x+2}{x+5} \neq 2\).
5.4. Raisonnement par l'absurde
Le raisonnement par l'absurde repose sur le principe suivant : pour montrer « \(P \Rightarrow Q\) », on suppose à la fois que \(P\) est vraie et que \(Q\) est fausse, et on cherche une contradiction. Ainsi si \(P\) est vraie alors \(Q\) doit être vraie, et donc « \(P \Rightarrow Q\) » est vraie.
Soient \(a > 0\) et \(b > 0\). Montrer que si \(\dfrac{a}{1+b} = \dfrac{b}{1+a}\) alors \(a = b\).
Nous raisonnons par l'absurde en supposant que \(\dfrac{a}{1+b} = \dfrac{b}{1+a}\) et \(a \neq b\).
Comme \(\dfrac{a}{1+b} = \dfrac{b}{1+a}\), alors \(a(1+a) = b(1+b)\), donc \(a + a^2 = b + b^2\), d'où \(a^2 - b^2 = b - a\). Cela conduit à
\[ (a-b)(a+b) = -(a-b). \]Comme \(a \neq b\), on a \(a - b \neq 0\) : en divisant par \(a-b\), on obtient \(a + b = -1\). Or la somme des deux nombres positifs \(a\) et \(b\) ne peut être négative. Nous obtenons une contradiction.
Conclusion : si \(\dfrac{a}{1+b} = \dfrac{b}{1+a}\) alors \(a = b\).
5.5. Raisonnement par contre-exemple
Si l'on veut montrer qu'une proposition du type « \(\forall x \in E \quad P(x)\) » est vraie, alors pour chaque \(x\) de \(E\) il faut montrer que \(P(x)\) est vraie. Par contre, pour montrer qu'elle est fausse, il suffit de trouver un \(x \in E\) tel que \(P(x)\) soit fausse. Trouver un tel \(x\), c'est trouver un contre-exemple à la proposition « \(\forall x \in E \quad P(x)\) ».
Montrer que la proposition \[ P : \quad (\forall x \in [0 ; 1]) \quad x^2 \geq x \] est fausse.
Sa négation est :
\[ \overline{P} : \quad (\exists x \in [0 ; 1]) \quad x^2 < x. \]En posant \(x = \dfrac{1}{2}\), on a \(\left(\dfrac{1}{2}\right)^2 = \dfrac{1}{4} < \dfrac{1}{2}\). Donc \(\overline{P}\) est vraie, et par conséquent \(P\) est fausse. Le réel \(x = \tfrac{1}{2}\) est un contre-exemple à \(P\).
5.6. Raisonnement par équivalence
Le raisonnement par équivalence repose sur le principe suivant : pour montrer qu'une proposition \(P\) est vraie, on montre que « \(P \Leftrightarrow Q\) » est vraie et que \(Q\) est vraie ; on en déduit alors que \(P\) est vraie.
Montrer que : \(\forall x > 0,\quad x + \dfrac{1}{x} \geq 2\).
Pour \(x > 0\), on a :
\[ \begin{aligned} x + \frac{1}{x} \geq 2 &\iff \frac{x^2 + 1}{x} \geq 2 \\[4pt] &\iff \frac{x^2 + 1}{x} - 2 \geq 0 \\[4pt] &\iff \frac{x^2 + 1 - 2x}{x} \geq 0 \\[4pt] &\iff \frac{(x-1)^2}{x} \geq 0. \end{aligned} \]Or \((x-1)^2 \geq 0\) et \(x > 0\), donc le quotient \(\dfrac{(x-1)^2}{x}\) est positif ou nul. Par équivalence, on conclut :
\[ \forall x > 0, \quad x + \frac{1}{x} \geq 2. \]5.7. Raisonnement par récurrence
Le principe de récurrence permet de montrer qu'une proposition \(P(n)\), dépendant de \(n\), est vraie pour tout \(n \in \NN\). La démonstration par récurrence se déroule en trois étapes :
- Initialisation. On prouve que \(P(0)\) est vraie.
- Hérédité. On suppose \(n \geq 0\) donné avec \(P(n)\) vraie (hypothèse de récurrence).
- Conclusion. On démontre que la proposition \(P(n+1)\) au rang suivant est vraie, puis on conclut que \(P(n)\) est vraie pour tout \(n \in \NN\).
Montrer que : \(\forall n \in \NN,\; n^3 + 2n\) est divisible par \(3\).
Il s'agit de montrer qu'il existe \(k \in \NN\) tel que \(n^3 + 2n = 3k\). Notons \(P(n)\) cette propriété.
1re étape — Initialisation. Pour \(n = 0\), on a
\[ 0^3 + 2 \times 0 = 0 = 3 \times 0, \]donc \(P(0)\) est vraie.
2e étape — Hérédité. Supposons que \(P(n)\) soit vraie, c'est-à-dire qu'il existe \(k \in \NN\) tel que \(n^3 + 2n = 3k\).
3e étape. Nous allons montrer que \(P(n+1)\) est vraie, c'est-à-dire qu'il existe \(k' \in \NN\) tel que \((n+1)^3 + 2(n+1) = 3k'\). Calculons :
\[ \begin{aligned} (n+1)^3 + 2(n+1) &= n^3 + 3n^2 + 3n + 1 + 2n + 2 \\ &= (n^3 + 2n) + 3n^2 + 3n + 3 \\ &= 3k + 3(n^2 + n + 1) \\ &= 3\bigl(k + n^2 + n + 1\bigr) \\ &= 3k' \quad \text{avec } k' = k + n^2 + n + 1 \in \NN. \end{aligned} \]Donc \(P(n+1)\) est vraie.
Conclusion. Par le principe de récurrence, on a : \[ \forall n \in \NN, \quad n^3 + 2n \text{ est divisible par } 3. \]
Pour comprendre ce principe, imaginons une file de dominos :
- Si l'on pousse le premier domino de la file (c'est l'initialisation),
- et si les dominos sont posés l'un après l'autre de manière à ce que la chute d'un domino entraîne la chute de son suivant (c'est l'hérédité),
- alors tous les dominos de la file tombent (c'est la conclusion).
À retenir
- Une proposition est une phrase vraie ou fausse, jamais les deux. Les connecteurs « et », « ou », « non », « \(\Rightarrow\) », « \(\Leftrightarrow\) » se manipulent avec des tables de vérité (voir §2.1 à §2.5).
- Une loi logique (ou tautologie) est toujours vraie, quelles que soient les valeurs de vérité des propositions qui la composent. Les huit lois usuelles sont rassemblées dans la Proposition 1.
- Les lois de De Morgan : \(\text{non}(P \text{ et } Q) \Leftrightarrow (\text{non } P) \text{ ou } (\text{non } Q)\) et \(\text{non}(P \text{ ou } Q) \Leftrightarrow (\text{non } P) \text{ et } (\text{non } Q)\).
- Contraposition : \((P \Rightarrow Q) \Leftrightarrow (\text{non } Q \Rightarrow \text{non } P)\).
- Négation des quantificateurs (voir §4.4) : on échange \(\forall\) et \(\exists\), puis on nie la proposition intérieure.
- L'ordre des quantificateurs est crucial : \(\forall x\, \exists y\, P(x,y)\) n'est pas la même chose que \(\exists y\, \forall x\, P(x,y)\).
- Sept schémas de raisonnement à maîtriser : direct (§5.1), disjonction des cas (§5.2), contraposition (§5.3), absurde (§5.4), contre-exemple (§5.5), équivalence (§5.6), récurrence (§5.7).
Leave a comment