Algorithme d'unification de Herbrand

Contents

Avant de voir l'algorithme d'unification de Herbrand, nous devons différencier les formes que peuvent prendre nos formules et fonctions.

Contents Haut

Formes normales conjonctives

Lorsque nous avons une conjonction de disjonctions, nous sommes en présence d'une forme normale conjonctive. Toute formule admet une forme normale conjonctive équivalante.

Nous pouvons transformer nos formules en forme normale conjonctive de la manière suivante :

  • Transformation des ⇒ par des équivalances p ⇒ q ⇔ ¬p ∨ q
  • Ajout de négations pour les atomes avec ¬¬X ⇔ X et les lois de de Morgan (inversion des conjonctions et disjonctions).
  • Application de la distributivité de ∧ et ∨ pour obtenir une conjonction (utilisation des ∧) de clauses.
  • Renommage des variables si nécessaire.

Contents Haut

Formes prénexes

Une formule est de forme prénexe (ou forme normale prénexe) si tous les quantificateurs sont en tête. La suite des quantificateur est le préfixe, et la formule sans quantificateurs est la matrice.

Contents Haut

Formes de Skolem

Une formule est de forme de Skolem (ou forme normale de Skolem) si elle est en forme prénexe et ne contient pas de quantificateur existentiel.

Contents Haut

Formes clausales

Un littéral est une formule atomique ou la négation d'une formule atomique. Une clause est une disjonction1 de littéraux.
Les variables d'une clause sont implicitement quantifiées universellement (∀) en tête de clause.

Une formule est de forme clausale (ou forme normale clausale) si elle est en forme de Skolem, fermée, et si sa matrice est en forme normale conjonctive propositionnelle.

Contents Haut

Terminologie d'Herbrand

Terme clos

Un terme clos est un terme ne contenant pas de variable. L'ensemble des termes clos forme l'univers d'Herbrand. L'univers de Herbrand d'un ensemble de clauses est l'ensemble des termes de base que nous pouvons construire à partir de l'ensemble des termes clos2 que nous retrouvons dans cet ensemble des clauses.

Atome clos

Un atome clos est un atome ne contenant pas de variable. L'ensemble des atomes clos forme la base d'Herbrand.

Interprétation d'Herbrand

Une interprétation de Herbrand est une interprétation dont :

  • son domaine est l'univers de Herbrand
  • les constantes sont assignées à elles-mêmes
  • les variables de l'ensemble de clauses sont remplacées par des éléments de l'univers de Herbrand

Les interprétations d'Herbrand ne diffèrent que par les assignations des prédicats.

Modèle d'Herbrand

Un modèle de Herbrand d'un ensemble de clauses est une interprétation de Herbrand de cet ensemble de clauses qui est un modèle de cet ensemble de clauses.

Contents Haut

Algorithme d'unification de Herbrand

Soit S un système d'équations.
Tant que possible répéter

  • Sélectionner une équation Eq
  • Modifier S selon la forme de Eq comme suit :
    • Eq : f(t1,...,tn) = f(u1,...,un)
      • Remplacer Eq par les équations t1 = u1,...,tn = un
    • Eq : f(t1,...,tm) = f(u1,...,un) avec m ≠ n
      • Arrêter avec échec (car le nombre d'arguments des fonctions n'est pas identique).
    • Eq : f(t1,...,tm) = g(u1,...,un) avec f ≠ g
      • Arrêter avec échec (foncteurs différents).
    • Eq : X = X avec X variable
      • Eliminer Eq.
    • Eq : t = X avec X variable, t non variable
      • Remplacer Eq par X = t.
    • Eq : X = t avec
      • X variable distincte de t
      • X apparaît dans S \ {Eq}
      • Si X apparaît dans t, arrêter avec échec.
      • sinon, remplacer X par t dans S \ {Eq}

English translation

You have asked to visit this site in English. For now, only the interface is translated, but not all the content yet.

If you want to help me in translations, your contribution is welcome. All you need to do is register on the site, and send me a message asking me to add you to the group of translators, which will give you the opportunity to translate the pages you want. A link at the bottom of each translated page indicates that you are the translator, and has a link to your profile.

Thank you in advance.

Document created the 15/06/2010, last modified the 28/10/2018
Source of the printed document:https://www.gaudry.be/en/programmation-declarative-unification-herbrand.html

The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.

Notes
  1. ↑ Disjonction : Une disjonction est une ou plusieures relations de type booléen OU.

  2. ↑ Univers de Herbrand : Quand nous évoquons l'ensemble des termes clos, c'est celui des symboles de fonctions et de constantes du langage du premier ordre considéré.

Contents Haut

References

  1. book Language of the document:fr IHDCB337 - Technique d'intelligence artificielle : JM Jacquet, Programmation déclarative (2009)
  2. book Language of the document:fr IHDCB337 - Technique d'intelligence artificielle : H Toussaint, Tp (2009)

These references and links indicate documents consulted during the writing of this page, or which may provide additional information, but the authors of these sources can not be held responsible for the content of this page.
The author This site is solely responsible for the way in which the various concepts, and the freedoms that are taken with the reference works, are presented here. Remember that you must cross multiple source information to reduce the risk of errors.

Contents Haut