Logique des pr edicats

2011-2012

1 Pourquoi les pr edicats

Limitations de la logique des propositions.

Exemple : on veut mod eliser le probl`eme suivant :

Si un etudiant a les UEs PROG001 et PROG002, il a le module PROG.

Sil a aussi lUE Stage, il a le CP PROGRAMMEUR.

On peut le faire en logique des propositions :

prog001 ' prog002 prog

prog ' stage cp

Mais ce syst`eme ne permet pas de g erer des informations sur plusieurs etudiants.

Par exemple, si Aragorn et Bilbo sont deux etudiants dinformatique, il faudrait ecrire

les formules :

aragornAprog001 ' aragornAprog002 aragornAprog

aragornAprog ' aragornAstage aragornAcp

bilboAprog001 ' bilboAprog002 bilboAprog

bilboAprog ' bilboAstage bilboAcp

Pour eviter de dupliquer les r`egles pour chaque cas particulier, on introduit la notion

de variables, qui nous permettra de raisonner de mani`ere plus g en erale :

X(prog001(X) ' prog002(X) prog(X))

X(prog(X) ' stage(X) cp(X))

On ajoute donc des arguments aux propositions. La nouvelle construction, qui est

vraie ou fausse pour certaines valeurs, est appel ee un pr edicat.

2 Syntaxe de la logique des pr edicats (sans symbole fonc-

tionnel)

Dans un premier temps, nous allons d ecrire un sous ensemble simpli e de la lo-

gique des pr edicats, que nous compl`eterons par la suite.

On d enit une logique du premier ordre sans symboles fonctionnel par la donn ee :

dun ensemble de de symboles de pr edicats P ; chaque pr edicat a une arit e, qui

est son nombre darguments.

dun ensemble de constantes C ;

dun ensemble de variables X.

On d enit les formules du premier ordre pour P et C inductivement :

Base : si p/n P alors p(a1, ..., an) est une formule, pour tout ai dans C * X

(cest aussi un atome). exemple : si X est une variable, et aragorn une constante, et que

(cid:28) prog (cid:29) est un pr edicat darit e 1, alors prog(X) et prog(aragorn) sont des formules

(et des atomes).

Cas particulier : les pr edicats darit e 0 correspondent aux propositions.

induction : Si A et B sont des formules et X une variable, alors

A est une formule ;

(A ' B) est une formule ;

(A ( B) est une formule ;

(A B) est une formule (on peut eventuellement ajouter et ) ;

XA est une formule ;

Les parentheses servent a eviter les ambigu 1t es.

fermeture : les seules formules du premier ordre sur P et C sans symboles fonc-

tionnels sont celles obtenues par induction.

Grammaire formelle (en utilisant les DCG) :

/ grammaire de la logique des pr edicats en DCG /

terme --> foncteur,"(",termes, ")".

terme --> constante.

terme --> variable.

termes --> terme.

termes --> terme, ",", termes.

atome --> predicat, "(", termes, ")".

formule --> atome.

formule --> "non", esp, formule.

formule --> "(", formule, esp, "ou", esp, formule, ")".

formule --> "(", formule, esp, "et", esp, formule, ")".

formule --> "(", formule, esp, "->", esp, formule, ")".

formule --> "pourtout", esp, variable, esp, formule.

formule --> "existe", esp, variable, esp, formule.

esp --> " ".

esp --> " ", esp.

/ Lexique /

non --> "non".

foncteur --> "fonc".

foncteur --> "f".

constante --> "a".

constante --> "b".

constante --> "c".

variable --> "x".

variable --> "y".

variable --> "z".

predicat --> "p".

3 Quantication et variables

Xp(X) : (cid:28) pour tout X, p(X) (cid:29), quantication universelle.

Xp(X) : (cid:28) il existe un X (au moins) pour lequel p(X) (cid:29), quantication existen-

tielle.

3.1 Quelques particularit es des quanticateurs

Dans une quantication, XA, la formule A est dite dans la port ee de la quanti-

cation. En effet, si on ecrit (p(X) ' Xq(X)), le premier X nest pas concern e

par la quantication, et le second, si. Les deux X sont donc `a consid erer comme

des variables diff erentes.

(XA(X)) equivaut `a X( A(X))

3.2 Variables quanti ees, li ees et libres

Une variable est quanti ee quand elle appara 1t juste derri`ere un quanticateur.

Par exemple, dans Xp(X), le premier X est dit quanti e, le second non.

une variable est dite li ee quand elle est dans la port ee dune quantication. Dans

la formule pr ec edente, X est li ee.

une variable X est libre si elle nest dans la port ee daucune quantication la

concernant. Par exemple, dans XY q(X, Y, Z), X et Y sont li ees, et Z est

libre.

Une formule est dite ferm ee (ou close) ssi elle na pas de variable libre. Un terme

est dit clos sil ne contient pas de variable.

Une formule est terminale (grounded en anglais) si elle ne contient pas de variable.

3.3 Notion dordre

La notion dordre explique sur quoi portent les quantications, et donc quelles sont

les variables possibles. Dans la logique du premier ordre, elles portent uniquement sur

les termes. Dans la logique du second ordre, les quantications peuvent aussi porter

sur les pr edicats.

Exemple de formule du second ordre : P Y P (Y )

4 S emantique logique

Comme pour la logique des proposition, un langage du premier ordre peut se voir

associer des interpr etations. Certaines propri et es d ependront de linterpr etation choisie,

dautre seront vraie dans toutes les interpr etations.

Une interpr etation donne un (cid:28) sens (cid:29) aux constantes et aux pr edicats. Les constantes

sont associ ees `a des valeurs prises dans un ensemble D qui d ependra de linterpr etation,

et les pr edicats prendront les valeurs (cid:28) vrai (cid:29) ou (cid:28) faux (cid:29). Comme les pr edicats prennent

des arguments, on consid`erera un pr edicat p/n comme une fonction de Dn dans {vrai, faux}.

Exemples :

Soit le langage du premier ordre de signature :

P = r/1

F = a, b

Voici quelques interpr etations possibles :

D = {1, 2} et jinterpr`ete a comme (cid:28) 1 (cid:29), et b comme (cid:28) 2 (cid:29). En interpr etant

r(X) comme signiant (cid:28) mon argument est pair, on voir que r(a) sinterpr`ete

comme (cid:28) faux (cid:29) et r(b) comme (cid:28) vrai (cid:29).

D = {java, lisp}, avec a interpr et e comme (cid:28) java (cid:29) et b comme (cid:28) lisp (cid:29), et r/1

comme signiant (cid:28) le langage est un langage imp eratif (cid:29). On aurait alors r(a)

faux et r(b) vrai.

Cependant, comme avec les propositions, certaines propri et es seront vraies dans

toutes les interpr etations : on aura toujours r(a) ( r(a), par exemple.

Pour interpr eter correctement une formule comme r(X), o`u X est une variable, il

faut, de plus, conna 1tre la valeur de X. On interpretera donc une formule par rapport a

une interpr etation et `a une assignation donn ee.

Linterpr etation sera d enie inductivement sur les formules : on d enira dabord

la s emantique des termes, puis celle des atome et des expressions complexes. Nous

donnerons une description formelle de la s emantique quand nous aurons introduit

lint egralit e de la logique des pr edicats.

5 Exemples et exercices

Nous allons voir des mod elisations qui permettent de g erer des bases de donn ees

d eductives (datalog).

On veut mod eliser `a partir de la logique des pr edicats lorganisation des cours dans

un iut.

On a, dans une base de donn ees, les tables suivantes :

Enseignant

nom

pr enom

01 Baggins Bilbo

Frodo

02 Baggins

Samwise

03 Gamgee

Etudiant

Pr enom

id Nom

01 Turing

Alan

02 Lovelace Ada

03 Babbage

04 Meyer

05 Wirth

Charles

Bertrand

Niklaus

Classe

Module

ID-mod

id-prof

On va interpr eter chacune de ces tables comme un pr edicat. On a ainsi le pr edicat

Intitule

Math

Logique

Programmation

Classe

enseignant/3, tel que enseignant(1,Baggins,Frodo) est vrai (etc...).

Ecrire une formule avec une variable libre X, qui sera vraie uniquement si...

X est le nom dun enseignant ;

X est le nom dun enseignant de programmation ;

X est le nom dun etudiant qui suit au moins un cours.

X est lintitul e dune mati`ere suivie par tous les etudiants

Exprimer en logique du premier ordre :

il ny a pas denseignant qui enseigne la programmation (on peut aussi ecrire des

formules fausses !)

tous les etudiants suivent au moins un cours.

il existe un enseignant qui donne des cours `a tous les etudiants.

6 Logique des pr edicats du premier ordre

En fait, les pr edicats peuvent avoir pour argument non seulement des variables

et des constantes, mais des structures cr e ees `a laide de symboles fonctionnels. Ces

symboles vont servir `a mod eliser non seulement des fonctions au sens classique du

terme, mais aussi `a repr esenter des structures comme par exemple les listes. Il ne faut

pas les confondre avec les pr edicats !

exemple : dans XestPair(plus(X, X)) est une formule dans laquelle estPair/1

est un pr edicat darit e 1, et plus/2 est un symbole fonctionnel darit e 2. Le premier,

quand on d enira une s emantique, sinterpr`etera comme vrai ou faux, et le second sera

compris comme une valeur.

On consid`ere g en eralement les constantes comme etant des symboles fonctionnels

darit e 0.

autre exemple : d enition des listes. On d ecrit g en eralement les listes en d enissant

une constante, vide, qui repr esente la liste vide, et un op erateur cons (un symbole

fonctionnel), qui prend deux arguments : le premier est le premier el ement de la liste,

et le second est la queue de la liste, qui est elle-m eme une liste. Une liste `a un seul

el ement a pour queue la liste vide.

Ainsi cons(4,cons(2, cons(8, vide))) repr esente la liste [4,2,8] ; et, si

pour le pr edicat membre/2, membre(X,L) signie que X est un el ement de la liste

Y, alors on peut dire que dans cette interpr etation, la formule

membre(2, cons(4, cons(2, cons(8, vide))))

sera vraie.

6.1 Syntaxe de la logique du premier ordre

On d enit les termes par induction comme :

une variable est un terme ;

une constante est un terme ;

si f/n est un symbole fonctionnel darit e n, et que t1, ...tn sont des termes, alors

f(t1, ...tn) est un terme.

Une fois les termes d enis, on reprend la d enition pr ec edente des formules, en

modiant simplement la base :

Si p/n est un symbole de pr edicat darit e n, et que t1, ...tn sont des termes, alors

p(t1, ...tn) est une formule.

6.2 S emantique de la logique du premier ordre

Par rapport `a la version (cid:28) sans symboles fonctionnels (cid:29), la difcult e sera justement

dinterpr eter ces symboles.

Un exemple simple (sur larithm etique).

On consid`ere le symbole fonctionnel s/1 (successeur), la constante (cid:28) z (cid:29), et le

pr edicat p/1.

On peut en donner linterpr etation suivante. On prend comme domaine D len-

semble des entiers, et

(cid:74)

I = 0

(cid:75)

s(z)

et en g en eral, si t est un terme,

Formellement :

D enition : une interpr etation I est la donn ee dun ensemble ID, et dune fonction

s(t)

(cid:74)

I est pair, faux sinon.

I = 1

(cid:75)

p(T )

(cid:75)

I = 1 +

(cid:75)

I = vrai si

(cid:74)

(cid:75)

(cid:74)

(cid:75)

qui :

`a toute constante associe une valeur dans ID ;

`a tout symbole fonctionnel darit e n associe une fonction de I n

`a tout pr edicat darit e n associe une fonction de I n

D enition : une assignation a est une application de lensemble V des variables

dans ID. Si a est une assignation, a est une assignation dans laquelle toutes les

variables prennent la valeur que leur donne a, sauf x, qui prend la valeur v.

D dans {vrai, faux}

D dans ID ;

On evalue une formule par rapport a une interpr etation I et a une assignation a. On

peut consid erer une interpr etation comme une fonction qui `a une assignation a donn ee

fera correspondre une valeur vraie ou faux.

Dans la d enition ci-dessous, on notera b, (b, ... les op erateurs usuels de lalg`ebre

bool eenne, qui sappliquent `a des bool eens, pour bien les diff erencier de ceux que nous

sommes en train de d enir.

On d enit par induction :

linterpr etation des termes :

I (a) =

pour une constante c,

(cid:75)

(cid:74)

I (a) = a(x)

pour une variable x,

(cid:75)

(cid:74)

pour un terme de la forme f (t1, ...tn), on a

I (a), ...,

(cid:74)

I (a))

(cid:74)

(cid:75)

I (a), ...,

I (a))

(cid:75)

I (

(cid:74)

I (a) = b

f (t1, ...tn)

(cid:74)

I (

I (a) =

(cid:74)

(cid:75)

Si A et B sont des formules :

pour un atome p(t1, ..., tn) :

(cid:75)

(cid:74)

I (a)

(cid:75)

I (a) 'b

(cid:74)

I (a) (b

(cid:74)

I (a) =

p(t1, ...tn)

(cid:75)

(cid:74)

(cid:75)

I (a) =

(A ' B)

(cid:75)

(cid:74)

I (a) =

(A ( B)

(cid:74)

(cid:75)

(A B)

I (a) = ( b

(cid:74)

(cid:75)

(cid:74)

les valeurs possibles).

I (a ) soit vraie.

(cid:75)

(cid:74)

(cid:75)

(cid:74)

I (a)

(cid:75)

(cid:74)

I (a) est vraie si et seulement si, pour toute el ement v dans ID,

I (a ) est vraie (i.e. la formule est vraie en remplac ant X par toutes

(cid:75)

(cid:74)

(cid:75)

I (a)) (b

I (a)

(cid:75)

I (a) est vraie si et seulement si il existe v dans ID tel que

7 Mod`eles, formules consistante, formules valides

Une interpr etation I est un mod`ele de la formule F si F est vraie dans I pour toute

assignation. On note

|=I F

On remarquera que cela revient `a supposer une quantication universelle (quel que

soit) devant chacune des variables libres de F.

Une formule est consistante si elle a au moins un mod`ele. Une formule inconsis-

tante est une formule qui na aucun mod`ele (comme p(X) ' p(X)).

Une formule est valide si elle est vraie dans toutes les interpr etations et toutes les

assignations. Par exemple : X(p(X) ( p(X)) est valide. On note :

|= X(p(X) ( p(X))

En dautre termes, une formule est valide si toute interpr etation est un mod`ele de cette

formule.

Une formule F est la cons equence logique des formules F 1, F 2...Fn si tout mod`ele

de F 1, F 2...Fn est aussi un mod`ele de F .

7.1

Interpr etation de Herbrand

Les interpr etations de Herbrand donnent une version compl`etement syntaxique de

linterpr etation. Dans une interpr etation I de Herbrand, lensemble ID est lensemble

des termes clos, quon appelle domaine de Herbrand. Ceux-ci sont leur propre image :

s(s(a))

La base de Herbrand est lensemble des formules atomiques closes (obtenues en

(cid:74)

utilisant toutes les combinaisons possibles d el ements du domaine de Herbrand).

I (a) = s(s(a)).

(cid:75)

Une interpr etation de Herbrand est obtenue en partitionnant la base de Herbrand

en deux ensembles, et en attribuant la valeur V au premier et F au second. On peut iden-

tier linterpr etation de Herbrand `a lensemble des atomes interpr et es comme vrais.

D`es quon introduit des symboles fonctionnels darit e non nulle, le domaine de

Herbrand devient inni.

7.1.1 Exemple 1

On consid`ere F = {sethy, ramses} et P = {pere/2}

Alors,

le domaine de Herbrand est DH = {sethy, ramses}

la base de Herbrand est

{pere(sethy, ramses), pere(sethy, sethy), pere(ramses, sethy), pere(ramses, ramses)}

Une interpr etation de Hebrand possible est {pere(sethy, ramses)}.

Cette interpr etation est, par exemple, un mod`ele de XY, pere(Y, X)

7.1.2 Exemple 2

On consid`ere F = {z/0, s/1} et P = {p/1}

Alors,

le domaine de Herbrand est DH = {z, s(z), s(s(z)), s(s(s(z))), ...} (inni).

la base de Herbrand est

{p(z), p(s(z)), p(s(s(z))), ...} (inni aussi)

Tout sous ensemble de la base de Herbrand d enit une interpr etation. On peut

consid erer I1 = la base en entier, ou I2 = les el ements de la base contenant un nombre

pair de s.

I1 et I2 sont tous deux des mod`eles de : X(p(X) p(s(s(X)))).

8 Manipulation des variables

Lorsquil sera question de d emonstration automatique (et de prolog), il faudra sou-

vent remplacer des variables par des termes (et non plus par des valeurs). Par exemple,

quand nous essaierons, en prolog, de montrer que la liste [3,5,8] contient la valeur

5, on tentera didentier cons(A,L) et cons(3,cons(5, cons(8,vide))).

Il faudra donc remplacer A par 3, ce qui correspond `a une assignation, mais L par

cons(5,cons(8, vide)), ce qui est compl`etement diff erent.

Dans ce cas, on ne parle plus dassignation, mais de substitution.

8.1 Substitution de variables

D enition : une substitution est une fonction qui, `a des variables libres associe des

termes.

Exemple : = est une substitution qui remplace les occur-

rences libres de X par Y, et celles de Z par s(X).

On applique la substitution sur une terme en remplac ant simultan ement toutes les

occurrences des variables concern ees dans le terme dorigine par la valeur `a substituer.

Ainsi, ((e(X, Y, Z)) = e(Y, Y, s(X)).

Quand on veut d enir la notion de substitution sur des formules, on ne substitue que

les variables libres. Le cas ech eant, il est toujours possible de renommer les variables.

Si A est une formule, on note A la formule obtenue en appliquant la substitution

aux variables de A.

Exemple de probl`eme : soit la formule Y dierent(X, Y ). La substitution X Y

donnera la formule Y dierent(Y, Y ), qui a visiblement un sens tr`es diff erent de la

pr ec edente. Pour eviter ce probl`eme, on ne nautorise pas de variables li ees dans les

valeurs donn ees par les substitutions.

En revanche, (Y dierent(X, Y )) donne (Y dierent(p(X, Q), Y )).

Si et sont des substitutions, note la substitution obtenue en appliquant

dabord et ensuite (notation diff erente de celle de la composition des fonctions).

8.2 Unication de variables

Un unicateur est une substitution qui permettra de rendre deux formules egales.

Cette op eration sera utilis ee dans les d emonstrations, et en particulier pour le langage

prolog.

Si nous savons que

contient(X, cons(X, L))

et (contient(X, L) contient(X, cons(A, L))))

Et que nous voulons prouver que contient(5, cons(2, cons(5, vide))) est vraie, il

nous faut identier X a 5 et L a cons(2, cons(5, vide)))

D enition : est un unicateur des formules A et B si A et B sont egales (`a

un renommage des variables li ees pr`es).

Par exemple, si A = Y p(Z, W, Y ) et B = Kp(A, A, K), alors

1 = est un unicateur.

2 = en est un autre.

On voit bien que 2 est meilleur que le premier ; en effet, il est plus g en eral. On

peut le formaliser en disant quil existe une substitution telle que 1 = 2 (en

loccurrence, = ).

On peut d emontrer lexistence de lunicateur le plus g en eral de deux formules.

Il nest pas unique, mais il est (cid:28) plus g en eral (cid:29) que tous les autres unicateurs, au

sens donn e ci-dessus. On d ecrira par la suite des algorithmes permettant dunier deux

formules.

9 Exercices

Pour raisonner sur des programmes concernant les tableaux, on se dote dune fonc-

tion case/2, dont le premier argument est le nom dun tableau (t, par exemple), et le

second est lindice de la case.

En supposant que le tableau t est de taille n, et en utilisant la logique des pr edicats

(et les symboles math ematiques usuels, comme <, >, =, quon supposera d enis),

exprimer les propri et es suivantes :

le tableau t contient la valeur a ;

m est le maximum des el ement du tableau t ;

le tableau t est tri e.

Un exemple en prolog : le pr edicat contient.

contient(X, cons(X,L)).

contient(X, cons(A,L)):- contient(X,L).

Traduction de chacune des r`egles en logique des pr edicats :

XLcontient(X, cons(X, L))

XAL(contient(X, L) contient(X, cons(A, L))))

(en r ealit e, le programme prolog correspond `a

XL(cid:0)contient(X, L) (L0(L = cons(X, L0)))

( (AL0(L = cons(A, L0) ' contient(X, L0)))(cid:1)

Logique des prédicats

Logique des prédicats