06. Quantificateurs

Sémantique des quantificateurs

Les quantificateurs $\forall$ et $\exists$ permettent d’exprimer des propriétés portant sur tous les éléments ou certains éléments d’un domaine.

Structures d’interprétation

Une structure (ou interprétation, ou modèle) $\mathcal{M}$ pour une signature $\Sigma$ consiste en:

1. Un ensemble non vide $D$, le domaine (ou univers).
2. Pour chaque constante $c$: un élément $c^\mathcal{M} \in D$.
3. Pour chaque fonction $f$ d’arité $n$: une fonction $f^\mathcal{M}: D^n \rightarrow D$.
4. Pour chaque prédicat $P$ d’arité $n$: une relation $P^\mathcal{M} \subseteq D^n$.

Assignation de variables

Une assignation est une fonction $s: Var \rightarrow D$ qui associe à chaque variable un élément du domaine.

Notation: $s[x \mapsto d]$ est l’assignation identique à $s$ sauf que $x$ est associé à $d$.

Le quantificateur universel $\forall$

Sémantique

$$ \mathcal{M}, s \models \forall x , \varphi \iff \text{pour tout } d \in D: \mathcal{M}, s[x \mapsto d] \models \varphi $$

“Pour tout $x$, $\varphi$” est vrai si $\varphi$ est vrai quelle que soit la valeur assignée à $x$.

Intuition

$\forall x , P(x)$ équivaut, pour un domaine fini ${a_1, \dots, a_n}$, à:

$$ P(a_1) \land P(a_2) \land \dots \land P(a_n) $$

Le quantificateur universel est une conjonction généralisée.

Domaine vide

Convention importante: En logique classique standard, le domaine est toujours non vide. Si on autorisait un domaine vide, $\forall x , \varphi$ serait trivialement vrai (pas de contre-exemple possible).

Exemples

$$ \forall x (x = x) $$

“Tout objet est égal à lui-même.” — Vrai dans toute structure.

$$ \forall x (Nombre(x) \rightarrow \exists y (y > x)) $$

“Tout nombre a un successeur.” — Vrai pour $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{R}$.

Le quantificateur existentiel $\exists$

Sémantique

$$ \mathcal{M}, s \models \exists x , \varphi \iff \text{il existe } d \in D: \mathcal{M}, s[x \mapsto d] \models \varphi $$

“Il existe $x$ tel que $\varphi$” est vrai si $\varphi$ est vrai pour au moins une valeur de $x$.

Intuition

$\exists x , P(x)$ équivaut, pour un domaine fini, à:

$$ P(a_1) \lor P(a_2) \lor \dots \lor P(a_n) $$

Le quantificateur existentiel est une disjonction généralisée.

Exemples

$$ \exists x (x > 0 \land x < 1) $$

“Il existe un nombre entre 0 et 1.” — Vrai pour $\mathbb{R}$, faux pour $\mathbb{Z}$.

$$ \exists x , \forall y (x \leq y) $$

“Il existe un plus petit élément.” — Vrai pour $\mathbb{N}$, faux pour $\mathbb{Z}$.

Interdéfinissabilité

Dualité des quantificateurs

Les deux quantificateurs sont interdéfinissables:

$$ \begin{aligned} \forall x , \varphi &\equiv \neg \exists x , \neg \varphi \ \exists x , \varphi &\equiv \neg \forall x , \neg \varphi \end{aligned} $$

Interprétation:

• “Tout x satisfait $\varphi$” = “Il n’existe pas de x ne satisfaisant pas $\varphi$”
• “Il existe x satisfaisant $\varphi$” = “Il n’est pas vrai que tout x ne satisfait pas $\varphi$”

Choix du quantificateur primitif

On peut prendre $\forall$ comme primitif et définir:

$$ \exists x , \varphi \stackrel{\text{def}}{=} \neg \forall x , \neg \varphi $$

ou vice versa. Les deux approches sont équivalentes.

Négation des quantificateurs

Règles fondamentales

