BURHAN.

Notions de logique : Résumé de cours de Mathématiques 1BAC Sciences Mathématiques

Notions de logique : résumé de maths 1BAC SM, avec les points essentiels, les formules et les méthodes à retenir pour réviser avant un contrôle. Pour les élèves de 1BAC Sciences Mathématiques, option française (BIOF).

Propositions et connecteurs

À retenirLe réflexe : vrai ou faux, sans ambiguïté

Une proposition a une seule valeur de vérité : V ou F. « 2+3=52 + 3 = 5 » est vraie ; « 77 est pair » est fausse. En revanche, « x>3x > 3 » n'est pas une proposition tant que xx n'est pas fixé : sa valeur dépend de xx.

DéfinitionProposition ; négation

Une proposition est un énoncé mathématique qui est soit vrai, soit faux, jamais les deux à la fois. Sa valeur de vérité est V (vraie) ou F (fausse).

La négation d'une proposition PP est la proposition notée P‾\overline{P}, lue « non PP ». Elle est vraie lorsque PP est fausse, et fausse lorsque PP est vraie.

DéfinitionConjonction et disjonction

Soit PP et QQ deux propositions.

  • La conjonction (P et Q)(P \text{ et } Q) est vraie lorsque PP et QQ sont vraies toutes les deux ; elle est fausse dans les trois autres cas.
  • La disjonction (P ou Q)(P \text{ ou } Q) est vraie lorsque l'une au moins des propositions PP, QQ est vraie ; elle est fausse seulement lorsque PP et QQ sont fausses toutes les deux. Le « ou » mathématique est inclusif.

DéfinitionImplication et équivalence

Soit PP et QQ deux propositions.

  • L'implication (P⇒Q)(P \Rightarrow Q), lue « PP implique QQ », est fausse seulement lorsque PP est vraie et QQ est fausse ; elle est vraie dans les trois autres cas. L'implication (Q⇒P)(Q \Rightarrow P) est sa réciproque.
  • L'équivalence (P⇔Q)(P \Leftrightarrow Q), lue « PP si et seulement si QQ », est vraie lorsque PP et QQ ont la même valeur de vérité, et fausse sinon.

En particulier, si PP est vraie et si (P⇒Q)(P \Rightarrow Q) est vraie, alors QQ est vraie.

Une loi logique est une proposition composée qui est vraie quelles que soient les valeurs de vérité des propositions qui la composent.

À retenirTable de vérité des connecteurs

Chaque connecteur se lit sur ses valeurs de vérité. Une ligne par cas, dans l'ordre VV, VF, FV, FF.

PP QQ P‾\overline{P} (P et Q)(P \text{ et } Q) (P ou Q)(P \text{ ou } Q) (P⇒Q)(P \Rightarrow Q) (P⇔Q)(P \Leftrightarrow Q)
V V F V V V V
V F F F V F F
F V V F V V F
F F V F F V V

Remarque

Deux points surprennent au début. Le « ou » est inclusif : (P ou Q)(P \text{ ou } Q) reste vraie quand PP et QQ sont vraies toutes les deux. L'implication (P⇒Q)(P \Rightarrow Q) n'est fausse que sur la ligne VF ; si PP est fausse, elle est vraie.

Exemple

Énoncé. On pose PP : « 1212 est un multiple de 44 » et QQ : « 1515 est pair ». Donne la valeur de vérité de (P et Q)(P \text{ et } Q), (P ou Q)(P \text{ ou } Q), (P⇒Q)(P \Rightarrow Q) et (Q⇒P)(Q \Rightarrow P).

Valeurs. 12=4×312 = 4 \times 3, donc PP est vraie. 15=2×7+115 = 2 \times 7 + 1 est impair, donc QQ est fausse.

Lecture. On lit la ligne VF : (P et Q)(P \text{ et } Q) est fausse, (P ou Q)(P \text{ ou } Q) est vraie, (P⇒Q)(P \Rightarrow Q) est fausse. Enfin QQ est fausse, donc (Q⇒P)(Q \Rightarrow P) est vraie.

Lois logiques : négation, contraposée, double implication

PropriétéDouble négation et lois de Morgan

