Propositions logiques

Une proposition est un énoncé vrai ou faux (pas les deux).

Connecteurs logiques :

Connecteur	Notation	Vrai quand
Et	$P \land Q$	$P$ et $Q$ tous les deux vrais
Ou	$P \lor Q$	Au moins l’un vrai
Non	$\lnot P$	$P$ est faux
Implique	$P \Rightarrow Q$	$P$ vrai implique $Q$ vrai
Équivaut	$P \Leftrightarrow Q$	$P$ et $Q$ même valeur

Implication et réciproque

$P \Rightarrow Q$ est fausse uniquement si $P$ est vraie et $Q$ est fausse.

Énoncé	Forme
Direct	$P \Rightarrow Q$
Réciproque	$Q \Rightarrow P$
Contraposée	$\lnot Q \Rightarrow \lnot P$
Contre-exemple	Un cas où $P$ est vraie et $Q$ fausse

La contraposée de $P \Rightarrow Q$ est équivalente à $P \Rightarrow Q$ .

Quantificateurs

Pour tout : $\forall x \in E,\; P(x)$ — vrai si $P(x)$ vraie pour chaque $x$
Il existe : $\exists x \in E,\; P(x)$ — vrai s’il existe au moins un $x$

Négations :

$\lnot(\forall x,\; P(x)) \equiv \exists x,\; \lnot P(x)$ $\lnot(\exists x,\; P(x)) \equiv \forall x,\; \lnot P(x)$

Raisonnement par l’absurde

Pour prouver $P$ :

Supposer $\lnot P$
Déduire une contradiction
Conclure que $P$ est vraie

Exemple : $\sqrt{2}$ est irrationnel.

Supposons $\sqrt{2} = \dfrac{p}{q}$ en forme irréductible. Alors $2q^2 = p^2$ → $p$ pair → $p = 2k$ → $q^2 = 2k^2$ → $q$ pair : contradiction avec pgcd $(p,q)=1$ .

Raisonnement par récurrence

Pour prouver $P(n)$ pour tout $n \geq n_0$ :

Initialisation : Vérifier $P(n_0)$
Hérédité : Supposer $P(n)$ vraie, montrer $P(n+1)$
Conclusion : $P(n)$ vraie pour tout $n \geq n_0$

Exemple : Montrer $\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$

Init. : $n=1$ : $1 = \dfrac{1\times2}{2}$ ✓
Hérédité : $\displaystyle\sum_{k=1}^{n+1} k = \frac{n(n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2}$ ✓