Théorie du module : Logique

Quantificateurs logiques

Les connecteurs logiques ne sont pas les seuls "petits mots" importants dans les textes mathématiques : il ne faut pas oublier les quantificateurs "\(\forall\)" et "\(\exists\)".

(a) Quantificateurs universel et existentiel

"\(\forall\)" est le quantificateur universel qui signifie "pour tout", tandis que "\(\exists\)" est le quantificateur existentiel qui signifie "il existe (au moins un)".

Par exemple, la formule

\(\forall x\, :\, x+1>0\)

signifie que pour tout objet \(x\), on a \(x+1>0\), ou encore que quelle que soit la valeur prise par \(x\), on a \(x+1>0\). D'autre part, la formule

\(\exists\, x\, :\, x+30<15\)

signifie qu'il existe au moins une valeur de \(x\) telle que \(x+30<15\).

Pour pouvoir déterminer si ces formules sont vraies ou fausses, il faut fixer l'univers du discours, c'est-à-dire préciser quel est l'ensemble des valeurs possibles de la variable quantifiée. Ainsi, la formule

\(\exists\, x\, :\, x+30<15\)

est vraie si l'ensemble des valeurs permises pour \(x\) est \(\mathbb{R}\) ou \(\mathbb{Z}\), mais elle est fausse si cet ensemble est \(\mathbb{N}\).

(b) Ordre des quantificateurs

Lorsqu'on manipule des affirmations avec quantificateurs, il importe de veiller à ne pas permuter l'ordre des quantificateurs.

Par exemple, l'affirmation suivante signifie que tout nombre réel a un opposé :

\(\forall x\in\mathbb{R},\, \exists\, y\in\mathbb{R}\, :\, x+y=0.\)

Cette affirmation est bien vraie dans \(\mathbb{R}\) (il suffit que \(y=-x\); ces \(y\) diffèrent donc suivant \(x\)). Par contre l'affirmation

\(\exists\, y\in\mathbb{R},\, \forall x\in\mathbb{R}\, :\, x+y=0\)

est fausse. Elle signifie en effet qu'il existerait un nombre réel \(y\) qui serait un absorbant pour l'addition : ajouté à n'importe quel nombre réel \(x\), il donnerait toujours une somme égale à zéro. Un tel nombre réel \(y\) n'existe pas.

On peut cependant permuter l'ordre des quantificateurs si ceux-ci sont identiques et l'un à côté de l'autre.

Par exemple, l'affirmation

\(\forall n\in\mathbb{N},\, \forall m\in\mathbb{N}\, :\, n\neq 0\Rightarrow n+m>m\)

est équivalente à l'affirmation

\(\forall m\in\mathbb{N},\, \forall n\in\mathbb{N}\, :\, n\neq 0\Rightarrow n+m>m.\)

(c) Négation des quantificateurs

La négation du quantificateur universel est le quantificateur existentiel et la négation du quantificateur existentiel est le quantificateur universel. Ainsi, pour nier une proposition contenant des quantificateurs, on nie les quantificateurs et on nie l'affirmation qui les suit :

la négation de "\(\exists\, x\, :\, P(x)\)" est "\(\forall x\, : \neg P(x)\)"
la négation de "\(\forall x\, :\, P(x)\)" est "\(\exists\, x\, : \neg P(x)\)"

Théorie