05. Logique des Prédicats

Limites de la logique propositionnelle

La logique propositionnelle, malgré son utilité, ne peut pas exprimer certains raisonnements fondamentaux.

Exemple: Le syllogisme aristotélicien

Considérons l’argument classique:

1. Tous les hommes sont mortels.
2. Socrate est un homme.
3. Donc, Socrate est mortel.

En logique propositionnelle, on ne peut qu’écrire:

$$ p, q \models r $$

où $p$, $q$, $r$ sont des propositions atomiques indépendantes. La structure interne des propositions — le fait que “Socrate” apparaît dans (2) et (3) — est invisible.

Autres limitations

La logique propositionnelle ne peut pas exprimer:

• Relations: “Jean est plus grand que Pierre”
• Quantification: “Tout nombre a un successeur”
• Propriétés partagées: “Quelque chose est à la fois rouge et rond”

Pour ces expressions, nous avons besoin d’un langage plus riche: la logique des prédicats du premier ordre (LPO).

Le langage de la logique du premier ordre

Signature

Une signature $\Sigma$ spécifie le vocabulaire non logique:

• Symboles de constantes: $a, b, c, \dots$ (objets spécifiques)
• Symboles de fonctions: $f, g, h, \dots$ avec leur arité $n \geq 1$
• Symboles de prédicats (relations): $P, Q, R, \dots$ avec leur arité $n \geq 1$

Exemple (arithmétique):

• Constantes: $0$
• Fonctions: $s$ (successeur, arité 1), $+, \times$ (arité 2)
• Prédicats: $=, <$ (arité 2)

Alphabet logique

En plus de la signature, on utilise:

• Variables: $x, y, z, \dots$ (ensemble dénombrable)
• Connecteurs: $\neg, \land, \lor, \rightarrow, \leftrightarrow$
• Quantificateurs: $\forall$ (universel), $\exists$ (existentiel)
• Symboles auxiliaires: parenthèses, virgules

Termes

Définition inductive

Les termes représentent les objets du domaine. Ils sont définis inductivement:

1. Base:

   • Toute variable $x$ est un terme.
   • Toute constante $c$ est un terme.

2. Induction:

   • Si $f$ est un symbole de fonction d’arité $n$ et $t_1, \dots, t_n$ sont des termes, alors $f(t_1, \dots, t_n)$ est un terme.

3. Clôture: Rien d’autre n’est un terme.

Exemples

Avec la signature arithmétique:

• $0$ (constante)
• $x$ (variable)
• $s(0)$ (représente 1)
• $s(s(0))$ (représente 2)
• $+(x, s(0))$ ou $x + 1$ en notation infixe
• $\times(s(s(0)), x)$ ou $2 \times x$

Termes clos

Un terme est clos (ou ground) s’il ne contient aucune variable.

Exemples:

• $s(s(0))$ est clos
• $+(x, s(0))$ n’est pas clos

Les termes clos désignent des objets spécifiques; les termes avec variables désignent des objets dépendant de l’interprétation des variables.

Formules atomiques

Définition

Une formule atomique est de la forme:

$$ P(t_1, \dots, t_n) $$

où $P$ est un symbole de prédicat d’arité $n$ et $t_1, \dots, t_n$ sont des termes.

Exemples

• $Homme(socrate)$ — “Socrate est un homme”
• $PlusGrand(x, y)$ — “x est plus grand que y”
• $=(+(x, y), +(y, x))$ — “$x + y = y + x$” (en notation infixe: $x + y = y + x$)
• $<(x, s(x))$ — “$x < x + 1$”

Égalité

Le symbole $=$ est généralement traité comme un prédicat logique spécial, présent dans toute signature. On écrit $t_1 = t_2$ en notation infixe.

Formules bien formées

Définition inductive

Les formules bien formées (FBF) de la logique du premier ordre:

1. Base: Toute formule atomique est une FBF.

2. Connecteurs: Si $\varphi$ et $\psi$ sont des FBF, alors:

   • $(\neg\varphi)$
   • $(\varphi \land \psi)$
   • $(\varphi \lor \psi)$
   • $(\varphi \rightarrow \psi)$
   • $(\varphi \leftrightarrow \psi)$

   sont des FBF.

3. Quantificateurs: Si $\varphi$ est une FBF et $x$ une variable, alors:

   • $(\forall x , \varphi)$
   • $(\exists x , \varphi)$

   sont des FBF.

4. Clôture: Rien d’autre n’est une FBF.

Exemples

$$ \begin{aligned} &Homme(socrate) \ &\forall x (Homme(x) \rightarrow Mortel(x)) \ &\exists y , PlusGrand(y, jean) \ &\forall x , \exists y (y = s(x)) \ &\forall x , \forall y ((x < y) \rightarrow \exists z (x < z \land z < y)) \end{aligned} $$

Variables libres et liées

Portée d’un quantificateur

La portée de $\forall x$ (ou $\exists x$) dans $\forall x , \varphi$ (ou $\exists x , \varphi$) est la formule $\varphi$.

