1. Prédicats

« $n$ est pair » n’est pas une proposition. Pour que cela en soit une, il nous faut connaître la valeur de $n$.

On notera $P(n)$: « $n$ est pair ».

Pour chaque $n$, on obtient une proposition.

• si $n=0$, $P(0)$: « $0$ est pair »
  • qui au passage est vraie,
• si $n=117$, $P(117)$: « $117$ est pair »,
  • qui au passage est fausse,
• …

De la même façon que si $f$ est définie par $f(x)=2x$, elle permet, pour chaque $x$, d’obtenir un nombre. La notation avec les parenthèses est donc cohérente avec celle des fonctions (quelque part, les prédicats sont des fonctions).

Remarque :

Certaines propositions peuvent dépendre de deux valeurs. Exemple :

En notant $P(m, n)$: « $n$ est un diviseur de $m$ », on a :

• $P(19, 3)$ est fausse,
• $P(396, 11)$ est vraie,
• …

Les deux valeurs peuvent ne pas appartenir au même ensemble.

2. Quantificateurs

2.1. Quantificateur universel

2.1.1. Définition

Si $E$ est un ensemble et $P$ un prédicat dépendant d’une valeur de $E$, alors

« Pour tout $x$ de $E$, $P(x)$ est vraie. »

est une proposition. On la notera :

$$\forall x \in E, P(x)$$

ou

$$\forall x, x \in E; P(x)$$

On pourra dire aussi : « Quel que soit $x$ dans $E$, $P(x)$ ».

2.1.2. Exemples

2.1.2.1. Pommes mûres

Toutes les pommes de cet arbre sont mûres.

• $E$ est l’ensemble des pommes de l’arbre
• $x$ est une pomme
• $P(x)$: « $x$ est mûre »

2.1.2.2. Carrés positifs

Tous les nombres réels ont leur carré positif.

• $E$ est l’ensemble des nombres réels : $\mathbb R$
• $x$ est un nombre réel
• $P(x)$: « $x^2$ est positif »

2.1.3. Remarques

• $\forall$ est un A à l’envers, A pour all en anglais ou alles en allemand.
• Ce quantificateur permet de traduire « aucun… » ou « tous… ».
• La variable utilisée, ici $x$, est dite muette. On aurait pu utiliser tout autre symbole :

$$\left(\forall x \in E, P(x)\right) \Leftrightarrow \left(\forall \lambda \in E, P(\lambda)\right) $$

2.2. Quantificateur existentiel

2.2.1. Définition

Si $E$ est un ensemble et $P$ un prédicat dépendant d’une valeur de $E$, alors

« Il existe un $x$ de $E$, tel que $P(x)$ est vraie. »

est une proposition. On la notera :

$$\exists x \in E, P(x)$$

ou

$$\exists x, x \in E; P(x)$$

On pourra dire aussi : « Il y a au moins un $x$ de $E$, tel que $P(x)$ est vraie. »

2.2.2. Exemples

2.2.2.1. Poires jaunes

Il existe une poire dans cet arbre qui est jaune.

• $E$ est l’ensemble des poires de l’arbre
• $x$ est une poire
• $P(x)$: « $x$ est jaune »

2.2.2.2. Carrés positifs

$x^2 = 64$ a au moins une solution réelle.

• $E$ est l’ensemble des nombres réels : $\mathbb R$
• $x$ est un nombre réel
• $P(x)$: « $x^2 = 64$ »

2.2.3. Remarques

• $\exists$ est un E à l’envers, E pour exists en anglais ou existieren en allemand.
• Ce quantificateur permet de traduire « certains… ».
• La variable utilisée est aussi muette.

3. Négation des quantificateurs

3.1. Sur les exemples

3.1.1. Pommes

« Toutes les pommes sont mûres », noté « $\forall x \in E, P(x)$ » a pour contraire

« Au moins une pomme n’est pas mûre », ou « Il existe une pomme qui n’est pas mûre », noté « $\exists x \in E, \overline{P(x)}$ ».

De même, le contraire de toujours n'est pas jamais.

3.1.2. Poires

De même pour les poires :

« Il existe une poire qui est jaune », noté « $\exists x \in E, P(x)$ » a pour contraire

« Toutes les poires ne sont pas jaumes », ou « Aucune poire n’est jaune », noté « $\forall x \in E, \overline{P(x)}$ ».

3.2. Formules de négation des quantificateurs

C’est une généralisation des lois de De Morgan. Voir l’article sur Wikipedia et le cours sur ce site.

$$ \overline{\forall x \in E, P(x)} \Leftrightarrow \exists x \in E, \overline{P(x)} $$

$$ \overline{\exists x \in E, P(x)} \Leftrightarrow \forall x \in E, \overline{P(x)} $$

3.3. Autre propriété

Si $P$ est un prédicat à deux variables,

$$ \forall x \in E, \forall y \in F, P(x, y) \Leftrightarrow \forall y \in F, \forall x \in E, P(x, y) $$

et

$$ \exists x \in E, \exists y \in F, P(x, y) \Leftrightarrow \exists y \in F, \exists x \in E, P(x, y) $$

Contre-exemple

$\forall x \in \mathbb R, \exists y \in \mathbb R, y = x$ est vraie,

$\exists y \in \mathbb R, \forall x \in \mathbb R, y = x$ est fausse.

Aller aux exercices