Logique et raisonnement

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 contraposée — Flowchart

flowchart TD
    O["Objectif : prouver P ⟹ Q"] --> C{"Difficile\ndirectement ?"}
    C -->|Oui| K["Stratégie : contraposée\n¬Q ⟹ ¬P"]
    C -->|Non| D["Preuve directe\nP est vraie → montrer Q"]
    K --> H["Supposer ¬Q\n(Q est fausse)"]
    H --> I["Déduire ¬P\n(P doit être fausse)"]
    I --> Z["Conclusion :\n¬Q ⟹ ¬P\néquivaut à P ⟹ Q ✓"]
    D --> Z2["Conclusion : P ⟹ Q ✓"]

Raisonnement par l’absurde

Pour prouver $P$ :

1. Supposer $\lnot P$
2. Déduire une contradiction
3. 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$ :

1. Initialisation : Vérifier $P(n_0)$
2. Hérédité : Supposer $P(n)$ vraie, montrer $P(n+1)$
3. 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}$ ✓