$$ \begin{aligned} \neg \forall x , \varphi &\equiv \exists x , \neg \varphi \ \neg \exists x , \varphi &\equiv \forall x , \neg \varphi \end{aligned} $$

Ces règles généralisent les lois de De Morgan aux quantificateurs.

Application: Négation d’énoncés composés

Exemple 1: Nier “Tous les cygnes sont blancs.”

$$ \neg \forall x (Cygne(x) \rightarrow Blanc(x)) $$

$$ \equiv \exists x , \neg(Cygne(x) \rightarrow Blanc(x)) $$

$$ \equiv \exists x (Cygne(x) \land \neg Blanc(x)) $$

“Il existe un cygne qui n’est pas blanc.”

Exemple 2: Nier “Il existe un nombre premier pair supérieur à 2.”

$$ \neg \exists x (Premier(x) \land Pair(x) \land x > 2) $$

$$ \equiv \forall x , \neg(Premier(x) \land Pair(x) \land x > 2) $$

$$ \equiv \forall x (Premier(x) \land Pair(x) \rightarrow x \leq 2) $$

“Tout nombre premier pair est inférieur ou égal à 2.”

Portée et ordre des quantificateurs

Portée (Scope)

La portée d’un quantificateur est la formule immédiatement quantifiée.

Dans $\forall x (P(x) \rightarrow \exists y , Q(x, y))$:

• Portée de $\forall x$: $(P(x) \rightarrow \exists y , Q(x, y))$
• Portée de $\exists y$: $Q(x, y)$

Quantificateurs imbriqués

L’ordre des quantificateurs de même type n’importe pas:

$$ \begin{aligned} \forall x , \forall y , \varphi &\equiv \forall y , \forall x , \varphi \ \exists x , \exists y , \varphi &\equiv \exists y , \exists x , \varphi \end{aligned} $$

Ordre des quantificateurs différents

L’ordre des quantificateurs de types différents importe généralement:

$$ \forall x , \exists y , \varphi \not\equiv \exists y , \forall x , \varphi $$

Exemple concret:

$$ \forall x , \exists y (y > x) $$

“Pour tout nombre, il existe un nombre plus grand.” — VRAI pour $\mathbb{N}$

$$ \exists y , \forall x (y > x) $$

“Il existe un nombre plus grand que tous les autres.” — FAUX pour $\mathbb{N}$

Règle générale

$$ \exists y , \forall x , \varphi \models \forall x , \exists y , \varphi $$

mais pas l’inverse. L’implication va du plus fort (∃∀) vers le plus faible (∀∃).

Équivalences avec quantificateurs

Distribution sur les connecteurs

Le $\forall$ distribue sur $\land$:

$$ \forall x (\varphi \land \psi) \equiv (\forall x , \varphi) \land (\forall x , \psi) $$

Le $\exists$ distribue sur $\lor$:

$$ \exists x (\varphi \lor \psi) \equiv (\exists x , \varphi) \lor (\exists x , \psi) $$

Non-distribution

Le $\forall$ ne distribue pas sur $\lor$:

$$ \forall x (\varphi \lor \psi) \not\equiv (\forall x , \varphi) \lor (\forall x , \psi) $$

Contre-exemple: Soit $P(x)$ = “$x$ est pair”, $Q(x)$ = “$x$ est impair”.

• $\forall x (P(x) \lor Q(x))$ est vrai (tout entier est pair ou impair)
• $(\forall x , P(x)) \lor (\forall x , Q(x))$ est faux (tout n’est pas pair, tout n’est pas impair)

Le $\exists$ ne distribue pas sur $\land$:

$$ \exists x (\varphi \land \psi) \not\equiv (\exists x , \varphi) \land (\exists x , \psi) $$

Extraction des quantificateurs

Si $x$ n’est pas libre dans $\psi$:

$$ \begin{aligned} (\forall x , \varphi) \land \psi &\equiv \forall x (\varphi \land \psi) \ (\forall x , \varphi) \lor \psi &\equiv \forall x (\varphi \lor \psi) \ (\exists x , \varphi) \land \psi &\equiv \exists x (\varphi \land \psi) \ (\exists x , \varphi) \lor \psi &\equiv \exists x (\varphi \lor \psi) \end{aligned} $$