Variables liées

Une occurrence d’une variable $x$ est liée si elle est dans la portée d’un quantificateur $\forall x$ ou $\exists x$.

Variables libres

Une occurrence d’une variable $x$ est libre si elle n’est pas liée.

Définition formelle

L’ensemble $FV(\varphi)$ des variables libres de $\varphi$ est défini inductivement:

$$ \begin{aligned} FV(P(t_1, \dots, t_n)) &= \bigcup_{i=1}^n Var(t_i) \ FV(\neg\varphi) &= FV(\varphi) \ FV(\varphi \circ \psi) &= FV(\varphi) \cup FV(\psi) \quad (\circ \in {\land, \lor, \rightarrow, \leftrightarrow}) \ FV(\forall x , \varphi) &= FV(\exists x , \varphi) = FV(\varphi) \setminus {x} \end{aligned} $$

où $Var(t)$ est l’ensemble des variables apparaissant dans le terme $t$.

Exemples

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

• $x$ est liée (les deux occurrences)
• $y$ est libre

Dans $\exists x , P(x) \land Q(x)$:

• La première occurrence de $x$ dans $P(x)$ est liée
• L’occurrence de $x$ dans $Q(x)$ est libre (si on interprète comme $(\exists x , P(x)) \land Q(x)$)

Formules closes (Énoncés)

Une formule est close (ou est un énoncé) si elle n’a pas de variables libres.

$$ FV(\varphi) = \emptyset $$

Seuls les énoncés ont une valeur de vérité déterminée dans une structure donnée.

Substitution

Définition

La substitution d’un terme $t$ pour une variable $x$ dans une formule $\varphi$, notée $\varphi[t/x]$, remplace toutes les occurrences libres de $x$ par $t$.

Définition formelle

$$ \begin{aligned} P(t_1, \dots, t_n)[t/x] &= P(t_1[t/x], \dots, t_n[t/x]) \ (\neg\varphi)[t/x] &= \neg(\varphi[t/x]) \ (\varphi \circ \psi)[t/x] &= \varphi[t/x] \circ \psi[t/x] \ (\forall y , \varphi)[t/x] &= \begin{cases} \forall y , \varphi & \text{si } y = x \ \forall y , (\varphi[t/x]) & \text{si } y \neq x \text{ et } y \notin Var(t) \ \forall z , (\varphi[z/y][t/x]) & \text{sinon, avec } z \text{ fraîche} \end{cases} \end{aligned} $$

Capture de variables

La substitution doit éviter la capture de variables libres.

Exemple problématique:

$$ (\forall y , (x < y))[y/x] $$

Une substitution naïve donnerait $\forall y , (y < y)$, ce qui change le sens. La variable libre $y$ a été “capturée” par le quantificateur.

Solution: Renommer la variable liée avant substitution:

$$ (\forall z , (x < z))[y/x] = \forall z , (y < z) $$

Terme libre pour une variable

Un terme $t$ est libre pour $x$ dans $\varphi$ si aucune variable de $t$ ne devient capturée lors de la substitution $\varphi[t/x]$.

Formalisation d’énoncés

Méthodologie

Pour traduire un énoncé en langage naturel:

1. Identifier le domaine de discours.
2. Choisir les symboles de prédicats et de fonctions.
3. Traduire les quantificateurs (“tous”, “certains”, “aucun”).
4. Structurer les connecteurs.

Exemples

1. “Tous les hommes sont mortels.”

Domaine: êtres vivants Prédicats: $H(x)$ = “x est un homme”, $M(x)$ = “x est mortel”

$$ \forall x (H(x) \rightarrow M(x)) $$

2. “Certains oiseaux ne volent pas.”

$$ \exists x (Oiseau(x) \land \neg Vole(x)) $$

3. “Tout nombre a un successeur.”

$$ \forall x , \exists y (y = s(x)) $$

4. “Il existe un plus petit nombre naturel.”

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

5. “Personne n’aime tout le monde.”

$$ \neg \exists x , \forall y , Aime(x, y) $$

ou équivalemment:

$$ \forall x , \exists y , \neg Aime(x, y) $$

Arbre syntaxique

Pour la formule $\forall x (P(x) \rightarrow \exists y , R(x, y))$:

        ∀x
         |
         →
        / \
     P(x)  ∃y
            |
         R(x,y)

Ordre de la logique

Premier ordre

En logique du premier ordre, les quantificateurs portent uniquement sur les individus (éléments du domaine).

On peut quantifier: $\forall x , P(x)$, où $x$ est une variable d’individu.

Ordre supérieur

En logique du second ordre, on peut quantifier sur les prédicats et fonctions:

$$ \forall P , (P(0) \land \forall x (P(x) \rightarrow P(s(x)))) \rightarrow \forall x , P(x) $$

(Axiome d’induction dans sa forme complète)

La logique du premier ordre est plus limitée mais a de meilleures propriétés méta-théoriques (complétude, compacité).