Raisonnements usuels - Quelques méthodes

Les symboles logiques et leur maniement

On formalise le raisonnement mathématiques à l'aide de symboles logiques: les règles d'utilisation de ces symboles permettent alors de rendre le raisonnement, cetet chose abstraite et floue, plus "calculable". Ainsi, prenons deux propositions mathématiques $p$ et $q$. On notera:

• $\neg p$ la proposition "non $p$" (la négation de $p$): elle est vraie si $p$ est fausse, et vice-versa. Ainsi, $\neg (1+1=0)$ est la proposition $1+1\neq0$.
• $p\wedge q$ la proposition "$p$ et $q$": elle est vraie, comme le nom l'indique, si, et seulement si $p$ et $q$ sont toutes les deux vraies.
• $p \vee q$ la proposition "$p$ ou $q$": elle est vraie, si, $p$ est vraie, ou si $q$ est vraie, ou les deux sont vraies.
• $p\Rightarrow q$ la proposition "$p$ implique $q$". Celle-ci a un comportement un peu curieux en logique mathématique: elle est vrai si $p$ est fausse ou si $q$ est vraie, autrement dit, elle est équivalente à $\neg p \vee q$. L'idée derrière est que $p \Rightarrow q$ est fausse si l'hypothèse $p$ est vraie et la conclusion $q$ fausse, et vraie dans tous les autres cas.
• $p \Leftrightarrow q$ la proposition "$p$ équivaut à $q$": elle est vraie, si $p$ et $q$ sont toutes deux vraies ou toutes deux fausses.

On peut réunir ces informations dans des tables de vérités:




p	q	p$\rightarrow$q
Vrai	Vrai	Vrai
Vrai	Faux	Faux
Faux	Vrai	Vrai
Faux	Faux	Vrai

p	q	p$\vee$q
Vrai	Vrai	Vrai
Vrai	Faux	Vrai
Faux	Vrai	Vrai
Faux	Faux	Faux

p	q	p$\wedge$q
Vrai	Vrai	Vrai
Vrai	Faux	Faux
Faux	Vrai	Faux
Faux	Faux	Faux

p	q	p$\Leftrightarrow$q
Vrai	Vrai	Vrai
Vrai	Faux	Faux
Faux	Vrai	Faux
Faux	Faux	Vrai




En combinant ces tables, on peut étudier des énoncés plus compliqués, comme par exemple $(\neg(p \wedge q) \Rightarrow r) \Rightarrow (q \wedge r)$, et en déduire s'ils sont vrais ou faux selon si $p$, $q$ et $r$ le sont. C'est ce que l'on appelle le "calcul propositionnel"...et il faut reconnaître que bien souvent, ce n'est pas comme cela qu'on fait des maths.

En revanche, le calcul propositionnel permet de montrer que certains énoncés complexes sont toujours vrais, quelles que soient les propositions $p$, $q$ ou $r$. Ces énoncés sont appelées des tautologies, et on peut s'en servir comme règles de raisonnement: ainsi $[(p \Rightarrow q) \wedge (q \Rightarrow r)] \Rightarrow (p \Rightarrow r)$ est une tautologie, que l'on appelle la "transitivité de l'implication", et dont vous vous êtes certainement déjà servi, car elle sous-tend quasiment tous les raisonnements mathématiques. Elle dit que pour montrer que $p$ implique $r$, on peut passer par une (ou plusieurs!) étapes intermédiaires $q$: on montre que $p$ implique $q$, puis, de là, que $q$ implique $r$.

On obtient aussi des règles concernant la négation:

• $\neg (p\vee q) \Leftrightarrow (\neg p) \wedge (\neg q)$: autrement dit, "$p$ ou $q$" est fausse si et seulement si $p$ et $q$ sont toutes deux fausses;
• $\neg (p\wedge q) \Leftrightarrow (\neg p) \vee (\neg q)$: autrement dit, "$p$ et $q$" est fausse si et seulement si $p$ est fausse, ou $q$ est fausse, ou elles sont toutes deux fausses;
• $\neg (p\Rightarrow q) \Leftrightarrow p\wedge (\neg q)$: autrement dit, "$p$ implique $q$" est fausse si et seulement si $p$ est vraie (l'hypothèse est vérifiée) et $q$ est fausse (la conclusion n'est pas vérifiée).

