Programmation logique et fonctionnelle – partie D

Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.

La logique du premier ordre

Les activités #.dec (dec pour Découverte) consistent à étudier des présentations explicatives et à traiter tous les exercices de découverte proposés. Si vous ne répondez pas correctement à un exercice de découverte, revenez en arrière pour relire les explications et identifier la cause de votre erreur.

Les activités #.ent (ent pour Entrainement) consistent à traiter des exercices d’entraînement. Vous devez d’abord tenter de traiter ces exercices sans dévoiler d’indice ni regarder la solution. Vous pouvez remonter dans le document pour relire certaines explications ou consulter les solutions des exercices de découverte ou d’entraînement précédemment traités.

Activité de découverte D.dec

Introduction

En logique propositionnelle (partie C), les formules sont constituées de variables, connecteurs logiques ($\vee$, $\wedge$, $\neg$, $\to$, $\leftrightarrow$), de parenthèses, et des constantes $\top$ et $\bot$. Lorsqu’on interprète ces formules, pour déterminer leur valeurs de vérités, on assigne des valeurs de vérité 0 ou 1 (vrai ou faux) à leurs variables.

En logique du premier ordre, les variables peuvent prendre des valeurs diverses et variées (par exemple des entiers naturels, des réels, des symboles) appartenant à un domaine d’interprétation. Ces variables peuvent être liées par des quantificateurs $\forall$ et $\exists$. En plus, un nombre illimité de nouveaux symboles apparaissent : les symboles fonctionnels et les symboles relationnels, aussi appelés symboles de prédicats.

Par convention, nous représenterons les variables du premier ordre par des lettres majuscules ou des mots commençant par une lettre majuscule, alors que les symboles fonctionnels et relationnels seront représentés par des lettres minuscules ou des mots commençant par une lettre minuscule.

Les formules de la logique du premier ordre sont donc beaucoup plus riches que celles de la logique propositionnelle, ce qui leur permet de modéliser beaucoup plus de choses. Mais il va falloir prendre le temps d’assimiler différents concepts avant de parvenir à saisir l’intérêt et la puissance de ce paradigme.

D.dec1 : Les termes fonctionnels

Les termes fonctionnels font partie des briques de construction des formules de la logique du premier ordre. Ils sont construits avec des symboles fonctionnels qui ont vocation à être interprétés comme des fonctions. Mais pour le moment nous les considérerons comme des objets purement syntaxiques.

Définition : Une signature fonctionnelle est un ensemble de symboles ayant chacun une arité, qui est un entier naturel.

Voici un exemple de signature fonctionnelle :

${\text{coul}/1, \text{mix}/2, \text{noir}/0}$

Le symbole $\text{coul}$ est d’arité 1, le symbole $\text{mix}$ est d’arité 2 et le symbole $\text{noir}$ est d’arité 0. Les symboles d’arité 0 sont appelé constantes fonctionnelles.

Définition : On appelle terme fonctionnel compatible avec une signature fonctionnelle $F$ tout terme pouvant être construit de manière inductive avec les règles suivantes :

• Une variable est un terme fonctionnel.
• Une constante fonctionnelle (i.e., un terme fonctionnel d’arité 0) appartenant à $F$ est un terme fonctionnel est un terme fonctionnel compatible avec $F$.
• Si $\mathcal{T}_1, \dots, \mathcal{T}_n$ sont des termes fonctionnels compatibles avec $F$ et $\mathcal{S}$ un symbole fonctionnel d’arité $n$ appartenant à $F$, alors $\mathcal{S}(\mathcal{T}_1, \dots, \mathcal{T}_n)$ est un terme fonctionnel compatible avec $F$.

Voici quelques exemples de termes fonctionnels compatibles avec la signature fonctionnelle ${\text{coul}/1, \text{mix}/2, \text{noir}/0}$ :

$X, ~ \text{coul}(X), ~ \text{mix}(\text{noir}, \text{coul}(\text{coul}(Y)))$

Exercice de découverte D.dec.x1

Parmi les expressions suivantes, quel sont les termes fonctionnels compatibles avec la signature ${\text{coul}/1, \text{mix}/2, \text{noir}/0}$ ?

• $\text{noir} $
• $\text{coul}(\text{coul (Y)} ) $
• $\text{coul}(\text{coul (noir)} ) $
• $Y$
• $\text{mix(X,Y)} $
• $\text{mix}(\text{noir}, \text{noir}) $
• $\text{mix}(\text{mix}(X,\text{noir} ) ) $
• $X(\text{noir} )$

D.dec2 : Les atomes

Les atomes font partie des briques de construction des formules de la logique du premier ordre. Ils sont construits avec des symboles relationnels qui ont vocation à être interprétés comme des prédicats, c’est à dire des fonctions à valeurs dans ${\text{vrai},\text{faux}}$. Mais pour le moment nous les considérerons comme des objets purement syntaxiques.

Définition : Une signature relationnelle est un ensemble de symboles ayant chacun une arité, qui est un entier naturel.

Voici un exemple de signature relationnelle :

${\text{arc}/2, \text{source}/1}$

Les symboles $\text{arc}$ et $\text{source}$ sont d’arités respectives 2 et 1. Les symboles d’arité 0 sont appelés variables propositionnelles. Ce sont en fait les variables de la logique propositionnelles introduites dans la partie C.

Définition : On appelle signature tout couple $(F,R)$ où $F$ est une signature fonctionnelle et $R$ une signature relationnelle telles que $F \cap R$ est vide.

Définition : On appelle atome compatible avec une signature $S=(F,R)$ tout terme pouvant être construit de manière inductive avec les règles suivantes :

