Formules en logique des prédicats avec quantificateurs

1. Les limites de la logique propositionnelle

Imaginez que vous souhaitiez formaliser la phrase "Tous les étudiants en informatique connaissent Python". En logique propositionnelle, vous seriez contraint de créer une proposition pour chaque étudiant : Etudiant1_connait_Python ∧ Etudiant2_connait_Python ∧ .... Cette approche est non seulement fastidieuse mais surtout impossible si le nombre d'étudiants est infini ou non connu. La structure interne de l'énoncé est perdue.

La logique des prédicats résout ce problème en introduisant trois nouveaux concepts : les objets, les prédicats et les quantificateurs.

La vidéo suivante, issue du cours d'Intelligence Artificielle de Stanford, explique de manière très claire pourquoi ce saut conceptuel est nécessaire.

2. La syntaxe de la logique du premier ordre

Pour construire des formules, nous avons besoin d'un vocabulaire et d'une grammaire précis. Votre formation en informatique vous rendra familier avec cette approche de définition formelle d'un langage.

Un langage du premier ordre se compose de :

1. Termes : expressions qui désignent des objets.
   • Constantes : symboles qui représentent des objets spécifiques (ex: alice, 0, null).
   • Variables : symboles qui agissent comme des conteneurs pour des objets (ex: $x,y,z$).
   • Fonctions : symboles qui, appliqués à des termes, produisent un nouveau terme (ex: successeur(x), somme(a, b)).
2. Formules : expressions qui ont une valeur de vérité (vrai ou faux).
   • Formules atomiques : un prédicat (symbole de relation) appliqué à des termes. Un prédicat exprime une propriété ou une relation entre des objets (ex: Etudiant(x), PlusGrandQue(y, 0)).
   • Formules complexes : construites à partir de formules atomiques en utilisant les connecteurs logiques que nous connaissons ($\neg ,\wedge ,\vee ,\Rightarrow ,\iff$).
   • Formules quantifiées : construites en appliquant un quantificateur ($\forall$ pour "pour tout", $\exists$ pour "il existe") à une variable dans une formule.

L'image suivante présente une grammaire formelle, similaire à la notation BNF (Backus-Naur Form), qui résume la construction des formules.

Pour une présentation détaillée de cette syntaxe, je vous invite à visionner la section suivante de la vidéo de Stanford.

Pour une définition encore plus formelle, digne d'un cours de préparation à l'Agrégation, vous pouvez vous référer au document suivant.

3. Traduire le langage naturel en formules logiques

Le cœur de cette leçon est d'apprendre à traduire des énoncés en français vers le langage formel des prédicats. Cette compétence est essentielle pour spécifier des propriétés d'algorithmes ou de systèmes.

Les deux règles d'or de la traduction

La principale difficulté réside dans le choix du connecteur à associer à chaque quantificateur.

1. Le quantificateur universel ($\forall$) s'associe presque toujours à l'implication ($\Rightarrow$).

   • "Tous les A sont B" se traduit par $\forall x(A(x)\Rightarrow B(x))$.
   • Signification : "Pour n'importe quel objet $x$, si $x$ a la propriété A, alors il a aussi la propriété B."
   • Erreur courante : Le traduire par $\forall x(A(x)\wedge B(x))$. Cela signifierait "Tout objet dans l'univers est à la fois un A et un B", ce qui est une affirmation beaucoup plus forte et généralement fausse.

2. Le quantificateur existentiel ($\exists$) s'associe presque toujours à la conjonction ($\wedge$).

   • "Certains A sont B" (ou "Il existe un A qui est B") se traduit par $\exists x(A(x)\wedge B(x))$.
   • Signification : "Il existe au moins un objet $x$ qui a à la fois la propriété A et la propriété B."
   • Erreur courante : Le traduire par $\exists x(A(x)\Rightarrow B(x))$. Cette formule est vraie dès qu'il existe un objet qui n'est pas un A, la rendant "trivialement vraie" et inutile dans la plupart des cas.

Le tableau suivant résume ces patrons de traduction fondamentaux.

La vidéo de Stanford explique ces règles de manière très pédagogique avec des exemples pertinents.

Importance de l'ordre des quantificateurs

L'ordre dans lequel les quantificateurs apparaissent change radicalement le sens de la formule. $\forall x\exists y$ n'est pas équivalent à $\exists y\forall x$.

• $\forall x\in \text{Humains},\exists y\in \text{Humains},\text{EstMeˋreDe}(y,x)$
  • "Pour chaque humain $x$, il existe un humain $y$ tel que $y$ est la mère de $x$." (Vrai)
• $\exists y\in \text{Humains},\forall x\in \text{Humains},\text{EstMeˋreDe}(y,x)$
  • "Il existe un humain $y$ qui, pour chaque humain $x$, est la mère de $x$." (Faux, cela impliquerait une mère universelle).

La vidéo française ci-dessous insiste sur ce point, et sur la bonne pratique de noter la dépendance (ex: $y_x$) pour ne pas l'oublier lors d'une démonstration.

4. Exercices de traduction

Mettons maintenant en pratique ces concepts. Le document suivant est une feuille de travaux dirigés classique. Nous allons nous en servir pour nous exercer.

Le contexte est un modèle simplifié du système solaire.

• Prédicats :
  • Px : $x$ est une planète.
  • Mxy : $x$ est plus petit ou aussi grand que $y$.
  • Sxy : $x$ est plus proche du Soleil ou à égale distance que $y$.
• Constantes :
  • t : la Terre.
  • j : Jupiter.
  • m1 : Mercure.

Votre tâche : Traduisez les phrases suivantes en logique du premier ordre. Prenez quelques instants pour écrire votre solution avant de consulter la correction.

1. Certaines planètes sont plus petites que la Terre.
2. Toutes les planètes sont plus petites que Saturne (constante s1).
3. Mercure est la planète la plus proche du Soleil. (Indice : Pensez à comment exprimer "la plus").
4. Si quelque chose est plus éloigné du Soleil que Pluton (constante p), alors ce n’est pas une planète.

Pour vous exercer davantage, je vous recommande de faire les autres questions de l'Exercice 1 du document LINK et de vérifier vos réponses avec le corrigé fourni.

Conclusion

Aujourd'hui, nous avons acquis un langage formel extrêmement puissant. Vous êtes maintenant capable de prendre une phrase ambiguë en langage naturel et de la traduire en une formule logique précise et sans équivoque.

Points clés à retenir :

• La logique des prédicats enrichit la logique propositionnelle avec les variables, constantes, fonctions, prédicats et quantificateurs.
• Les quantificateurs $\forall$ ("pour tout") et $\exists$ ("il existe") permettent de faire des affirmations sur des ensembles d'objets.
• La traduction suit des règles précises : $\forall$ s'utilise avec $\Rightarrow$, et $\exists$ s'utilise avec $\wedge$.
• L'ordre des quantificateurs est crucial et change le sens d'une formule.
• Les lois de De Morgan s'étendent aux quantificateurs : $\neg \forall xP(x)\iff \exists x\neg P(x)$ et $\neg \exists xP(x)\iff \forall x\neg P(x)$.

Dans notre prochaine leçon, nous allons utiliser ce nouveau langage pour aborder un domaine fondamental de l'informatique et des mathématiques : la théorie des ensembles. Nous apprendrons à définir formellement ce qu'est un ensemble et à démontrer des propriétés ensemblistes (comme l'inclusion, l'union, l'intersection) par manipulation formelle, en utilisant la logique des prédicats comme outil de preuve.