International Baccalaureate · DP 2 : Analysis and Approaches SL

Raisonnement et Démonstration

⌚ ~242 min ▢ 28 blocs ✓ 99 exercices ➣ Prérequis : Propriétés sur les nombres entiers

Maîtrisez les bases de la logique et de la démonstration mathématique. Ce module couvre les connecteurs logiques, les quantificateurs et les lois de De Morgan. Explorez des méthodes rigoureuses : preuve directe, contraposée, absurde, récurrence et exhaustion via divers exercices.

I Proposition

Définition — Proposition et Valeur de Vérité

Une proposition est un énoncé qui peut être soit vrai, soit faux, mais pas les deux. On note souvent les propositions par des lettres telles que $p$, $q$ et $r$.

Note

Sauf indication contraire, toute proposition ou tout théorème présenté dans un texte mathématique est affirmé comme étant vrai. Le but d'une démonstration est de justifier cette vérité.

Exemple

$p$ : « Le nombre 9 est un nombre premier. » (Faux)
$q$ : « 3 est un diviseur de 12. » (Vrai)

Compétences à pratiquer

Déterminer des valeurs de vérité
Déduire des valeurs de vérité

II Négation

Définition — Négation

La négation d'une proposition $p$, notée $\neg p$, est la proposition « non $p$ ». La valeur de vérité de $\neg p$ est l'opposé de la valeur de vérité de $p$.

Exemple

$p$ : « L’entier $4$ est un nombre pair. » (Vrai)
$\neg p$ : « L’entier $4$ n’est pas un nombre pair. » (Faux)

Compétences à pratiquer

Trouver la négation d'une proposition
Déduire des valeurs de vérité

III Propositions composées

Définition — Conjonction

La conjonction de $p$ et $q$, notée $\boldsymbol{p \wedge q}$, est la proposition « $p$ et $q$ ». Elle est vraie seulement si $p$ et $q$ sont toutes les deux vraies.

Exemple

Soit $p$ : « $n$ est un multiple de $2$ » et $q$ : « $n$ est un multiple de $3$ ».
La conjonction $p \wedge q$ est « $n$ est un multiple de $2$ et $n$ est un multiple de $3$ »,ce qui signifie que $n$ est un multiple à la fois de $2$ et de $3$ (par exemple, $n = 6, 12, 18, \dots$).

Définition — Disjonction

La disjonction de $p$ et $q$, notée $\boldsymbol{p \vee q}$, est la proposition « $p$ ou $q$ ». Elle est vraie si au moins l'une des deux est vraie. C'est un ou inclusif.

Exemple

Soit $p$ : « $n$ est un multiple de 2 » et $q$ : « $n$ est un multiple de 3 ».
La disjonction $p \vee q$ est vraie si $n$ est un multiple de 2, ou un multiple de 3, ou les deux (par exemple pour $n=2, 3, 4, 6, 8, 9, \dots$).

Proposition — Lois de De Morgan

La négation d'une conjonction ou d'une disjonction suit un schéma spécifique connu sous le nom de lois de De Morgan.

Négation d'une conjonction : $\boldsymbol{\neg(p \wedge q) \Leftrightarrow (\neg p \vee \neg q)}$
Pour nier un énoncé « et », on nie chaque partie et on remplace le « et » par « ou ».
Négation d'une disjonction : $\boldsymbol{\neg(p \vee q) \Leftrightarrow (\neg p \wedge \neg q)}$
Pour nier un énoncé « ou », on nie chaque partie et on remplace le « ou » par « et ».

Exemple

Trouver la négation de l'énoncé « $x \le 1$ ou $x > 4$ ».

Correction

Soit $p$ l'énoncé « $x \le 1$ » et $q$ l'énoncé « $x > 4$ ». L'énoncé est une disjonction, $p \vee q$. Nous utilisons la deuxième loi de De Morgan : $\neg(p \vee q) \Leftrightarrow (\neg p \wedge \neg q)$.D'abord, nous trouvons la négation de chaque partie :

La négation de $p : x \le 1$ est $\neg p : x > 1$.
La négation de $q : x > 4$ est $\neg q : x \le 4$.

Maintenant, nous les combinons avec un « et » :$$ (\neg p \wedge \neg q) \text{ est } (x > 1) \wedge (x \le 4). $$Ceci peut s'écrire plus simplement comme l'intervalle $\boldsymbol{1 < x \le 4}$.

Compétences à pratiquer

Évaluer des propositions composées
Déterminer la négation de conjonctions et de disjonctions

IV Implication et équivalence

