tite fractale

Calcul des prédicats

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.

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 :

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.

2.1.2.2. Carrés positifs

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

2.1.3. Remarques

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

3 logicians walk into a bar.
Barman: Would you all like a drink?
1st logician: I don't know.
2nd logician: I don't know.
3rd logician: YES!

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.

2.2.2.2. Carrés positifs

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

2.2.3. Remarques

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




Christophe Gragnic, le 06/11/2015, 22h13'44".






Page générée le 04/12/2016, 10h08'07" (source).
historique de la page
historique global

 TogetherJS