Pour toutes propositions PP et QQ, les propositions suivantes sont des lois logiques :

  • P‾‾⇔P\overline{\overline{P}} \Leftrightarrow P ;
  • (P et Q)‾⇔(P‾ ou Q‾)\overline{(P \text{ et } Q)} \Leftrightarrow (\overline{P} \text{ ou } \overline{Q}) ;
  • (P ou Q)‾⇔(P‾ et Q‾)\overline{(P \text{ ou } Q)} \Leftrightarrow (\overline{P} \text{ et } \overline{Q}).

PropriétéImplication : écriture, négation et contraposée

Pour toutes propositions PP et QQ, les propositions suivantes sont des lois logiques :

  • (P⇒Q)⇔(P‾ ou Q)(P \Rightarrow Q) \Leftrightarrow (\overline{P} \text{ ou } Q) ;
  • (P⇒Q)‾⇔(P et Q‾)\overline{(P \Rightarrow Q)} \Leftrightarrow (P \text{ et } \overline{Q}) ;
  • (P⇒Q)⇔(Q‾⇒P‾)(P \Rightarrow Q) \Leftrightarrow (\overline{Q} \Rightarrow \overline{P}).

L'implication (Q‾⇒P‾)(\overline{Q} \Rightarrow \overline{P}) est la contraposée de l'implication (P⇒Q)(P \Rightarrow Q).

PropriétéDouble implication et transitivité

Pour toutes propositions PP, QQ et RR, les propositions suivantes sont des lois logiques :

  • (P⇔Q)⇔((P⇒Q) et (Q⇒P))(P \Leftrightarrow Q) \Leftrightarrow \big((P \Rightarrow Q) \text{ et } (Q \Rightarrow P)\big) ;
  • ((P⇒Q) et (Q⇒R))⇒(P⇒R)\big((P \Rightarrow Q) \text{ et } (Q \Rightarrow R)\big) \Rightarrow (P \Rightarrow R) ;
  • ((P⇔Q) et (Q⇔R))⇒(P⇔R)\big((P \Leftrightarrow Q) \text{ et } (Q \Leftrightarrow R)\big) \Rightarrow (P \Leftrightarrow R).
Double négation
P‾‾⇔P\overline{\overline{P}} \Leftrightarrow P
Négation de « et »
(P et Q)‾⇔(P‾ ou Q‾)\overline{(P \text{ et } Q)} \Leftrightarrow (\overline{P} \text{ ou } \overline{Q})
Négation de « ou »
(P ou Q)‾⇔(P‾ et Q‾)\overline{(P \text{ ou } Q)} \Leftrightarrow (\overline{P} \text{ et } \overline{Q})
Implication réécrite
(P⇒Q)⇔(P‾ ou Q)(P \Rightarrow Q) \Leftrightarrow (\overline{P} \text{ ou } Q)
Négation d'une implication
(P⇒Q)‾⇔(P et Q‾)\overline{(P \Rightarrow Q)} \Leftrightarrow (P \text{ et } \overline{Q})
Contraposée
(P⇒Q)⇔(Q‾⇒P‾)(P \Rightarrow Q) \Leftrightarrow (\overline{Q} \Rightarrow \overline{P})
Double implication
(P⇔Q)⇔((P⇒Q) et (Q⇒P))(P \Leftrightarrow Q) \Leftrightarrow \big((P \Rightarrow Q) \text{ et } (Q \Rightarrow P)\big)

AttentionNier « et » donne « ou »

La négation de (P et Q)(P \text{ et } Q) est (P‾ ou Q‾)(\overline{P} \text{ ou } \overline{Q}). Écrire (P‾ et Q‾)(\overline{P} \text{ et } \overline{Q}) est faux. Avec PP vraie et QQ fausse, (P et Q)(P \text{ et } Q) est fausse, donc sa négation est vraie ; or (P‾ et Q‾)(\overline{P} \text{ et } \overline{Q}) est fausse. De même, nier « pour tout » donne « il existe », jamais « pour aucun ».

AttentionLa réciproque n'est pas la contraposée

