Chapitre 5
Logique des prédicats
5.1
Introduction
Dans la logique des propositions on considère une proposition comme un tout, repré- senté par une variable, dont on ne détaille pas le contenu. On ne s’intéresse qu’à la vérité ou à la fausseté d’une proposition. La logique des prédicats, également appelée logique du premier ordre, regarde les propositions de plus près. Dans l’analyse des propositions élémentaires en langue naturelle on peut distinguer
– un sujet (ce dont on parle) et d’éventuels compléments – un prédicat (ce qu’on dit à propos du sujet et de ses compléments)
Par exemple, dans la proposition « Jules est grand » on a
– un sujet : Jules – le prédicat : est grand
Dans la proposition « Maya mange une pomme » on a
– un sujet Maya et un complément pomme – le prédicat : mange
On pourrait réécrire les propositions précédentes sous une forme qui met en évidence le prédicat, soit :
est grand (Jules)
mange(M aya, pomme)
Suivant ce modèle, la logique des prédicats représente les propositions élémentaires (ato- miques) son la forme :
nom-prédicat(objet1, objet2, . . .)
où objet 1, objet 2, . . . sont les objets sur lesquels porte le prédicat (le sujet et ses éven-
tuels compléments)
45
5.2. SYNTAXE DE LA LOGIQUE DES PRÉDICATS
En logique des prédicats les variables représentent non pas des propositions mes des objets sur lesquels portent les prédicats. L’introduction de variables permet de formuler deux types d’énoncés.
Les énoncés universels. Dans ce cas les variables représentent tous les objets d’un domaine. Comme dans
Si X est une girafe alors X est un animal.
Les énoncés existentiels. qu’on le connaisse précisément ou non. Comme dans
Ici une variable représente un objet particulier du domaine,
Il y a au moins un nombre entier Z tel que Z > 3 et Z 2 < 30.
Contrairement aux variables, les constantes représentent des objets particulier et
connus : 1642 (un nombre entier), Ivan (une personne particulière), etc.
Enfin, la notion de fonction correspond à la notion habituelle de fonction qui associe à un ou plusieurs objets (les paramètres) une valeur (le résultat de la fonction). Par exemple age(x) associe à une personne x un nombre entier (son âge) ou distance(x, y) qui fournit la distance entre deux villes x et y.
5.2 Syntaxe de la logique des prédicats
Langage logique
Pour écrire des formules de logique des prédicats, on commence par se donner un
vocabulaire (ou signature) W composé de symboles de différents types :
– variables ( x , y , z , ...) – constantes ( a , b , c , ...) – fonctions ( f , g , h , ...) – prédicats ( p , q , r , ...)
à chaque symbole de fonction et de prédicat est associée un nombre d’arguments (arité) qui est un entier positif ou nul. On peut considérer que les constantes sont des fonctions 0-aires.
Université de Genève – G. Falquet
c
46
5.2. SYNTAXE DE LA LOGIQUE DES PRÉDICATS
Grammaire de la logique des prédicats
terme = constante | variable
| fonction "(" terme { "," terme } ")"
atome = prédicat "(" terme { "," terme } ")"
formule = atome
variable formule variable formule formule
| | | | formule connecteur formule
∀ ∃ ¬
connecteur =
|
∧
∨
|
⇒
|
⇔
Priorité des connecteurs
Pour éviter les ambiguités on fixe une priorité des connecteurs logiques et
et
>
∃
¬
>
∀
∨
⇔
> b
et g signifie ((
∧ a ∨ x b
⇒ ⇒ ¬ g signifie ( ∀ ∀ qui est différent de
⇒
a)
¬ x b)
x (b
∀
∨ ⇒
⇒
g
⇒
b) g
g)
Variables libres et liées
Les variables qui apparaissent dans une formule sont dites libres ou liées, selon le
principe suivant :
– toutes les variables d’une formule sans quantificateur sont libres – si x est libre dans w , x est liée dans
xw et dans
xw
∀
∃
Exemple 5.1. Dans la formule
x et y sont libres.
Dans
x est liée, y est libre
Dans
p(x)
q(y)
∨
x(p(x)
∀
∧
r(y, x))
x(p(x)
q(x))
r(x)
∨
∧
∃
la variable x joue deux rôles différents, elle est liée dans la partie à gauche de et libre dans la partie de droite. Bien que cette formule soit syntaxiquement correcte, il est fortement déconseillé de l’écrire ainsi, mieux vaut renommer x en y dans l’une des deux parties.
∧
Définition 5.1. Une formule dont toutes les variables sont liées est dite formule fermée ou proposition.
Université de Genève – G. Falquet
c
47
5.3. SÉMANTIQUE
Une formule avec une ou des variables libre est dite ouverte. On notera w(x, y, z) pour
indiquer que la formule w possède x, y et z comme variables libres.
Par exemple, w(x, z) = p(x)
yq(x, y, z) est une formule ouverte où x et z sont libres.
∧∃
5.3 Sémantique
Le sens d’une formule fermée sera l’une des valeurs booléennes vrai (1) ou faux (0). Pour pouvoir interpréter une formule il faut – donner une valeur aux variables – donner une valeur à chaque constante – un moyen d’interpréter les atomes p(t1, . . . , tn) – un moyen d’interpréter les fonctions f (t1, . . . , tn) – une règle d’interprétation des formules quantifiées
Rappel
Une fonction n -aire f sur un ensemble A, notée f : A
valeurs (a1, . . . , an) une valeur f (a1, . . . , an) = a
A Une relation n-aire r sur un ensemble A, notée r (a1, . . . , an) dont les éléments appartiennent tous à A.
∈
A, associe à un n-tuple de
→
An est un ensemble de n-tuples
∈
Définition 5.2. Une interprétation I de W (ou structure relationnelle sur W ) est la donnée de :
– un ensemble non vide D, le domaine de l’interprétation – une fonction I qui associe
– à chaque variable une valeur de D – à chaque constante une valeur de D – à chaque symbole de fonction à n arguments une fonction totale de Dn dans D – à chaque symbole de prédicat à k arguments une relation k
aire dans D (un
−
sous-ensemble de Dk
Interprétation des termes
On définit une fonction d’interprétation I par
Terme constante c variable x f (t1, . . . , tn)
I(Terme) I(c) I(x) I(f )(I(t1), . . . , I(tn))
Exemple 5.2. On a une interprétation I définie par
– un domaine D =
0, 1, 2, 3 }
{
Université de Genève – G. Falquet
c
48
5.3. SÉMANTIQUE
– I(a) = 0, I(b) = 1, I(c) = 2, I(d) = 3 – I(f ) = 0, (1, 0) (0, 0) { – I(x) = 1, I(y) = 0
0, (0, 1)
→
→
→
2, (2, 3)
2, (3, 3)
3,
→
· · · →
→
3 pour le reste
}
calcul de quelques interprétations de termes selon I :
– I(a) = 0 – I(f (a, x)) = I(f )(0, 1) = 0 – I(f (x, f (y, b))) = I(f )(1, I(f )(0, 1)) = I(f )(1, 0) = 2
Interprétation des atomes
Le principe d’interprétation des atomes consiste à évaluer les termes donnés comme paramètres au prédicat puis à voir si le n-uplet de termes obtenu fait partie de l’interpré- tation du prédicat.
I(p(t1, . . . , tn) = v
si et seulement si
(I(t1), . . . , I(tn))
I(p)
∈
La relation qui forme l’interprétation I(p) du prédicat p fournit donc l’ensemble des
valeurs de paramètres pour lesquels on veut que le prédicat soit vrai.
L’interprétation des atomes étant définie, on peut interpréter toutes les formules pos- en utilisant les mêmes règles qu’en logique des
sédant des connecteurs logiques propositions.
Publicité
∧∨ ⇒ ¬
Extension aux formules avec quantificateurs
Pour interpréter les formules quantifiées on commence par introduire la notion de variante d’une interprétation. On dit qu’une interprétation J est une variante de I en x si J est partout identique à I, sauf pour la variable x. On note Ix=d la variante de I où I(x) = d (d D) Remarque. I est une variante de I en x (qui consiste à reprendre la même valeur pour
∈
x)
On peut alors interpréter les formules quantifiées en appliquant les deux règles sui-
vantes :
1. Quantification universelle
si et seulement si pour tout d
D on a
∈
I(
xΦ) = v
∀
Ix=d(Φ) = v
Université de Genève – G. Falquet
c
49
5.3. SÉMANTIQUE
autrement dit, la formule doit être vraie pour toutes les valeurs possibles de la variable
x quantifiée.
2. Quantification existentielle
I(
xΦ) = v
∃
si et seulement si il existe un élément d
D tel que
∈
Ix=d(Φ) = v
Exemple 5.3. Soit le vocabulaire composé des symboles :
constantes a, b, c, d, k1, k2, k3, k4 prédicats P (unaire), E (unaire), C (unaire), I (binaire) variables x, y, z, u, v, w
On interprète ce langage dans le domaine composé des étudiants, des cours, des personnes et des inscriptions d’une (micro) université. Le domaine est l’ensemble D = Personne Etudiant
Cours, où
∪
∪ – Personne = – Etudiant = – Cours =
Alice, Bob, Charles, Diane { Alice, Bob, Charles {
C1122, C1101, M2001, M2002 {
}
}
}
L’interprétation des constantes est donnée par :
– I(a) = Alice, I(b) = Bob, I(c) = Charles, I(d) = DianeI(k1) = C1122, I(k2) =
C1101, I(k3) = M2001, I(k4) = M2002
et l’interprétation des prédicats par
– I(P ) = Personne, I(E) = Etudiant, I(C) = Cours – I(I) = Inscription =
(Alice, Histoire), (Bob, Chimie), (Charles, Histoire) }
.
{
(La figure 5.1 résume graphiquement cette interprétation.)
Interprétons quelques formules selon I 1. I(a) = Alice 2. I(C(k3)) = v car I(k3) = M2001 et M2001 3. I(C(a)) = f car Alice 4. I(I(c, k1)) = v car (Charles, C1122) 5. I( 6. I( 7. I(
y I(x, y)) = f car Ix=M2001(
y I(x, y))) = vrai car
x I(x, C1101)) = v car Ix=Bob(I(x, C1101)) = v. x
I(C).
∈
I(C)
I(I)
∈
∈
∃
∃
∃
∀
x(E(x) ⇒ ∃ – Ix=Alice(E(x)
∀
y I(x, y)) = v (prendre y = C1122)
⇒ ∃
y I(x, y)) = f (entre autres).
Université de Genève – G. Falquet
c
50
5.3. SÉMANTIQUE
a
b
c
d
k1
k2
k3
k4
P
E
Bob
Alice
Charles Diane
Etudiant
Personne
C1101
M2002
C1122
M2001
Cours
Inscription
I
C
Figure 5.1 – Une interprétation du vocabulaire a, b, c, d, k1, k2, k3, k4, P, E, I, C
⇒ ∃
y I(x, y)) = v (prendre y = C1101)
– Ix=Bob(E(x) – Ix=Charles(E(x) y I(x, y)) = v (prendre y = C1122) – et E(x) = f , donc la formule est vraie, pour toutes les autres valeurs de x. Lorsqu’on évalue une formule il faut faire attention aux fait que deux variables qui portent des noms différents peuvent représenter la même valeur du domaine.
⇒ ∃
Exemple 5.4. Si on considère l’interprétation J définie par
– D = – J(ville) = – J(distance) =
Milan, Tokyo, Oslo {
N Milan, Tokyo, Oslo } {
}∪
La formule
(Milan, Tokyo, 9710), (Milan, Oslo, 1608), (Oslo, Tokyo, 8401) }
{
x
∀
y(ville(x)
∀
ville(y)
∧
z (distance(x, y, z)
⇒ ∃
distance(y, x, z))
∨
représente le fait qu’entre deux villes il y a toujours une distance (z). Cependant elle est fausse dans l’interprétation J car les variables x et y peuvent représenter la même ville. Pour rendre la formule vraie il faudrait ajouter à l’interprétation de distance : (Milan, Milan, 0), (Tokyo, Tokyo, 0), (Oslo, Oslo, 0).
Propriétés des formules fermées
Les formules fermées représentant des propositions, on peut reprendre telles qu’elles les définitions de satisfiabilité, modèle, équivalence et conséquence logique de la logique des propositions.
Définition 5.3. Étant donné une interprétation I est une formule fermée f , on note = A le fait que I(A) = f . Une formule fermée f et I |
= A le fait que I(A) = v et I |
Université de Genève – G. Falquet
c
51
5.4. DÉDUCTION
satisfiable s’il existe une interprétation I telle que I = A, on dit alors que I est un modèle | de A. Dans le cas contraire on dit que A est inconsistante. Une formule A est valide si = A. I |
= A pour toute interprétation , on note |
Exemple 5.5. L’ensemble de formule
F =
{
p(a, b),
y p(a, y) }
¬∃
est inconsistant car pour avoir I(p(a, b)) = v il faut nécessairement que (I(a), I(b))
∈ y p(a, y)) = f . Les deux formules ne peuvent jamais être vraies
I(p). Mais alors I( simultanément. La formule
¬∃
∨ est valide. Si l’interprétation I(P ) contient tous les éléments du domaine D la partie gauche de la formule est vraie, si ce n’est pas le cas, c’est la partie droite qui est vraie.
¬
x P (x))
( ∀
y ( ∃
P (y))
5.4 Déduction
Les règles de déduction naturelle pour la logique des propositions restent valables. Pour obtenir un système complet il faut leur adjoindre des règles spécifique aux formules quantifiées :
Elimination du quantificateur universel
SI F (x) est une formule où x est libre et t est un terme qui ne contient aucune variable
liée de F , on peut remplacer x dans
x F (x) par t pour obtenir F (t)
∀
x F (x)
1. ∀ 2. F (t) Exemple : de
∀
x(x + 1 > x) on peut déduire 3 + 1 > 3.
Introduction de
∀
Si on a pu déduire une formule F (x) où x est libre alors on peut déduire 1. F (x) 2. En général la variable x est introduite dans une hypothèse.
x F (x)
∀
x F (x)
∀
Université de Genève – G. Falquet
c
52
5.5. NORMALISATION ET RÉSOLUTION
Introduction de
∃
Si on a déduit une formule F (t) qui contient un terme t (p.ex. une constante) on peut
en déduire qu’il existe un x qui satisfait F (x)
x F (x)
Publicité
1. F (t) 2. ∃ Exemple 1. 0.52 < 0.5 x(x2 < x) 2. ∃
Suppression de
∃
∃
À partir de
x F (x) on peut formuler une hypothèse F (y) puis faire des déductions
avec elle. 1. 2. 3. 4. R (élimination de ”il existe” dans 1 et 3)
x F (x) (hypothèse) F (y) (”y” variable nouvelle) R (déduction à partir de 2)
∃
Exemple de déduction
x A(x)]
[ ∀ A
y [ ∃
A(y)] hypothèse A(t)]
¬ [ ¬ A(t)
⊥
⊥ y ( ∃ ¬ x A(x)
∀
élimination A(y)) y ( ∃
¬
¬ ⇒¬
A(y))
∃ absurde
importation et introduction de
∀
5.5 Normalisation et Résolution
L’application de règles d’inférence telles que le principe de résolution exige la mise en forme normale des formules. Dans le cas de la logique des prédicats cette mise en forme se fait en quatre étapes :
1. Mise en forme prenex (déplacement de tous les quantificateurs au début de la for-
mule)
2. Skolemisation (suppression des
)
∃
Université de Genève – G. Falquet
c
53
5.5. NORMALISATION ET RÉSOLUTION
3. Mise en forme normale conjonctive
4. Mise en forme clausale (suppression des
)
∀
Forme prenex
Une formule est dite en forme prenex si tous ses quantificateurs apparaissent au début. Il est toujours possible de transformer une formule en une formule équivalente sous forme prenex. Pour cela on applique autant de fois que nécessaire les équivalences
x w
¬∀
x
≡ ∃
w
¬
x w
¬∃
x
≡ ∀
w
¬
x w1)
( ∀
w2 ≡ ∀
x(w1 ∧
∧
w2) si x n’apparait pas dans w2
x w1)
( ∀
w2 ≡ ∀
x(w1 ∨
∨
w2) si x n’apparait pas dans w2
Exemple 5.6. La mise en forme prenex préserve les quantificateurs
z A(x, z))
x
y(E(x, y) ∀ ∀ x y( ∀ ≡ ∀ y x ∀ ≡ ∀ y x ∀ ≡ ∀
⇒ ∃ E(x, y) ¬ z( ∃ z(E(x, y) ∃
¬
E(x, y)
∨ ∃ ∨ ⇒
z A(x, z)) A(x, z)) A(x, z))
Exemple 5.7. La mise en forme prenex modifie les quantificateurs
x((
y(A(x, y))
∀ ≡ ∀ ≡ ∀ ≡ ∀ ≡ ∀
⇒ y(A(x, y)) A(x, y)) A(x, y)
∃ x( ( ∃ ¬ x(( y ∀ ¬ y( x( ¬ ∀ y(A(x, y) x ∀
⇒
B(x))
B(x)) B(x)) B(x)))
∨ ∨ ∨ B(x))
Skolemisation
Le but de cette opération est de supprimer les quantificateurs
sation provient de l’observation suivante : lorsque on a une formule du type
. L’idée de la skolémi-
∃
x
∀
y p(x, y)
∃
(5.1)
54
Université de Genève – G. Falquet
c
5.5. NORMALISATION ET RÉSOLUTION
cela signifie que pour chaque x on peut trouver au moins un y tel que p(x, y). Donc on peut définir une fonction f (x) qui nous fournit une valeur y = f (x) telle que p(x, y) est vraie. Ceci qui nous permet de réécrire la formule 5.1 comme
S’il y a plusieurs quantificateurs universels, la fonction dépend de toutes les variables
x p(x, f (x))
∀
qui viennent avant y dans la formule.
Exemple 5.8. Skolemisation
1. A1 =
x
∀
y ∀
∃
z(E(x, y)
A(x, z)).
⇒ sk(A1) =
x
∀
y(E(x, y)
∀
⇒
A(x, f (x, y))).
2. A2 =
x
∀
u
∃
y ∀
z(P (x, u)
(Q(u, y)
R(y, z))).
∃ sk(A2) =
⇒ x
∧ y(P (x, f (x))
∀
∀
(Q(f (x), y)
∧
⇒
R(y, g(x, y)))).
La skolemisation ne conserve pas le sens des formules. En général sk(A) n’est pas équiva- lente à A, mais
Théorème 5.1. A est satisfiable si et seulement si sk(A) l’est.
Par conséquent, pour démontrer que
on peut démontrer (par exemple avec le principe de résolution) que
f1, . . . , fn} |
= g
{
sk(f1), . . . , sk(fn), sk(
g) }
¬
{
est inconsistant.
Forme clausale
Un fois que la formule a été skolémisée il ne reste que des variables quantifiées univer- sellement. On peut donc se passer de l’écriture explicite des quantificateurs. La formule restante est composée d’atomes et de connecteurs logiques. On peut alors appliquer la même technique qu’en logique propositionnelle pour la mettre en forme normale conjonc- tive, puis sous forme d’un ensemble de clauses.
Université de Genève – G. Falquet
c
55
5.5. NORMALISATION ET RÉSOLUTION
Exemple 5.9. Si on repart de la formule skolémisée
sk(A2) =
x
∀
y(P (x, f (x))
∀
⇒
(Q(f (x), y)
∧
R(y, g(x, y))))
, l’élimination des quantificateurs universels donne
P (x, f (x))
(Q(f (x), y)
∧
⇒
R(y, g(x, y)))
. En appliquant la transformation
Publicité
on obtient
⇒ −∨
P (x, f (x))
¬
∨
(Q(f (x), y)
∧
R(y, g(x, y)))
. Puis par distributivité
P (x, f (x))
( ¬
∨
Q(f (x), y))
P (x, f (x))
( ¬
∧
∨
R(y, g(x, y)))
et donc deux clauses :
1.
2.
P (x, f (x))
P (x, f (x))
¬
¬
Q(f (x), y))
R(y, g(x, y))
∨
∨
Application du principe de résolution en logique des prédicats
On se rappel que la règle de résolution en logique propositionnelle stipule qu’étant
donné deux clauses
et
C1 = L1 ∨
. . .
Li ∨
∨
. . .
∨
Lm
C2 = M1 ∨
. . .
Mj ∨
∨
. . .
∨
Mn
où Li = p et Mj = Le résolvant de C1 et C2 sur Li et Mj est la clause
p.
¬
Li
. . .
CR = L1 ∨
Lm ∨ Dans le cas de la logique des prédicats, on peut effectuer la résolution sur deux littéraux P (u1, . . . , un) non seulement s’ils sont égaux mais également si les ti et
Mj+1 ∨
Li+1 ∨
M1 ∨
1 ∨
1 ∨
Mn
Mj
. . .
. . .
. . .
∨
∨
∨
∨
−
−
P (t1, . . . , tn) et ui unifiables.
¬
Définition 5.4. Deux formules atomiques sont unifiables s’il existe une substitution des variables par des termes qui rend les deux formules identique.
Université de Genève – G. Falquet
c
56
5.5. NORMALISATION ET RÉSOLUTION
Par exemple, les formules atomiques P (x, a, y) et P (c, a, z) , où a et c sont des
constantes, sont unifiables par la substitution x
c, y
z .
→
→
Par contre P (x, a, y) et P (c, b, z) ne sont pas unifiables car les constantes a et b ne
peuvent être unifiées (on ne peut remplacer une constante par une autre).
Exemple 5.10. Résolution avec unification
C1 =
P (x)
¬
∨¬
Q(y)
∨
R(x, y)
C2 = Q(a)
C3 = P (b)
y
→
x
→
a sur C1 permet la résolution avec C2 :
CR = b sur CR, résolution avec C3 :
P (x)
¬
∨
R(x, a)
CS = R(b, a)
Comme en logique des propositions, on emploie généralement la résolution pour faire
des preuves par réfutation.
Exemple 5.11. On veut montrer que les trois formules
∀
x ((S(x)
f1 = P (x)) , f2 = T (x)) ont pour conséquence la formule P (a) . Passage en forme clausale :
⇒
∨
x (S(x)
∀
∨
R(x)) , f3 =
R(a)
¬
et produit donc les deux clauses
f1 ≡
x (S(x)
( ∀
⇒
P (x))
∧
x (T (x)
( ∀
⇒
P (x))
C1 =
S(x)
¬
C2 =
T (x)
¬
P (x)
P (x)
∨
∨
f2 ≡
C3 = S(x)
R(x)
∨
f3 ≡
C4 =
R(a)
¬
.
La négation de la conséquence cherchée donne
C5 =
P (a)
¬
Université de Genève – G. Falquet
c
57
5.5. NORMALISATION ET RÉSOLUTION
Par résolution sur R de C3 et C4 avec x
a on produit
→
Par résolution sur S de C1 et C6 on produit
C6 = S(a)
C7 = P (a)
Enfin C5 et C7 donnent la clause vide. On a donc prouvé la conséquence logique.
Université de Genève – G. Falquet
c
58