• Un symbole relationnel d’arité 0 appartenant à la signature relationnelle $R$ est un atome compatible avec $S$.
• Si $\mathcal{T}_1, \dots, \mathcal{T}_n$ sont des termes fonctionnels compatibles avec la signature fonctionnelle $F$ et si est $\mathcal{R}$ un symbole relationnel d’arité $n$ appartenant à la signature relationnelle $R$, alors $\mathcal{R}(\mathcal{T}_1, \dots, \mathcal{T}_n)$ est un atome compatible avec $S$.

Voici quelques exemples d’atomes compatibles avec la signature $({\text{coul}/1}, {\underline{\text{arc}}/2, \underline{\text{source}}/1})$ :

$\text{arc}(X,Y), ~ \text{source}(\text{coul}(X), ~ \text{arc}(\text{coul}(Y),Z) $

Exercice de découverte D.dec.x2

Parmi les expressions suivantes, quel sont les atomes compatibles avec la signature $({\text{coul}/1}, {\underline{\text{arc}}/2, \underline{\text{source}}/1})$ ? (Les symboles relationnels ont été soulignés.)

• $\text{arc}(X) $
• $\text{coul}(Y) $
• $\text{coul}(\text{arc}(X,Y) ) $
• $\text{arc}(X,\text{coul(X)} ) $
• $\text{source}(\text{coul}(\text{coul}(X) ) ) $
• $Z$

D.dec3 : Interprétation d’une signature

Les symboles fonctionnels et relationnels ne sont… que des symboles tant qu’on ne leur donne pas une interprétation.

Une interprétation donne un sens à chaque symbole relationnel et chaque symbole fonctionnel d’une signature.

Une interprétation d’une signature $(F,R)$ est constituée :

• D’un domaine d’interprétation qui est un ensemble non vide $D$.
• Pour chaque chaque constante fonctionnelle $\mathcal{F}/0\in F $, d’une valeur de $D$.
• Pour chaque symbole fonctionnel d’arité non nulle $\mathcal{F}/n \in F$, d’une application de $D^n$ dans $D$.
• Pour chaque symbole relationnel $R/0 \in R$, d’une valeur de vérité 0 ou 1.
• Pour chaque symbole relationnel d’arité non nulle $\mathcal{R}/n $, d’une application de $D^n$ dans ${\text{vrai},\text{faux}}$.

On associe donc à chaque constante fonctionnelle une valeur du domaine d’interprétation, à chaque symbole fonctionnel d’arité non nulle une fonction, à chaque symbole relationnel un prédicat (ou de manière équivalente, une relation) et à chaque symbole relationnel d’arité 0 une valeur de vérité.

Voici deux exemples concrets d’interprétations d’une même signature :

$S = ({\text{zero}/0, \text{plus}/2 },{\underline{\text{egal}}/2 })$

Interprétation 1 :

• Le domaine d’interprétation est l’ensemble $\mathbb{N}$ des entiers naturels.
• Le symbole $\text{zero}$ représente l’entier 0. (Attention, pas la valeur faux.)
• Le symbole $\text{plus}$ représente la fonction somme standard qui à tout couple $(x,y)$ d’entiers naturels associe $x+y$.
• Le symbole $\text{egal}$ représente la relation d’égalité standard : $\text{egal}(x,y)$ est vrai si et seulement si $x=y$ au sens usuel de l’égalité entre entiers naturels.

Interprétation 2 :

• Le domaine d’interprétation est l’ensemble ${0,1,2}$.
• Le symbole $\text{zero}$ représente l’entier 0. (Attention, pas la valeur faux.)
• Le symbole $\text{plus}$ représente la fonction somme modulo 3 qui à tout couple $(x,y)$ d’entiers naturels associe $(x+y) \mod 3$.
• Le symbole $\text{egal}$ représente la relation d’égalité standard : $\text{egal}(x,y)$ est vrai si et seulement si $x=y$ au sens usuel de l’égalité entre entiers naturels.

Exercice de découverte D.dec.x3

Combien y a t-il d’interprétations différentes de la signature $S = ({\text{zero}/0 },{\underline{\text{egal}}/2 })$ ayant l’ensemble ${1,2}$ comme domaine d’interprétation ?

D.dec4 : Interprétation des termes fonctionnels

On appelle valuation d’un ensemble $V$ de variables sur un domaine d’interprétation $D$ toute application de $V$ dans $D$. En d’autre termes, une valuation assigne à chaque variable un élément du domaine d’interprétation.

Étant donnés :

• un terme fonctionnel $f$,
• une interprétation $I$ des symboles fonctionnels apparaisant dans $f$,
• une valuation $A$ des variables apparaissant dans le terme $f$,

L’interprétation de $f$ pour la valuation $A$ consiste à déterminer la valeur $\text{Val}(f,A)$ par induction d’après les règles suivantes :

• La valeur d’une constante fonctionnelle est celle qui lui est assignée par l’interprétation $I$.
• La valeur d’une variable est celle qui lui est assignée par la valuation $A$.
• Pour tout symbole $\mathcal{F}/n$ ayant pour interprétation la fonction $\text{Val}_ \mathcal{F}$, $\text{Val}(\mathcal{F}(f_1,…,f_n),A)$ $=$ $\text{Val}_ \mathcal{F}(\text{Val}(f_1,A),…,\text{Val}(f_n,A))$.

Exemple :

On considère la signature fonctionnelle ${\text{zero}/0, \text{plus}/2 }$ et l’interprétation suivante de cette signature :

**Interprétation 1 ** :

• Le domaine d’interprétation est l’ensemble $\mathbb{N}$ des entiers naturels.
• Le symbole $\text{zero}$ représente l’entier 0. (Attention, pas la valeur faux.)
• Le symbole $\text{plus}$ représente la fonction somme standard qui à tout couple $(x,y)$ d’entiers naturels associe $x+y$.

Soit le terme fonctionnel $f = \text{plus}(\text{plus}(\text{zero},X),Y))$ et la valuation $A = {(X,1), (Y,2)}$.

