Intelligence Artificielle AI - Prolog : Travaux Dirigés 3 – Les formes clausales
Télécharger PDFExercices sur les Formes Clausales et l'Unification en Logique
Exercice 1
Mettre sous forme prénexe les formules suivantes :
- (∃x P(x) ∨ ∀x Q(x)) ∧ (R ⇒ ∀x S(x))
- ¬((∃x P(x) ∨ ∀x Q(x)) ∧ (R ⇒ ∀x S(x)))
- ∀x P(x) ⇔ ∃x Q(x)
Exercice 2
Mettre sous forme clausale les formules suivantes :
- ∀x ∃y ∀z [R(x,y,z) ⇒ ∀t ∃z S(t,z)]
- ∀y ∃x R(x,y) ⇔ ∀z ∀x R(z,x)
- ∀x ∀y (GP(x,y) ⇒ ∃z (P(x,z) ∧ P(y,z)))
- ∀x [P(x) ∧ ∀y ∃t (¬Q(t,y) ⇒ ∀z R(A,t,y))]
- ∀x (∃y [R(y,x) ⇒ ∃u R(u,x) ∧ ¬∃t (R(t,x) ∧ R(t,y))])
- ∀x ∃y [P(x,A,z) ⇒ ∃z S(y,z,t)]
Exercice 3
Trouvez, quand il existe, un unificateur pour chacun des ensembles de clauses ci-dessous. Donnez en outre la formule booléenne résultante de l’unification :
-
Clauses :
- G(x, f(A, y))
- G(x, B)
- G(x, f(A, g(z)))
-
Clauses :
- P(u, g(f(a, b)), u)
- P(f(x, g(z)), x, f(y, g(b)))
-
Clauses :
- G(x,y)
- G(f(x), A)
Exercice 4
Pour chaque cas, dire si les deux formules atomiques sont unifiables et donner, le cas échéant, un unificateur :
-
a) f(x, g(x,y)) et f(g(y,z), g(g(h(u),y), h(u)))
-
b) k(x, f(g(y)), f(x)) et k(h(t,z), f(z), f(h(y,z)))
-
c) P(x, f(x), g(f(x),x)) et P(z, f(f(A)), g(f(g(A,z)), v))
-
d) P(u, g(f(A,b)), u) et P(f(x, g(z)), x, f(y, g(B)))
-
e) P(x, f(x), f(f(x))) et P(f(f(y)), y, f(y))
FAQ
Qu’est-ce qu’une forme prénexe ?
Une forme prénexe est une expression logique où tous les quantificateurs (∀, ∃) sont placés au début, suivis d’une formule sans quantificateurs.
Comment transformer une formule en forme clausale ?
La forme clausale se construit en appliquant les règles de transformation suivantes :
- Supprimer les équivalences (⇔) en utilisant les implications (⇒).
- Déplacer les négations vers l’intérieur en utilisant les lois de De Morgan.
- Éliminer les quantificateurs universels (∀) en remplaçant par des existentiels (∃) ou vice versa.
- Appliquer la résolution pour obtenir des clauses.
Qu’est-ce qu’un unificateur ?
Un unificateur est une substitution qui rend deux formules atomiques identiques. Si un unificateur existe, les formules sont dites unifiables.