Cours 2 Logique de PrédicatsVocabulaire- Syntaxe - Sémantique

Kaninda Musumbu

1Département d’InformatiqueUniversité de Bordeaux

Notes du cours et TD :http://dept-info.labri.u-bordeaux.fr/ musumbu/Expert/

K Musumbu Système Experts

Introduction

RemarqueEn logique des propositions on considère une propositioncomme un tout, représenté par une variable, dont on nedétaille pas le contenu.On ne s’intéresse qu’à sa vérité ou à sa fausseté.En logique des prédicats, ou logique du premier ordre, onregarde les propositions de plus près.Exemple : Charles est grandest grand est un prédicat (ce qu’on dit à propos dusujet) Qu’on réécrit sous une forme qui met en évidence leprédicat: estgrand(Charles)

K Musumbu Système Experts

Introduction

NotationSuivant ce modèle, la logique des prédicats représente lespropositions élémentaires (atomiques) sous la forme :nom-prédicat(objet1,objet2,...) oùobjet1,objet2,...)sont les objets sur lesquels porte le prédicat (le sujet et seséventuels complément)

K Musumbu Système Experts

Motivation

DéfinitionComment exprimer les phrases suivantes

"No all birds fly" est équivalente à "Some birds don’t fly"."Not all integers are even" equiv est équivalente à "Someintegers are not even"."Not all cars are expensive" equiv "Some cars are notexpensive".

RemarqueLogique propositionnelle pas suffisament expressive(puissante) pour représenter tous types d’assertions telle que "

x ≥ 1

".

K Musumbu Système Experts

Extension de la logique propositionnnelle

ObjectifOn veut parler des individus et leur donner un nom.On veut parler de propriétés de ces individus et desrelations entre eux.

RemarquesLes variables représentent non pas des propositions mesdes objets sur lesquels portent les prédicats.L’introduction de variables permet de formuler deux typesd’énoncés:

énoncés universelsSi X est une girafe alors X est un animalénoncés existentielsIl y a au moins un nombre entier N tel que

N > 3etN ∗ N < 30.

K Musumbu Système Experts

Syntaxe de la logique de Prédicat

Langage

Pour écrire des formules de logique des prédicats, on a besoind’un vocabulaire

constantes (a, b, c, ...)variables (x,y,z, ...)fonctions (f,g,h, ...)prédicats (p,q,r, ...)quantificateurs (∀, ∃):

K Musumbu Système Experts

Grammaire de la logique de Prédicat

terme = constante | variable| fonction"("terme,...,terme")"

atome = prédicat"("terme,...,terme")"formule = atome

| ∀ variable formule| ∃ variable formule| ¬ formule| formule connecteur formule

connecteur = ∨ | ∧ | ⇒ | ⇔

K Musumbu Système Experts

Priorité des connecteurs

Ordre de priorité

(, ) > ∀,∃ > ¬ > ∨,∧ >→>↔

Exemples:Parenthéser ces formules1 ¬a ∨ b → q2 ∀x b → q3 ∀x ∈ E∃y ∈ E 6 r(x) ∧ w(y , x)→ g(x)4 ∀x p(x)→ ∃yq(y , x)

K Musumbu Système Experts

Définition de Prédicat

Prédicat:Tout énoncé exprime une propriété d’un ensemble ou d’unecollection d’ensemble.

Soient E1, ...,En, des ensembles d’Univers on appelle�prédicat� ou relationtoute application de E1 × E2 × ...× En dans V .Donc E1, ...,En, la donnéede G ( n-uplets (x1, x2, ..., xn)) telle que

(x1, x2, ..., xn) ∈ G⇐⇒ P(x1, ..., xn)

ariténombre d’argument associé à chaque prédicat.

K Musumbu Système Experts

Exemples

"La robe de Monica est blue","Le ciel est blue","La couverture de ce livre est blue",

est blue", est un prédicat, on lui associe un nom est_blue ouBlue ou B.Ainsi une phrase qui affirme qu’un objet est blue s’ecrit:"B(x)", où x représente un objet quelconque.B(x) se lit "x est blue".

K Musumbu Système Experts

Calcul de Prédicats

ObjectifDéfinir quels sont les énoncés qui sont valides et quels sontceux qui ne le sont pas.