L’interprétation de $f$ pour $A$ est 3 car :

• $\text{Val}(\text{zero},A) = 0$,
• $\text{Val}(X,A) = 1$
• $\text{Val}(Y,A) = 2$
• $\text{Val}(\text{plus}(\text{zero},X),A) = 1$

En termes informels, interpréter un terme fonctionnel consiste à déterminer sa valeur à partir des valeurs de ses variables et des fonctions assignées à ses symboles fonctionnels par leur interprétation.

Exercice de découverte D.dec.x4

Donnez la valeur du terme fonctionnel $f = \text{plus}(\text{plus}(\text{zero},X),Y)$ pour la valuation $A = {(X,1), (Y,2)}$ et l’interprétation suivante :

**Interprétation 2 ** :

• Le domaine d’interprétation est l’ensemble ${0,1,2}$.
• Le symbole $\text{zero}$ représente l’entier 0. (Attention, pas la valeur faux.)
• Le symbole $\text{plus}$ représente la fonction somme modulo 3 qui à tout couple $(x,y)$ d’entiers naturels associe $(x+y) \mod 3$.

D.dec5 : Interprétation des atomes

Pour mémoire, la valuation d’un ensemble $V$ de variables sur un domaine d’interprétation $D$ est une application qui assigne à chaque variable de $V$ un élément de $D$.

Étant donnés :

• un atome $t$,
• une interprétation $I$ des symboles fonctionnels et du symbole relationnel apparaissant dans $t$,
• une valuation $A$ des variables apparaissant dans $t$,

L’interprétation de $t$ pour la valuation $A$ consiste à déterminer la valeur $\text{Val}(t,A)$ par induction d’après les règles suivantes :

• La valeur d’une constante relationnelle est celle qui lui est assignée par l’interprétation $I$ ($\text{vrai} $ ou $\text{faux}$).
• Pour tout terme relationnel $\mathcal{T}/n$ ayant pour interprétation la fonction $\text{Val}_ \mathcal{T}$, $\text{Val}(\mathcal{T}(f_1,…,f_n),A)$ $=$ $\text{Val}_ \mathcal{T}(\text{Val}(f_1,A),…,\text{Val}(f_n,A))$.

Exemple :

On considère la signature fonctionnelle $S = ({\text{zero}/0, \text{plus}/2 },{\underline{\text{egal}}/2 })$ et l’interprétation suivante de cette signature :

**Interprétation 1 ** :

• Le domaine d’interprétation est l’ensemble $\mathbb{N}$ des entiers naturels.
• Le symbole $\text{zero}$ représente l’entier 0. (Attention, pas la valeur faux.)
• Le symbole $\text{plus}$ représente la fonction somme standard qui à tout couple $(x,y)$ d’entiers naturels associe $x+y$.
• Le symbole $\text{egal}$ représente la relation d’égalité standard : $\text{egal}(x,y)$ est vrai si et seulement si $x=y$ au sens usuel de l’égalité entre entiers naturels.

Soit l’atome $t =$ $\text{egal}(1, \text{plus}(\text{plus}(\text{zero},X),Y)) )$ et la valuation $A = {(X,1), (Y,2)}$.

L’interprétation de $f$ pour $A$ est $\text{faux} $ car :

• $\text{plus}(\text{plus}(\text{zero},X),Y)) = 3$
• et $\text{egal(3,0}) = \text{faux}$

En termes informels, interpréter un atome consiste à déterminer sa valeur à partir des valeurs de ses variables, des fonctions assignées à ses symboles fonctionnels et de la relation assignée à son symbole relationnel par leur interprétation.

Exercice de découverte D.dec.x5

Donnez la valeur de l’atome $t = \text{p}( \text{plus}(\text{plus}(\text{zero},X),Y))$ pour la valuation $A = {(X,1), (Y,2)}$ et l’interprétation suivante :

**Interprétation 2 ** :

• Le domaine d’interprétation est l’ensemble ${0,1,2}$.
• Le symbole $\text{zero}$ représente l’entier 0. (Attention, pas la valeur faux.)
• Le symbole $\text{plus}$ représente la fonction somme modulo 3 qui à tout couple $(x,y)$ d’entiers naturels associe $(x+y) \mod 3$.
• Le symbole $\text{p}$ représente la fonction telle que $\text{p}(0) = \text{p}(2) = \text{vrai}$ et $\text{p}(1) = \text{faux} $.

D.dec6 : Formules

Jusqu’à maintenant, nous n’avons vu que des parties de formules appelées termes fonctionnels et atomes. Ces expressions sont construites à partir de symboles fonctionnels, variables et symboles relationnels.

Une formule du premier ordre est constituée d’atomes, de connecteurs logiques, de parenthèses et de quantificateurs.

On appelle formule complètement parenthésée toute expression pouvant être construite par induction en utilisant les règles suivantes :

• Tout atome est une formule.
• Si $\sigma$ est une formule, alors $\neg \sigma$ en est une.
• Si $\sigma_1$ et $\sigma_2$ sont des formules, alors $(\sigma_1 \vee \sigma_2)$, $(\sigma_1 \wedge \sigma_2)$, $(\sigma_1 \to \sigma_2)$ et $(\sigma_1 \leftrightarrow \sigma_2)$ sont des formules.
• Si $\sigma$ est une formule et $X$ une variable, alors $(\exists X \sigma)$ et $(\forall X \sigma)$ sont des formules.

