Calcul des prédicats : les unifications

Unification

Si nous avons un ensemble d'équations $P$ de la forme où tout $t$ et tout $s$ sont des termes, nous pouvons parler de problème d'unification; il est peut-être possible de trouver une substitution qui joue le rôle d'unificateur.

Nous pouvons unifier les deux termes $\mathrm{<msub>t<mn>1</mn></msub>}$, $\mathrm{<msub>t<mn>2</mn></msub>}$ ssi $\exists \text{une substitution}\sigma : \mathrm{<msub>t<mn>1</mn></msub>}\sigma =\mathrm{<msub>t<mn>2</mn></msub>}\sigma$. Le signe « = » correspond ici à une égalité syntaxique.
La substitution $\sigma$ porte le nom d'unificateur de $\mathrm{<msub>t<mn>1</mn></msub>}$ et $\mathrm{<msub>t<mn>2</mn></msub>}$.

Nous parlons de l'ensemble des unificateurs (nous noterons U(P) l'ensemble des unificateurs de P), car pouvons avoir plus d'un unificateur pour une même substitution. Nous dirons donc que P est unifiable si U(P) ≠ ∅.

Inhaltsverzeichnis Haut

Particularité

Nous dirons d'une substitution $\alpha$ qu'elle est plus particulière qu'une autre substitution $\beta$ s'il existe une substitution $\sigma$ telle que $\alpha =\beta \sigma$. Nous noterons la particularité comme ceci : $\alpha ⊴\beta$.

Inhaltsverzeichnis Haut

MGU

Un mgu de deux termes est un unificateur $\alpha$ tel que pour tout autre unificateur $\beta$ de ces deux termes, $\beta$ est plus particulier que $\alpha$

Nous pouvons déterminer le mgu de deux termes gràce à l'algorithme d'unification de Herbrand.

Inhaltsverzeichnis Haut

You are on the German version of the site, but your system indicates that you prefer to use the English language.
The entire site is not translated yet, but the menus and buttons on the interface are largely translated.

Would you like to reach the page in English?
Click here to continue in English: Consult the English version of this page

U bevindt zich op de Duits versie van de site, maar uw systeem geeft aan dat u liever de Nederlandse taal gebruikt.
De hele site is nog niet vertaald, maar de menu's en knoppen op de interface zijn grotendeels vertaald.

Wilt u de pagina in het Nederlands bereiken?
Klik hier om door te gaan in het Nederlands: Raadpleeg de Nederlandse versie van deze pagina

Vous vous trouvez sur la version allemande du site, mais votre système indique que vous préférez utiliser la langue française.

Souhaitez-vous atteindre la page en français?
Cliquez ici pour continuer en français: Consulter la page en français