Quelques méthodes:

• p et q: Pour montrer qu'une proposition du type $p\wedge q$ est vraie, pas le choix: il faut montrer $p$ et $q$ séparément!
• p implique q: Pour montrer qu'une implication $p\Rightarrow q$ est vraie, il y a deux façons de faire:
  • On peut procéder directement: on écrit "Supposons que $p$ soit vraie. Montrons que $q$ est vraie".
  • On peut procéder par contraposée: le calcul propositionnel montre que $"(p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)"$. On peut donc choisir de montrer que $\neg q \Rightarrow \neg p$. Pour cela, on écrit: "Procédons par contraposée. On suppose que $q$ est fausse, autrement dit, on suppose $\neg q$. Montrons $\neg p$".
• p n'implique pas q: Pour montrer qu'une implication $p\Rightarrow q$ est fausse, on doit montrer que sa négation $\neg (p\Rightarrow q)$ est vraie; d'après les règles sur la négation, on doit donc montrer $p\wedge (\neg q)$. On montre donc séparément que $p$ est vraie et que $q$ est fausse.
• p ou q: Pour montrer $p\vee q$, on peut remarquer que, puisque $(p\Rightarrow q)$ équivaut à $\neg p \vee q$, on a donc $p\vee q$ équivaut à $\neg p \Rightarrow q$. Ainsi, pour montrer $p\vee q$, on peut monter que $\neg p \Rightarrow q$. On écrit alors "Supposons que $p$ soit fausse. Montrons qu'alors $q$ est vraie."
• p équivaut à q: Pour montrer une équivalence $p \Leftrightarrow q$, il y a deux façons de faire:
  • On peut procéder par double inclusion: on montre séparément que $p\Rightarrow q$ et que $q \Rightarrow p$.
  • On peut procéder par équivalences successives, via des étapes intermédiaires toutes équivalentes entre elles: $$p\Leftrightarrow \dots \Leftrightarrow \dots\Leftrightarrow q$$

Exemple 1

Montrons que, pour deux réels $x$ et $y$, si $xy=0$ alors $x=0$ ou $y=0$.
C'est une implication: Supposons donc que $xy=0$ et montrons que ($x=0$ ou $y=0$). On va montrer que $\neg(x=0)\Rightarrow (y=0)$, ce qui montrera ($x=0$ ou $y=0$). Supposons donc que "x=0" soit fausse, c'est-à-dire $x\neq 0$. Alors, dans l'égalité $xy=0$, on peut diviser par $x$ de part et d'autre de l'égalité. On obtient alors $y=0$, ce qu'il fallait démontrer.

Bien sûr, cet exemple est détaillé au-delà de ce qui est raisonnablement exigible ! On cherche ici à mettre en avant les mécanismes de raisonnement, plutôt que de proposer un modèle de rédaction.



Exemple 2

Montrons que, pour tout entier $p$, si $p^2$ est pair alors $p$ est pair.
On va procéder par contraposée. On doit donc montrer que si $p$ n'est pas pair, alors $p^2$ n'est pas pair. Autrement dit, on doit montrer que si $p$ est impair, alors $p^2$ est impair.
Supposons donc $p$ impair. Il existe alors $k\in \mathbb N$ tel que $p=2k+1$. On calcule alors $$ p^2= (2k+1)^2= 4k^2 + 4k +1 = 2(2k^2+2k)+1 = 2K+1, \text{ où } K=2k^2+2k \in \mathbb N $$ donc $p^2$ est impair, ce qu'il fallait démontrer.

Quantificateurs et prédicats

Un prédicat est un énoncé mathématique dont la valeur dépend d'une variable, typiquement notée $x$. Par exemple, "$x\geq 3$" n'est ni vrai ni faux, tant qu'on ne sait pas qui est $x$; contrairement à "2+2=5", qui est faux, point barre. Pour transformer les prédicats en propositions, autrement dit pour leur attribuer une valeur de vérité (et donc pouvoir les étudier et avoir quelque chose à démontrer !), on introduit un ensemble $E$, où $x$ va vivre, et on définit deux nouveaux symboles logiques, appelés quantificateurs:

• Le quantificateur universel $\forall$, qui se lit "pour tout": si $P(x)$ est un prédicat dépendant de la variable $x$, la proposition $\forall x \in E,\ P(x)$ est vraie si et seulement si, pour n'importe quel élément $x$ de $E$, la proposition $P(x)$ est vraie. Par exemple, si $P(x)$ est le prédicat $x^2 \geq 0$, alors la proposition $\forall x \in \mathbb R, P(x)$ est vraie.
• Le quantificateur existentiel $\exists$, qui se lit "il existe": si $P(x)$ est un prédicat dépendant de la variable $x$, la proposition $\exists\, x \in E,\ P(x)$ est vraie si et seulement si, il existe (au moins) un "cas" d'élément $x_0$ de $E$ tel que $P(x_0)$ soit vraie. Par exemple, si $P(x)$ est le prédicat $x + 3 = 4$, alors la proposition $\exists x \in \mathbb R, P(x)$ est vraie, puisque $P(1)$ est vraie.

Attention: la valer de vérité d'une telle proposition dépend de l'ensemble où vit $x$. Par exemple, si $P(x)$ est le prédicat $x^2=-1$, alors, $\exists x \in \mathbb R, x^2 = -1$ est faux, mais $\exists x \in \mathbb C, x^2 = -1$ est vraie, puisque $P(i)$ est vrai.

Négation des quantificateurs: On applique les règles suivantes pour la négation des quantificateurs:

• $\neg (\forall x \in E,\ P(x)) \Leftrightarrow \exists x \in E, \neg P(x)$: autrement dit, un énoncé universel sur un ensemble $E$ "$\forall x \in E,\ P(x)$" est faux si, et seulement si, il existe un contre-exemple: un élément $x$ du même ensemble $E$ tel que $P(x)$ soit faux
• $\neg (\exists x \in E,\ P(x)) \Leftrightarrow \forall x \in E, \neg P(x)$: autrement dit, un énoncé existentiel sur un ensemble $E$ "$\exists x \in E,\ P(x)$" est faux si, et seulement si, pour n'importe quel élément $x$ du même ensemble $E$, $P(x)$ est faux. Autrement dit, on ne trouve aucun exemple d'élément $x$ qui rende $P(x)$ vrai.

Attention derechef: lorsque l'on prend la négation d'une proposition comportant des quantificateurs, les ensembles où vivent les variables ne changent pas ! Il faut être particulièrement prudent lorsque ces ensembles sont définis par des inégalités, ce qui arrive très souvent. Ainsi, la négation de "$\forall x>0, P(x)$" n'est pas "$\exists x\leq 0, P(x)$", mais plutôt $"\exists x>0, P(x)$". Ce qui est plus intuitif si on réécrit la propostion "$\forall x \in \mathbb R^*_+, P(x)$".

Méthodes de démonstration/rédaction:

• Pour montrer qu'un énoncé du type "$\forall x \in E,\ P(x)$" est vrai: on ne va pas vérifier $P(x)$ pour chaque $x$ dans $E$! On choisit donc un élément quelconque (ce qui est une façon de dire "on ne sait pas lequel spécifiquement") de $E$, qu'on note $x$, et on montre que $P(x)$ est vrai. On écrit donc "Soit $x \in E$. Montrons $P(x)$".
• Pour montrer qu'un énoncé du type "$\exists x \in E,\ P(x)$" est vrai: on doit trouver un élément spécifique de $E$ qui vérifie $P(x)$, et un seul suffit. Si on ne voit pas immédiatement quel $x$ va marcher, on peut en essayer quelques-uns au brouillon. Une fois qu'on a trouvé notre exemple, on écrit "Posons x=..." (où "..." est l'exemple en question) et montrons $P(x)$".
• Pour montrer qu'un énoncé du type "$\forall x \in E,\ P(x)$" est faux: d'après les règles de négation, il s'agit alors de montrer que "$\exists x \in E,\ \neg P(x)$" est vrai. On procède alors comme pour le deuxième point: on cherche un exemple de $x$ dans $E$ tel que $\neg P(x)$ soit vrai. Autrement dit, tel que $P(x)$ soit faux: c'est donc un contre-exemple de $P(x)$. On écrit alors "Posons $x=\dots$ et montrons $\neg P(x)$".
• Pour montrer qu'un énoncé du type "$\exists x \in E,\ P(x)$" est faux: d'après les règles de négation, il s'agit alors de montrer que "$\forall x \in E,\ \neg P(x)$" est vrai. On procède alors comme pour le premier point: on commence par écrire "Soit $x\in E$ quelconque", et on montre $\neg P(x)$.
Exemples

1) Démontrons la proposition "$\forall x\in \mathbb R,\ \frac{2x}{x^2+1} \leq 1$".
C'est un énoncé universel. Soit donc $x\in \mathbb R$. Montrons que $\frac{2x}{x^2+1} \leq 1$. On a $(x-1)^2 \geq 0$, donc $x^2 - 2x + 1 \geq 0$. On en déduit $2x \leq x^2 +1$. Or, $x^2+1 >0$, donc on peut diviser cette inégalité par $x^2+1$ pour obtenir $\frac{2x}{x^2+1} \leq 1$, ce qu'il fallait démontrer.




2) Démontrons la proposition "$\exists x\in \mathbb R,\ x^2 - 3x + 2 = 0$".
C'est un énoncé existentiel. Il s'agit donc de trouver un réel spécifique $x_0$ qui vérifie l'égalité. Ici, on remarque que 1 convient. On écrit donc: Posons $x_0=1$. Alors $1^2 - 3*1 +2 = 0$, donc $x_0$ convient.




Ici, le plus important est de bien distinguer les cas où un exemple ou contre exemple suffit, et les cas où il faut démontrer une propriété sur un $x$ général et inconnu.

Beaucoup d'énoncés mathématiques commencent par, non pas un, mais plusieurs quantificateurs. Par exemple, "la suite $(u_n)_n$ converge vers le réel $\ell$" se traduit par le fait que, pour des entiers $n$ suffisamment grands, $u_n$ est proche de $\ell$, c'est à dire que la distance entre eux devient plus petite que tout écart $\varepsilon$ préalablement choisi. Ce qui s'écrit, plus compactement: $$\forall\, \varepsilon >0, \exists N \in \mathbb N, \forall n \geq N, |u_n - \ell | < \varepsilon$$ ou encore, plus explicitement $$\forall\, \varepsilon >0, \exists N \in \mathbb N, \forall n\in \{k\in\mathbb{N}, k\geq N\}, |u_n - \ell | < \varepsilon$$ Ceci peut sembler effrayant, mais donne en fait une "recette" pour démontrer la propriété, en appliquant sans trop réfléchir les méthodes ci-dessus:

1. Le premier quantificateur est "$\forall\, \varepsilon >0$". On commence donc par poser "Soit $\varepsilon >0$". Ce $\varepsilon$ étant maintenant posé, on va pouvoir l'utiliser dans la suite du raisonnement.
2. Le suivant est "$ \exists N \in \mathbb N$": il s'agit donc d'exhiber un certain entier $N$ qui vérifie la propriété $P(N): \forall n \geq N, |u_n - \ell | < \varepsilon$: le but du jeu est maintenant de trouver $N$. On étudie alors l'inégalité $|u_n - \ell | < \varepsilon$ la recherche d'un candidat $N$. Ce $N$ dépendra certainement $\varepsilon$: plus l'écart fixé est petit, plus il faudra aller "loin" dans la suite $u_n$ pour être proche de $\ell$ de moins de $\varepsilon$.
3. Une fois ce $N$ trouvé, on écrit "Posons $N=...$", puis on passe à la suite:
4. On doit enfin montrer que "$ \forall n \geq N, |u_n - \ell | < \varepsilon$". On écrit donc "Soit $n\geq N$" (où $N$ est le $N$ trouvé à l'éape précédente !) et on montre que $|u_n - \ell | < \varepsilon$, ce qui est un calcul.
Exemple

Démontrons que la suite $u_n=\frac 1n$ converge vers 0. On doit donc montrer $$\forall\, \varepsilon >0, \exists N \in \mathbb N, \forall n \geq N, |\frac 1n - 0 | < \varepsilon$$ Soit donc $\varepsilon >0$. On cherche un rang $N$ à partir duquel $|\frac 1n - 0 | < \varepsilon$, autrement dit $\frac 1n < \varepsilon$. Donc, si $N> \frac 1{\varepsilon}$, cela va "marcher". Posons $N= E(\frac 1{\varepsilon}) + 1$ (où $E$ est la fonction partie entière). Montrons que $ \forall n \geq N, \frac 1n < \varepsilon$. Soit donc $n \geq N$, alors $\frac 1n \geq \frac 1N< \frac 1{1/\varepsilon} = \varepsilon$. On a donc bien $|\frac 1n - 0 | < \varepsilon$, ce qu'il fallait démontrer.




La négation de ce type d'énoncé à plusieurs quantificateurs s'obtient en appliquant les règles de négation successivement.

• $\neg (\forall x \in E,\ \forall y \in F,\ P(x,y)) \Leftrightarrow \exists x \in E,\ \exists y \in F,\ \neg P(x,y)$;
• $\neg (\exists x \in E,\ \exists y \in F, P(x,y)) \Leftrightarrow \forall x \in E, \ \forall y \in F,\ \neg P(x,y))$;
• $\neg (\forall x \in E,\ \exists y \in F, P(x,y)) \Leftrightarrow \exists x \in E,, \ \forall y \in F,\ \neg P(x,y))$;
• $\neg (\exists x \in E,\ \forall y \in F,\ P(x,y)) \Leftrightarrow \forall x \in E,\ \exists y \in F,\ \neg P(x,y)$.

A nouveau, ces règles nous donne des "recettes" pour montrer que des énoncés complexes sont faux. Par exemple, pour montrer qu'une suite ne converge pas vers un réel $\ell$, on doit montrer $$\neg(\forall\, \varepsilon >0, \exists N \in \mathbb N, \forall n\in \{k\in\mathbb{N}, k\geq N\}, |u_n - \ell | < \varepsilon)$$ autrement dit $$\exists\, \varepsilon >0, \forall N \in \mathbb N, \exists n \in \{k\in\mathbb{N}, k\geq N\}, |u_n - \ell | \geq \varepsilon$$ autrement dit, $$\exists\, \varepsilon >0, \forall N \in \mathbb N, \exists n\geq N, |u_n - \ell | \geq \varepsilon$$ Il s'agit donc d'exhiber un écart "minimal" $\varepsilon >0$, tel que, aussi loin qu'on aille dans la suite $(u_n)$, autrement dit "pour tout rang $N$", il existe un entier $n$ encore plus grand tel que $u_n$ reste à une distance au moins $\varepsilon$ de $u_n$.

Raisonnement par l'absurde

Pour montrer qu'une proposition $p$ est vraie, on peut procéder par l'absurde. Dans ce cas, on suppose que $p$ est fausse, et on utilise cette hypothèse pour aboutir à quelque chose de contradictoire ou que l'on sait être faux. Ainsi, $p$ ne peut pas être fausse, donc elle est vraie.

Exemple 1

Démontrons qu'un entier $n$ ne peut être à la fois pair et impair.
Soit $n\in \mathbb N$. On suppose, par l'absurde, que $n$ soit pair et impair. Alors, il existe $k\in \mathbb N$ tel que $n= 2k$, et il existe $l \in \mathbb N$ tel que $n=2l+1$. On a donc $2k = 2l+1$, que l'on réécrit $2(k-l)=1$, ou encore $k-l= \frac12$. Or, $k-l$ est un entier, mais pas $\frac12$: ils ne peuvent pas être égaux. Contradiction. On en déduit que $n$ ne peut pas être à la fois pair et impair.



Exemple 2

