Propositions et connecteurs
Définition Définition
Une proposition est un énoncé mathématique qui est soit vrai (V), soit faux (F), jamais les deux.
>> Exemple : « $\sqrt{9}=3$ » est vraie ; « $2>5$ » est fausse.
| $P$ | $Q$ | $\neg P$ | $P\wedge Q$ | $P\vee Q$ | $P\Rightarrow Q$ | $P\iff 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 |
Remarque Remarque
- La négation de $P$ se note $\neg P$ (on lit « non $P$ »).
- « $P\wedge Q$ » (et) est vraie seulement si les deux sont vraies.
- « $P\vee Q$ » (ou) est vraie si au moins une est vraie.
[!] « $P\Rightarrow Q$ » est fausse uniquement quand $P$ est vraie et $Q$ fausse.
Lois logiques
Formules Formules
$\neg(\neg P)\iff P$ ; $\neg(P\wedge Q)\iff\neg P\vee\neg Q$ ; $\neg(P\vee Q)\iff\neg P\wedge\neg Q$ (lois de Morgan)
- $(P\Rightarrow Q)\iff\left(\neg P\vee Q\right)$ ; donc $\neg(P\Rightarrow Q)\iff P\wedge\neg Q$.
- Contraposée : $(P\Rightarrow Q)\iff\left(\neg Q\Rightarrow\neg P\right)$.
- $(P\iff Q)\iff\left[(P\Rightarrow Q)\wedge(Q\Rightarrow P)\right]$.
Quantificateurs
Définition Définitions
- $(\forall x\in E)\ P(x)$ : « pour tout $x$ de $E$, $P(x)$ est vraie ».
- $(\exists x\in E)\ P(x)$ : « il existe au moins un $x$ de $E$ tel que $P(x)$ ».
- $(\exists!x\in E)\ P(x)$ : « il existe un unique $x$ … ».
Méthode Négation d'une proposition quantifiée
On échange $\forall$ et $\exists$, et on nie la propriété : la négation de « $(\forall x\in E)\ P(x)$ » est « $(\exists x\in E)$ : non $P(x)$ ».
>> Exemple : la négation de $(\forall x\in\mathbb{R})\ x^2\geq0$ est $(\exists x\in\mathbb{R})\ x^2<0$.
Erreur fréquente Attention à l'ordre
$(\forall x)(\exists y)\ x+y=0$ est vraie ($y=-x$) ; mais $(\exists y)(\forall x)\ x+y=0$ est fausse.
Les raisonnements
Méthode Raisonnement par équivalences successives
On transforme la proposition par des $\iff$ jusqu'à une proposition vraie (souvent : un carré $\geq0$).
>> $a^2+b^2\geq2ab\iff(a-b)^2\geq0$ : vrai.
Méthode Raisonnement par contraposée
Pour montrer $P\Rightarrow Q$, on montre $\neg Q\Rightarrow\neg P$.
>> « $n^2$ pair $\Rightarrow$ $n$ pair » : on montre « $n$ impair $\Rightarrow$ $n^2$ impair ».
Méthode Raisonnement par l'absurde
On suppose que la proposition à démontrer est fausse, et on aboutit à une contradiction.
>> Exemple classique : $\sqrt{2}\notin\mathbb{Q}$.
Méthode Raisonnement par disjonction des cas
On sépare les cas couvrant toutes les possibilités ($n$ pair / impair ; $x\geq a$ / $x<a$…).
Méthode Contre-exemple
Pour montrer qu'une proposition « $\forall$ » est fausse, il suffit d'un contre-exemple.
Théorème Raisonnement par récurrence
Soit $P(n)$ une propriété et $n_0\in\mathbb{N}$. Si :
- Initialisation : $P(n_0)$ est vraie ;
- Hérédité : pour tout $n\geq n_0$, $P(n)\Rightarrow P(n+1)$ ;
[!] alors $P(n)$ est vraie pour tout $n\geq n_0$.
À retenir À retenir
- Négation : $\forall\leftrightarrow\exists$, « et » $\leftrightarrow$ « ou », « $<$ » $\leftrightarrow$ « $\geq$ ».
- $\neg(P\Rightarrow Q)$ est « $P$ et $\neg Q$ » (ce n'est pas une implication).
- Récurrence : ne jamais oublier l'initialisation.
Astuce Astuce
Si l'énoncé contient « $\neq$ » dans la conclusion (comme $f(a)\neq f(b)$), pensez à la contraposée : on part d'une égalité, plus facile à manipuler.