UE 102e. M1.IST-IE cours n°2

cours n°2 UE102e(S. Sidhom)

UE 102e. M1.IST-IE cours n°2

Systèmes à base de règles

Par :Sahbi SIDHOM

MCF. Université Nancy 2Équipe de recherche SITE – LORIA

[email protected]

cours n°2 UE102e(S. Sidhom) 2

Mécanisme d’inférence

Logique des prédicats&Différents types de raisonnement


I.Logique des prédicats


Introduction

Le langage des prédicats du premier ordre (LP1) est un langage formel :

Il permet d’exprimer des connaissances (complexes) avec rigueur

Il permet de combiner les connaissances pour engendrer de nouvelles


Syntaxe LP1L’alphabet du LP1 comprend : Séparateurs : , ( ) Constantes : ensemble de symboles Lettres minuscules latines et leur concaténation :

« a », « bloc »,… Variables : ensemble de symboles Lettres majuscules latines et leur concaténation :

« X », « NOM »,… Fonctions : une quantité calculée mathématiquement Lettres minuscules latines, leur concaténation et leur arité n>0 :

age(X), arité n=1 ;occurrence(X,Y), arité n=2 ;


Prédicats : propositions et leurs arités ou nombre d’arguments n0 (à valeur logique 0 ou 1)

Lettres majuscules latines, leur concaténation et leur arité :PERE(X,Y), arité n=2 ;HOMME(X), arité n=1 ;

Connecteurs logiques : ensemble de signes Signes logiques un-aire ou binaire :

négation : conjonction (et) : disjonction (ou) : implication (implique) : implication mutuelle (équivalence) :

Quantificateurs : ensemble de 2 signes Signes « quel que soit » et « il existe » :

quantificateur universel (quel que soit) : quantificateur existentiel (il existe):


Termes Les termes sont définis inductivement comme suit :

1. Toute constante est un terme2. Toute variable est un terme3. Si f est une fonction d’arité n>0

si t1, t2, …,tn sont des termes alors f(t1, t2, …,tn) est un terme

Exemples : Sont des termes :

X a f(b) g(a,f(b,X,Y))

Ne sont pas des termes : P(a,X) AGE(f(X))


Atomes (ou formules atomiques) Formule atomique :

si P est un prédicat d’arité n0 Et si t1, t2, …,tn sont des termes Alors P(t1, t2, …,tn) est un atome

Exemple : Sont des atomes : P(X), Q(a,X) Ne sont pas des atomes : successeur(X,Y), f(a,X)


Portée d’un quantificateur

C’est l’expression sur laquelle agit le quantificateur (soit universel soit existentiel)

Exemples : X P(X) Q(f(X)) : la portée de X est P(X) X (P(X) Q(f(X))) : la portée de X est P(X) Q(f(X))


Occurrence (libre ou liée) d’une

variable Une occurrence d’une variable X est liée

si et seulement siX apparaît dans la portée d’un quantificateur utilisant cette variable.

sinon X est libre

Exemples : 1. P(a,f(X,Y)) Z Q(a,Z)

Z : variable liée X,Y : variables libres

2. X (P(a,X)) Z (Q(X,Z)) X: variable à la fois libre et liée


Formule bien formée (fbf)Toute fbf est engendrée par application des 3 lois suivantes :

1. Les atomes sont des fbf2. Si G et H sont des fbf

Alors G, H, GH, GH, GH, GH sont des fbf3. Si G est une fbf et X est une variable

alors X G(X), X G(X) sont des fbf

Exemples : X Y Z (PERE(X,Y) PERE(Y,Z) GRANDPERE(X,Z)) : est une fbf f(a,X), g(P(X,a)) : ne sont pas des fbf


Validité (ou invalidité) d’une fbf

Une fbf est valide ssi sa valeur de vérité est vrai (V) selon toute interprétationSinon elle est invalide


Consistance (ou inconsistance) d’une fbf

Une fbf est inconsistante ssi sa valeur de vérité est à faux (F) selon toute interprétationSinon elle est consistante


fbf équivalentes

Deux fbf G et H sont équivalentes ssi elles prennent les mêmes valeurs de vérité (V ou F) pour toute interprétation.Exemples :P(X) Q(X) et P(X) Q(X) sont équivalentes


fbf conséquences logiques

G est une fbf conséquence logique des fbf H1, H2, …, Hn ssi

tout modèle de H1, H2, …, Hn est modèle de G

Exemples : P(a) est conséquence logique de X P(X),

X Q(X) est conséquence logique de X (P(X) Q(X))


II.Règles d’inférence

Documents

UE 102e. M1.IST-IE cours n°2