L’implication formalise la déduction : de $p$ on déduit $q$. Si $p\Rightarrow q$ et $p$ est vraie, alors $q$ doit être vraie.

Définition — Implication

Une implication, notée $\boldsymbol{p \Rightarrow q}$, est la proposition « si $p$, alors $q$ ». Elle est fausse uniquement lorsque $p$ est vraie et $q$ est fausse.

Définition — Réciproque/Inverse/Contraposée

Pour l'implication $p \Rightarrow q$ :

La réciproque est $q \Rightarrow p$.
La contraposée est $\neg q \Rightarrow \neg p$.
L'inverse est $\neg p \Rightarrow \neg q$.

Exemple

« Si $x=1$ alors $x^2=1$ » est vraie. Sa réciproque « Si $x^2=1$ alors $x=1$ » est fausse (car $x=-1$ convient aussi).

Définition — Équivalence

Une équivalence, notée $\boldsymbol{p \Leftrightarrow q}$, est la proposition « $p$ si et seulement si $q$ ». Elle est vraie seulement lorsque $p$ et $q$ ont la même valeur de vérité. C'est la conjonction d'une implication et de sa réciproque : $(p \Rightarrow q) \wedge (q \Rightarrow p)$.

Proposition — Équivalence avec la contraposée

Une implication et sa contraposée sont logiquement équivalentes : $\boldsymbol{(p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)}$.

Supposons que l’implication « S’il pleut, alors le sol est mouillé. » soit vraie. Comme une implication et sa contraposée sont logiquement équivalentes, on peut en déduire que la contraposée est également vraie :

Implication : « S’il pleut, alors le sol est mouillé. »
Contraposée : « Si le sol n’est pas mouillé, alors il ne pleut pas. »

En revanche, on ne peut pas en déduire que la réciproque « Si le sol est mouillé, alors il pleut. » est vraie. Le sol peut être mouillé pour une autre raison (par exemple, le jardinier l’a arrosé), donc la réciproque n’est pas logiquement équivalente à l’implication de départ.

Compétences à pratiquer

Identifier les implications liées
Écrire la réciproque et la contraposée
Traduire des énoncés en implications

V Quantificateurs

Définition — Quantificateurs

Le quantificateur universel $\forall$ signifie « pour tout ». « $\forall x\in E,\;P(x)$ » affirme que $P(x)$ vaut pour tout $x\in E$.
Le quantificateur existentiel $\exists$ signifie « il existe ». « $\exists x\in E,\;P(x)$ » affirme qu’il existe au moins un $x\in E$ tel que $P(x)$ soit vraie.

Exemple

Soit $E = \{1, 2, 3\}$.

$\forall x \in E, x < 4$ est un énoncé vrai, car on a $1<4$, $2<4$ et $3<4$.
$\exists x \in E, x \text{ est pair}$ est un énoncé vrai car $2$ est pair.
$\forall x \in E, x \text{ est impair}$ est un énoncé faux, car $2$ n'est pas impair.

Proposition — Négation des quantificateurs

La négation de « $\forall x\in E, P(x)$ » est « $\exists x\in E, \neg P(x)$ ».
La négation de « $\exists x\in E, P(x)$ » est « $\forall x\in E, \neg P(x)$ ».

Exemple

La négation de l’énoncé « Tous les entiers sont pairs »$$\forall n \in \mathbb{Z},\; n \text{ est pair}$$est « Il existe au moins un entier qui est impair »$$\exists n \in \mathbb{Z},\; \neg(n \text{ est pair}) \quad\text{c’est-à-dire}\quad \exists n \in \mathbb{Z},\; n \text{ est impair}.$$

Compétences à pratiquer

Évaluer des énoncés quantifiés
Identifier la négation d'énoncés quantifiés
Traduire des énoncés en forme quantifiée

VI Structure des démonstrations écrites

Méthode — Structure des démonstrations écrites

Une démonstration claire et bien structurée suit généralement ces étapes :

Énoncé : Énonce clairement la proposition que tu comptes prouver et, si besoin, la méthode que tu utiliseras.
Hypothèses : Énonce explicitement tes hypothèses de départ. Pour une preuve directe, cela revient à supposer la prémisse $p$ de l’implication $p \Rightarrow q$.
Étapes logiques : Présente une séquence de déductions logiques claires, en justifiant chaque étape à l’aide de définitions, d’axiomes ou de théorèmes déjà démontrés.
Conclusion : Énonce la conclusion finale, en la reliant explicitement à la proposition initiale.

Exemple