Quantificateurs et implication

$$ \begin{aligned} (\forall x , \varphi) \rightarrow \psi &\equiv \exists x (\varphi \rightarrow \psi) \quad \text{si } x \notin FV(\psi) \ \varphi \rightarrow (\forall x , \psi) &\equiv \forall x (\varphi \rightarrow \psi) \quad \text{si } x \notin FV(\varphi) \ (\exists x , \varphi) \rightarrow \psi &\equiv \forall x (\varphi \rightarrow \psi) \quad \text{si } x \notin FV(\psi) \ \varphi \rightarrow (\exists x , \psi) &\equiv \exists x (\varphi \rightarrow \psi) \quad \text{si } x \notin FV(\varphi) \end{aligned} $$

Forme prénexe

Définition

Une formule est en forme prénexe si tous les quantificateurs sont au début:

$$ Q_1 x_1 , Q_2 x_2 , \dots Q_n x_n , \varphi $$

où chaque $Q_i \in {\forall, \exists}$ et $\varphi$ est sans quantificateur (la matrice).

Algorithme de conversion

1. Renommer les variables liées pour éviter les conflits.
2. Éliminer $\rightarrow$ et $\leftrightarrow$.
3. Pousser les négations vers l’intérieur (De Morgan, négation des quantificateurs).
4. Extraire les quantificateurs en utilisant les équivalences.

Exemple

Convertir $\forall x , P(x) \rightarrow \exists y , Q(y)$ en forme prénexe:

$$ \begin{aligned} \forall x , P(x) \rightarrow \exists y , Q(y) &\equiv \neg(\forall x , P(x)) \lor \exists y , Q(y) \ &\equiv \exists x , \neg P(x) \lor \exists y , Q(y) \ &\equiv \exists x (\neg P(x) \lor \exists y , Q(y)) \ &\equiv \exists x , \exists y (\neg P(x) \lor Q(y)) \end{aligned} $$

Quantificateurs bornés

Définition

Les quantificateurs bornés (ou restreints) limitent le domaine de quantification:

$$ \begin{aligned} \forall x \in A , \varphi &\stackrel{\text{def}}{=} \forall x (x \in A \rightarrow \varphi) \ \exists x \in A , \varphi &\stackrel{\text{def}}{=} \exists x (x \in A \land \varphi) \end{aligned} $$

Exemples

$$ \forall x \in \mathbb{N} (x \geq 0) $$

“Tout entier naturel est positif ou nul.”

$$ \exists x \in \mathbb{R} (x^2 = 2) $$

“Il existe un réel dont le carré est 2.”

Quantificateur d’unicité

Notation

Le quantificateur d’unicité “$\exists!$” signifie “il existe un unique”:

$$ \exists! x , \varphi(x) $$

Définition

$$ \exists! x , \varphi(x) \stackrel{\text{def}}{=} \exists x (\varphi(x) \land \forall y (\varphi(y) \rightarrow y = x)) $$

ou de manière équivalente:

$$ \exists! x , \varphi(x) \equiv \exists x , \varphi(x) \land \forall x , \forall y ((\varphi(x) \land \varphi(y)) \rightarrow x = y) $$

Exemple

$$ \exists! x (x + x = x) $$

“Il existe un unique nombre égal à son double.” — Vrai, c’est 0.

Quantification multiple

Patterns courants

“Tout… a un…”:

$$ \forall x , \exists y , R(x, y) $$

“Pour tout x, il existe un y en relation R avec x.”

“Il existe… pour tout…”:

$$ \exists x , \forall y , R(x, y) $$

“Il existe un x en relation R avec tout y.”

“Il existe exactement n…”:

$$ \exists x_1 , \exists x_2 , \dots \exists x_n \left( \bigwedge_{i \neq j} x_i \neq x_j \land \bigwedge_i \varphi(x_i) \land \forall y (\varphi(y) \rightarrow \bigvee_i y = x_i) \right) $$