Logique et raisonnement mathématique
1.1 Propositions et connecteurs logiques
Une proposition est un énoncé qui est soit vrai (V), soit faux (F), jamais les deux.
| Connecteur | Notation | Vrai quand… |
|---|---|---|
| Négation | $\neg P$ | $P$ est fausse |
| Conjonction | $P \wedge Q$ | $P$ et $Q$ sont vraies |
| Disjonction | $P \vee Q$ | $P$ ou $Q$ (ou les deux) est vraie |
| Implication | $P \Rightarrow Q$ | Fausse uniquement si $P$ vraie et $Q$ fausse |
| Équivalence | $P \Leftrightarrow Q$ | $P$ et $Q$ ont la même valeur de vérité |
Table de vérité de l'implication :
| $P$ | $Q$ | $P \Rightarrow Q$ |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | V |
| F | F | V |
1.2 Les lois fondamentales
$$\neg(P \wedge Q) \equiv \neg P \vee \neg Q \qquad \neg(P \vee Q) \equiv \neg P \wedge \neg Q \quad \text{(lois de De Morgan)}$$
$$(P \Rightarrow Q) \equiv (\neg Q \Rightarrow \neg P) \quad \text{(contraposée)} \qquad \neg(P \Rightarrow Q) \equiv P \wedge \neg Q$$
⚠️ Contraposée ≠ réciproque. La réciproque de $P \Rightarrow Q$ est $Q \Rightarrow P$ : elle n'a aucune raison d'être vraie. La contraposée, elle, est toujours équivalente à l'implication de départ.
1.3 Les quantificateurs
| Quantificateur | Lecture |
|---|---|
| $\forall x \in E$ | « pour tout $x$ de $E$ » (universel) |
| $\exists x \in E$ | « il existe au moins un $x$ de $E$ » (existentiel) |
| $\exists !\, x \in E$ | « il existe un unique $x$ » |
Négation d'une proposition quantifiée — la règle la plus testée en examen :
$$\neg\big(\forall x \in E,\; P(x)\big) \equiv \exists x \in E,\; \neg P(x)$$ $$\neg\big(\exists x \in E,\; P(x)\big) \equiv \forall x \in E,\; \neg P(x)$$
📌 L'ordre des quantificateurs change le sens : $\forall x, \exists y, \; y > x$ est vrai dans $\mathbb{R}$, alors que $\exists y, \forall x, \; y > x$ est faux (il n'existe pas de réel plus grand que tous les autres).
1.4 Les types de raisonnement
| Raisonnement | Principe |
|---|---|
| Direct | On part des hypothèses et on déduit la conclusion |
| Par contraposée | Pour montrer $P \Rightarrow Q$, on montre $\neg Q \Rightarrow \neg P$ |
| Par l'absurde | On suppose $\neg Q$ et on aboutit à une contradiction |
| Par disjonction de cas | On découpe l'ensemble des possibilités et on traite chaque cas |
| Par contre-exemple | Pour réfuter $\forall x, P(x)$, il suffit d'un seul $x$ tel que $P(x)$ est faux |
| Par récurrence | Initialisation ($P(n_0)$ vraie) + hérédité ($P(n) \Rightarrow P(n+1)$) ⟹ $P(n)$ vraie $\forall n \geq n_0$ |
Exercice 1
- Écrivez la négation de : « Tous les clients de l'entreprise ont réglé leur facture. »
- Écrivez la négation de : $\forall x \in \mathbb{R},\; x^2 + 1 > 0$. Cette négation est-elle vraie ?
- Donnez la contraposée et la réciproque de : « Si une entreprise est cotée en bourse, alors elle est une société anonyme. » Laquelle est nécessairement vraie si l'implication l'est ?
- Démontrez par récurrence que pour tout $n \geq 1$ : $$1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$$
Voir le corrigé
1) « Il existe au moins un client de l'entreprise qui n'a pas réglé sa facture. » ⚠️ Erreur classique à éviter : « aucun client n'a réglé » — c'est beaucoup trop fort. La négation de « tous » est « il existe au moins un… qui ne… pas ».
2) Négation : $\exists x \in \mathbb{R},\; x^2 + 1 \leq 0$. Elle est fausse : pour tout réel, $x^2 \geq 0$ donc $x^2 + 1 \geq 1 > 0$. La proposition initiale est donc vraie.
3) Soit $P$ : « l'entreprise est cotée en bourse », $Q$ : « c'est une SA ».
- Contraposée : « Si une entreprise n'est pas une SA, alors elle n'est pas cotée en bourse. » → nécessairement vraie si l'implication l'est.
- Réciproque : « Si une entreprise est une SA, alors elle est cotée en bourse. » → fausse : la plupart des SA marocaines ne sont pas cotées à la Bourse de Casablanca.
4) Démonstration par récurrence. Soit $P(n)$ : $\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$.
Initialisation ($n=1$) : $$\text{Membre de gauche} = 1 \quad ; \quad \text{Membre de droite} = \frac{1 \times 2}{2} = 1 \quad \Rightarrow \quad P(1) \text{ vraie}$$
Hérédité : supposons $P(n)$ vraie pour un $n \geq 1$ fixé. Alors : $$\sum_{k=1}^{n+1} k = \underbrace{\sum_{k=1}^{n} k}_{\text{hypothèse}} + (n+1) = \frac{n(n+1)}{2} + (n+1)$$ $$= (n+1)\left(\frac{n}{2} + 1\right) = (n+1) \cdot \frac{n+2}{2} = \frac{(n+1)\big((n+1)+1\big)}{2}$$ C'est exactement $P(n+1)$. L'hérédité est établie.
Conclusion : $P(1)$ est vraie et $P$ est héréditaire, donc par récurrence $P(n)$ est vraie pour tout $n \geq 1$. $\blacksquare$
Exercice 2 — Négations et récurrence
- Écrivez la négation de : a) « $\forall x \in \mathbb{R},\; x^2 \geq 0$ » ; b) « $\exists n \in \mathbb{N},\; n > 100$ » ; c) « S'il pleut, alors je prends mon parapluie ».
- Donnez la contraposée et la réciproque de : « Si un nombre est divisible par 4, alors il est pair ». Laquelle est vraie ?
- Montrez par récurrence que, pour tout $n \geq 1$ : $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$.
Voir le corrigé
1) a) $\exists x \in \mathbb{R},\; x^2 < 0$ ; b) $\forall n \in \mathbb{N},\; n \leq 100$ ; c) « Il pleut et je ne prends pas mon parapluie ».
2) Contraposée : « Si un nombre n'est pas pair, il n'est pas divisible par 4 » (vraie). Réciproque : « Si un nombre est pair, il est divisible par 4 » (fausse : 6 est pair mais non divisible par 4).
3) Initialisation : pour $n = 1$, $1 = \dfrac{1 \times 2}{2}$ ✓. Hérédité : si $1 + \dots + n = \dfrac{n(n+1)}{2}$, alors $1 + \dots + n + (n+1) = \dfrac{n(n+1)}{2} + (n+1) = \dfrac{(n+1)(n+2)}{2}$ ✓. La propriété est vraie pour tout $n \geq 1$.
L'essentiel — Logique
- Connecteurs : $\neg P$, $P \wedge Q$, $P \vee Q$, $P \Rightarrow Q$ (fausse seulement si $P$ vraie et $Q$ fausse), $P \Leftrightarrow Q$.
- De Morgan : $\neg(P \wedge Q) \equiv \neg P \vee \neg Q$ ; $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$.
- Contraposée : $(P \Rightarrow Q) \equiv (\neg Q \Rightarrow \neg P)$ ; la réciproque $Q \Rightarrow P$ n'est pas équivalente.
- $\neg(P \Rightarrow Q) \equiv P \wedge \neg Q$.
- Négation : $\neg(\forall x, P(x)) \equiv \exists x, \neg P(x)$ et $\neg(\exists x, P(x)) \equiv \forall x, \neg P(x)$ ; l'ordre des quantificateurs compte.
- Raisonnements : direct, contraposée, absurde, disjonction de cas, contre-exemple, récurrence (initialisation + hérédité).