Preuve directe : la somme de deux entiers pairs est paire.

Énoncé :
Nous prouvons par preuve directe : si $a,b$ sont des entiers pairs, alors $a+b$ est pair.
Hypothèses :
Supposons $a,b$ deux entiers pairs. Par définition d’un entier pair, il existe $k,\ell\in\Z$ tels que$$ a=2k \quad\text{et}\quad b=2\ell. $$
Étapes logiques :
$$\begin{aligned}a+b &= 2k + 2\ell \\ &= 2(k+\ell).\end{aligned}$$Comme $k+\ell\in\Z$, la somme $a+b$ est un multiple de $2$.
Conclusion :
Par définition d’un entier pair, $a+b$ est pair.

Méthode — Conseils pour rédiger des démonstrations

Écris d’abord les hypothèses et la conclusion visée ; elles guideront ton chemin. Il peut être utile de remonter à partir de la conclusion sur une feuille de brouillon.
Démonstration en cours : la « main » gauche représente l’hypothèse, la « main » droite la conclusion — elles se rejoignent au milieu.
Utilise un brouillon. Explore librement sur une feuille de brouillon avant de rédiger l’argument final et soigné.
La grande mathématicienne Maryam Mirzakhani travaillant intensément sur un brouillon.
Itère. Recueille des retours, révise, et ne t’attends pas à une démonstration parfaite du premier coup.
Boucle de retours avec Dr. Tariel et un étudiant de la CommeUnJeu Academy.

Compétences à pratiquer

Analyser des structures de preuve

VII Introduire une variable

Pour raisonner sur tous les éléments d’un ensemble $E$, on introduit un élément générique par « Soit $x\in E$. » Il représente un élément quelconque pendant toute la preuve.

Méthode — Introduire une variable

Soit $x\in E$.
$\vdots\quad\quad \quad\quad$ (raisonner sur $x$)
Par conséquent, l'énoncé vaut pour tout $x\in E$.

Compétences à pratiquer

Structurer une démonstration

VIII Démonstration directe (par déduction)

Méthode — Démonstration directe

Pour prouver $p \Rightarrow q$, une preuve directe suppose que $p$ est vraie et utilise une suite de déductions logiques pour montrer que $q$ doit aussi être vraie.$$\begin{aligned}&\text{Supposons que } p \text{ soit vraie.} && (\text{Hypothèse})\\ &\quad\vdots\quad && (\text{Étapes logiques})\\ &\text{Donc } q \text{ est vraie.} && (\text{Conclusion})\end{aligned}$$

Exemple

Démontrer que si un entier $a$ divise les entiers $b$ et $c$, alors $a$ divise leur somme $b+c$.

Correction

Soient $a, b$ et $c$ des entiers.
Supposons que $a$ divise $b$ et que $a$ divise $c$.
Par définition de la divisibilité, il existe des entiers $k$ et $m$ tels que$$ b = ak \quad \text{et} \quad c = am. $$Considérons la somme $b+c$ :$$\begin{aligned}b + c &= ak + am \\ &= a(k+m).\end{aligned}$$Par définition, cela signifie que $a$ divise $b+c$.

Compétences à pratiquer

Ecrire des démonstrations directes en Arithmétique
Construire des démonstrations directes dans divers contextes
Construire des démonstrations directes : prouver qu'un énoncé est vrai

IX Preuve par contraposée

Méthode — Preuve par contraposée

Pour prouver l’implication $p \Rightarrow q$, on peut plutôt démontrer sa contraposée, logiquement équivalente, $\neg q \Rightarrow \neg p$.$$\begin{aligned} &\text{Supposons que } \neg q \text{ soit vraie.} && (\text{Hypothèse})\\ &\quad\vdots\quad && (\text{Étapes logiques})\\ &\text{Donc } \neg p \text{ est vraie.}&& (\text{Conclusion})\end{aligned}$$

Exemple

Démontrer que si $a^2$ est pair, alors $a$ est pair.

Correction

Nous allons prouver la contraposée : « Si $a$ est impair, alors $a^2$ est impair. »
Supposons que $a$ soit un entier impair.
Il existe alors un entier $k$ tel que $a=2k+1$.$$\begin{aligned} a^2 &= (2k+1)^2\\ &= 4k^2+4k+1\\ &= 2(2k^2+2k)+1.\end{aligned}$$Donc $a^2$ est de la forme $2m+1$ et est donc impair.
Puisque nous avons prouvé la contraposée, l’énoncé initial est vrai.

Compétences à pratiquer

Construction de démonstrations par contraposée

X Preuve par exhaustion

