Mathématiques MPSI

1.1

Logique et modes de raisonnement

Notions : assertions, connecteurs, quantificateurs, négation, contraposée, absurde, analyse-synthèse, récurrences simple, double et forte

Cours

Assertions et connecteurs logiques

Une assertion (ou proposition) est un énoncé mathématique dont on peut dire qu'il est vrai ou faux, sans ambiguïté. « $2 + 2 = 4$ » est une assertion vraie, « $\sqrt{2} \in Q$ » une assertion fausse. Un énoncé qui dépend d'une variable, comme « $x \geq 0$ », est un prédicat : il devient une assertion quand on fixe $x$ .

Définition Connecteurs

À partir de deux assertions $P$ et $Q$ , on construit : la négation $\neg P$ (« non $P$ »), la conjonction $P \land Q$ (« $P$ et $Q$ »), la disjonction $P \lor Q$ (« $P$ ou $Q$ », ou inclusif), l'implication $P \Rightarrow Q$ et l'équivalence $P \Leftrightarrow Q$ . Leurs valeurs de vérité sont données par la table ci-dessous.

$P$	$Q$	$\neg P$	$P \land Q$	$P \lor Q$	$P \Rightarrow 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

L'implication $P \Rightarrow Q$ est donc fausse dans un seul cas : $P$ vraie et $Q$ fausse. En particulier, une implication dont l'hypothèse est fausse est vraie. Par définition, $P \Rightarrow Q$ a la même table que $(\neg P) \lor Q$ . On dit que $P$ est une condition suffisante pour $Q$ , et que $Q$ est une condition nécessaire pour $P$ .

Proposition Règles de calcul

Pour toutes assertions $P, Q, R$  :

double négation : $\neg (\neg P) \Leftrightarrow P$  ;
lois de De Morgan : $\neg (P \land Q) \Leftrightarrow (\neg P) \lor (\neg Q)$ et $\neg (P \lor Q) \Leftrightarrow (\neg P) \land (\neg Q)$  ;
distributivité : $P \land (Q \lor R) \Leftrightarrow (P \land Q) \lor (P \land R)$ et $P \lor (Q \land R) \Leftrightarrow (P \lor Q) \land (P \lor R)$  ;
négation d'une implication : $\neg (P \Rightarrow Q) \Leftrightarrow P \land \neg Q$  ;
contraposée : $(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P)$  ;
double implication : $(P \Leftrightarrow Q) \Leftrightarrow ((P \Rightarrow Q) \land (Q \Rightarrow P))$ .

Démonstration

Chaque équivalence se vérifie sur une table de vérité à 4 ou 8 lignes. Par exemple pour la contraposée : $\neg Q \Rightarrow \neg P$ équivaut à $\neg (\neg Q) \lor \neg P$ , c'est-à-dire à $Q \lor \neg P$ , qui est exactement $P \Rightarrow Q$ . Pour la négation de l'implication : $\neg (\neg P \lor Q) \Leftrightarrow P \land \neg Q$ par De Morgan.

Attention

La réciproque de $P \Rightarrow Q$ est $Q \Rightarrow P$  : elle n'a aucune raison d'être vraie ( $x = 2 \Rightarrow x^{2} = 4$ est vraie, la réciproque est fausse). La contraposée $\neg Q \Rightarrow \neg P$ , elle, est toujours équivalente à l'implication de départ. Et la négation de « $P \Rightarrow Q$ » n'est pas une implication : c'est « $P$ et non $Q$ ».

Quantificateurs

Définition Quantificateurs

Soit $P (x)$ un prédicat portant sur les éléments $x$ d'un ensemble $E$ .

$\forall x \in E, P (x)$ signifie : pour tout élément $x$ de $E$ , $P (x)$ est vraie.
$\exists x \in E, P (x)$ signifie : il existe au moins un élément $x$ de $E$ tel que $P (x)$ soit vraie.
$\exists! x \in E, P (x)$ signifie : il existe un et un seul tel $x$ .

La variable quantifiée est muette : $\forall x \in R, x^{2} \geq 0$ et $\forall t \in R, t^{2} \geq 0$ disent la même chose. En revanche, l'ordre des quantificateurs de natures différentes compte.

Exemple L'ordre change tout

« $\forall x \in R, \exists y \in R, y > x$ » est vraie (prendre $y = x + 1$  : $y$ dépend de $x$ ). « $\exists y \in R, \forall x \in R, y > x$ » est fausse : elle affirme qu'un même réel $y$ est plus grand que tous les réels, y compris lui-même. On peut toujours échanger deux $\forall$ consécutifs, ou deux $\exists$ consécutifs, mais jamais un $\forall$ et un $\exists$ .