Démontrons que $\sqrt{2}$ n'est pas un rationnel.
Supposons, par l'absurde, que $\sqrt 2$ soit rationnel. Il existe donc deux entiers $p$ et $q$ sans diviseur commun tels que $\sqrt 2 = \frac pq$ (s'il y a des facteurs communs, on peut les simplifier dans la fraction). Autrement dit, $p = \sqrt 2 q$. On en déduit, en élevant l'égalité au carré, que $p^2 = 2 q^2$: $p^2$ est donc pair, ce qui implique que $p$ est pair. Donc il existe un entier $p'$ tel que $p=2p'$. Mais alors $p^2 = 4p'^2 = 2q^2$, donc $q^2= 2p'^2$, donc $q^2$ est pair. Comme précédemment, ceci implique que $q$ est pair. Au final, $p$ et $q$ ont un diviseur commun: 2, ce qui contredit notre hypothèse. On en déduit que $\sqrt 2$ n'est pas rationnel.




Attention à ne pas confondre le raisonnement par l'absurde avec le raisonnement par contraposée !

Raisonnement par récurrence

Le raisonnement par récurrence s'applique lorsque l'on veut démontrer une propriété sur les entiers $P(n)$; par exemple $P(n)$ pourrait être "l'entier $6^n - 1$ est divisible par 5". Pour démontrer la proposition $\forall n \in \mathbb N,\ P(n)$, on peut procéder par récurrence:

• La première étape, qu'on appelle "initialisation", consiste à démontrer $P(0)$.
• La seconde étape, appellée "hérédité" consiste à montrer l'implication $P(k) \Rightarrow P(k+1)$: on montre que si la propriété $P$ est vraie pour un entier $k$, alors elle est aussi vraie pour l'entier suivant $k+1$. La supposition "P est vérifiée pour $k$" s'appelle l'hypothèse de récurrence.

Ainsi, la propriété $P$ est vraie pour le premier entier, 0. Mais, d'après la seconde étape, si elle est vraie pour 0, alors elle est vraie pour 1. Donc $P(1)$ est aussi vraie. Mais si elle est vraie pour 1, alors elle est vraie pour 2, toujours d'après la seconde étape. Donc $P(2)$ est aussi vraie. Et ainsi de suite: $P(n)$ doit donc être vraie pour tout $n$.

On peut généraliser ce raisonnement pour démontrer qu'une propriété $P(n)$ est vraie pour tout entier plus grand que 1: on fait alors l'initialisation en montrant $P(1)$. En fait, on peut ainsi démontrer qu'une propriété est vraie à partir d'un entier fixé $n_0$ en initialisant avec $P(n_0)$. L'hérédité se traite de la même façon.

Exemple

Démontrons que pour tout entier $n \geq 1$, la somme des $n$ premiers entiers est égale à $\frac{n(n+1)}{2}$, autrement dit $$ P(n): 1+2+\dots+n = \sum_{k=1}^n k = \frac{n(n+1)}{2} $$
On procède par récurrence.
Initialisation: Montrons que la propriété est vraie pour n=1. On a $\sum_{k=1}^1 k = 1$ et $\frac{1(1+1)}{2}=1$: ces quantités sont bien égales.
Hérédité: Supposons que la propriété est vraie pour un entier $n$, c'est-à-dire $1+2+\dots+n = \sum_{k=1}^n k = \frac{n(n+1)}{2}$, et montrons qu'elle est vraie pour $n+1$. On calcule $$ \sum_{k=1}^{n+1} k = 1+2+\dots+n+(n+1) = \sum_{k=1}^n k + (n+1) = \frac{n(n+1)}{2} + (n+1) $$ d'après l'hypothèse de récurrence. On calcule alors $$ \sum_{k=1}^{n+1} k = 1+2+\dots+n+(n+1) = \frac{n(n+1)}{2} + \frac{2(n+1)}{2} = \frac{n(n+1)+2(n+1)}2 = \frac{(n+1)(n + 2)}2 = \frac{(n+1)((n+1)+1)}2, $$ ce qu'il fallait démontrer. On a bien $P(n)\Rightarrow P(n+1)$.
On en déduit, par le principe de récurrence, que pour tout $n\geq 1$, $\sum_{k=1}^n k = \frac{n(n+1)}{2}$.