Voici un exemple de formule complètement parenthésée dans la quelle les atomes ont été soulignés :

$(\exists Y((\forall X \underline{\text{egal}(\text{plus}(X,Y),X)})$ $\to$ $\neg \underline{\text{egal}(\text{zero},Y)}))$

Attention, on ne s’intéresse pas, pour le moment, aux valeurs de vérité des formules, qui peuvent dépendre de l’interprétation de leurs symboles fonctionnels er relationnel, comme nous le verrons plus loin.

On peut supprimer certaines parenthèses en utilisant les mêmes règles d’associativité et priorités que pour la logique propositionnelle, auxquelles d’ajoutes les règles suivantes :

• Les quantificateurs ont la même priorité que le connecteur $\neg$, donc une priorité plus élevée que les connecteurs $\vee, \wedge, \to, \leftrightarrow$.
• Les quantificateurs sont associatifs à droite (donc par exemple $\exists X \forall Y \exists Z ~ \sigma$ se lit $\exists X (\forall Y (\exists Z ~ \sigma))$).

La formule donnée en exemple peut donc s’écrire :

$\exists Y(\forall X \underline{\text{egal}(\text{plus}(X,Y),X)}$ $\to$ $\neg \underline{\text{egal}(\text{zero},Y)})$

Mais pour améliorer la lisibilité, n’hésitez pas à mettre plus de parenthèses que ce qui est strictement nécessaire.

Exercice de découverte D.dec.x6

Voici une formule complètement parenthésée :

$(\exists X((\forall Y(\text{p}(X,Y) \wedge \text{q}(Y)))$ $\to$ $(\forall Y(\text{p}(Y,X) \vee \text{q}(X) ))))$

Supprimez les parenthèses qui ne sont pas strictement nécessaires.

Y-a-t-il des symboles relationnels dans cette formule ? Si oui lesquels ? Y-a-t-il des symboles fonctionnels ? Si oui lesquels. Soulignez tous les atomes.

D.dec7 : Formules closes

Les variables apparaissant dans une formule peuvent être liées ou libres.

Les variables liées sont introduites par les quantificateurs $\forall$ et $\exists$. Chaque quantificateur lie entre elle toutes les occurrence de la variables qu’il quantifie et qui se situent dans sa portée, c’est à dire entre les parenthèses associée à ce quantificateur dans la forme complètement parenthésée de la formule.

Voici un exemple de formule où les occurrences de variables liées par chaque quantificateur sont mises en évidence.

Les variables qui ne sont pas liées sont dites libres.

Toute formule dont toutes les variables sont liées est dite close.

Exercice de découverte D.dec.x7

Dans la formule suivante, soulignez les atomes, reliez par des flèches les occurrences de variables liées entre elles, et entourez les variables libres.

$\forall A ~ \text{p}(A,B)$ $\to$ $\exists A ~ (~ q(A,C) \vee \exists B ~ t(f(B))~) $

Cette formule est-elle close ?

D.dec8 : Interprétation d’une formule close

Nous avons vu précédemment comment interpréter les termes fonctionnels et les atomes de formules en nous basant sur un domaine d’interprétation et en donnant un sens aux symboles fonctionnels et aux symboles relationnels.

Interpréter une formule close consiste à déterminer sa valeur de vérité pour une interprétation donnée de ses symboles fonctionnels et de ses symboles relationnels.

Pour une valuation $A$ donnée de ses variables, un atome s’interprète à $\text{vrai}$ ou $\text{faux}$. Une formule constituée uniquement d’atomes et de connecteurs logiques s’interprète selon les mêmes règles qu’en logique propositionnelle, basées sur les tables de vérités des connecteurs.

Toujours pour une valuation donnée, la valeur de vérité d’une formule est déterminée par induction d’après les règles suivantes :

• La valeur de vérité d’un atome $t$ (qui est un cas particulier de formule) pour une valuation $A$ de ses variables est $\text{Val}(t,A)$. (Voir section D.dec5).
• Si $\Sigma$ est une formule, alors $\text{Val}(\neg \Sigma,A)$ $=$ $\underline\neg \text{Val} (\Sigma, A)$
• Si $\Sigma$ et $\Omega$ sont des formules, alors :
  • $\text{Val}(\Sigma \vee \Omega, A)$ $=$ $\text{Val}(\Sigma,A) \underline\vee \text{Val}(\Omega,A)$
  • $\text{Val}(\Sigma \wedge \Omega, A)$ $=$ $\text{Val}(\Sigma,A) \underline\wedge \text{Val}(\Omega,A)$
  • $\text{Val}(\Sigma \to \Omega, A)$ $=$ $\text{Val}(\Sigma,A) \underline\to \text{Val}(\Omega,A)$
  • $\text{Val}(\Sigma \leftrightarrow \Omega, A)$ $=$ $\text{Val}(\Sigma,A) \underline\leftrightarrow \text{Val}(\Omega,A)$
• Si $\Sigma$ est une formule et $X$ une variable non assignées par $A$, alors $\text{Val}(\exists X ~ \Sigma,A) = \text{vrai}$ si et seulement si il existe au moins un élément $x$ du domaine d’interprétation tel que $\text{Val}(\Sigma, A\cup{X,x}) = \text{vrai}$.
• Si $\Sigma$ est une formule et $X$ une variable non assignées par $A$, alors $\text{Val}(\forall X ~ \Sigma,A) = \text{vrai}$ si et seulement si pour tout élément $x$ du domaine d’interprétation, $\text{Val}(\Sigma, A\cup{X,x}) = \text{vrai}$.

