1. Propositions et connecteurs
Une proposition est un énoncé vrai ou faux. On combine les propositions avec : la négation \(\overline{P}\), la conjonction \(P\wedge Q\), la disjonction \(P\vee Q\), l'implication \(P\Rightarrow Q\) et l'équivalence \(P\Leftrightarrow Q\).
- \(P\Rightarrow Q\) est fausse seulement quand \(P\) est vraie et \(Q\) fausse.
- \((P\Rightarrow Q)\Leftrightarrow(\overline{P}\vee Q)\).
- Négation d'une implication : \(\overline{P\Rightarrow Q}\Leftrightarrow 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)\) ».
Pour nier, on échange \(\forall\) et \(\exists\) et on nie la propriété : \(\overline{\forall x,\ P(x)}\Leftrightarrow\exists x,\ \overline{P(x)}\).
L'ordre des quantificateurs compte : « \(\forall x,\ \exists y,\ y > x\) » est vraie, « \(\exists y,\ \forall x,\ y > x\) » est fausse dans \(\mathbb{R}\).
3. Raisonnements
- Direct : de \(P\) on déduit \(Q\).
- Contraposée : on montre \(\overline{Q}\Rightarrow\overline{P}\) au lieu de \(P\Rightarrow Q\).
- Absurde : on suppose le contraire et on obtient une contradiction.
- Disjonction des cas : on étudie séparément chaque cas possible.
- Équivalences successives.
- Contre-exemple : un seul cas suffit pour réfuter une proposition universelle.
- Récurrence : initialisation \(P(n_0)\) puis hérédité \(P(n)\Rightarrow P(n + 1)\).
Exemple (récurrence)
Montrons que \(2^n\ge n + 1\) pour tout \(n\in\mathbb{N}\). Pour \(n = 0\) : \(1\ge1\). Si \(2^n\ge n + 1\), alors \(2^{n+1}\ge2n + 2\ge n + 2\). La propriété est vraie pour tout \(n\).