Premier ordre : le langage

Ce que le calcul propositionnel ne sait pas dire

« Tous les étudiants aiment la logique. Paul est un étudiant. Donc Paul aime la logique. » Le raisonnement est correct, mais le calcul propositionnel ne le voit pas : il ne peut que donner une variable à chaque phrase, $p$, $q$, $r$, et $\{p, q\} \vDash r$ est faux. Ce qui rend le raisonnement correct est à l'intérieur des phrases : un objet (Paul), des propriétés (être étudiant, aimer la logique), et le mot « tous ».

La logique du premier ordre (ou calcul des prédicats) ajoute ce qu'il faut pour parler des objets : des noms d'objets, des fonctions, des propriétés et des relations, et deux quantificateurs, « pour tout » et « il existe ».

Les ingrédients

La signature

On choisit d'abord le vocabulaire du domaine dont on parle, la signature :

• des constantes : des noms d'objets précis, comme $a$, $\mathit{paul}$, $0$ ;
• des symboles de fonction, chacun avec son arité (son nombre d'arguments) : $f$ d'arité 1, $+$ d'arité 2, $\textit{mère}$ d'arité 1 ;
• des symboles de prédicat, avec leur arité : $\mathit{Etud}$ d'arité 1 (« est un étudiant »), $\mathit{Aime}$ d'arité 2 (« aime »), $<$ d'arité 2.

On dispose en plus d'une infinité de variables : $x$, $y$, $z$, $x_1$…

Les termes

Les termes désignent des objets :

1. une variable ou une constante est un terme ;
2. si $f$ est un symbole de fonction d'arité $n$ et $t_1, \ldots, t_n$ des termes, $f(t_1, \ldots, t_n)$ est un terme.

Exemples : $x$, $\mathit{paul}$, $\textit{mère}(\mathit{paul})$, $f(x, g(a))$. Un terme n'est ni vrai ni faux : il désigne quelque chose.

Les formules

1. Si $P$ est un symbole de prédicat d'arité $n$ et $t_1, \ldots, t_n$ des termes, $P(t_1, \ldots, t_n)$ est une formule, dite atomique. On admet souvent aussi l'égalité $t_1 = t_2$.
2. Si $A$ et $B$ sont des formules, $\lnot A$, $A \land B$, $A \lor B$, $A \to B$ et $A \leftrightarrow B$ en sont.
3. Si $A$ est une formule et $x$ une variable, $\forall x\, A$ (« pour tout $x$, $A$ ») et $\exists x\, A$ (« il existe $x$ tel que $A$ ») en sont.

Exemple : $\forall x\, (\mathit{Etud}(x) \to \mathit{Aime}(x, \mathit{log}))$ dit « tout étudiant aime la logique ».

La portée d'un quantificateur

Un quantificateur porte, comme $\lnot$, sur la formule la plus courte qui le suit. $\forall x\, P(x) \to Q(x)$ se lit donc $(\forall x\, P(x)) \to Q(x)$, et le dernier $x$ n'est pas concerné par le $\forall$. Pour qu'il le soit, on écrit $\forall x\, (P(x) \to Q(x))$.

Variables libres et liées

Définition

Dans $\forall x\, A$ ou $\exists x\, A$, la formule $A$ est la portée du quantificateur. Une occurrence d'une variable $x$ est liée si elle se trouve dans la portée d'un quantificateur sur $x$ ; elle est alors liée par le plus proche. Sinon, elle est libre.

Une variable est libre dans une formule si elle y a au moins une occurrence libre. Une formule sans variable libre est close : c'est une affirmation qui sera vraie ou fausse. Une formule avec des variables libres est plutôt une propriété de ces variables : $\exists y\, (x = 2 \times y)$ dit « $x$ est pair », et n'est ni vraie ni fausse tant que $x$ n'est pas fixé.

Le renommage

Le nom d'une variable liée n'a pas d'importance : $\forall x\, P(x)$ et $\forall y\, P(y)$ disent la même chose, comme $\sum_{i=1}^n i$ et $\sum_{j=1}^n j$. On peut donc renommer une variable liée, avec un nom neuf (qui n'apparaît pas dans la portée), sans changer le sens.

On s'en sert pour qu'aucune variable ne soit à la fois libre et liée, ni liée par deux quantificateurs : dans l'exemple, $\forall u\, (P(u) \to \exists y\, R(u, y)) \land Q(x, z)$. Chaque nom n'a plus qu'un rôle.

La substitution

Définition

$A[x := t]$ désigne la formule obtenue en remplaçant, dans $A$, toutes les occurrences libres de $x$ par le terme $t$. Les occurrences liées ne bougent pas : elles désignent un autre $x$.

La capture

La substitution a un piège. Soit $A = \exists y\, (y > x)$, « il existe un nombre plus grand que $x$ », vraie pour tout $x$ dans les entiers. Remplaçons $x$ par $y$ :

Le $y$ qu'on voulait introduire a été capturé par $\exists y$ : la formule dit maintenant « un nombre est plus grand que lui-même », fausse. Le sens a changé.

La règle : avant de substituer, renommer les variables liées de $A$ qui apparaissent dans $t$. Ici, on renomme d'abord $y$ en $z$ : $\exists z\, (z > x)$, puis on substitue : $\exists z\, (z > y)$. On dit que $t$ est libre pour $x$ dans $A$ quand aucune variable de $t$ ne se ferait capturer.