La contraposée (Q‾⇒P‾)(\overline{Q} \Rightarrow \overline{P}) a toujours la même valeur que (P⇒Q)(P \Rightarrow Q). La réciproque (Q⇒P)(Q \Rightarrow P), non : sur la ligne FV, (P⇒Q)(P \Rightarrow Q) est vraie et (Q⇒P)(Q \Rightarrow P) est fausse. Démontrer la réciproque ne démontre donc pas l'implication.

Exemple

Énoncé. Soit xx un réel. On considère l'implication « si x<−1x < -1, alors x2>1x^{2} > 1 ». Écris sa négation, sa contraposée et sa réciproque.

Négation (F05) : « x<−1x < -1 et x2≤1x^{2} \leq 1 ».

Contraposée (F05) : « si x2≤1x^{2} \leq 1, alors x≥−1x \geq -1 ».

Réciproque : « si x2>1x^{2} > 1, alors x<−1x < -1 ». Elle est fausse pour x=2x = 2 : 22=4>12^{2} = 4 > 1, mais 2≥−12 \geq -1.

À retenirVérifier une loi logique

Une loi logique est vraie dans tous les cas. Pour la vérifier, examine les quatre lignes VV, VF, FV, FF ; il y en a huit avec trois propositions. Une seule ligne fausse suffit : ce n'est alors pas une loi logique.

Quantificateurs et négation

À retenirLire et écrire une proposition quantifiée

Écris dans l'ordre le quantificateur, la variable, l'ensemble, une virgule, puis la propriété : ∀x∈R, x2+1>0\forall x \in \mathbb{R},\ x^{2} + 1 > 0. La variable est muette : ∀t∈R, t2+1>0\forall t \in \mathbb{R},\ t^{2} + 1 > 0 dit la même chose. L'ensemble compte : ∃n∈Z, 3n=7\exists n \in \mathbb{Z},\ 3n = 7 est fausse, mais ∃x∈Q, 3x=7\exists x \in \mathbb{Q},\ 3x = 7 est vraie.

DéfinitionFonction propositionnelle ; quantificateurs

Soit EE un ensemble. Une fonction propositionnelle P(x)P(x) de la variable xx de EE est un énoncé qui devient une proposition chaque fois que l'on remplace xx par un élément de EE.

  • La proposition (∀x∈E, P(x))(\forall x \in E,\ P(x)), lue « pour tout xx de EE, P(x)P(x) », est vraie lorsque P(x)P(x) est vraie pour chaque élément xx de EE. Le symbole ∀\forall est le quantificateur universel.
  • La proposition (∃x∈E, P(x))(\exists x \in E,\ P(x)), lue « il existe au moins un xx de EE tel que P(x)P(x) », est vraie lorsque P(x)P(x) est vraie pour au moins un élément xx de EE. Le symbole ∃\exists est le quantificateur existentiel.
  • La proposition (∃!x∈E, P(x))(\exists! x \in E,\ P(x)), lue « il existe un unique xx de EE tel que P(x)P(x) », est vraie lorsque P(x)P(x) est vraie pour exactement un élément xx de EE.

PropriétéNégation d'une proposition quantifiée

Soit EE un ensemble et P(x)P(x) une fonction propositionnelle de la variable xx de EE. Les propositions suivantes sont des lois logiques :

  • (∀x∈E, P(x))‾⇔(∃x∈E, P(x)‾)\overline{(\forall x \in E,\ P(x))} \Leftrightarrow (\exists x \in E,\ \overline{P(x)}) ;
  • (∃x∈E, P(x))‾⇔(∀x∈E, P(x)‾)\overline{(\exists x \in E,\ P(x))} \Leftrightarrow (\forall x \in E,\ \overline{P(x)}).

En particulier, s'il existe un élément x0x_0 de EE tel que P(x0)P(x_0) soit fausse, alors la proposition (∀x∈E, P(x))(\forall x \in E,\ P(x)) est fausse : l'élément x0x_0 est un contre-exemple.

