Théorie du module : Logique

Théorèmes et méthodes de démonstration

Nous allons ici expliquer ce qu'est une démonstration ainsi que donner différents types de démonstration.

Démontrer consiste à déduire la vérité d'une affirmation mathématique, appelée la thèse, à partir d'un ensemble d'affirmations mathématiques que l'on suppose être vraies le temps de la démonstration (les hypothèses) et à partir d'un ensemble d'affirmations mathématiques qui sont vraies (des axiomes ou des théorèmes qui ont déjà été démontrés auparavant). Notons que les hypothèses sont en général écrites explicitement dans l'énoncé que l'on cherche à démontrer, ce qui n'est pas le cas des axiomes et des théorèmes que l'on aura à utiliser au cours de la démonstration.

Il est important de bien comprendre que la démonstration d'un théorème sert uniquement à prouver que sa thèse est vraie lorsque ses hypothèses sont vraies. Lorsqu'on voudra utiliser un théorème, il faudra donc toujours commencer par vérifier que ses hypothèses sont bien satisfaites.

Remarque :Puisque l'énoncé "\(\neg(\forall x\, :\, P(x))\)" est équivalent à l'énoncé "\(\exists\, x\, :\, \neg P(x)\)", pour prouver qu'une propriété n'est pas vraie pour toutes les valeurs de \(x\), il suffit de trouver une valeur de \(x\) pour laquelle la propriété n'est pas satisfaite. Une telle valeur est appelée un contre-exemple.

Les hypothèses et thèse d'un théorème sont en général composées de plusieurs propositions \(p\), \(q\), \(r,\ldots\). Pour simplifier la présentation, nous écrirons \(P\) et \(Q\) au lieu de \(P(p, q, r,\ldots) \) et \(Q(p, q, r,\ldots) \).

Méthodes de démonstration de \(P\Rightarrow Q\)

Si on appelle théorème l'affirmation \(P\Rightarrow Q\), où \(P\) sont les hypothèses et \(Q\) les conclusions, démontrer le théorème \(P\Rightarrow Q\) revient à tester la validité de l'affirmation. Voici différentes manières de procéder.

  • Démonstration directe (modus ponens) :

Il faut montrer que \(P\Rightarrow Q\) est une tautologie donc, d'après la définition de l'opérateur logique \(\Rightarrow\), il convient de montrer que si \(P\) est vraie, alors \(Q\) est aussi vraie.

Par exemple, voyons que tout nombre naturel qui est un carré a un nombre impair de diviseurs. Soit

\(P\) : \(x\) est un nombre naturel qui est un carré.
\(Q\) : \(x\) a un nombre impair de diviseurs.

Preuve directe :
Le nombre \(x\) admet trivialement comme diviseurs \(1\) et lui-même \(x\). Comme \(x=y^2\) il admet \(y\) comme diviseur. Ce qui en fait déjà trois \(1\), \(y\) et \(x\). Pour tout autre nombre \(a\) (différent de \(1\), \(y\) et \(x\)), diviseur de \(x\), il doit y avoir un nombre \(b\) tel que \(x=a\cdot b\) Le nombre \(b\) est également diviseur de \(x\) et doit également être différent de \(1\), \(y\), \(x\) et \(a\). Donc s'il y a d'autres diviseurs que \(1\), \(y\) et \(x\), ils doivent être différents et exister par paires. Le nombre total de diviseurs est dès lors impair.

  • Démonstration par l'absurde (contradiction) :

Le principe de démonstration par l'absurde s'énonce de la manière suivante :