Proposition Négation d'une assertion quantifiée

\neg (\forall x \in E, P (x)) ⟺ \exists x \in E, \neg P (x) \neg (\exists x \in E, P (x)) ⟺ \forall x \in E, \neg P (x)

Pour nier une assertion, on échange les $\forall$ et les $\exists$ sans changer leur ordre, puis on nie le prédicat final.

Exemple Nier une définition

« La suite $(u_{n})$ est majorée » s'écrit $\exists M \in R, \forall n \in N, u_{n} \leq M$ . Sa négation, « $(u_{n})$ n'est pas majorée », s'écrit $\forall M \in R, \exists n \in N, u_{n} > M$ . Pour une fonction $f : R \to R$ , « $f$ est croissante » s'écrit $\forall (x, y) \in R^{2}, x \leq y \Rightarrow f (x) \leq f (y)$ , et « $f$ n'est pas croissante » s'écrit $\exists (x, y) \in R^{2}, x \leq y et f (x) > f (y)$ . Attention : « non croissante » ne veut pas dire « décroissante ».

Les modes de raisonnement

Raisonnement direct. Pour montrer $P \Rightarrow Q$ , on suppose $P$ vraie et on en déduit $Q$ . La rédaction commence par « Supposons $P$ . » ou « Soit $x$ tel que… ».

Par contraposée. Pour montrer $P \Rightarrow Q$ , on montre $\neg Q \Rightarrow \neg P$ . Exemple : si $n^{2}$ est pair, alors $n$ est pair. Contraposée : si $n$ est impair, $n = 2 k + 1$ , alors $n^{2} = 2 (2 k^{2} + 2 k) + 1$ est impair.

Par l'absurde. Pour montrer $P$ , on suppose $\neg P$ et on aboutit à une contradiction.

Théorème Irrationalité de $\sqrt{2}$

$\sqrt{2}$ n'est pas un nombre rationnel.

Démonstration

Par l'absurde, supposons $\sqrt{2} = p / q$ avec $p \in Z$ , $q \in N^{*}$ , et la fraction irréductible. Alors $p^{2} = 2 q^{2}$ est pair, donc $p$ est pair (contraposée ci-dessus) : $p = 2 p^{'}$ . Il vient $4 p^{' 2} = 2 q^{2}$ , soit $q^{2} = 2 p^{' 2}$ , donc $q$ est pair aussi. Alors $2$ divise $p$ et $q$ , ce qui contredit l'irréductibilité.

Théorème Euclide

Il existe une infinité de nombres premiers.

Démonstration

Par l'absurde, supposons qu'il n'y en ait qu'un nombre fini $p_{1}, \dots, p_{r}$ . Posons $N = p_{1} p_{2} \dots p_{r} + 1 \geq 2$ . $N$ admet un diviseur premier $p$ (son plus petit diviseur $\geq 2$ est premier), qui est l'un des $p_{i}$ . Alors $p$ divise $N$ et $p_{1} \dots p_{r}$ , donc divise leur différence $1$  : contradiction.

Disjonction de cas. Pour montrer $P$ , on sépare en cas qui recouvrent toutes les possibilités (par exemple $n$ pair / $n$ impair, $x \geq 0$ / $x < 0$ ).

Analyse-synthèse. Pour déterminer tous les objets vérifiant une propriété, on procède en deux temps. Analyse : on suppose qu'un objet convient et on accumule des conditions nécessaires, jusqu'à n'avoir plus qu'un petit nombre de candidats. Synthèse : on vérifie quels candidats conviennent réellement.

Proposition Fonctions paires et impaires

Toute fonction $f : R \to R$ s'écrit de manière unique $f = p + i$ avec $p$ paire et $i$ impaire.

Démonstration

Analyse. Si $f = p + i$ convient, alors $f (- x) = p (x) - i (x)$ . En ajoutant et soustrayant avec $f (x) = p (x) + i (x)$ , on obtient $p (x) = \frac{f (x) + f (- x)}{2}$ et $i (x) = \frac{f (x) - f (- x)}{2}$  : il y a au plus une décomposition (unicité).

Synthèse. Les fonctions $p$ et $i$ ainsi définies sont respectivement paire et impaire, et $p + i = f$  : la décomposition existe. Exemple : $e^{x} = ch x + sh x$ .

Le raisonnement par récurrence

Axiome Principe de récurrence