Nier « pour tout »
(∀x∈E, P(x))‾⇔(∃x∈E, P(x)‾)\overline{(\forall x \in E,\ P(x))} \Leftrightarrow (\exists x \in E,\ \overline{P(x)})
Nier « il existe »
(∃x∈E, P(x))‾⇔(∀x∈E, P(x)‾)\overline{(\exists x \in E,\ P(x))} \Leftrightarrow (\forall x \in E,\ \overline{P(x)})
Nier une implication quantifiée
(∀x∈E, (P(x)⇒Q(x)))‾⇔(∃x∈E, (P(x) et Q(x)‾))\overline{\big(\forall x \in E,\ (P(x) \Rightarrow Q(x))\big)} \Leftrightarrow \big(\exists x \in E,\ (P(x) \text{ et } \overline{Q(x)})\big)
Nier deux quantificateurs
(∀x∈E, ∃y∈E, P(x,y))‾⇔(∃x∈E, ∀y∈E, P(x,y)‾)\overline{(\forall x \in E,\ \exists y \in E,\ P(x, y))} \Leftrightarrow (\exists x \in E,\ \forall y \in E,\ \overline{P(x, y)})

Méthodenier une proposition

  1. Lis la structure : d'abord les quantificateurs, dans l'ordre, puis les connecteurs.
  2. Remplace chaque ∀\forall par ∃\exists et chaque ∃\exists par ∀\forall ; garde l'ordre et les ensembles (F08).
  3. Nie la propriété finale : « et » devient « ou », « ou » devient « et » (F04), et (P⇒Q)(P \Rightarrow Q) devient (P et Q‾)(P \text{ et } \overline{Q}) (F05).
  4. Contrôle : si l'une est vraie, l'autre est fausse, et inversement.

Exemple

Énoncé. Nie la proposition ∀x∈R, ∃n∈N, n>x\forall x \in \mathbb{R},\ \exists n \in \mathbb{N},\ n > x.

Quantificateurs. ∀x\forall x devient ∃x\exists x, puis ∃n\exists n devient ∀n\forall n, dans le même ordre.

Propriété. La négation de n>xn > x est n≤xn \leq x.

Résultat. ∃x∈R, ∀n∈N, n≤x\exists x \in \mathbb{R},\ \forall n \in \mathbb{N},\ n \leq x.

Méthoderéfuter par un contre-exemple

  1. Écris ce qu'il faut montrer : ∃x0∈E, P(x0)‾\exists x_0 \in E,\ \overline{P(x_0)} (F08).
  2. Cherche x0x_0 parmi des valeurs simples : 00, 11, −1-1, un entier négatif, une fraction.
  3. Calcule pour établir que P(x0)P(x_0) est fausse, puis conclus : la proposition universelle est fausse.

Exemple

Énoncé. La proposition « pour tout entier naturel nn, si nn est un multiple de 44, alors nn est un multiple de 88 » est-elle vraie ?

Contre-exemple. Prenons n=12n = 12. C'est un multiple de 44, car 12=4×312 = 4 \times 3. Ce n'est pas un multiple de 88, car 8×1<12<8×28 \times 1 < 12 < 8 \times 2.

Conclusion. La proposition est fausse.

AttentionDes exemples ne prouvent pas un « pour tout »

Tester P(x)P(x) pour cinq valeurs, ou pour mille, ne démontre pas ∀x∈E, P(x)\forall x \in E,\ P(x). Il faut un argument valable pour un xx quelconque, introduit par « Soit x∈Ex \in E ». À l'inverse, un seul contre-exemple suffit pour réfuter.

L'ordre des quantificateurs

PropriétéOrdre des quantificateurs

Soit EE un ensemble et P(x,y)P(x, y) une fonction propositionnelle des variables xx et yy de EE : elle devient une proposition chaque fois que l'on remplace xx et yy par des éléments de EE.

  • Deux quantificateurs de même nature s'échangent : (∀x∈E, ∀y∈E, P(x,y))⇔(∀y∈E, ∀x∈E, P(x,y))(\forall x \in E,\ \forall y \in E,\ P(x, y)) \Leftrightarrow (\forall y \in E,\ \forall x \in E,\ P(x, y)), et de même avec deux quantificateurs ∃\exists.
  • (∃y∈E, ∀x∈E, P(x,y))⇒(∀x∈E, ∃y∈E, P(x,y))(\exists y \in E,\ \forall x \in E,\ P(x, y)) \Rightarrow (\forall x \in E,\ \exists y \in E,\ P(x, y)).
  • La réciproque de cette dernière implication est fausse en général : on n'échange pas un quantificateur ∀\forall et un quantificateur ∃\exists.