Le sens des quantificateurs est donc celui usuellement utilisé en mathématique.

En résumé, pour attribuer une valeur de vérité à une formule $\Sigma$, il faut :

• Une interprétation, incluant un domaine d’interprétation et une interprétation de tous les symboles fonctionnels et relationnels apparaissant dans $\Sigma$.
• Une valuation des variables libres apparaissant dans $\Sigma$.

L’interprétation d’une formule close repose uniquement sur une interprétation de ses symboles fonctionnels et relationnels.

Considérons l’exemple suivant.

$\Sigma =$ $\exists Y(\forall X ~ \underline{\text{egal}(\text{plus}(X,Y),X)}$ $\to$ $\neg \underline{\text{egal}(\text{zero},Y)})$

Cette formule est close. Sa valeur de vérité dépend uniquement de l’interprétation de la signature $({\text{zero}/0, \text{plus}/2 },{\underline{\text{egal}}/2 })$, c’est à dire du domaine d’interprétation considéré et du sens donné aux symboles $\text{egal}$, $\text{plus}$ et $\text{zero}$.

Pour certaines interprétations, la formule a la valeur $\text{vrai}$ et pour d’autre elle a la valeur $\text{faux}$.

Prenons l’interprétation que nous avons déjà utilisée section D.dec5.

**Interprétation 1 ** :

• Le domaine d’interprétation est l’ensemble $\mathbb{N}$ des entiers naturels.
• Le symbole $\text{zero}$ représente l’entier 0. (Attention, pas la valeur faux.)
• Le symbole $\text{plus}$ représente la fonction somme standard qui à tout couple $(x,y)$ d’entiers naturels associe $x+y$.
• Le symbole $\text{egal}$ représente la relation d’égalité standard : $\text{egal}(x,y)$ est vrai si et seulement si $x=y$ au sens usuel de l’égalité entre entiers naturels.

Quelle est la valeur de vérité de $\Sigma$ pour cette interprétation ?

Pour le savoir, il nous faut déterminer s’il existe une valeur de $Y$ telle que…

$\Sigma =$ $\underbrace{\forall X ~ \text{egal}(\text{plus}(X,Y),X)}_ {\sigma_1}$ $\to$ $\neg \underbrace{\text{egal}(\text{zero},y)}_ {\sigma_2}$

… s’interprète à $\text{vrai}$.

Or pour $Y=1$, par exemple, $\sigma_1$ s’interprète à $\text{faux}$ (puisque cette valuation de $Y$, $\sigma_1$ dit que pour tout $X$, on a $X+1=X$) et $\sigma_2$ s’interprète à $\text{vrai}$, donc $\sigma_1 \to \sigma_2$ s’interprète à $\text{vrai}$ (d’après la table de vérité du connecteur $\to$).

On en conclu que notre interprétation donne la valeur $\text{vrai}$ à $\Sigma$.

Exercice de découverte D.dec.x8

On reprend la même interprétation, mais une formule différente :

$\Omega =$ $\forall X(\exists Y ~ \text{egal}(X,Y) \to \text{egal}(\text{zero},X))$

Donnez la valeur de vérité de $\Omega$.

D.dec9 : Validité et cohérence

On s’intéresse uniquement aux formules closes de la logique du premier ordre.

On dit qu’une interprétation $I$ satisfait une formule $\Sigma$ si et seulement si elle donne à cette formule la valeur $\text{vrai}$. Dans le cas contraire, on dit que $I$ falsifie $\Sigma$. On appelle modèle d’une formule close $\Sigma$ toute interprétation qui satisfait $\Sigma$. Toute interprétation qui falsifie $\Sigma$ est appelée contre-modèle de $\Sigma$.

Une formule close est une tautologie, ou formule valide, si et seulement si elle n’admet aucun contre-modèle. Autrement dit, la formule s’interprète à $\text{vrai}$ quels que soient le domaine d’interprétation et le sens donné à ses symboles relationnels et à ses symboles fonctionnels. En quelque sorte, une telle formule est "toujours vraie".

Une formule close est cohérente si et seulement si elle admet au moins un modèle. Dans le cas contraire, elle est dite incohérente.

Prenons comme exemple la formule $\Sigma = \forall X~ \text{p}(X,X)$. Une interprétation de cette formule définit un domaine d’interprétation et donne un sens au symbole relationnel $\text{t}$. Considérons deux interprétations ayant pour domaine ${1,2}$. Ces deux interprétations se différencie donc uniquement par le sens donné au symbole $\text{p}$.

Interprétation $I_1$ :

Voici trois représentations de la première interprétation. Une seule est suffisante, mais c’est l’occasion de voir les différente manière de représenter l’interprétation d’un symbole relationnel d’arité 2 lorsque le domaine d’interprétation comporte relativement peu de valeurs.

La première représentation est dite sagittale. Elle marque par une flèche les couples $x,y$ pour lesquels $\text{p}(x,y) = \text{vrai}$. La deuxième représentation donne ces même couples sous la forme d’une matrice avec le premier argument en ligne et le deuxième en colonne. La troisième représentation est généralisable aux symboles relationnels d’arité quelconque.

Cette interprétation falsifie $\Sigma$ puisque par exemple pour $X=1$, $\text{p}(X,X)$ s’interprète à $\text{faux}$.

Interprétation $I_2$ :

Cette interprétation satisfait $\Sigma$ puisque pour toutes les valeurs de $X$, $\text{p}(X,X)$ s’interprète à $\text{vrai}$.

La formule $\Sigma$ est cohérente, puisqu’elle a au moins un modèle, mais ce n’est pas une tautologie car elle admet au moins un contre-modèle.