Soit $n_{0} \in N$ et $P (n)$ un prédicat défini pour $n \geq n_{0}$ . Si $P (n_{0})$ est vraie (initialisation) et si, pour tout $n \geq n_{0}$ , $P (n) \Rightarrow P (n + 1)$ (hérédité), alors $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Ce principe est équivalent à une propriété fondamentale de $N$  : **toute partie non vide de $N$ admet un plus petit élément**. On l'admet.

Exemple Une récurrence simple

Montrons que pour tout $n \in N^{*}$ , $\sum_{k = 1}^{n} k = \frac{n (n + 1)}{2}$ . Notons $P (n)$ cette égalité. Initialisation : pour $n = 1$ , les deux membres valent $1$ . Hérédité : soit $n \geq 1$ tel que $P (n)$ soit vraie. Alors $\sum_{k = 1}^{n + 1} k = \frac{n (n + 1)}{2} + (n + 1) = \frac{(n + 1) (n + 2)}{2}$ , c'est $P (n + 1)$ . Conclusion : $P (n)$ est vraie pour tout $n \geq 1$ .

Théorème Récurrences double et forte

Récurrence double : si $P (n_{0})$ et $P (n_{0} + 1)$ sont vraies, et si pour tout $n \geq n_{0}$ , $(P (n) \land P (n + 1)) \Rightarrow P (n + 2)$ , alors $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Récurrence forte : si $P (n_{0})$ est vraie, et si pour tout $n \geq n_{0}$ , $(P (n_{0}) \land \dots \land P (n)) \Rightarrow P (n + 1)$ , alors $P (n)$ est vraie pour tout $n \geq n_{0}$ .

Démonstration

Pour la récurrence forte, on applique la récurrence simple au prédicat $Q (n)$  : « $P (k)$ est vraie pour tout $k \in [[n_{0}, n]]$ ». $Q (n_{0})$ est $P (n_{0})$ , vraie. Si $Q (n)$ est vraie, l'hypothèse donne $P (n + 1)$ , donc $Q (n + 1)$ . Ainsi $Q (n)$ est vraie pour tout $n$ , et a fortiori $P (n)$ . La récurrence double se traite de même avec $Q (n) = P (n) \land P (n + 1)$ .

Exemple Récurrence forte : décomposition en facteurs premiers

Tout entier $n \geq 2$ est un produit de nombres premiers. Si c'est vrai pour tous les entiers de $[[2, n]]$ , considérons $n + 1$  : soit il est premier (c'est un produit à un facteur), soit $n + 1 = a b$ avec $2 \leq a, b \leq n$ , et il suffit de multiplier les décompositions de $a$ et de $b$ , qui existent par hypothèse. Une récurrence simple ne suffirait pas : on a besoin de $P (a)$ et $P (b)$ , pas de $P (n)$ .

Attention

Une hérédité qui ne fonctionne pas pour tous les $n$ ruine la preuve. Le célèbre « tous les chevaux ont la même couleur » échoue au passage de $n = 1$ à $n = 2$  : les deux groupes de $n$ chevaux utilisés n'ont alors aucun cheval en commun.

Vrai ou faux ? Réponds avant d'ouvrir.

P

est fausse, alors

P \Rightarrow Q

est vraie, quelle que soit

Q

Vrai. C'est la troisième et la quatrième ligne de la table de vérité. « Si $1 = 2$ , alors je suis le pape » est une implication vraie.

La négation de «

\forall ε > 0, \exists N \in N, \forall n \geq N, | u_{n} | \leq ε

» est «

\forall ε > 0, \exists N, \forall n \geq N, | u_{n} | > ε

».

Faux. On n'a pas échangé les quantificateurs. La négation correcte est $\exists ε > 0, \forall N \in N, \exists n \geq N, | u_{n} | > ε$ .

(P \Rightarrow Q)

est équivalente à

(\neg Q \Rightarrow \neg P)

Vrai. C'est la contraposée ; les deux ont la même table de vérité.

Pour montrer qu'une propriété est vraie pour tout

n

, il suffit de la vérifier pour

n = 0, 1, 2, \dots, 10

Faux. Aucun nombre fini de vérifications ne remplace une preuve. $n^{2} + n + 41$ est premier pour $n = 0, \dots, 39$ , mais pas pour $n = 40$  : $40^{2} + 40 + 41 = 41^{2}$ .

Mathématiques MPSI

Fondements

Logique et raisonnements

Logique et modes de raisonnement

Assertions et connecteurs logiques

Quantificateurs

Les modes de raisonnement

Le raisonnement par récurrence