Exemple

Énoncé. Compare ∀x∈R, ∃y∈R, x+2y=1\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ x + 2y = 1 et ∃y∈R, ∀x∈R, x+2y=1\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ x + 2y = 1.

Première. Soit x∈Rx \in \mathbb{R}. Le réel y=1−x2y = \dfrac{1 - x}{2} convient : elle est vraie. Ici, yy dépend de xx.

Seconde. Soit y∈Ry \in \mathbb{R}. Pour x=−2yx = -2y, on a x+2y=0≠1x + 2y = 0 \neq 1. Aucun yy ne convient pour tous les xx : elle est fausse.

AttentionNe permute pas un pour tout et un il existe

Dans ∀x, ∃y\forall x,\ \exists y, tu choisis yy après xx : il peut changer avec xx. Dans ∃y, ∀x\exists y,\ \forall x, un seul yy doit servir pour tous les xx. Échanger deux quantificateurs de natures différentes change le sens (F09).

Démontrer une implication : directement ou par contraposée

Méthoderaisonnement direct

  1. Introduis les objets et l'hypothèse : « Soit x∈Ex \in E. Supposons P(x)P(x). »
  2. Déduis pas à pas ; chaque pas cite une hypothèse, un calcul ou un résultat.
  3. Termine par « donc Q(x)Q(x) » : l'implication est démontrée pour tout xx.

Exemple

Énoncé. Montre que, pour tout réel xx, si x>3x > 3, alors x2−3x>0x^{2} - 3x > 0.

Rédaction. Soit xx un réel tel que x>3x > 3. On écrit x2−3x=x(x−3)x^{2} - 3x = x(x - 3). Par hypothèse, x>3>0x > 3 > 0 et x−3>0x - 3 > 0. Un produit de deux réels strictement positifs est strictement positif, donc x2−3x>0x^{2} - 3x > 0.

Méthoderaisonnement par contraposée

  1. Annonce : « Raisonnons par contraposée » (F05).
  2. Écris Q‾\overline{Q} et P‾\overline{P} en clair, sans barre.
  3. Démontre directement (Q‾⇒P‾)(\overline{Q} \Rightarrow \overline{P}).
  4. Conclus : par contraposée, (P⇒Q)(P \Rightarrow Q) est vraie.

Exemple

Énoncé. Soit nn un entier. Montre que si 3n+13n + 1 est impair, alors nn est pair.

Annonce. Raisonnons par contraposée : montrons que si nn est impair, alors 3n+13n + 1 est pair.

Rédaction. Supposons nn impair : il existe k∈Zk \in \mathbb{Z} tel que n=2k+1n = 2k + 1. Alors 3n+1=6k+4=2(3k+2)3n + 1 = 6k + 4 = 2(3k + 2), avec 3k+2∈Z3k + 2 \in \mathbb{Z}. Donc 3n+13n + 1 est pair, et l'implication est démontrée par contraposée.

À retenirQuand choisir la contraposée

Pense à la contraposée quand la conclusion est une négation : « nn n'est pas… », « x≠ax \neq a ». Alors Q‾\overline{Q} devient une égalité ou une écriture explicite. C'est une hypothèse plus facile à utiliser.

Démontrer une équivalence

Méthodedémontrer une équivalence

  1. Double implication : démontre (P⇒Q)(P \Rightarrow Q), puis (Q⇒P)(Q \Rightarrow P), en deux parties titrées (F06).
  2. Équivalences successives : enchaîne P⇔P1⇔⋯⇔QP \Leftrightarrow P_1 \Leftrightarrow \dots \Leftrightarrow Q. À chaque pas, vérifie que l'on peut revenir en arrière.
  3. Conclus par transitivité de l'équivalence (F06).

Exemple

Énoncé. Résous dans R\mathbb{R} l'inéquation ∣2x−3∣≤5\lvert 2x - 3 \rvert \leq 5.

