Logique propositionnelle et quantificateurs

Logique propositionnelle et quantificateurs

### 1. Propositions et connecteurs logiques

Une proposition est un énoncé qui est soit vrai (V), soit faux (F), mais jamais les deux. On combine des propositions $P$, $Q$ à l'aide de connecteurs logiques :

| Connecteur | Notation | Lecture |
|---|---|---|
| Négation | $\text{non } P$ ou $\overline{P}$ | "il est faux que $P$" |
| Conjonction | $P \wedge Q$ | "$P$ et $Q$" |
| Disjonction | $P \vee Q$ | "$P$ ou $Q$" (inclusif) |
| Implication | $P \Rightarrow Q$ | "$P$ implique $Q$" |
| Équivalence | $P \Leftrightarrow Q$ | "$P$ équivaut à $Q$" |

### 2. Tables de vérité

Point clé sur l'implication : $P \Rightarrow Q$ n'est fausse que dans le seul cas où $P$ est vraie et $Q$ est fausse. En particulier, si $P$ est fausse, $P \Rightarrow Q$ est automatiquement vraie, quelle que soit la valeur de $Q$ (on dit que "le faux implique n'importe quoi").

### 3. Implication, contraposée, réciproque

Pour une implication $P \Rightarrow Q$, on distingue trois énoncés associés :

- Réciproque : $Q \Rightarrow P$ (n'a en général pas la même valeur de vérité que $P \Rightarrow Q$).
- Contraposée : $\overline{Q} \Rightarrow \overline{P}$. C'est une proposition logiquement équivalente à $P \Rightarrow Q$ (même table de vérité) : $(P \Rightarrow Q) \Leftrightarrow (\overline{Q} \Rightarrow \overline{P})$.

Exemple : $P$ : "$x = 2$", $Q$ : "$x^2 = 4$". L'implication $P \Rightarrow Q$ est vraie. La réciproque $Q \Rightarrow P$ est fausse (car $x = -2$ vérifie $Q$ mais pas $P$). La contraposée "$x^2 \neq 4 \Rightarrow x \neq 2$" est vraie, comme attendu puisqu'elle équivaut à $P \Rightarrow Q$.

### 4. Lois de De Morgan et négation des connecteurs

Pour nier une proposition composée, on applique les règles suivantes :

Justification de la dernière règle : $P \Rightarrow Q$ est équivalente à $\overline{P} \vee Q$ (vérifiable par table de vérité). Donc :

Exemple : La négation de "il pleut $\Rightarrow$ je prends un parapluie" est "il pleut et je ne prends pas de parapluie" (et non pas "il ne pleut pas $\Rightarrow$ je ne prends pas de parapluie", qui est une erreur fréquente).

### 5. Quantificateurs universel et existentiel

- Quantificateur universel $\forall$ : $\forall x \in E,\ P(x)$ signifie "pour tout élément $x$ de $E$, $P(x)$ est vraie".
- Quantificateur existentiel $\exists$ : $\exists x \in E,\ P(x)$ signifie "il existe (au moins) un élément $x$ de $E$ tel que $P(x)$ est vraie".
- On note parfois $\exists! x$ pour "il existe un unique $x$".

Exemple : $\forall x \in \mathbb{R},\ x^2 \geq 0$ (vraie). $\exists x \in \mathbb{R},\ x^2 = -1$ (fausse, car aucun réel n'a un carré négatif).

### 6. Négation des propositions quantifiées

La négation échange les quantificateurs et nie la proposition finale :

Exemple : Nier "$\forall x \in \mathbb{R},\ x \geq 0 \Rightarrow x^2 \geq 1$" donne, en utilisant aussi la négation de l'implication (section 4) :

(c'est vrai : $x = 0{,}5$ convient.)

### 7. Quantificateurs multiples et ordre des quantificateurs

Lorsqu'une proposition contient plusieurs quantificateurs, l'ordre est crucial et ne peut pas être échangé sans changer le sens de l'énoncé.

Piège classique : comparons

Dans le premier énoncé ($\forall \exists$), $y$ peut dépendre de $x$ : pour chaque $x$, on a le droit de choisir un $y$ différent. Dans le second ($\exists \forall$), $y$ est choisi une fois pour toutes, avant $x$, et doit convenir simultanément pour tous les $x$. Le second énoncé est plus fort : il implique le premier, mais la réciproque est fausse en général.

Exemple concret : Soit $E = F = \mathbb{R}$ et $R(x,y)$ : "$y > x$".
- $\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y > x$ : vraie (pour chaque $x$, on prend $y = x+1$).
- $\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ y > x$ : fausse (aucun réel $y$ ne peut être strictement supérieur à tous les réels $x$, en particulier pas à $y$ lui-même, ni à $y+1$).

Cet exemple montre bien que $\exists \forall \Rightarrow \forall \exists$, mais pas l'inverse.

### 8. Négation d'une proposition à quantificateurs multiples

On applique la règle de négation (section 6) successivement, de gauche à droite :

Exemple : Nier $\forall \varepsilon > 0,\ \exists N \in \mathbb{N},\ \forall n \geq N,\ |u_n| < \varepsilon$ (définition de $u_n \to 0$) donne :

C'est exactement la méthode systématique utilisée pour nier les définitions $\varepsilon$-$\delta$ rencontrées en analyse.