1. Propositions et connecteurs
Une proposition est un énoncé qui est soit vrai, soit faux. On lui associe une valeur de vérité (\(V\) ou \(F\)).
| \(P\) | \(Q\) | \(\overline{P}\) | \(P\wedge Q\) | \(P\vee 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 |
\(P\Rightarrow Q\) est équivalente à \(\overline{P}\vee Q\). Sa contraposée est \(\overline{Q}\Rightarrow\overline{P}\) ; sa réciproque est \(Q\Rightarrow P\).
Lois de Morgan
\[\overline{P\wedge Q}\Leftrightarrow\overline{P}\vee\overline{Q} \qquad \overline{P\vee Q}\Leftrightarrow\overline{P}\wedge\overline{Q}\]
2. Quantificateurs
- \(\forall x\in E,\ P(x)\) : « pour tout \(x\) de \(E\), \(P(x)\) ».
- \(\exists x\in E,\ P(x)\) : « il existe au moins un \(x\) de \(E\) tel que \(P(x)\) » ; \(\exists!\) : « il existe un unique ».
Négations : \(\overline{\forall x,\ P(x)}\Leftrightarrow\exists x,\ \overline{P(x)}\) et \(\overline{\exists x,\ P(x)}\Leftrightarrow\forall x,\ \overline{P(x)}\).
L'ordre des quantificateurs différents compte : \(\forall x\in\mathbb{R},\ \exists y\in\mathbb{R},\ y > x\) est vraie, mais \(\exists y\in\mathbb{R},\ \forall x\in\mathbb{R},\ y > x\) est fausse.
3. Types de raisonnement
- Raisonnement direct : on part des hypothèses et on enchaîne des implications.
- Contraposée : pour montrer \(P\Rightarrow Q\), on montre \(\overline{Q}\Rightarrow\overline{P}\).
- Par l'absurde : on suppose la négation de la conclusion et on aboutit à une contradiction.
- Contre-exemple : pour montrer qu'une proposition \(\forall x,\ P(x)\) est fausse, il suffit d'un \(x\) vérifiant \(\overline{P(x)}\).
- Disjonction des cas : on étudie séparément tous les cas possibles.
- Équivalences successives.
Récurrence : si \(P(n_0)\) est vraie et si, pour tout \(n\ge n_0\), \(P(n)\Rightarrow P(n + 1)\), alors \(P(n)\) est vraie pour tout \(n\ge n_0\).
Exemple de récurrence
Montrons que \(\forall n\ge1,\ 1 + 2 + \dots + n = \frac{n(n + 1)}{2}\). Initialisation : pour \(n = 1\), \(1 = \frac{1\times2}{2}\). Hérédité : si \(1 + \dots + n = \frac{n(n + 1)}{2}\), alors \(1 + \dots + n + (n + 1) = \frac{n(n + 1)}{2} + n + 1 = \frac{(n + 1)(n + 2)}{2}\).