Une démonstration par exhaustion (ou par cas) consiste à décomposer un énoncé en un nombre fini de cas distincts et à prouver que l'énoncé est vrai pour chacun de ces cas. Il est crucial de montrer que les cas choisis couvrent toutes les possibilités.

Méthode — Preuve par exhaustion

Pour prouver une proposition $P$, identifie un ensemble fini de cas $\{C_1, C_2, \dots, C_n\}$ qui soient exhaustifs (couvrent toutes les possibilités).

Prouver que $P$ est vraie pour le cas $C_1$.
...
Prouver que $P$ est vraie pour le cas $C_n$.

Exemple

Démontrer que pour tout entier $n$, $n(n+1)$ est pair.

Correction

Soit $n$ un entier.

Cas 1 : $n$ est pair.
Il existe un entier $k$ tel que $n=2k$. $$ \begin{aligned} n(n+1) &= 2k(2k+1)\\ &= 2[k(2k+1)]. \end{aligned} $$ Donc $n(n+1)$ est pair.
Cas 2 : $n$ est impair.
Il existe un entier $k$ tel que $n=2k+1$. $$ \begin{aligned} n(n+1) &= (2k+1)((2k+1)+1)\\ &= (2k+1)(2k+2)\\ &= 2\left[(2k+1)(k+1)\right]. \end{aligned} $$ Donc $n(n+1)$ est pair.

Donc $n(n+1)$ est pair.

Compétences à pratiquer

Construction de démonstrations par exhaustion

XI Réfutation par contre-exemple

Pour prouver qu'un énoncé universel est faux, il suffit de trouver un seul cas pour lequel il ne s'applique pas. Par exemple, pour prouver que l'énoncé « Tous les élèves de ma classe sont des garçons » est faux, il suffit de trouver une élève qui est une fille. En notation logique, dire que « $\forall x\in E,\;P(x)$ » est faux revient à dire que « $\exists x\in E,\;\neg P(x)$ » est vrai.

Méthode — Réfutation par contre-exemple

Pour réfuter l'énoncé « $\forall x\in E,\;P(x)$ », il suffit de trouver un élément $c \in E$ pour lequel $P(c)$ est faux. Cet élément $c$ est appelé un contre-exemple. Autrement dit, on montre que l’énoncé existentiel « $\exists x\in E,\;\neg P(x)$ » est vrai.

Exemple

Réfuter « Tous les nombres impairs sont des nombres premiers. »

Correction

Contre-exemple : $9$ est impair mais n’est pas premier (car $9 = 3 \times 3$).

Compétences à pratiquer

Réfutater des énoncés par contre-exemple

XII Preuve par équivalence

Pour prouver $p\Leftrightarrow q$, on peut montrer séparément $p\Rightarrow q$ et $q\Rightarrow p$, ou transformer $p$ en $q$ par équivalences successives.

Méthode — Preuve par équivalence

Pour prouver $p \Leftrightarrow q$, deux méthodes sont possibles :

Double implication :
1. Prouver le sens direct : supposer que $p$ est vraie et montrer que $q$ doit être vraie ($p \Rightarrow q$).
2. Prouver le sens réciproque : supposer que $q$ est vraie et montrer que $p$ doit être vraie ($q \Rightarrow p$).
Chaîne d'équivalences : partir de l'énoncé $p$ et construire une suite d'énoncés logiquement équivalents qui se termine par $q$. $$ p \quad \Leftrightarrow \quad s_1 \quad \Leftrightarrow \quad s_2 \quad \Leftrightarrow \quad \dots \quad \Leftrightarrow \quad q. $$

Exemple

Pour $n\in\Z$, les énoncés suivants sont équivalents :$$n \text{ est pair} \;\Leftrightarrow\; n^2 \text{ est pair}.$$

($\Rightarrow$) Supposons que $n$ soit pair. Il existe alors $k\in\Z$ tel que $n = 2k$. Ainsi$$n^2 = (2k)^2 = 4k^2 = 2(2k^2),$$donc $n^2$ est pair.
($\Leftarrow$) Supposons que $n^2$ soit pair. D’après le résultat démontré plus haut (« Si $a^2$ est pair, alors $a$ est pair »), on en déduit que $n$ est pair.

Compétences à pratiquer

Construire des preuves d'équivalence
Construire et analyser des preuves par équivalence pour des identités

XIII Raisonnement par l'absurde

Le raisonnement par l'absurde repose sur l'idée que si une supposition mène à une absurdité logique, cette supposition doit être fausse (par exemple $1=0$). On peut résumer la forme logique ainsi : si supposer $\neg p$ conduit à une contradiction, alors $p$ doit être vraie.