Équivalences. Pour tout réel xx : ∣2x−3∣≤5⇔−5≤2x−3≤5⇔−2≤2x≤8⇔−1≤x≤4.\lvert 2x - 3 \rvert \leq 5 \Leftrightarrow -5 \leq 2x - 3 \leq 5 \Leftrightarrow -2 \leq 2x \leq 8 \Leftrightarrow -1 \leq x \leq 4.

Justification. Le premier pas traduit ∣a∣≤r⇔−r≤a≤r\lvert a \rvert \leq r \Leftrightarrow -r \leq a \leq r, valable pour r≥0r \geq 0. Ajouter 33, puis diviser par 2>02 > 0, sont des opérations réversibles. Les solutions sont les réels xx tels que −1≤x≤4-1 \leq x \leq 4.

AttentionChaque équivalence se justifie dans les deux sens

Élever au carré ne donne qu'une implication : x=2x = 2 entraîne x2=4x^{2} = 4, mais x2=4x^{2} = 4 est vraie aussi pour x=−2x = -2. Multiplier par un nombre qui peut être nul fait aussi perdre la réversibilité. Avant d'écrire ⇔\Leftrightarrow, vérifie les deux sens.

Disjonction des cas, raisonnement par l'absurde

PropriétéPrincipe du raisonnement par disjonction des cas

Pour toutes propositions PP, QQ et RR, la proposition suivante est une loi logique : ((P⇒R) et (Q⇒R))⇔((P ou Q)⇒R).\big((P \Rightarrow R) \text{ et } (Q \Rightarrow R)\big) \Leftrightarrow \big((P \text{ ou } Q) \Rightarrow R\big).

En particulier, si (P⇒R)(P \Rightarrow R) et (P‾⇒R)(\overline{P} \Rightarrow R) sont vraies, alors RR est vraie.

Méthodedisjonction des cas

  1. Annonce des cas qui n'oublient rien : nn pair ou nn impair ; x≥0x \geq 0 ou x<0x < 0.
  2. Traite chaque cas sous un titre, avec sa propre hypothèse.
  3. Conclus : la propriété est vraie dans chaque cas, donc toujours (F10).

Exemple

Énoncé. Montre que, pour tout réel xx, ∣x∣≥x\lvert x \rvert \geq x.

Soit xx un réel. Les deux cas suivants couvrent toutes les possibilités.

Premier cas : x≥0x \geq 0. Alors ∣x∣=x\lvert x \rvert = x, donc ∣x∣≥x\lvert x \rvert \geq x.

Second cas : x<0x < 0. Alors ∣x∣=−x>0>x\lvert x \rvert = -x > 0 > x.

Conclusion. Dans les deux cas, ∣x∣≥x\lvert x \rvert \geq x.

PropriétéPrincipe du raisonnement par l'absurde

Soit PP et QQ deux propositions. Si l'implication (P‾⇒Q)(\overline{P} \Rightarrow Q) est vraie et si QQ est fausse, alors PP est vraie.

En particulier, s'il existe une proposition SS telle que l'implication (P‾⇒(S et S‾))\big(\overline{P} \Rightarrow (S \text{ et } \overline{S})\big) soit vraie, c'est-à-dire si l'on déduit de P‾\overline{P} une contradiction (S et S‾)(S \text{ et } \overline{S}), alors PP est vraie.

Méthoderaisonnement par l'absurde

  1. Annonce : « Supposons par l'absurde que P‾\overline{P} », et écris P‾\overline{P} en clair.
  2. Déduis jusqu'à heurter un fait établi ou une hypothèse ; nomme cette contradiction.
  3. Conclus : P‾\overline{P} est impossible, donc PP est vraie (F11).

Exemple

Énoncé. Montre qu'il n'existe pas de plus petit réel strictement positif.

Hypothèse absurde. Supposons par l'absurde qu'il existe un réel a>0a > 0 tel que ∀x∈R, (x>0⇒a≤x)\forall x \in \mathbb{R},\ (x > 0 \Rightarrow a \leq x).

Contradiction. Le réel a2\dfrac{a}{2} est strictement positif, donc a≤a2a \leq \dfrac{a}{2}, c'est-à-dire a≤0a \leq 0. Cela contredit a>0a > 0.

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

Raisonnement par récurrence

ThéorèmePrincipe de récurrence