AritéChaque symbole de prédicat a une arité qui détermine lenombre d’arguments ou d’objets auxquels il est appliqué

B(x) , B(x,y) , B(x,y,z)

K Musumbu Système Experts

Valeur d’un Prédicat

ValuationSoit θ une application (ou valuation) de E dans V .La valeur de vérité d’un prédicat P esttoute valuation θ telle que Pθ ∈ V .

Un prédicat clos n’a qu’une seule valeur possible de vérité.C’est, donc, une proposition.Un prédicat qui ne contient aucune variable libre admetune et une seule valeur de vérité.Les prédicats à deux places sont dits binaires.Les prédicats à une place sont dits unaires oumonadiques.Il y a deux prédicats à 0 places, chacun d’eux estidentifiable à l’un des éléments de V .

K Musumbu Système Experts

Quantificateurs

Définitionopérateur reliant une ou plusieurs variables à un ensemble

Soit A un énoncé contenant ou non des occurrences libres dela variable x de domaine E :

∀xA signifie� pour tout x de E , A(x)�.∃xA signifie� il existe au moins un x de E , tel que A(x)�.

RemarqueUn prédicate avec variables libre n’est pas une proposition.Exemple: x > 1 n’est pas une proposition.Ce sont des opérateurs qui transforment des prédicatsn−aires en prédicats (n − 1)−aires ( et en particulier lesprédicats monadiques en propositions)

K Musumbu Système Experts

Valeur d’une expression quantifiée

∀xA = v si chaque x0 de l’ensemble E : A(x0) = v .∃xA = v s’il y a au moins un x0 de E :A(x0) = v .

Exemples:1 ∃x(18 = 3x) signifie� 18 est multiple de 3�.2 ∀x(x ∗ 1 = x) signifie� 1 est neutre pour ∗ � .3 ∀x ∈ E∃y ∈ E(x 6= 0⇒ x ∗ y = 1) signifie� (E , ∗) est un groupe� .

K Musumbu Système Experts

Négation d’une Formule Quantifiée

Soit A un énoncé¬(∀x : A(x))⇐⇒ ∃x(¬A(x))¬(∃x : A(x))⇐⇒ ∀x(¬A(x))

K Musumbu Système Experts

Portée des Quantificateurs

DéfinitionLe concept de portée est central pour un systèmed’infèrence.Elle permet de distinguer les différents usages du mêmesymbole de variable.

Portéatome ou formule à laquelle la quantification s’applique

∀xA(x), A(x) est la portée de ∀x

K Musumbu Système Experts

Portée des Quantificateurs

Variables liéesvariables sous la portée de quantificateurs

Ensemble de variables liéesSi A est un atome ou formue, l’ensemble Varlie(A) de variablesliées de A est défini par :

si A est un atome alors Varlie(A)Porté= ∅si A est de la forme B → C alors Varlie(A)= Varlie(B)∪Varlie(C)si A est de la forme ¬B alors Varlie(A) = Varlie(B)si A est de la forme ∀xB ou ∃xBalors Varlie(A) = Varlie(B)\ { x }