Principe de démonstration par l’absurde
Pour démontrer une affirmation \(P\) par l'absurde,
on suppose que \(\neg P\) est vraie (c'est-à-dire que \(P\) est fausse)
et on en déduit une absurdité.

 

Intuitivement, on comprend que si l'on déduit une absurdité de l'hypothèse \(\neg P\), c'est que cette hypothèse est fausse, ce qui revient à dire que \(P\) est vraie.

Reprenons l'exemple précédent. On va supposer que \(P\) est vraie et que \(Q\) est fausse et montrer que cela ne peut pas se produire.

Preuve par l'absurde :
Supposons que le nombre \(x\) est un carré et \(x\) possède \(2k\) diviseurs. Soit \(y\) tel que \(x=y\cdot y\). Enlevons \(1\), \(x\) et \(y\). Il reste un nombre impair de diviseurs. Formons parmi ceux-ci les couples \(z_1\), \(z_2\) de nombres différents tels que \(x=z_1\cdot z_2\). Cela en fait un nombre pair, il doit donc en rester un. Soit \(a\) ce nombre, comme il n'est pas \(1\), \(y\) ou \(x\), il doit alors vérifier \(x=a\cdot a\), ce qui est absurde car \(a\not= y\).

  • Démonstration par contraposée :

Grâce à l'équivalence entre un énoncé et sa contraposée, démontrer \(P \Rightarrow Q\) revient à démontrer\(\neg Q \Rightarrow \neg P\).

Principe de démonstration par contraposée
Pour démontrer une affirmation de la forme \(P\Rightarrow Q\) par contraposition,
on démontre la contraposée \(\neg Q\Rightarrow\neg P\),
c'est-à-dire : on suppose que \(Q\) est fausse et on en déduit que \(P\) est fausse.

 

Dans l'exemple ci-dessus, \(\neg Q\Rightarrow\neg P\) revient à "\(x\) possède un nombre pair de diviseurs \(\Rightarrow\) \(x\) n'est pas un carré".

Preuve par contraposition :
On doit pouvoir regrouper les diviseurs par paires de nombres différents \(y,z\) tels que \(x=y\cdot z\). Il ne peut donc pas rester un nombre unique \(a\), tel que \(x=a\cdot a\). Le nombre \(x\) n'est donc pas un carré.

Méthode de démonstration de \(P \Leftrightarrow Q\)

Une affirmation de la forme \(P \Leftrightarrow Q\) est équivalente à \((P\Rightarrow Q)\wedge (Q\Rightarrow P)\). Pour prouver \(P \Leftrightarrow Q\), il suffit donc de prouver \(P\Rightarrow Q\) et de prouver \(Q\Rightarrow P\).

Méthode de démonstration par récurrence (ou par induction)

On utilise le principe de démonstration par récurrence lorsqu'on veut prouver qu'une propriété est vraie pour tous les nombres naturels. Le principe est le suivant :

 

Principe de démonstration par récurrence
Pour prouver qu'une affirmation de la forme "\(\forall n\in\mathbb{N}\, :\, P(n)\)" est vraie, il suffit de prouver que
  • "\(P(0)\)" est vraie,
  • "\(\forall k\in \mathbb{N}\, :\, P(k)\Rightarrow P(k+1)\)" est vraie.

 

Par exemple, on veut prouver que pour tout \(n\in \mathbb{N}\), on a

\(0^3+1^3+2^3+\cdots +n^3=\displaystyle\frac{n^2(n+1)^2}{4}\)

Preuve par récurrence :

  • \(P(0)\) est l'affirmation

    \(0^3=\displaystyle\frac{0^2(0+1)^2}{4}.\)

    Cette affirmation est clairement vraie.
  • Supposons que \(P(k)\) soit vraie pour un certain \(k\in \mathbb{N}\), c'est-à-dire supposons que

    \(0^3+1^3+2^3+\cdots +k^3=\displaystyle\frac{k^2(k+1)^2}{4}\)

    (ceci est l'hypothèse de récurrence) et voyons que \(P(k+1)\) est encore vraie.
    On a par hypothèse de récurrence

    \(0^3+1^3+2^3+\cdots+k^3+(k+1)^3=\displaystyle\frac{k^2(k+1)^2}{4}+(k+1)^3.\)

    De plus,

    \(\begin{array}{rl} \displaystyle\frac{k^2(k+1)^2}{4}+(k+1)^3&=\displaystyle\frac{k^2(k+1)^2}{4}+\frac{4}{4}(k+1)(k+1)^2,\\ &=\displaystyle\frac{(k+1)^2}{4}(k^2+4(k+1)),\\ &=\displaystyle\frac{(k+1)^2}{4}(k+2)^2 \end{array}\)

    et on obtient

    \(0^3+1^3+2^3+\cdots+k^3+(k+1)^3=\displaystyle\frac{(k+1)^2((k+1)+1)^2}{4},\)

ce qui est exactement \(P(k+1)\). Puisque l'affirmation est vraie pour le premier entier et que si elle est vraie pour un entier quelconque, elle l'est aussi pour le suivant, on peut donc en conclure qu'elle est vraie pour tous les entiers.

Remarque : Si l'on veut prouver que l'énoncé "\(\forall n\geq c\, :\, P(n)\)" est vrai, il suffit de prouver que "\(P(c)\)" est vraie et que "\(\forall k\geq c\,:\, P(k)\Rightarrow P(k+1)\)" est vraie. De même, si l'on veut prouver qu'une propriété \(P\) est satisfaite par tous les nombres naturels pairs, il suffit de montrer que "\(P(0)\)" est vraie et que "\(\forall k\in\mathbb{N}\, :\, P(k)\Rightarrow P(k+2)\)" est vraie.

Théorie