Soit n0n_0 un entier naturel et P(n)P(n) une fonction propositionnelle de la variable entière n≥n0n \geq n_0. On suppose :

  • initialisation : P(n0)P(n_0) est vraie ;
  • hérédité : pour tout entier n≥n0n \geq n_0, l'implication (P(n)⇒P(n+1))(P(n) \Rightarrow P(n + 1)) est vraie.

Alors, pour tout entier naturel n≥n0n \geq n_0, P(n)P(n) est vraie.

Remarque

Au cours, F12 est démontré à partir d'une propriété de N\mathbb{N} : si une propriété est vérifiée par au moins un entier naturel, il existe un plus petit entier naturel qui la vérifie. Cette propriété de N\mathbb{N} est admise.

Méthoderédiger une récurrence

  1. Nomme la propriété P(n)P(n) et le rang de départ n0n_0.
  2. Initialisation : vérifie P(n0)P(n_0) par un calcul.
  3. Hérédité : « Soit n≥n0n \geq n_0 un entier tel que P(n)P(n) soit vraie ; montrons que P(n+1)P(n + 1) est vraie. » Utilise P(n)P(n) à un endroit précis, et dis-le.
  4. Conclusion : par le principe de récurrence (F12), P(n)P(n) est vraie pour tout entier n≥n0n \geq n_0.

Exemple

Énoncé. Pour tout n∈Nn \in \mathbb{N}, on note P(n)P(n) : « 5n−15^{n} - 1 est un multiple de 44 ». Montre que P(n)P(n) est vraie pour tout n∈Nn \in \mathbb{N}.

Initialisation. Pour n=0n = 0, 50−1=0=4×05^{0} - 1 = 0 = 4 \times 0 : P(0)P(0) est vraie.

Hérédité. Soit n∈Nn \in \mathbb{N} tel que P(n)P(n) soit vraie. D'après l'hypothèse de récurrence, il existe k∈Zk \in \mathbb{Z} tel que 5n−1=4k5^{n} - 1 = 4k. Alors 5n+1−1=5(4k+1)−1=4(5k+1)5^{n+1} - 1 = 5(4k + 1) - 1 = 4(5k + 1), avec 5k+1∈Z5k + 1 \in \mathbb{Z} : P(n+1)P(n + 1) est vraie.

Conclusion. D'après le principe de récurrence (F12), P(n)P(n) est vraie pour tout n∈Nn \in \mathbb{N}.

AttentionL'initialisation est obligatoire

Sans initialisation, une hérédité vraie ne prouve rien. Exemple : « n+1=nn + 1 = n » entraîne « n+2=n+1n + 2 = n + 1 », et pourtant aucun entier ne vérifie n+1=nn + 1 = n. Dans l'hérédité, P(n)P(n) est supposée pour un seul entier nn, fixé, jamais pour tous.

Choisir son raisonnement

MéthodeQuel raisonnement pour quel énoncé ?

Repère la forme de ce qu'on te demande, puis choisis.

Forme de l'énoncé Raisonnement à essayer
(P⇒Q)(P \Rightarrow Q) direct ; contraposée si Q‾\overline{Q} est plus maniable
(P⇔Q)(P \Leftrightarrow Q) double implication ou équivalences successives
∀x∈E, P(x)\forall x \in E,\ P(x) à démontrer « Soit x∈Ex \in E », puis raisonnement direct
∀x∈E, P(x)\forall x \in E,\ P(x) à réfuter un contre-exemple x0x_0 vérifié par le calcul
∃x∈E, P(x)\exists x \in E,\ P(x) exhiber un xx et vérifier P(x)P(x)
« il n'existe pas », « n'est pas » raisonnement par l'absurde
propriété selon la parité ou le signe disjonction des cas
« pour tout entier n≥n0n \geq n_0 » récurrence, si P(n+1)P(n + 1) se relie à P(n)P(n)

À retenirRédiger en devoir

Introduis chaque objet avant de t'en servir : « Soit… ». Annonce le raisonnement : « Raisonnons par contraposée », « Supposons par l'absurde ». Cite l'hypothèse ou le résultat utilisé à chaque pas. Termine par une phrase qui reprend la conclusion demandée.