Exercice de découverte D.dec.x9

Donnez une interprétation qui falsifie et une qui satisfait la formule suivante :

$\Omega =$ $\underbrace{(\forall X \exists Y ~ \text{p}(X,Y))}_ {\omega_1}$ $\to$ $\underbrace{(\forall X \exists Y ~ \neg \text{p}(X,Y))}_ {\omega_2}$

Les deux interprétations doivent avoir pour domaine l’ensemble ${1,2}$. Commencez par rechercher un modèle (réponse 1), puis un contre-modèle (réponse 2).

D.dec10 : Conséquence logique

La conséquence logique et l’équivalence logique sont définie exactement de la même façon en logique propositionnelle et en logique du premier ordre.

Une formule $\Omega$ est conséquence logique d’une formule $\Sigma$, i.e., $\Sigma \models \Omega$ si et seulement si tout modèle de $\Sigma$ est un modèle de $\Omega$.

Deux formules sont logiquement équivalentes si et seulement si elles ont les même modèles.

La grosse différence entre la logique du premier ordre et la logique propositionnelle tient à la notion de modèle. En logique propositionnelle, un modèle est simplement une valuation des variables qui satisfait la formule. En logique du premier ordre, un modèle est une interprétation qui satisfait la formule. Une formule du premier ordre à une infinité d’interprétations différentes, chacune constituée d’un domaine (qui peut être fini ou infini) et de fonctions donnant un sens à chacun des symboles fonctionnel et relationnel utilisé.

En logique propositionnelle, comme en logique du premier ordre, déterminer si une logique est conséquence logique d’une autre est de même difficulté que déterminer si une formule est une tautologie ou que déterminer si une formule est cohérente.

En logique propositionnelle, déterminer si une formule est cohérente ou si elle est valide est un problème NP-complet, pour lequel aucun algorithme efficace, au sens d’une complexité en temps polynomiale, n’est connu.

En logique du premier ordre c’est encore pire : le problème est indécidable. Aucun algorithme ne peut, pour toute formule placée en entrée, déterminer en un temps fini si cette formule est une tautologie. Déterminer si une formule est cohérente est également indécidable.

En pratique, il est possible de déterminer et de prouver que certaines formules sont valides ou sont cohérentes en réalisant des déductions.

Par exemple, considérons la formule suivante :

$\Sigma =$ $\underbrace{\forall X ~ \text{p}(X)}_ {\sigma_1} \to \underbrace{ \exists X ~ \text{p}(X)}_ {\sigma_2}$

Il est évident que $\Sigma$ est une tautologie. En effet, si une interprétation $I$ est un modèle de $\sigma_1$, alors $\text{p}(X)$, tel que défint par $I$, est $\text{vrai}$ pour toute valeur $X$ du domaine d’interprétation de $I$. Donc $\text{p}(X)$ il est vrai pour au moins une valeur $X$ du domaine d’interprétation de $I$, donc $I$ est aussi un modèle de $\sigma_2$.

Il existe des algorithmes permettant de déterminer si certaines formules sont des tautologies en utilisant des ensembles de règles appelés systèmes de preuve. Cela relève d’un champ de l’intelligence artificielle appelé raisonnement automatique. Comme le problème sous-jacent est indécidable, de tels algorithmes ne s’arrêtent jamais et ne peuvent pas conclure pour certaines formules placées en entrée. Mais il peuvent traiter certaines autres formules. Ces algorithmes sont qualifiés de corrects parce que s’ils s’arrêtent et fournissent un résultat (par exemple : la formule d’entrée est une tautologie), alors ce résultat est correct. Par contre, pour certaines formules, il ne s’arrêtent jamais. Si le programme ne s’est pas arrêté après un certain temps, vous n’avez aucun moyen de savoir s’il va fournir une réponse ou si son exécution va se prolonger indéfiniment :slightly_smiling_face:. Et le problème, c’est que même dans les cas où si le programme va s’arrêter en théorie, en pratique l’exécution peut être d’une durée astronomique, sans vous laisser aucune chance d’avoir le résultat.

D.dec11 : Modélisation

La logique du premier ordre permet de formaliser des énoncés faisant intervenir des objets (les éléments du domaine d’interprétation) et des relations entre ces objets (les interprétations des symboles relationnels et des symboles fonctionnels).

On dit qu’une formule $\Sigma$ modélise une émoncé $E$ si et seulement si elle est satisfaite par les interprétations qui ne sont pas en contradiction avec $E$, et seulement pour ces interprétations.

Prenons pour exemple l’énoncé suivant :

Tout humain qui possède un chien est anglophone.

Cet énoncé est-il vrai ou faux ? Cela dépend, pour commencer, du sens donné aux mots chien, humain, possède et anglophone. Mais admettons que nous leur donnions leur sens usuel. La valeur de vérité de l’énoncé dépend du domaine d’interprétation. S’il s’agit des êtres vivants terrestre, alors clairement l’énoncé est faux. Mais si on réduit ce domaine aux êtres vivant situés dans le village de Capel, en Angleterre, il n’est pas impossible que l’énoncé soit vrai. Et si le domaine d’interprétation est l’ensemble des êtres vivant de l’ile de Achi Kochi au Japon, où il est interdit de posséder un chien, alors l’énoncé est… vrai ! En effet, si personne ne possède de chien, alors il est vrai que toute personne humaine en possédant un parle anglais.

Pour modéliser cet énoncé par une formule du premier ordre, il nous faut définit les symboles relationnels et symboles fonctionnels utilisés. Dans la suite, nous ne travaillerons qu’avec des symbole relationnel pour simplifier les exercices, compte tenu du faible nombre d’heures d’enseignement consacrées à la logique du premier ordre.