Méthode — Raisonnement par l'absurde

Pour prouver qu'une proposition $p$ est vraie par l'absurde :$$\begin{aligned} &\text{Supposons que } \neg p \text{ soit vraie.} && (\text{Hypothèse})\\ &\quad\vdots\quad && (\text{Étapes logiques menant à une contradiction, par exemple } 1=0)\\ &\text{Contradiction ! Donc l’hypothèse } \neg p \text{ est fausse.} && \\ &\text{Ainsi, } p \text{ doit être vraie.}&& (\text{Conclusion})\end{aligned}$$

Exemple

Démontrer par l'absurde que le nombre de nombres premiers est infini.

Correction

Supposons qu'il n'existe qu'un nombre fini $n$ de nombres premiers, que nous notons $p_1, p_2, \dots, p_n$.
Tout entier positif strictement supérieur à 1 est soit un membre de cette liste, soit divisible par un membre de cette liste.
Soit $N = p_1 \times p_2 \times \dots \times p_n + 1$. Remarquons que :

$N > p_k$ pour tout $k=1, \dots, n$.
Donc $N$ n'est pas un membre de la liste.
Si nous divisons $N$ par n'importe quel $p_k$, $k=1, \dots, n$, alors le reste est $1$.
Donc $N$ n'est divisible par aucun $p_k$.

Ceci contredit notre supposition selon laquelle tout entier strictement supérieur à 1 est dans la liste ou divisible par un nombre premier de la liste. Notre supposition est donc fausse, et il existe une infinité de nombres premiers.

Compétences à pratiquer

Analyse de la structure d'une démonstration par l'absurde
Construire de démonstrations par l'absurde

XIV Raisonnement par récurrence

Le raisonnement par récurrence est une technique puissante utilisée pour démontrer qu'une proposition $P(n)$ est vraie pour tous les entiers $n$ à partir d'une certaine valeur de départ. C'est analogue à faire tomber une rangée de dominos : si tu peux faire tomber le premier, et que tu sais que chaque domino fera tomber le suivant, alors tous les dominos finiront par tomber.

Méthode — Le principe du raisonnement par récurrence

Pour prouver par récurrence qu'une proposition $P(n)$ est vraie pour tous les entiers $n \ge n_0$ :

Initialisation : prouver que $P(n_0)$ est vraie.
Hérédité :
- supposer que $P(k)$ est vraie pour un entier arbitraire $k \ge n_0$ (hypothèse de récurrence) ;
- en utilisant cette hypothèse, prouver que $P(k+1)$ doit aussi être vraie.

Exemple

Démontrer par récurrence que pour tout entier $n \ge 1$,$$1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}.$$

Correction

Soit $P(n)$ la proposition$$P(n) : \quad 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$$pour tout entier $n \ge 1$.

Initialisation ($n=1$) :\$$0.2em]À gauche, on a $1$. À droite,$$\frac{1(1+1)}{2} = \frac{2}{2} = 1.$$Donc $P(1)$ est vraie.\$$0.4em]
Hérédité :
Supposons $P(k)$ vraie pour un certain entier $k \ge 1$, c’est-à-dire$$1 + 2 + 3 + \dots + k = \frac{k(k+1)}{2}.$$Nous devons montrer que $P(k+1)$ est vraie :$$1 + 2 + 3 + \dots + k + (k+1) = \frac{(k+1)(k+2)}{2}.$$En partant du membre de gauche de $P(k+1)$ :$$\begin{aligned}1 + 2 + \dots + k + (k+1)&= \left(1 + 2 + \dots + k\right) + (k+1) \\ &= \frac{k(k+1)}{2} + (k+1) \quad &&\text{(d’après l’hypothèse de récurrence)}\\ &= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} \\ &= \frac{(k+1)(k+2)}{2}.\end{aligned}$$Ainsi, $P(k+1)$ est vraie.

Comme $P(1)$ est vraie et que $P(k) \Rightarrow P(k+1)$ pour tout entier $k \ge 1$, d’après le principe de récurrence, $P(n)$ est vraie pour tout entier $n \ge 1$.

Compétences à pratiquer

Démontrer des inégalités par récurrence
Démontrer par récurrence des sommes de puissances
Démontrer par récurrence des propriétés des suites
Démontrer par récurrence des propriétés de divisibilité

XV R\'{e}vision \& Au-del\`{a}

Compétences à pratiquer

Quiz

Aller à la section