Embed Size (px)
DESCRIPTION
logique des prédicats du premier ordre
Citation preview
Approche logique de l’Intelligence Artificielle
Où l’on voit comment une méthode de démonstration automatique de théorèmes en logique des prédicats
permet la conception d’un langage de programmation logique, capable de concevoir des systèmes
« intelligents »
Jean-Philippe Préaux
EOAA – 2010-11
Logique des prédicatsSyntaxe :Elle donne les règles de formation des formules.
Sémantique : Elle assigne une valeur de vérité vrai ou faux aux formules.
Système axiomatique : Formalise le concept de preuve et la méthode déductive.Copyrig
ht : Jean-Philip
pe Préaux
Syntaxe
Copyright :
Jean-Philippe Préaux
Symboles du calcul des prédicats
Les variables : Les constantes : Les fonctions (munies d’une arité) :Les prédicats (munis d’une arité) :Les connecteurs logiques : le ‘non’ ,le ‘et’ , le ‘ou’ , le ‘implique’ , et le ‘équivaut à’ .Les quantificateurs universel et existentiel Les séparateurs : parenthèses ‘()’ et virgule ‘,’.
1 2, , , , ,...x y z x x, , ,...a b c
, ,...f g, , ,...P Q R
¬ ∧ ∨ ⇔
∀ ∃Copyrig
ht : Jean-Philip
pe Préaux
Les termesToute variable, toute constante sont des termes.
Si est une fonction d’arité et si sont termes
alors est un terme.
Tous les termes s’obtiennent ainsi (propriété de clôture).
f 0n >1 2, ,..., nT T T n
1 2( , ,..., )nf T T T
Copyright :
Jean-Philippe Préaux
Les atomes
Si est un prédicat d’arité 0,alors est un atome (une proposition) .
Si est un prédicat d’arité et si sont termesalors est un atome.
Propriété de clôture.
P
0n>P
1 2, ,..., nT T T n1 2( , ,..., )nP T T T
P
Copyright :
Jean-Philippe Préaux
Les formules bien formées (FBF)
Les atomes sont des FBFs.
Si et sont des FBFs, alorssont des FBFs.
Si est une FBF, et une variable,alors et sont des FBFs.
Propriété de clôture.
P
P
Q;( );( );( );( )P P Q P Q P Q P Q¬ ∨ ∧ ⇔
x,x P∀ ,x P∃
Copyright :
Jean-Philippe Préaux
Représentation d’un FBF sous forme d’arbre
x∀
x∃
P
x
∨
P
a
¬
Q
,( , ( ) ( ( ) ))x x P x P a Q∀ ∃ ∨ ¬
Copyright :
Jean-Philippe Préaux
Portée d’un quantificateur
x∀
x∃
P
x
∨
P
a
¬
Q
,( , ( ) ( ( ) ))x x P x P a Q∀ ∃ ∨ ¬
La portée d’un quantificateurest la sous-formule quidébute à sa base.
Copyright :
Jean-Philippe Préaux
Portée d’un quantificateur
x∀
x∃
P
x
∨
P
a
¬
Q
,( , ( ) ( ( ) ))x x P x P a Q∀ ∃ ∨ ¬
La portée d’un quantificateurest la sous-formule quidébute à sa base.
Ex: La portée de est :x∀, ( ) ( ( ) )x P x P a Q∃ ∨ ¬
Copyright :
Jean-Philippe Préaux
Portée d’un quantificateur
x∀
x∃
P
x
∨
P
a
¬
Q
,( , ( ) ( ( ) ))x x P x P a Q∀ ∃ ∨ ¬
La portée d’un quantificateurest la sous-formule quidébute à sa base.
Ex: La portée de est :
La portée de est :
x∀, ( ) ( ( ) )x P x P a Q∃ ∨ ¬
x∃( )P xCopyrig
ht : Jean-Philip
pe Préaux
Variable libre, liée
L’occurrence d’une variable dans une formule est libre si elle n’est pas dans la portée d’un quantificateur ou . Sinon elle est dite liée.Une variable apparaissant dans une formule est libre si elle admet une occurrence libre. Sinon elle est liée.Une formule dont toutes les variables sont liées est une formule close.
x∀ x∃
x
Copyright :
Jean-Philippe Préaux
Exemple :x∀
P
y
Q
f
z
y∃
y x
,( , ( ) ( , , ( )))x y P y Q y x f z∀ ∃
Copyright :
Jean-Philippe Préaux
Exemple :x∀
P
y
Q
f
z
y∃
y x
,( , ( ) ( , , ( )))x y P y Q y x f z∀ ∃
La variable est liée.Elle est dans la portée de
xx∀
Copyright :
Jean-Philippe Préaux
Exemple :x∀
P
y
Q
f
z
y∃
y x
,( , ( ) ( , , ( )))x y P y Q y x f z∀ ∃
La variable est liée.Elle est dans la portée de
xx∀
La variable a une occurrence liée, et uneoccurrence libre.
y
C’est une variable libre
Copyright :
Jean-Philippe Préaux
Exemple :x∀
P
y
Q
f
z
y∃
y x
,( , ( ) ( , , ( )))x y P y Q y x f z∀ ∃
La variable est liée.Elle est dans la portée de
xx∀
La variable a une occurrence liée, et uneoccurrence libre.
y
C’est une variable libre
La variable est libre.zCopyrig
ht : Jean-Philip
pe Préaux