Ici, nous utiliserons les symboles relationnels suivants : $\text{hum}/1$, $\text{chien}/1$, $\text{angl}/1$ et $\text{poss}/2$.

L’énoncé peut alors être modélisé ainsi :

$\forall X$ $[\underbrace{(\text{hum}(X) \wedge \underbrace{\exists Y~(\text{chien}(Y) \wedge \text{poss}(X,Y)}_ {\mu})}_ {\sigma}$ $\to$ $\underbrace{\text{angl}(X)}_{\omega} ]$

La sous-formule $\omega$ modélise la propriété : $X$ est anglophone.

La sous formule $\mu$ modélise la propriété : $X$ possède un chien.

La sous-formule $\sigma$ modélise la propriété : $X$ est un humain qui possède un chien.

L’utilisation du symbole $\to$ traduit l’implication sous-jacente à l’énoncé : "Si $X$ est un humain qui possède un chien, alors $X$ est anglophone".

Le quantificateur $\forall$ traduit le fait que pour satisfaire l’énoncé, il faut que tout humain possédant un chien soit anglophone.

Le quantificateur $\exists$ traduit la condition "$X$ possède au moins un chien", i.e., il existe au moin un chien possédé par $X$.

Exercice de découverte D.dec.x9

Nous reprenons la formule…

$\forall X$ $[\underbrace{(\text{hum}(X) \wedge \underbrace{\exists Y~(\text{chien}(Y) \wedge \text{poss}(X,Y)}_ {\mu})}_ {\sigma}$ $\to$ $\underbrace{\text{angl}(X)}_{\omega} ]$

…qui modélise l’énoncé :

Tout humain qui possède un chien est anglophone.

Imaginons une planète où il n’y a aucun humain, où nul être vivant ne peut être à la fois une salade et un chien, et qui est peuplée uniquement :

• d’un chien anglophone nommé $\alpha$, qui ne possède rien.
• d’une salade nommée $\beta$ (son vrai nom est $\beta$via) qui ne parle pas anglais et possède le chien et rien d’autre.

La situation sur cette planète est-elle en contradiction avec l’énoncé $E$ ? (Réponse 1)

Donnez l’interprétation correspondante (dont le domaine d’interprétation est ${\alpha, \beta}$. (Réponse 2)

Cette interprétation est-elle un modèle de $\Sigma$ ? (Réponse 3)

Activité d’entraînement D.ent

Chacune des deux itération propose un panel d’exercices couvrant les compétences qui seront évaluées à l’examen.

Itération D.ent1

Exercice d’entrainement D.ent1.1

Soit la formule :

$\Sigma = \forall X \exists Y$ $\underbrace{[\underbrace{(p(X) \wedge p(Y))}_ {\sigma_1} \to \underbrace{(q(X) \vee q(Y))}_ {\sigma_2}]}_ {\sigma}$

L’interprétation suivante est-elle un modèle de $\Sigma$ ? (Les valeurs entourées sont celles qui satisfont l’interprétation du symbole relationnel d’arité 1 mentionné au dessus.)

Donnez un contre-modèle de $\Sigma$ ayant le même domaine mais une interprétation différente des symboles relationnels $p$ et $q$.

Exercice d’entrainement D.ent1.2

Soit les formules suivantes :

• $\Sigma_1 = \forall X ~ r(X,X)$
• $\Sigma_2 =$ $\forall X \forall Y (r(X,Y) \to r(Y,X))$
• $\Sigma_3$ $=$ $\forall X \forall Y \forall Z$ $(~[(r(X,Y) \wedge r(Y,Z)] \to r(X,Z)~)$

L’interprétation suivante est-elle un modèle de $\Sigma_1$ ? de $\Sigma_2$ ? de $\Sigma_3$ ?

Proposez une modification minimale (en termes de nombre d’arcs ajoutés ou enlevés) pour que l’interprétation satisfasse les trois formules.

Exercice d’entrainement D.ent1.3

Donnez une interprétation $I_1$ qui satisfait (Réponse 1) et une interprétation $I_2$ qui falsifie (Réponse 2) la formule suivante :

$\Omega = [\forall X \exists Y~ p(X,Y)]$ $\to$ $[\exists Y \forall X~ p(X,Y)]$

Ces deux interprétations doivent avoir pour domaine ${1,2}$.

Exercice d’entrainement D.ent1.4

Soient les 2 formules suivantes :

• $\Omega_1 = \exists Y \forall X~ p(X,Y)$
• $\Omega_2 = \exists Y \forall X~ p(Y,X)$

Quel critère doit respecter la représentation sagittale de l’interprétation du symbole relationnel $p$ pour que $\Omega_1$ soit satisfaite ? Donnez deux exemples avec un nombre minimal de flèches et avec le domaine ${1,2,3}$.

Quel critère doit respecter la représentation sagittale de l’interprétation du symbole relationnel $p$ pour que $\Omega_2$ soit satisfaite ? Donnez deux exemples avec un nombre minimal de flèches et avec le domaine ${1,2,3}$.

La formule $\Omega_1 \leftrightarrow \Omega_2$ est-elle une tautologie ? Justifiez votre réponse.

Exercice d’entrainement D.ent1.5

Modélisez la phrase suivante par une formule de la logique du premier ordre.

Il existe au moins un plombier riche.

Les symboles relationnels sont $\text{plombier}/1$ et $\text{riche}/1$.

Pourquoi la formule suivante n’est-elle pas une modélisation correcte de la phrase ?

$\Omega =$ $\exists X$ $(\underbrace{\text{plombier}(X) \to \text{riche}(X)}_{\omega})$

Domaine : {donald, picsou}
riche(donald) = faux, riche(picsou) = vrai
plombier(donald) = vrai, plombier(picsou) = faux

Modélisez maintenant la phrase :

Tous les plombiers sont riches.

Pourquoi la formule suivante n’est-elle pas une modélisation correcte de la phrase ?

$\Lambda = \forall X$ $(\underbrace{\text{plombier}(X) \wedge \text{riche}(X)}_{\omega})$

Domaine : {donald, picsou}
riche(donald) = faux, riche(picsou) = vrai
plombier(donald) = faux, plombier(picsou) = vrai

Exercice d’entrainement D.ent1.6

Modélisez la phrase suivante par une formule de la logique du premier ordre.

Nul n’a assassiné un souverain auquel il est fidèle.

Les symboles relationnels sont $\text{souv}/1$, $\text{ass}/2$ et $\text{fid}/2$.

Exercice d’entrainement D.ent1.6

Soit la formule suivante :

$\Sigma = $ $\forall X$ $[\exists Y~p(X,Y) \to \exists Y~q(X,Y)]$

Parmi les interprétations suivantes ayant pour domaine ${1,2}$, lesquelles sont des modèles de $\Sigma$ ?

Exercice d’entrainement D.ent1.7

On définit une relation $r$ sur une ensemble $D$ par un ensembles de couples d’éléments de $D$ (flèches sur la représentation sagittale).

La relation complémentaire d’une relation $r$ est définie par l’ensemble :

{$(x,y) \in D \times D$, $(x,y) \notin r$}

Modélisez la propriété…

$q$ est la relation complémentaire de $r$

…en utilisant les symboles de prédicats $r/2$ et $q/2$.

Itération D.ent2

Exercice d’entrainement D.ent2.1

Soit la formule :

$\Sigma =$ $\exists Y \forall X$ $\underbrace{[\underbrace{(p(X) \wedge q(Y))}_ {\sigma_1} \to \underbrace{(p(X) \vee q(Y))}_ {\sigma_2}]} _{\sigma}$

L’interprétation suivante est-elle un modèle de $\Sigma$ ? (Les valeurs entourées sont celles qui satisfont l’interprétation du symbole relationnel d’arité 1 mentionné au dessus.)

Exercice d’entrainement D.ent2.2

Soit la formule :

$\Sigma =$ $[\forall X(g(X) \vee h(X))]$ $\to$ $([\forall X ~ g(X)] \vee [\forall X ~ h(X)])$

Donnez une interprétation $I_1$ qui satisfait $\Sigma$ (Réponse 1) et une interprétation $I_2$ qui falsifie $\Sigma$ (Réponse 2). ces deux interprétations doivent avoir pour domaine ${1,2}$.

Exercice d’entrainement D.ent2.3

Soit la formule suivante :

$\Omega =$ $\underbrace{[\exists X \forall Y~ p(X,Y)]}_ {\omega_1}$ $\to$ $\underbrace{[\forall Y \exists X~ p(X,Y)]}_ {\omega_2}$

Quel critère doit respecter la représentation sagittale de l’interprétation du symbole relationnel $p$ pour que $\omega_1$ soit satisfaite ?

Quel critère doit respecter la représentation sagittale de l’interprétation du symbole relationnel $p$ pour que $\omega_2$ soit satisfaite ?

Existe-t-il une interprétation qui satisfait $\omega_1$ et falsifie $\omega_2$ ?

$\Omega$ est-elle une tautologie ?

Si on change le sens du connecteur $\to$, la formule devient :

$\Theta =$ $\underbrace{[\forall Y \exists X~ p(X,Y)]}_ {\omega_2}$ $\to$ $ \underbrace{[\exists X \forall Y~ p(X,Y)]}_ {\omega_1}$

Cette nouvelle formule est-elle une tautologie ? Autrement dit tout modèle de $\omega_2$ est-il un modèle de $\omega_1$ ?

Exercice d’entrainement D.ent2.4

Modélisez la phrase suivante par une formule de la logique du premier ordre.

Tous les humains qui possèdent une voiture ont un chien.

Les symboles relationnels sont $\text{hum}/1$ (pour humain), $\text{chien}/1$, $\text{voit}/1$ (pour voiture) et $\text{poss}/2$ (pour possède).

Exercice d’entrainement D.ent2.5

Soit la formule suivante :

$\Sigma =$ $\forall X$ $\forall Y$ $[p(X,Y) \to (q(X) \wedge \neg q(Y))]$

On considère uniquement les interprétations ayant pour domaine ${1,2}$. Donnez deux modèles de $\Sigma$ pour lesquels la représentation sagittale de $p$ comporte exactement une flèche.

Combien y a-t-il de modèles pour lesquels la représentation sagittale de $p$ comporte au moins deux flèches ?

Combien y a-t-il de modèles pour lesquels la représentation sagittale de $p$ ne comporte aucune flèche ?

Exercice d’entrainement D.ent2.6

Modélisez l’énoncé suivant :

Tout nombre pair supérieur à 2 est la somme de 2 nombres premiers.

On appelle nombre toute valeur du domaine d’interprétation. Les symboles relationnels à utiliser sont les suivants :

• $\text{pair}/1$ : $\text{pair}(X)$ modélise "$X$ est pair"
• $\text{prem}/1$ : $\text{prem}(X)$ modélise "$X$ est premier"
• $\text{sup2}/1$ : $\text{sup2}(X)$ modélise "$X$ est supérieur à 2"
• $\text{add}/3$ : $\text{add}(X,Y,Z)$ modélise "$Z$ est la somme de $X$ et $Y$"