1. Propositions
Une proposition est un énoncé qui est soit vrai (V), soit faux (F), mais pas les deux.
Exemples : « \(2+3=5\) » est vraie ; « \(\sqrt{2}\in\mathbb{Q}\) » est fausse.
2. Connecteurs logiques
- Négation \(\overline{P}\) (non \(P\)) : vraie si \(P\) est fausse.
- Conjonction \(P \wedge Q\) (\(P\) et \(Q\)) : vraie si les deux sont vraies.
- Disjonction \(P \vee Q\) (\(P\) ou \(Q\)) : vraie si au moins l'une est vraie.
- Implication \(P \Rightarrow Q\) : fausse uniquement si \(P\) est vraie et \(Q\) fausse.
- Équivalence \(P \Leftrightarrow Q\) : vraie si \(P\) et \(Q\) ont la même valeur de vérité.
| \(P\) | \(Q\) | \(P\wedge Q\) | \(P\vee Q\) | \(P\Rightarrow Q\) | \(P\Leftrightarrow Q\) |
|---|---|---|---|---|---|
| V | V | V | V | V | V |
| V | F | F | V | F | F |
| F | V | F | V | V | F |
| F | F | F | F | V | V |
Lois de Morgan
Implication et contraposée
3. Quantificateurs
- \(\forall\) : « pour tout ». \(\exists\) : « il existe ». \(\exists!\) : « il existe un unique ».
- Négation : \(\overline{\forall x \in E,\ P(x)} \Leftrightarrow \exists x \in E,\ \overline{P(x)}\) et \(\overline{\exists x \in E,\ P(x)} \Leftrightarrow \forall x\in E,\ \overline{P(x)}\).
4. Types de raisonnement
Raisonnement direct
On part de \(P\) vraie et on déduit \(Q\).
Raisonnement par contraposée
Pour montrer \(P\Rightarrow Q\), on montre \(\overline{Q} \Rightarrow \overline{P}\). Exemple : montrer que si \(n^2\) est pair alors \(n\) est pair. Contraposée : si \(n\) est impair, \(n = 2k+1\), alors \(n^2 = 4k^2+4k+1 = 2(2k^2+2k)+1\) est impair.
Raisonnement par l'absurde
On suppose le contraire de ce qu'on veut montrer et on aboutit à une contradiction.
Raisonnement par disjonction des cas
Exemple : \(n(n+1)\) est pair pour tout \(n\in\mathbb{N}\) (étudier \(n\) pair puis \(n\) impair).
Contre-exemple
Pour montrer qu'une proposition « \(\forall x,\ P(x)\) » est fausse, il suffit d'un \(x\) qui ne la vérifie pas.
Raisonnement par équivalence
On transforme l'énoncé par des équivalences successives.
Raisonnement par récurrence
Pour montrer \(P(n)\) pour tout \(n \ge n_0\) : on vérifie \(P(n_0)\) (initialisation), puis on montre que \(P(n) \Rightarrow P(n+1)\) (hérédité).
Exemple : \(1+2+\dots+n = \frac{n(n+1)}{2}\).