Exemple∀x(enfant(x)⇒ ∃y(mere(y , x))∃x(∀yR(x , y)⇒ ∃z¬S(x , z, v))

K Musumbu Système Experts

Variables libres et liées

Variables libresUne occurrence d’une variable est libre si elle n’est dans laportée d’aucun quantificateur. Sinon elle est liée.

∀y(P(x) ∨ ∃x(P(x) ∧Q(y))

formule close ou ouverteformule sans variables libres, sinon elle est ouverte.

∀x(entier(x)⇒ ∃y(entier(y) ∧ plusGrand(y , x)

K Musumbu Système Experts

Variables libres et liées

Exemple

mere(x) ∨ pere(y)∀x(mere(x) ∧ pere(y , x)∀x(enfant(x)⇒ ∃y(mere(y , x))∃x∀yR(x , y)⇒ ∃z¬S(x , z))∃x∀yR(x , y) ∨ R(y , x)⇒ ∃z¬S(x , z))

K Musumbu Système Experts

Exemples de formalisation

Tous les hommes sont mortels

Seulement les hommes sont mortels

Il existe un homme mortel

Il n’existe pas d’homme mortel

K Musumbu Système Experts

Exemples de formalisation

Tous les hommes sont mortels

∀x(H(x)⇒ M(x))

Seulement les hommes sont mortels

∀x(M(x)⇒ H(x))

Il existe un homme mortel

∃x(H(x)⇒ M(x))

Il n’existe pas d’homme mortel

∃x(H(x) ∧ ¬M(x))

K Musumbu Système Experts

Localité de la notion de Variable

DéfinitionDans un système basé sur la logique, le nom d’une variable estcomplètement local à la règle dans laquelle elle apparaît.

Exemple

X est mortelsi

X est humain

X est un commerçantsi

X possède une boutique

Remarque : il n’y a aucun lien entre les occurrences de X dansles deux règles ci-dessus.

K Musumbu Système Experts

Quantification Revisitée

1 Les quantificateurs sont implicites dansla manière dont sont écrites les règles.Donc, on peut considérer toutes les variablescomme étant quantifiées.

2 Si une variable apparaît dans la conclusion d’une règleelle est supposée vraie pour toute constantepour laquelle la règle est appliquée.On dit que les variables de conclusions sont quantifiéesuniversellement.

3 Les variables qui apparaissent uniquementdans les prémisses et non dans la conclusiond’une règle sont dites quantifiées existentiellement

K Musumbu Système Experts

Quantification Revisitée

Exemple

Si Y est un sportet X pratique Yalors X est athlétique

Pour chaque valeur de X , la règle est vraie,si une certaine valeur de Y peut-être trouvéeAutrement dit: du moment qu’on trouve Y , on n’a pas besoin desavoir de quel Y il s’agit.

RemarqueLa raison de cette convention se base sur l’analyse de lamanière dont les règles sont exécutée

K Musumbu Système Experts

Substitution et Instance

Définitionune substitution est une application des variables dans lestermes

θ : Variable −→ Terme

L’application d’une substitution à une expression E est lerésultat du remplacement simultané de toutes les occurrenceslibres des variables dans E par leur terme associé.

DéfinitionSi E est une expression et θ une substitution alors Eθ estappelé une instance de E .

Notation Soit x = {x1, ..., xn} tel que θ(x) 6= x , La substitutionθ, est alors notée

θ(x) = {x1 ← t1, . . . , xn ← tn}

K Musumbu Système Experts

Unificateur, Most general unifier

Unificateur:Soient t1, t2, deux termes et θ une substitution. θ est ditunificateur ssi t1θ = t2θ

Définition : mgut1, t2, admettent une instance commune t ssi

∃θ1, θ2 t.q. t1θ1 = t2θ2 = t

Exemple t1 = f (a,g(Y )) et t2 = f (X ,g(b))t1 est plus général que t2 ssi t2 est une instance de t1 et t1non de t2.un unificateur de t1, t2 est une substitutionθ t.q. t1θ = t2θ.un unificateur général (mgu) de t1, t2 est un unificateur telleque l’instance associée aux 2 soit la plus générale.

K Musumbu Système Experts

Algorithme d’Unification (1/3)

Entrée: T1 et T2 à unifierSortie: θ = mgu(T1,T2) ou echec

AlgorithmeInitialisation

θ = {};vide_pile(P);echec=false;empile(P,T1 = T2);

K Musumbu Système Experts

Algorithme d’Unification (2/3)

Tant_que( non_vide(P) et non(echec)) faireeq=depile(P); (* eq=(X=Y) *)eqθ ;case:

(var(X) et var(Y)) ou(const(X) et const(Y)) et X==Y

continue;var(X) et X 6∈ occ(Y );

subst Y à X dans P et θ ;θ= θ ∪ {X ← Y}

K Musumbu Système Experts

Algorithme d’Unification (3/3)

var(Y) et Y 6∈ occ(X )subst X à Y dans P et θ ;θ= θ ∪ {Y ← X}

X = f (X1, . . . ,Xn) et Y = f (Y1, . . . ,Yn)empile(P,Xi = Yi , ∀i = 1..n)

sinon echec = true;Fin TQSi echec alors sortie= echec

sinon sortie= θFin

K Musumbu Système Experts

Exercice

Les expressions suivantes sont-elles unifiables,si oui quel est leur mgu

p(f (a),g(X )) et p(Y ,Y )

p(a,X ,h(g(Z ))) et p(Z ,h(Y ),h(Y ))

p(X ,X ) et p(Y , f (Y ))

K Musumbu Système Experts